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

Closed
ugorji opened this issue Jun 4, 2019 · 17 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone

Comments

@ugorji
Copy link
Contributor

ugorji 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
Copy link
Contributor

Sure.
@zdjones @rasky @brtzsnr

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

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

@bcmills bcmills added the NeedsFix The path to resolution is known, but the work has not been done. label Jun 4, 2019
@dpinela
Copy link
Contributor

dpinela 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
Copy link
Contributor

martisch commented Jun 6, 2019

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

@go101
Copy link

go101 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
Copy link
Contributor

zdjones 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

@mvdan mvdan added the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Aug 30, 2019
@rasky
Copy link
Member

rasky commented Aug 31, 2019

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

@go101
Copy link

go101 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
Copy link

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.)

@zdjones
Copy link
Contributor

zdjones 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 Issue is not actionable because of missing required information, which needs to be provided. label Oct 1, 2019
@mvdan mvdan reopened this Oct 1, 2019
@randall77
Copy link
Contributor

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
Copy link

go101 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
@go101
Copy link

go101 commented Aug 5, 2021

It looks the slice expression in the following code has already BCEed at least since Go 1.12.

		_ = b[blen-1] // bounds check: Found IsInBounds (expected)
		use(b[:blen]) // BCEed

So maybe it also should for OP's code:

		b[blen-1] = '"' // bounds check: Found IsInBounds (expected)
		use(b[:blen]) // bounds check: Found IsSliceInBounds (unexpected as above is sufficient)

Rethought it for a while, even if blen is MinInt, the bound check for the slice expression could be also eliminated, for blen-1 is MaxInt, so the expression b[blen-1] will always cause a panic. If it doesn't panic, then the slice expression is absolutely safe.

@go101
Copy link

go101 commented Aug 5, 2021

And it looks this problem only happens for package-level slices or indexes:

package main

var blen int = 1
var b []byte = make([]byte, 1)
var b2 []byte

func fff(b []byte, blen int) {
	type _ int
	b[blen-1] = '"' //  Found IsInBounds
	b2 = b[:blen]
}

func ggg() {
	type _ int
	b[blen-1] = '"' // Found IsInBounds
	b2 = b[:blen] //  Found IsSliceInBounds
}

func ggg2(b []byte) {
	type _ int
	b[blen-1] = '"' // Found IsInBounds
	b2 = b[:blen] //  Found IsSliceInBounds
}

func ggg3(blen int) {
	type _ int
	b[blen-1] = '"' // Found IsInBounds
	b2 = b[:blen] //  Found IsSliceInBounds
}

func main() {
	b[blen-1] = '"' // Found IsInBounds
	b2 = b[:blen] // Found IsSliceInBounds
	
	ggg()
	ggg2(b)
	ggg3(blen)
	
	fff(b, blen)
}

@randall77
Copy link
Contributor

@go101, the compiler assumes global variables can be reassigned at any time. The two reads of b might be completely different slices.

@go101
Copy link

go101 commented Aug 5, 2021

@randall77, then it looks this issue could be closed now, as this problem doesn't happen to local slices.

BTW, more evidences to prove global variables are not BCE friendly.

package main

var blen int = 1
var b []byte = make([]byte, 1)
var b2 []byte
var x byte

func ggg1() {
	_ = b[blen-1] // Found IsInBounds
	b2 = b[:blen]
}

func ggg2() {
	_ = b[blen-1] // Found IsInBounds
	b2 = b[:blen]
	b[blen-1] = '"' // Found IsInBounds
}

func ggg3() {
	_ = b[blen-1] // Found IsInBounds
	b[blen-1] = '"'
	b2 = b[:blen] //  Found IsSliceInBounds
}

func ggg1b() {
	x = b[blen-1] // Found IsInBounds
	b2 = b[:blen] // Found IsSliceInBounds
}

func ggg2b() {
	x = b[blen-1]   // Found IsInBounds
	b2 = b[:blen]   // Found IsSliceInBounds
	b[blen-1] = '"' // Found IsInBounds
}

func ggg3b() {
	x = b[blen-1]   // Found IsInBounds
	b[blen-1] = '"' // Found IsInBounds
	b2 = b[:blen]   //  Found IsSliceInBounds
}

func main() {
	ggg1()
	ggg2()
	ggg3()
}

@go101
Copy link

go101 commented Aug 17, 2021

It looks there is still a little unreasonable in BCE decision making:

package main

var s = make([]int, 100)

func f() (r int) {
	for i := range s {
		r += s[i] // bound check eliminated
	}
	return r
}

func g() {
	for i := range s {
		s[i] = i // need bound check
	}
}

func main() {
}

I filed another issue: #47736

@golang golang locked and limited conversation to collaborators Aug 17, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Development

No branches or pull requests