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: missing BCE in range expression #54753

Closed
tamird opened this issue Aug 29, 2022 · 4 comments
Closed

cmd/compile: missing BCE in range expression #54753

tamird opened this issue Aug 29, 2022 · 4 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. Performance
Milestone

Comments

@tamird
Copy link
Contributor

tamird commented Aug 29, 2022

What version of Go are you using (go version)?

$ go version
1.19

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
Linux amd64

What did you do?

package main

type foo struct {
    number int
}

var foos []foo

func main() {
    foos = make([]foo, 5)
    for i := range foos {
        _ = &foos[i] // No IsInBounds
    }
    for i := range foos {
        f := &foos[i] // IsInBounds
        f.number = i
    }
    for i := 0; i < len(foos); i++ {
        f := &foos[i] // No IsInBounds
        f.number = i
    }
    foos2 := make([]foo, 5)
    for i := range foos2 {
        f := &foos2[i] // No IsInBounds
        f.number = i
    }
}

compiler output visible on godbolt

What did you expect to see?

No bounds checks.

What did you see instead?

Bounds check when ranging over a variable declared and initialized separately.

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Aug 29, 2022
@heschi heschi added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Aug 29, 2022
@heschi heschi added this to the Backlog milestone Aug 29, 2022
@heschi
Copy link
Contributor

heschi commented Aug 29, 2022

cc @golang/runtime

@randall77
Copy link
Contributor

randall77 commented Aug 29, 2022

This is a consequence of the interaction between global variables and the details of the for loop.

For case 1, the two reads of the global variable (foos in the range statement and &foos[i] in the loop) can be CSE'd because there are no writes in between.

For the third loop, foos is reread every time in the conditional and in the body, so the reads in len(foos) and &foos[i] can be CSEd. (Note that foos needs to be reread every time though the loop, though. That's probably more expensive than the bounds check.)

For the fourth loop, there is no global variable so there's no possibility of foos2 being modified by the loop. In fact, foos2 gets completely optimized away because nothing uses its final value.

In the second loop, the read of foos in the range statement (which happens only once) and the read of foos in &foos[i] (which happens every iteration) are separated by memory writes. Thus they aren't CSE'd, so the loop condition and the bounds check are no longer obviously related. That means we keep the bounds check.

Moral of the story: don't use global variables. The compiler needs to assume that they might get modified. In theory, we can assume that global variables don't change if no synchronization operations occur between two loads. But in practice, the compiler "approximates" that by assuming any write operation could be a synchronization. So two reads from the same global are only assumed to be equal if no write separates them.

If you have to use global variables, do:

a := foos
for i := range a {
   a[i].number = i
}

@randall77 randall77 added Performance and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Aug 29, 2022
@tamird
Copy link
Contributor Author

tamird commented Aug 29, 2022

Makes sense, thanks for explaining that.

@randall77
Copy link
Contributor

randall77 commented Aug 29, 2022

I'm going to close this, as I don't think there's anything to do here. We could improve the compiler to change its CSE rule from "any write might be synchronization" to something more complicated, but that's a really big lift for an issue that's pretty easy to work around.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. Performance
Projects
None yet
Development

No branches or pull requests

4 participants