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: improve BCE to detect safe unbounded slicing #35483

Closed
nhooyr opened this issue Nov 9, 2019 · 4 comments
Closed

cmd/compile: improve BCE to detect safe unbounded slicing #35483

nhooyr opened this issue Nov 9, 2019 · 4 comments

Comments

@nhooyr
Copy link
Contributor

@nhooyr nhooyr commented Nov 9, 2019

See #31586 (comment)

Core problem can be reduced to:

package scratch

import "encoding/binary"

func A1(b []byte) {
	key64 := uint64(1024)
	for len(b) >= 32 {
		v := binary.LittleEndian.Uint64(b)
		binary.LittleEndian.PutUint64(b, v^key64)
		v = binary.LittleEndian.Uint64(b[8:])
		binary.LittleEndian.PutUint64(b[8:], v^key64)
		v = binary.LittleEndian.Uint64(b[16:])
		binary.LittleEndian.PutUint64(b[16:], v^key64)
		v = binary.LittleEndian.Uint64(b[24:])
		binary.LittleEndian.PutUint64(b[24:], v^key64)
		b = b[32:]
	}
}

func A2(b []byte) {
	key64 := uint64(1024)
	for len(b) >= 32 {
		v := binary.LittleEndian.Uint64(b)
		binary.LittleEndian.PutUint64(b, v^key64)
		v = binary.LittleEndian.Uint64(b[8:16])
		binary.LittleEndian.PutUint64(b[8:16], v^key64)
		v = binary.LittleEndian.Uint64(b[16:24])
		binary.LittleEndian.PutUint64(b[16:24], v^key64)
		v = binary.LittleEndian.Uint64(b[24:32])
		binary.LittleEndian.PutUint64(b[24:32], v^key64)
		b = b[32:]
	}
}

BCE:

$ go build -gcflags="-d=ssa/check_bce/debug=1" scratch.go
# command-line-arguments
./scratch.go:10:34: Found IsInBounds
./scratch.go:12:34: Found IsInBounds
./scratch.go:14:34: Found IsInBounds

Bound checks remain in A1 even though they are not needed but are eliminated in A2 due to the explicit and not unbounded slices.

@renthraysk stated:

It was the _ = b[7] line in PutUint64() that was cause the bounds checks. The compiler failed to prove it's not needed with PutUint64(b[8:], x) however it does eliminate the first check in PutUint64(b, x).

I'm on 1.13.4 on macOS.

@josharian

This comment has been minimized.

Copy link
Contributor

@josharian josharian commented Nov 9, 2019

@agnivade agnivade changed the title cmd/go: improve BCE to detect safe unbounded slicing cmd/compile: improve BCE to detect safe unbounded slicing Nov 10, 2019
@agnivade agnivade added this to the Unplanned milestone Nov 10, 2019
@ALTree ALTree added the Performance label Nov 10, 2019
@zdjones

This comment has been minimized.

Copy link
Contributor

@zdjones zdjones commented Nov 11, 2019

This is a duplicate of #24876. Also see #19126

The issue is that the prove pass does not currently do any arithimetic when assesing b[16:] and therefore has no information about the length of the resulting slice. see this comment: #19126 (comment).

I have a chain of CLs that fix this, but they are not complete this cycle.

@zdjones

This comment has been minimized.

Copy link
Contributor

@zdjones zdjones commented Nov 11, 2019

Here is the CL chain that fixes this issue: https://go-review.googlesource.com/c/go/+/190657

@agnivade

This comment has been minimized.

Copy link
Contributor

@agnivade agnivade commented Nov 11, 2019

Closing as a duplicate.

@agnivade agnivade closed this Nov 11, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants
You can’t perform that action at this time.