cmd/compile: missing bounds check elimination for complex conditionals

[jub0bs]

Go version

go version go1.24.1 darwin/amd64

Output of go env in your module/workspace:

AR='ar'
CC='cc'
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_ENABLED='1'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
CXX='c++'
GCCGO='gccgo'
GO111MODULE=''
GOAMD64='v1'
GOARCH='amd64'
GOAUTH='netrc'
GOBIN='/Users/jcretel/go/bin'
GOCACHE='/Users/jcretel/Library/Caches/go-build'
GOCACHEPROG=''
GODEBUG=''
GOENV='/Users/jcretel/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFIPS140='off'
GOFLAGS=''
GOGCCFLAGS='-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/0k/mmhg_4vd4rxdzzxp8hr1564r0000gn/T/go-build2912752211=/tmp/go-build -gno-record-gcc-switches -fno-common'
GOHOSTARCH='amd64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMOD='/Users/jcretel/Desktop/oauth2/go.mod'
GOMODCACHE='/Users/jcretel/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='darwin'
GOPATH='/Users/jcretel/go'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/usr/local/Cellar/go/1.24.1/libexec'
GOSUMDB='sum.golang.org'
GOTELEMETRY='on'
GOTELEMETRYDIR='/Users/jcretel/Library/Application Support/go/telemetry'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/usr/local/Cellar/go/1.24.1/libexec/pkg/tool/darwin_amd64'
GOVCS=''
GOVERSION='go1.24.1'
GOWORK=''
PKG_CONFIG='pkg-config'

What did you do?

Run go build -gcflags '-d=ssa/check_bce/debug=1'on the following two programmes:

// int.go
package bce_int

import "cmp"

var _ = insertionSortOrdered[int] // <---------

func insertionSortOrdered[E cmp.Ordered](data []E, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data[j] < data[j-1]; j-- {
			// two bounds checks here when E is string, none when E is int
			data[j], data[j-1] = data[j-1], data[j]
		}
	}
}

// string.go
package bce_string

import "cmp"

var _ = insertionSortOrdered[string] // <---------

func insertionSortOrdered[E cmp.Ordered](data []E, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data[j] < data[j-1]; j-- {
			// two bounds checks here when E is string, none when E is int
			data[j], data[j-1] = data[j-1], data[j]
		}
	}
}

What did you see happen?

The first programme has no bounds checks on the swap line:

$ go build -gcflags '-d=ssa/check_bce/debug=1' ./bce_int
# whatever/bce_int
bce_int/int.go:10:28: Found IsInBounds
bce_int/int.go:10:38: Found IsInBounds
bce_int/int.go:8:6: Found IsInBounds

Surprisingly, the second programme has two bounds checks on the swap line:

$ go build -gcflags '-d=ssa/check_bce/debug=1' ./bce_string 
# whatever/bce_string
bce_string/string.go:10:28: Found IsInBounds
bce_string/string.go:10:38: Found IsInBounds
bce_string/string.go:12:29: Found IsInBounds # <----
bce_string/string.go:12:40: Found IsInBounds # <----
bce_string/string.go:8:6: Found IsInBounds

What did you expect to see?

Given the absence of any type switch on insertionSortOrdered's type parameter, I expected the number of bounds checks to be insensitive to the choice of type argument.

[gabyhelp]

Related Issues

• cmd/compile: BCE optimizes less for string than slice #27585
• cmd/compile: missing BCE case #41335
• cmd/compile: generic functions are significantly slower than identical non-generic functions in some cases #50182 (closed)
• cmd/compile: missed trivial bound check elimination #66826 (closed)
• cmd/compile: missed BCE in multi expression switch cases #67329 (closed)
• cmd/compile: unnecessary bounds check in a loop passed as a closure #39756
• cmd/compile: Improve BCE when using positive int as slice index #28885 (closed)
• cmd/compile: bounds check not removed after "if index < length" #15074 (closed)
• cmd/compile: gcflags="-d=ssa/check_bce" doesn't work or doesn't work well for generic functions #58139 (closed)
• cmd/compile: BCE does not take transitivity into account #19714 (closed)

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

[randall77]

I think that's just a line numbering problem. There are bounds checks in all the examples.
(Look for panicIndex calls.)

[jub0bs]

@randall77 There are bounds checks in all examples, but (unless I'm missing something) double the amount in the string version. Search for "panicindex" on godbolt:

• 4 hits for the int version;
• 8 hits for the string version.

[randall77]

Ah, ok, I see it now. Somehow the bounds checks in the loop condition are not making the bounds checks in the swap line redundant.

I suspect this has something to do with the cmpstring call that's needed for string <.

Note this has nothing to do with generics, replacing E with string shows the same behavior.

[randall77]

Here's a simpler reproducer:

package p

func f(x []string, i int, b bool) {
	if b && x[i] < "foo" {
		x[i] = "bar"
	}
}

This has 2 bounds checks. Remove b && and it has only one.

[jub0bs]

@randall77 Thanks! Glad I'm not hallucinating. 😌

[JunyangShao]

By looking at the discussion, this looks like WAI, closing

[jub0bs]

@JunyangShao What? No...

Edit: Even though the problem appears unrelated to generics, this issue could be re-purposed to track down those spurious bounds checks (confirmed by @randall77 in #72132 (comment)). I'm not aware of any open issue about that.

[as]

Please reopen the issue at this time.