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
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone

Comments

@mvdan
Copy link
Member

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

zdjones commented Jan 21, 2019

Same as #28885?

@mvdan
Copy link
Member Author

mvdan commented Jan 21, 2019

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

@mvdan mvdan closed this as completed Jan 21, 2019
@mvdan
Copy link
Member Author

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

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 The path to resolution is known, but the work has not been done. label Feb 7, 2019
@zdjones
Copy link
Contributor

zdjones 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
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
@golang golang locked and limited conversation to collaborators Mar 28, 2020
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

4 participants