cmd/compile: quadratic branch lookup in prove for large switches #82407

Go version

go version go1.28-devel_d8b75948 Wed Oct 21 15:55:22 2026 -0700 linux/amd64

Output of go env in your module/workspace:

Relevant settings from go env:

GOOS=linux
GOARCH=amd64
GOAMD64=v1
GOEXPERIMENT=
GOFLAGS=
CGO_ENABLED=1

What did you do?

Compiled a generated switch whose cases make distinct calls to a
non-inlined function:

python3 - <<'PY' > switch.go
n = 4000
print('package p')
print('//go:noinline')
print('func F(x int) int { return x }')
print('func Lookup(x int) int { switch x {')
for i in range(n):
    print(f'case {i}: return F({i * 3 + 1})')
print('}; return -1 }')
PY
go tool compile -d=ssa/prove/time switch.go

Repeated with 1,000, 2,000, 4,000 and 8,000 cases.

What did you see happen?

Median prove-pass times over five runs on an Intel i9-13900K:

The jump-table case in
getBranch
scans the successors for each case visited by prove. An 8,000-case CPU
profile attributes 60 ms of 360 ms sampled compiler CPU time to this
scan through SparseTree.IsAncestorEq.

CL 841945 changes traversal order in the same pass, but leaves this scan
unchanged.

What did you expect to see?

Branch lookup should not scan the whole jump table for each direct
successor. This produces quadratic work as the number of cases grows.