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

[Jorropo]

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.

[thanm]

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

[Jorropo]

Would you be interested in sending a CL?

If I find time I'll.

[gopherbot]

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