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.

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

cmd/compile: flashing optimization indexing into arrays bounded by a modulo bellow or equal to the length only works if the modulo is a sub expression of the indexing #63110

Open
Jorropo opened this issue Sep 20, 2023 · 3 comments
Open

cmd/compile: flashing optimization indexing into arrays bounded by a modulo bellow or equal to the length only works if the modulo is a sub expression of the indexing #63110

Jorropo opened this issue Sep 20, 2023 · 3 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Backlog

Comments

@Jorropo
Copy link
Member

Jorropo commented Sep 20, 2023 •
edited

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

$ go version
go version go1.21.1 linux/amd64

Does this issue reproduce with the latest release?

Yes

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

go env Output
$ go envGO111MODULE=''
GOARCH='amd64'
GOBIN=''
GOCACHE='/home/hugo/.cache/go-build'
GOENV='/home/hugo/.config/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='linux'
GOINSECURE=''
GOMODCACHE='/home/hugo/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='linux'
GOPATH='/home/hugo/go'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/home/hugo/Documents/Scripts/go'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/home/hugo/Documents/Scripts/go/pkg/tool/linux_amd64'
GOVCS=''
GOVERSION='go1.21.1'
GCCGO='/usr/bin/gccgo'
GOAMD64='v3'
AR='ar'
CC='gcc'
CXX='g++'
CGO_ENABLED='1'
GOMOD='/dev/null'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -m64 -pthread -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=/tmp/go-build2448092634=/tmp/go-build -gno-record-gcc-switches'

What did you do?

Compile:

func Minimized(x uint, arr *[100]uint) uint {
    i := x % 100
    return arr[i]
}

What did you expect to see?

No bound check

What did you see instead?

A bound check is present.

However this:

func Minimized(x uint, arr *[100]uint) uint {
    return arr[x % 100]
}

correctly omits the bound check.

Why is this broken ?

func Minimized(x uint, arr *[100]uint) uint {
    i := x % 100
    return arr[i]
}

Fails to be picked up by prove because opt rewrites it to something along the lines of:

func Minimized(x uint, arr *[100]uint) uint {
    i := 100 - (-6640827866535438581 * (x >> 1) * 100)
    return arr[i]
}

which it has no idea what to do with.
arr[x % 100] is specially handled with internal/ir.

I think a simple enough fix is to delay strength reduction to late opt (except for powers of two since prove knows how to handle theses), this will make it miss the main CSE passes but I don't think it's that bad, there is still lowered cse, need to experiment and see what this yields.
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Sep 20, 2023
@Jorropo Jorropo changed the title cmd/compile: indexing into arrays bounded by a modulo bellow or equal to the length only works if the modulo is a sub expression of the indexing cmd/compile: flashing optimization indexing into arrays bounded by a modulo bellow or equal to the length only works if the modulo is a sub expression of the indexing Sep 20, 2023
@mknyszek mknyszek added this to the Backlog milestone Sep 20, 2023
@thanm thanm added the NeedsFix The path to resolution is known, but the work has not been done. label Sep 25, 2023
@thanm
Copy link
Contributor

thanm commented Sep 25, 2023

Thanks for the report. Would you be interested in sending a CL?

@Jorropo
Copy link
Member Author

Jorropo commented Sep 25, 2023

Would you be interested in sending a CL?

If I find time I'll.

@gopherbot
Copy link

Change https://go.dev/cl/532815 mentions this issue: cmd/compile: delay unsigned strength reduction to late opt

@Jorropo Jorropo mentioned this issue Dec 31, 2023
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
Go Compiler / Runtime
Status: Todo
Milestone
Backlog
Development

No branches or pull requests
5 participants
@mknyszek @dmitshur @gopherbot @thanm @Jorropo