Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: bce: if slice[n] is in bounds, then slice[:n+1] should have bounds check eliminated #32431

Open
ugorji opened this issue Jun 4, 2019 · 12 comments

Comments

@ugorji
Copy link
Contributor

commented Jun 4, 2019

I expect that if we can access the nth element of a slice, then we can slice up to n+1.

See below.

		var blen int
		var b []byte
		// ... do some computation
		b[blen-1] = '"' // bounds check: Found IsInBounds (expected)
		use(b[:blen]) // bounds check: Found IsSliceInBounds (unexpected as above is sufficient)

Consequently, I do not expect a bounds check for b[:blen].

However, I get a bounds check for both b[blen-1] and b[:blen].

What version of Go are you using (go version)?

$ go version
go version devel +1531192272 Mon May 27 17:58:39 2019 +0000 darwin/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE="on"
GOARCH="amd64"
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOOS="darwin"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/bt/526m392x16x8y149jwx28mkm0000gp/T/go-build760118559=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

What did you expect to see?

What did you see instead?

@randall77

This comment has been minimized.

Copy link
Contributor

commented Jun 4, 2019

@randall77 randall77 added this to the Go1.14 milestone Jun 4, 2019
@randall77

This comment has been minimized.

Copy link
Contributor

commented Jun 4, 2019

Need to watch out for blen==MinInt. Then the index succeeds but the slice fails.

@bcmills bcmills added the NeedsFix label Jun 4, 2019
@dpinela

This comment has been minimized.

Copy link
Contributor

commented Jun 5, 2019

@randall77 While not immediately useful, I think it's worth noting that this would no longer be a concern if we adopted #19623 or #31500.

@martisch

This comment has been minimized.

Copy link
Member

commented Jun 6, 2019

I think the titles suggestion is not safe for when n==MaxInt as n+1 would overflow.

@go101

This comment has been minimized.

Copy link

commented Jun 6, 2019

It looks Go 1.12 does BCE for this case.

Some finding:

package main

type T = uint64

func f(s []int, n T) {
	_ = s[n]
	_ = s[:n+1] // BCEed when T is int/uint/int64/uint64 for Go SDK 1.12, but not for tip.
	// I think T=unsignedIntergerType should be ok here.
}

func g(s []int, n T) {
	_ = s[n-1]
	_ = s[:n] // BCEed when T is int/uint/int64/uint64 for Go SDK 1.12, but not for tip.
	// I think T=unsignedIntergerType should be ok here.
}

func main() {}

[edit]: If Go specification can specify (, or gc can limit) that the lengths of arrays/slices/strings may not exceed MaxInt-1 (which is practical), then the second lines of the above two functions can be safely BCEed for int and int64.

@zdjones

This comment has been minimized.

Copy link
Contributor

commented Aug 30, 2019

@ugorji It seems the bounds check in your example is removed, at least as of 1.12.6. Do you have an example where the bounds check is not removed?

Otherwise this can be closed, fixed somewhere <= 1.12.6

@rasky

This comment has been minimized.

Copy link
Member

commented Aug 31, 2019

@zdjones did you check the behaviour is correct when n==MaxIntT?

@go101

This comment has been minimized.

Copy link

commented Sep 1, 2019

It is impossible for a program to successfully allocate a slice with lengh n == MaxIntT for T is int/uint/int64/uint64, even if the element type is byte. For other signed interger types, if n==MaxIntT, then n+1 is negative, so the bound check can't be removed for sure. For unsigned integer types, n+1 is zero, so the bound check can be removed for sure.

In short, bound check can be removed for int, int64 and any unsigned integer types.

@gopherbot

This comment has been minimized.

Copy link

commented Sep 30, 2019

Timed out in state WaitingForInfo. Closing.

(I am just a bot, though. Please speak up if this is a mistake or you have the requested information.)

@gopherbot gopherbot closed this Sep 30, 2019
@zdjones

This comment has been minimized.

Copy link
Contributor

commented Oct 1, 2019

This still needs more thought, don't close it yet.

I've started checking the current behaviour near MaxInt and ended up down quite the rabbit-hole (exploring how big of a slice the compiler and runtime will allow, compared with what the spec allows for)

@mvdan mvdan removed the WaitingForInfo label Oct 1, 2019
@mvdan mvdan reopened this Oct 1, 2019
@randall77

This comment has been minimized.

Copy link
Contributor

commented Oct 1, 2019

Note that you can make slices of 0-sized items. That will let you test near maxint without using huge amounts of memory.

package main

type T struct{}

func main() {
	s := make([]T, 1<<63-1)
	println(len(s))
}

@go101

This comment has been minimized.

Copy link

commented Oct 4, 2019

With @randall77's comment, the conclusion in my last comment is wrong (for int and int64).

@rsc rsc modified the milestones: Go1.14, Backlog Oct 9, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
You can’t perform that action at this time.