vault

Bounds Check Elimination

9 min read

Bounds Check Elimination

Go is a memory-safe language: every indexing or slicing operation (s[i], s[i:j]) is, by specification, checked at runtime so that an out-of-range access panics rather than corrupting memory. Bounds Check Elimination (BCE) is the set of compiler optimizations that prove a given access is always in range and therefore delete the runtime check — keeping the safety guarantee while removing its cost. In the Go gc compiler this happens in the SSA backend, primarily in the prove pass (cmd/compile/internal/ssa/prove.go), with help from rewrite rules in generic.rules and induction-variable analysis in loopbce.go. BCE is not a separate user-facing feature — it is invisible when it works, and the only way to observe it is -gcflags=-d=ssa/check_bce/debug=1, which prints every check the compiler failed to eliminate.

Mental Model

Every s[i] in Go source becomes, in SSA, an explicit comparison plus a conditional panic. Conceptually:

t := IsInBounds i len(s)   // is 0 <= i < len(s) ?
if !t { panicIndex(i, len(s)) }
... = s[i]

IsInBounds is a single SSA op that means “is the unsigned value i strictly less than len?” — and because it is unsigned, it checks i >= 0 and i < len in one comparison (a negative i, reinterpreted as unsigned, is a huge number that fails < len). The prove pass’s job is to decide, for each such op, whether it can be replaced by the constant true. If it can, the conditional panic becomes dead code and is deleted by a later dead-code pass.

flowchart TD
    A["s[i] in source"] --> B["SSA: t = IsInBounds i len<br/>If t goto ok else panic"]
    B --> C[prove pass walks dominator tree]
    C --> D{factsTable: can it prove<br/>0 &le; i &lt; len always?}
    D -->|Yes| E["Rewrite IsInBounds to ConstBool true"]
    D -->|No| F[Leave the check]
    E --> G[Branch becomes unconditional;<br/>panic block is dead]
    G --> H[deadcode pass removes<br/>the panic + comparison]
    F --> I["check survives —<br/>-d=ssa/check_bce reports it"]

Figure: the lifecycle of one bounds check. Insight: BCE never makes code unsafe — it only removes a check after proving it can never fire. A check that “survives” is not a bug; it is the compiler being honestly unable to prove safety.

Mechanical Walk-through

The prove pass and the facts table

The prove pass (prove.go) walks the function’s dominator tree. The key idea: when control flow takes the true branch of if i < len(s), then within the entire region dominated by that branch the fact “i < len(s)” is known. The pass accumulates such facts as it descends and discards them as it backtracks.

The facts are stored in a factsTable with three components:

  • Posets (partially ordered sets): two of them, orderS for the signed domain and orderU for the unsigned domain, recording relative orderings like “a < b” between SSA values.
  • An orderings map: explicit pairwise relations indexed by value ID, without computing full transitive closure (kept cheap on purpose).
  • A limits array: for each value, a limit struct holding four bounds — min, max (signed) and umin, umax (unsigned). A value whose signed min is provably ≥ 0 can have that fact propagated into the unsigned domain.

Relations are encoded as bit combinations of lt, eq, gt, so lt|eq is ”≤” and gt|lt is ”≠”. Domains are signed, unsigned, boolean, and pointer (the last for nil-vs-non-nil tracking, which the same pass uses for nil-check elimination).

When the pass reaches an OpIsInBounds (for s[i]) or OpIsSliceInBounds (for s[i:j]) used as a branch condition:

  • On the true branch it learns “i is non-negative AND i < len” (or ≤ for the slice variant) and tightens both the signed and unsigned limits for i.
  • On the false branch it learns the negation.

If, when the pass reaches an IsInBounds, the facts table already implies the result — i’s umax < len’s umin, for instance — the op is rewritten to ConstBool true. The branch then has a constant condition, the panic side becomes unreachable, and the deadcode pass deletes it. The source itself states the design is “sound, but incomplete”: outside special cases the table does little deduction or arithmetic, an intentional trade of completeness for compile speed.

Rewrite rules — the cheap cases

Many bounds checks are eliminated even before prove, by pattern-matching rewrite rules in _gen/generic.rules (generic.rules). These handle range facts that are obvious from a value’s construction:

  • A value zero-extended from 8 bits cannot exceed 255: (IsInBounds (ZeroExt8to32 _) (Const32 [c])) && (1<<8) <= c => (ConstBool [true]).
  • A value masked with a constant is bounded by that mask: (IsInBounds (And8 (Const8 [c]) _) (Const8 [d])) && 0 <= c && c < d => (ConstBool [true]).
  • A modulo result is bounded by its divisor: (IsInBounds (Mod64u _ y) y) => (ConstBool [true]) — x % y is always < y.
  • Trivial slice cases: (IsSliceInBounds x x) => (ConstBool [true]), (IsSliceInBounds (Const64 [0]) _) => (ConstBool [true]), (IsSliceInBounds (SliceLen x) (SliceCap x)) => (ConstBool [true]).

