-
Notifications
You must be signed in to change notification settings - Fork 17.9k
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: for range loop reading past slice end #40367
Comments
Thanks for the report. I can reproduce this on tip, too. |
(Tentatively labelling as a 1.15 release blocker, feel free to change) |
it seems that changing the line |
This issue appears to have been introduced a while ago. According to bisection, commit b812eec seems to be the most likely culprit |
// Check for i2 < max or max > i2.
var max *Value
if r == lt && pred.Control.Args[0] == i2 {
max = pred.Control.Args[1]
} else if r == gt && pred.Control.Args[1] == i2 {
max = pred.Control.Args[0]
} else {
continue
}
// Check condition 4 now that we have a
// candidate max. For this we can query the
// fact table. We "prove" min < max by showing
// that min >= max is unsat. (This may simply
// compare two constants; that's fine.)
ft.checkpoint()
ft.update(b, min, max, tr.d, gt|eq)
proved := ft.unsat
ft.restore()
if proved {
// We know that min <= i1 < max.
if b.Func.pass.debug > 0 {
printIndVar(b, i1, min, max, 1, 0)
}
ft.update(b, min, i1, tr.d, lt|eq)
ft.update(b, i1, max, tr.d, lt)
} Here the condition is
Here is another way to reproduce (similar to the test in that commit) package main
func main() {
i := 0
top:
if i < 2 {
i++
if i < 1 {
return
}
println(i)
goto top
}
} |
Wow, thanks for reporting. Yeah, as you mentioned, this is related to the prove pass. Running with cc @dr2chase |
Moving the milestone to 1.16, as this issue, while significant, is old enough not to block the 1.15 release at this point in the cycle. Please let me know if I am wrong. |
I'm going to take a crack at patching this in the morning (if noone else has gotten to it by then). It is late here, but my completely unconfirmed guess is that this loop has been compiled to OFORUNTIL (placing the increment and condition after the body) and |
Change https://golang.org/cl/244579 mentions this issue: |
Interesting, reproducible for all primitive number types as well as for boolean slice. EDIT: I just checked a few more, here's what I got, might be useful. https://play.golang.org/p/EuZTWueokp8 package main
import "fmt"
func main() {
// following ones work fine
rates := []int{1}
// rates := make([]int32, 5, 5)
// rates := make([]int32, 5)
// following ones break
// rates := make([]int32, 1, 5)
// rates := make([]int32, 0, 5)
// rates := make([]int32, 4, 5)
rates = append(rates, 2, 3, 4)
for star, rate := range rates {
if star+1 < 1 {
panic("")
}
fmt.Println(star, rate)
}
} |
This has a small fix, and pretty terrible consequences. Shouldn't it be 1.15? And also needs 1.13 & 1.14 backport... |
This would be really nice to fix for 1.15. As it has been broken for several releases, our policy is to not block a release for it. |
Could you consider reverting the commit that causes it in 1.15? And backporting that since both 1.13 & 1.14 are affected? |
Sure, that's a possibility. It's a pretty old CL, though, it might not revert cleanly. |
In case it wasn't clear, I meant revert it before the 1.15 release. |
SummaryGeneric CSE is turning this code into a pattern that prove incorrectly identifies as OFORUNTIL. Prove adds the OFORUNTIL induction variable bounds as facts in the loop header, leading to the removal of the loop exit branch. BackgroundProve has two ways of identifying loop induction variables and their min/mix:
During prove proper (DFS of the SSA dominator tree), prove adds facts based on the bounds of loop induction variables in two ways - the difference is part of the present issue:
Why is prove removing the loop exitWhen prove analyses this SSA, How is generic CSE involvedGeneric CSE is identifying the
becomes
The result of the above is a loop header with a loop induction edit: typos |
Learning What (we think) we prove:
What we require:
But it's obvious that Another example may help. It's not starting from 0, without i+1 and as I understand actually a OFORUNTIL case.
edit: fix a lot of typos : ( |
A more OFORUNTIL one: package main
func main() {
i := 5
top:
i++
println(i)
if !(i < 6 || i > 6) {
goto top
}
} |
any idea why it's not a problem for string slices or other type slices? I've been able to reproduce this only for numbers & boolean slices |
Is it worth trying to figure out how often this happens in practice on a large codebase? Given that it's been around for a while it seems fairly rare. |
So, is there some reliable estimation on time to fix this bug? |
There's never a reliable estimation on bug fix time :) |
@WZZ1998 as of now I'm happy with the fix, but waiting to see whether it makes the cut for 1.15 or a dot release, and would love other eyes on my assessment of what the original code thought it was doing, and how the fix interacts with that. I'm also benchmarking the fix to see if this accidentally causes terrible regressions; there's a chance that we lose some (correct) optimization that we had come to expect, since the fixed code will match a more restricted set of patterns. |
@gopherbot, please open backport issues for 1.14 and 1.13. |
Backport issue(s) opened: #40500 (for 1.13), #40501 (for 1.14). Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://golang.org/wiki/MinorReleases. |
What version of Go are you using (
go version
)?1.13.5,1.14.6
Does this issue reproduce with the latest release?
yes!
What operating system and processor architecture are you using (
go env
)?linux,amd64
What did you do?
try this in playground
What did you expect to see?
0,1
1,2
2,3
3,4
4,5
5,6
What did you see instead?
timeout running program
0 1
1 2
2 3
3 4
4 5
5 6
6 180344
7 192
8 4846592
9 0
10 180424
11 192
12 4846720
13 0
14 5822560
15 192
16 438224
17 192
18 4396406
19 0
20 385024
.....
The text was updated successfully, but these errors were encountered: