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: prove/BCE don't seem affected by hints that signed integers are not negative #28956

Closed
mvdan opened this issue Nov 26, 2018 · 5 comments

Comments

Projects
None yet
4 participants
@mvdan
Copy link
Member

commented Nov 26, 2018

$ cat f.go
package p

func f(i int, data []byte) {
        if i >= 0 {
                for i < len(data) {
                        _ = data[i] // bounds check!
                        i++
                }
        }
}
$ go build -gcflags=-d=ssa/check_bce/debug=1 f.go
# command-line-arguments
./f.go:6:33: Found IsInBounds
$ go version
go version devel +048c9164a0 Sat Nov 24 23:55:07 2018 +0000 linux/amd64

If we make the index an unsigned integer instead of using the if i >= 0 hint, the bounds check goes away.

I haven't found this in real code, but I tried this hint while trying to remove a bounds check from real code. I was surprised to see that BCE would still not do its thing with the hint. Seems to me like this should be a simple fix somewhere in the prove or BCE passes.

/cc @aclements @rasky

@zdjones

This comment has been minimized.

Copy link
Contributor

commented Jan 21, 2019

Same as #28885?

@mvdan

This comment has been minimized.

Copy link
Member Author

commented Jan 21, 2019

Indeed looks like it :) thanks for pointing that out.

@mvdan mvdan closed this Jan 21, 2019

@mvdan

This comment has been minimized.

Copy link
Member Author

commented Jan 30, 2019

@blobdon is looking into this issue, and he believes that this case is simpler than some of the cases listed in #28885; for now, I'm reopening this issue for him to experiment with the simple case.

Edit: it appears I can't assign issues to people ooutside the golang organisation.

@gopherbot

This comment has been minimized.

Copy link

commented Feb 6, 2019

Change https://golang.org/cl/161437 mentions this issue: cmd/compile: make prove use poset to check non-negatives

@bradfitz bradfitz modified the milestones: Unplanned, Go1.13 Feb 7, 2019

@bradfitz bradfitz added the NeedsFix label Feb 7, 2019

@zdjones

This comment has been minimized.

Copy link
Contributor

commented Feb 11, 2019

Change https://golang.org/cl/161437 fixes this issue.

zdjones added a commit to zdjones/go that referenced this issue Feb 17, 2019

cmd/compile: make prove use poset to check non-negatives
Prove currently fails to remove bounds checks of the form:

if i >= 0 {              // hint that i is non-negative
    for i < len(data) {  // i becomes Phi in the loop SSA
        _ = data[i]      // data[Phi]; bounds check!!
	i++
    }
}

addIndVarRestrictions fails to identify that the loop induction
variable, (Phi), is non-negative. As a result, the restrictions,
i <= Phi < len(data), are only added for the signed domain. When
testing the bounds check, addBranchRestrictions is similarly unable
to infer that Phi is non-negative. As a result, the restriction,
Phi >= len(data), is only added/tested for the unsigned domain.

This CL changes the isNonNegative method to utilise the factTable's
partially ordered set (poset). It also adds field factTable.zero to
allow isNonNegative to query the poset using the zero(0) constant
found or created early in prove.

Fixes golang#28956

Change-Id: I792f886c652eeaa339b0d57d5faefbf5922fe44f

@gopherbot gopherbot closed this in ddef157 Mar 29, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.