This is why s[i&0xff] on a slice of length ≥ 256, or s[i%len(s)], are check-free without any flow analysis at all.

Loops — induction variables

The hardest and most valuable case is for i := 0; i < len(s); i++ { s[i] }. Here i is not a constant, but it is bounded by the loop. The loopbce.go pass (loopbce.go) detects induction variables: it finds the SSA pattern where a Phi node merges an initial value with an incremented value (nxt = i + step), and the loop branches on i < max. It records this as an indVar struct (ind, nxt, min, max, step, entry, flags), establishing the invariant that within the loop body min ≤ i < max. It validates that step is a nonzero constant and that the increment cannot overflow (addWillOverflow). The prove pass then consumes these facts: knowing 0 ≤ i < len(s) inside the body, it eliminates the s[i] check entirely.

This is also the source of a well-known subtlety. The check on s[i] eliminates cleanly, but s[i+1] inside the same loop may not — the compiler must separately prove i+1 < len(s), and if the loop condition is i < len(s) it cannot (issue #30945). The standard fix is to hoist a length assertion: _ = s[i+1] earlier, or reslice once before the loop.

Reading the BCE diagnostic

Unlike inlining, there is no -m line for “eliminated a bounds check”. The diagnostic flag instead reports surviving checks:

go build -gcflags='-d=ssa/check_bce/debug=1' ./...

For a file like:

func sum(s []int) int {
    total := 0
    for i := 0; i < len(s); i++ {
        total += s[i]            // line 4 — eliminated, no output
    }
    total += s[len(s)/2]         // line 6 — may survive
    return total
}

Output is one line per remaining check:

./main.go:6:14: Found IsInBounds
  • Line 4 produces no output — loopbce + prove eliminated it. Silence here is success.
  • Line 6 prints Found IsInBounds — the compiler could not prove len(s)/2 < len(s) for an empty slice (len(s)/2 is 0 and 0 < 0 is false), so the check stays. Honest, and correct.

Found IsSliceInBounds appears for surviving slice-expression checks. The way to remove a stubborn check is to give the compiler a fact it can use — most commonly the “BCE hint” idiom _ = s[n] placed where the access happens, which proves n < len(s) for every later access of index ≤ n in the same dominated region.

Failure Modes and Common Misunderstandings

  • “Disabling bounds checks makes Go fast.” The flag -gcflags=-B disables bounds checking globally, but this trades away memory safety for usually a tiny gain — the prove pass already removes most checks in hot loops, and a missed check is a single well-predicted branch. -B is a debugging/measurement tool, not a production tactic.
  • prove is incomplete by design. It will miss provable cases — non-linear index arithmetic, indices flowing through function calls the inliner did not collapse, complex modular reasoning. A surviving check is not necessarily eliminable.
  • s[i] then s[i+1]. As above, prove the largest index first (_ = s[i+1]) so the dominated region carries the strongest fact.
  • Inlining gates BCE. BCE runs on SSA after Function Inlining. If a length and an index are computed in different functions and the call was not inlined, the prove pass cannot relate them. Many “why isn’t this check eliminated” puzzles are really “why wasn’t this inlined”.
  • Signed vs unsigned indices. Indexing with a signed int is fine — IsInBounds folds the ≥ 0 test into one unsigned comparison. But an index that the compiler cannot prove non-negative will keep its check; deriving an index from subtraction (i-1) is a classic offender.

Alternatives and When to Choose Them

  • -gcflags=-B — global disable. Measurement only; never ship it.
  • Restructuring for the prover — reslice once (s = s[:n]) so subsequent accesses are against a known-length slice; iterate with range (the compiler knows range indices are in bounds by construction, so for i := range s { s[i] } is reliably check-free); hoist a _ = s[maxIndex] hint.
  • unsafe indexing — unsafe.Add/unsafe.Slice bypass checks entirely. This abandons memory safety and is justified only in audited hot paths; see The unsafe Package.

Production Notes

The most reliable production guidance is structural: prefer range loops and slice-once-then-index over manual index arithmetic, because those forms hand the prover the facts it needs. When a profiled hot loop shows bounds-check overhead (visible as panicIndex/panicSlice call stubs in the disassembly via go tool objdump or -gcflags=-S), the fix is almost always to add a single BCE hint or reslice, not to reach for -B or unsafe. The Go standard library uses the _ = b[7] hint pattern extensively in encoding/binary so that a sequence of byte accesses collapses to one check covering all of them.

See Also

Graph View

Backlinks