cmd/compile: exponential traversal of shared OR expressions #82671

Go version and environment

go1.28-devel_99291162c3 (2026-10-26), linux/amd64. Intel i9-13900K; GOMAXPROCS=1, GOGC=100, GOMEMLIMIT=off. Measurements recorded on 27 October 2026.

Also reproduced at 63313a0 on linux/arm64 (CIX P1 CP8180) on 28 October 2026.

What did you do?

Generate diamond-22.go with:

with open("diamond-22.go", "w") as f:
    f.write("package p\nfunc F(x []uint64) uint64 {\nv0 := x[0] | x[1]\n")
    for i in range(1, 23):
        f.write(f"a{i} := v{i-1} | x[{2*i}]\n")
        f.write(f"b{i} := v{i-1} | x[{2*i+1}]\n")
        f.write(f"v{i} := a{i} | b{i}\n")
    f.write("return v22\n}\n")

Then run go tool compile -d=ssa/memcombine/time=1 diamond-22.go.

What did you see happen?

memcombineLoads traverses the shared expression graph as a tree. A separate instrumented compiler counted 16,777,213 visits for 67 unique OR values. The uninstrumented full compile took a median 1.867 seconds over six alternating comparison pairs. A separate allocation profile attributed approximately 789 MiB of cumulative allocation to memcombineLoads.

What did you expect to see?

Shared expressions should not cause exponential traversal.

CartoGopher tooling for source navigation; reproduction, implementation and testing with Codex.