cmd/compile: teach BCE about `min` builtin

[tdakkota]

Go version

go version go1.22.5 linux/amd64

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='amd64'
GOBIN=''
GOCACHE='/home/tdakkota/.cache/go-build'
GOENV='/home/tdakkota/.config/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='linux'
GOINSECURE=''
GOMODCACHE='/home/tdakkota/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='linux'
GOPATH='/home/tdakkota/go'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/home/tdakkota/go/pkg/mod/golang.org/toolchain@v0.0.1-go1.22.5.linux-amd64'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='go1.22.5+auto'
GOTOOLDIR='/home/tdakkota/go/pkg/mod/golang.org/toolchain@v0.0.1-go1.22.5.linux-amd64/pkg/tool/linux_amd64'
GOVCS=''
GOVERSION='go1.22.5'
GCCGO='gccgo'
GOAMD64='v1'
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-build2547774337=/tmp/go-build -gno-record-gcc-switches'

What did you do?

for i := range min(len(keys), len(values)) {
    println(keys[i]) // Found IsInBounds
    println(values[i]) // Found IsInBounds
}

https://go.dev/play/p/wE9DX4D3Iga https://go.godbolt.org/z/11PYfc6x3

What did you see happen?

Bound checks are not eliminated.

What did you expect to see?

Given that min(len(x), len(y)) is non-negative and less or equal than len(x) and len(y) , i is always in bounds of both slices, so bounds checks could be eliminated.

Iteration patterns like this are quite common, especially in columnar data formats.

[gabyhelp]

Related Issues and Documentation

• cmd/compile: Improve BCE when using positive int as slice index #28885 (closed)
• cmd/compile: No BCE for str[len(str):] #53409 (closed)
• cmd/compile: bounds check elimination thwarted by if-foruntil idiom #22236 (closed)
• cmd/compile: missed trivial bound check elimination #66826
• cmd/compile: BCE optimizes less for string than slice #27585
• cmd/compile: BCE does not take transitivity into account #19714 (closed)
• cmd/compile: bce: if slice[n] is in bounds, then slice[:n+1] should have bounds check eliminated #32431 (closed)
• cmd/compile: some subsequent bounds checks are not eliminated #50365
• cmd/compile: unnecessary bounds check for position len/2 #27249 (closed)
• cmd/compile: improve BCE to detect safe unbounded slicing #35483 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[tdakkota]

It seems like CL 622240 mostly solved this issue:

$ go version
go version devel go1.24-4b30a40d88 Tue Oct 29 16:47:05 2024 +0000 linux/amd64
$ go tool compile -d=ssa/check_bce/debug=1 test.go
test.go:5:21: Found IsInBounds

func iter(keys, values []string) {
    for i := 0; i < min(len(keys), len(values)); i++ {
        println(keys[i]) // Found IsInBounds
        println(values[i])
    }
}

func iter2(keys, values []string) {
    l := min(len(keys), len(values))
    for i := range l {
        println(keys[i])
        println(values[i])
    }
}

[zigo101]

No bound checks in the following code

func iter(keys, values []string) {
    l := min(len(keys), len(values))
    for i := 0; i < l; i++ {
        println(keys[i])
        println(values[i])
    }
}

func iter2(keys, values []string) {
    for i := range min(len(keys), len(values)) {
        println(keys[i])
        println(values[i])
    }
}