cmd/compile: loop induction with `*` and `<<` induction operators

[Jorropo]

go version go1.27-devel_a6500456f3 Wed Mar 25 22:41:27 2026 -0700 linux/amd64

See the following minimal repro:

package p

func f(s []byte) {
    for i := uint(1); i < uint(len(s)); i *= 2 {
        _ = s[i]
    }
}

This generate a bounds check even tho we don't need to.

[Jorropo]

Plenty of other operators have monotonic regions when applied successively with the same constant but I don't know if they are commonly used as the next operator in loops that prove would benefit from learning.

[gabyhelp]

Related Issues

• cmd/compile: prove only notices one of a pair of induction variables (missed optimization) #76269 (closed)
• cmd/compile: missed trivial bound check elimination #66826 (closed)
• cmd/compile: teach prove about incrementing, len, and overflow #36346 (closed)
• cmd/compile: No BCE for len(x)&y in slice expression #52563 (closed)
• cmd/compile: lack of BCE in for loops without inline increment #75184 (closed)
• cmd/compile: prove bounds for & of positive values #38717 (closed)

Related Code Changes

• cmd/compile/internal/ssa: BCE for induction variables
• cmd/compile: in prove, detect loops with negative increments
• cmd/compile: enhance induction variable detection for unrolled loops
• cmd/compile: implement loop BCE in prove

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

[adonovan]

This optimization isn't sound for signed numbers and very large arrays, since successive doubling will cause it to become negative. If the length is more than ~2 billion (for int32), we would attempt to access a negative index.

I guess it is fine for int64 indices, or for arrays whose element type is larger than 1 byte.

[Jorropo]

@adonovan bad example fixed thanks.

[dmitshur]

CC @golang/compiler.