Skip to content

cmd/compile: prove/BCE don't seem affected by hints that signed integers are not negative #28956

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.

Sign up for GitHub

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

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

cmd/compile: prove/BCE don't seem affected by hints that signed integers are not negative #28956

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
Go1.13

Comments

@mvdan
Copy link
Member

mvdan commented Nov 26, 2018 •
edited
Loading 

$ 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
@mvdan mvdan mentioned this issue Nov 26, 2018
Open
@mvdan mvdan added this to the Unplanned milestone Dec 2, 2018
@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 •
edited
Loading

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

@mvdan mvdan reopened this Jan 30, 2019
@zdjones zdjones mentioned this issue Jan 30, 2019
Closed
@gopherbot
Copy link
Contributor

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
@zdjones
cmd/compile: make prove use poset to check non-negatives
7667e4b 
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.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Milestone
Go1.13
Development

No branches or pull requests
4 participants
@bradfitz @mvdan @zdjones @gopherbot