Loopsimplementation

Bounds Check Elimination

A memory-safe language checks every array index. Removing the checks it can prove redundant is what makes safe languages fast — and it is why a loop written over a whole array is faster than the same loop written with index arithmetic the compiler cannot follow.

The question

If every array access in Rust and Java is bounds-checked, why is the generated code not slower than C?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

IR in which each array access is preceded by an explicit comparison and a branch to a failure path — the check is a real instruction sequence, not an abstract property. Alongside it, a range analysis: for each integer value, an interval or a set of symbolic relations bounding it. Elimination is the intersection of the two: a check whose condition is implied by the known range is removable.

What this phase may assume or do

A check may be removed only if the condition it tests is provably true on every execution that reaches it. "Provably" means implied by a dominating check, by the loop bounds, or by range analysis over the index — never by the absence of an observed failure. Removing a check that could fail converts a defined, trapping error into out-of-bounds memory access: not a slightly faster program but a memory-safety vulnerability, which is why this is one of the transformations where the legality argument is a security argument.

Key points

A bounds check is a real compare and branch; eliminating the provably-redundant ones is what makes safe languages competitive.
Three routes: a dominating identical check, an index range implied by the loop bound, or hoisting the check out of the loop via versioning.
The idiomatic form — iterators, or a loop bounded by the array's own length — is the form the compiler can prove, and therefore the fast one.
An index the compiler cannot bound (indirect indexing, unrelated arithmetic) keeps its check, and no amount of optimization level changes that.
The surviving check costs more than its instructions: the branch to the failure path is an extra loop exit that blocks vectorization.
Removing an unprovable check does not produce a faster program, it produces a memory-safety vulnerability — which is why this transformation is held to a security standard.

The check, and the three ways it goes away

Each array access in a memory-safe language expands to roughly: compare the index against the length, branch to a panic or exception path if out of range, then perform the access. On its own that is a compare and a well-predicted branch — perhaps a cycle of throughput — plus, more importantly, an obstacle to every other optimization, because a branch to a failure path is a possible exit from the loop and a barrier to reordering.

Removal by dominance. If an identical check dominates this one and nothing has changed the index or the length between them, the second check is redundant. This is [[common-subexpression-elimination]] applied to the check condition, and it is the reason a loop that indexes the same array several times per iteration pays for at most one check.

Removal by range. If the compiler knows 0 <= i < len from the loop bound, and the array's length is that same len, the check is implied. This is the case that matters, and it is why the ordinary counted loop over an array is completely check-free after optimization while a loop whose index is computed from unrelated arithmetic is not.

Removal by hoisting the check out of the loop. If the compiler cannot prove the range but can compute the maximum index the loop will use, it can check *once* before the loop and remove the per-iteration checks. This is loop versioning: emit a fast loop with no checks, guarded by a single test, and a slow checked loop for when the test fails. It costs code size and buys a check-free inner loop.

The counted loop, before and after

Before

// conceptual expansion of the checked form:
for i in 0..a.len() {
    if i >= a.len() { panic_out_of_bounds(); }
    sum += a[i];
}

After

for i in 0..a.len() {
    sum += a[i];          // no check: 0 <= i < a.len() is the loop bound
}

Legal only when

The loop bound is literally the array's length, and a is not reassigned or resized in the body, so i < a.len() is implied by the loop condition on every iteration. The check is provably true whenever it is reached and can be deleted. Rust's slices carry their length with them, so a.len() is not a memory load whose value could change — which is what makes the implication available.

Illegal when

The index is not the loop counter, or the length can change. for i in 0..n { sum += a[idx[i]]; } cannot be proved: idx[i] is arbitrary data, so the check on a stays. Neither can a loop over a container that can be mutated inside the body, where the length is a load whose value may differ each iteration. Removing the check in either case is not an optimization, it is a memory-safety hole.

Why the idiomatic version is the fast version

implementationHotSpot eliminates range checks in counted loops via loop predication — hoisting the check into a guard before the loop and deoptimizing if it fails — which is a JIT-specific form of loop versioning where the slow path is not code but a return to the interpreter. Rust relies on LLVM's range analysis and instruction combining instead, with no deoptimization available, so its checks must be eliminated statically or not at all.

This is the practical heart of the lesson, and it inverts the usual folklore. In Rust, iterating with for x in &a or with an iterator chain produces code with no bounds checks at all, because the iterator's own invariant guarantees the index is in range — there is no index to check. Iterating with for i in 0..a.len() { a[i] } also usually eliminates, because the relation is provable. Iterating with a hand-computed index — a[i * stride + offset] where the compiler cannot bound the expression — does not, and pays a check per access.

So the "clever" low-level-looking version is the slow one, and the high-level version is the fast one, for a completely mechanical reason: the high-level version hands the compiler a proof, and the low-level version hides it. The same holds in Java, where the JIT eliminates range checks in counted loops over arrays and cannot do so when the index comes from elsewhere.

The corollary is that get_unchecked and its equivalents are almost never the right answer. They trade a memory-safety guarantee for a check the optimizer has usually already removed, and the correct first step is to look at whether the check is actually still there.

Four ways to write the same loop, and what happens to the checkstypical

Form	Checks eliminated?	Why
`for x in &a` (iterator)	No checks exist	The iterator holds a pointer and a bound; there is no index to validate
`for i in 0..a.len() { a[i] }`	Yes, usually	The loop bound is the length, so the condition is implied
`for i in 0..n { a[i] }` with `n` unrelated	Only via loop versioning	The compiler must first check `n <= a.len()` once, then use an unchecked loop
`a[idx[i]]` (indirect)	No	`idx[i]` is data; no static range can be derived from it
Java counted loop over an arrayimplementation	Yes, in compiled code	HotSpot performs range-check elimination for counted loops; the interpreter still checks

What it costs when the checks stay, and the security argument for keeping them

A bounds check that survives costs a compare, a predictable branch, and — usually more — the constraint it places on the optimizer. A loop containing a branch to a panic path has an extra exit, which blocks vectorization outright and limits reordering. So the cost of an un-eliminated check in a hot loop is frequently much larger than the check itself.

That is the argument for making the checks eliminable, not for removing them. Out-of-bounds access is the root of a very large fraction of memory-safety vulnerabilities in C and C++ code, and the entire premise of a safe language is that the check is not optional. A compiler that removed a check it could not prove would be reintroducing the vulnerability class the language exists to eliminate.

This is why bounds-check elimination is a good closing lesson for the module: it is the clearest case where the value of an optimization is not that it makes the program faster than an unsafe one, but that it makes safety affordable. The check is the semantics; eliminating the provable ones is the compiler's contribution to making those semantics cheap.

And it is why the failure mode matters so much. If the range analysis is wrong, the result is not a slow program — it is an out-of-bounds write in a language that promised there could not be one. Compiler test suites for this transformation are correspondingly paranoid, and the transformation is a standard target for [[compiler-fuzzing]] and [[differential-testing]].

How it works

The steps, in the order the compiler takes them.

Recognise the check: a comparison of an index against a length, guarding a branch to a failure path.
Run a range analysis over integer values, deriving intervals and symbolic relations from loop bounds, dominating comparisons and constant assignments.
For each check, ask whether its condition is implied by the known range at that point. If so, delete the check and the failure edge.
Otherwise, look for a dominating check with the same condition and unchanged operands, which makes this one redundant by dominance.
Otherwise, attempt loop versioning: compute the maximum index the loop can reach, emit a single guard before the loop, and generate an unchecked copy of the body for the guarded path.
Re-run simplification: removing the failure edges makes the loop single-exit, which is often what unblocks vectorization.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A hot loop refuses to vectorize and the diagnostic mentions multiple exits — the bounds check's panic edge is the second exit, and nothing about the source suggests it.
Rewriting an iterator loop into an index loop for "clarity" reintroduces checks the iterator form did not have, and the loop gets measurably slower with no change in the arithmetic.
A Rust or Java loop is fast in a microbenchmark with a constant length and slow in production with a dynamic one, because the range implication held in one case and not the other.
Someone reaches for get_unchecked to remove a check that was already being eliminated, gaining nothing and giving up memory safety in exchange.
A compiler bug in the range analysis removes a check that could fail, producing an out-of-bounds access in a language that guarantees none — the most serious class of miscompilation there is, and the reason this pass is fuzzed heavily.

When it helps

Every counted loop over an array in a memory-safe language, which is most numeric and data-processing code in Rust, Java, C# and Go.
As an enabler for vectorization: a loop whose only extra exit was the panic path becomes single-exit once the checks are gone.
Nested access patterns where the same check dominates several accesses, so one proof serves many.

When it hurts

It does not hurt, but relying on it does: an index expression that becomes unprovable after a refactor silently reintroduces the checks, and the regression appears in a benchmark with no obvious cause.
Loop versioning costs code size — two copies of the body — which matters when many loops are versioned in a size-constrained binary.

What it costs

Every one of these is paid by something.

Range analysis buys the elimination and pays compile time; a more precise, symbolic relational analysis proves more checks and costs more, which is why compilers use interval analysis plus targeted symbolic reasoning rather than a full relational domain.
Loop versioning buys a check-free inner loop and pays with two copies of the body plus a guard, which is a poor trade for loops with small trip counts.
Keeping the checks at all buys memory safety and pays with a branch per access and a constraint on the optimizer — the trade the language made, and the reason this pass exists to reduce the bill rather than to remove the guarantee.

What else you could do

What a different compiler or language does instead, and when that is better.

Iterators, which carry the invariant instead of re-deriving it. This is the language-level version of the optimization and it is why idiomatic Rust and idiomatic Java both look the way they do.
Slice up front: take a subslice of the exact length once, and every access within it is provably in range. One check for the whole loop, written in the source.
Dependent types or refinement types make the index's range part of its type, so the check is discharged by the type checker and never emitted. Available in ATS, F* and Liquid Haskell; not in mainstream languages.
get_unchecked / Unsafe.getInt: remove the check by assertion. Correct only when you have proved what the compiler could not, and giving up the guarantee the language exists to provide.
Hardware-assisted bounds checking — CHERI capabilities, Intel MPX historically — moves the check into the memory access itself. CHERI is the live research direction; MPX was withdrawn for being slower than the software checks.

See it for yourself

The flag, dump or tool that shows you this directly.

Rust: cargo asm or Compiler Explorer on the function, and look for the panic path. If panic_bounds_check does not appear, the check was eliminated.
The A/B test: write the loop with an iterator and with an index and diff the assembly. The difference is this transformation, made visible in about a minute.
HotSpot: -XX:+PrintCompilation with -XX:+TraceLoopPredicate shows range-check elimination via loop predication, including when it deoptimizes instead.
LLVM: opt -passes=irce -S runs inductive range check elimination explicitly; -Rpass-missed=loop-vectorize will often name the panic edge as the multiple-exit blocker.
Go: bounds-check elimination decisions are reported by go build -gcflags="-d=ssa/check_bce/debug=1", which prints each check that could not be removed.

Plausible wrong readings

Stated the way a confident engineer states them.

"Safe languages are slower because of bounds checks." They are slower where the checks survive. In the ordinary counted loop over an array, they do not, and the generated code is the same as the unchecked version.
"Using unchecked indexing is how you make Rust fast." It is how you give up the guarantee. Check whether the bound check is still present first; usually it is not, and the unsafe version buys nothing.
"The optimizer removes bounds checks at -O2." It removes the ones it can prove. Whether yours is provable depends on how you wrote the index, and that is under your control in a way the optimization level is not.
"A bounds check is just a compare and a predicted branch." It is also an extra exit from the loop, which is what stops the vectorizer, and that cost is much larger than the compare.

Misconceptions

The claim, and what is actually true.

Bounds checking makes safe languages fundamentally slower.

It makes them slower where the check survives. In the common loop shapes it does not survive, and the argument is empirical: look at the generated code before accepting the premise.

Writing lower-level-looking index arithmetic is faster.

It is usually slower, because it hides the relation that made the check provable. The higher-level form is the one that hands the compiler the proof.

The compiler removes bounds checks because they usually pass.

It removes them only when it proves they cannot fail. "Usually passes" is a JIT's justification for a guard plus a deoptimization path, never a static compiler's justification for deletion.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Languages that promise you cannot read past the end of an array check every access. Most of those checks are provably unnecessary — if the loop runs from zero to the array's length, the index cannot be out of range — and the compiler removes those. The ones it cannot prove stay, which is why how you write the index matters.

practical

Prefer iterators and loops bounded by the container's own length; they are the forms that eliminate. If a loop is hot, look at the disassembly for the panic path before reaching for unchecked access, because the check has usually already gone. If it has not, the fix is to restructure the index so the bound is provable, or to slice once up front, not to remove the guarantee.

advanced

The general machinery is a range analysis over integers, and its precision is the whole game. Interval analysis alone proves the constant cases; proving the interesting ones needs symbolic relations between the index, the loop bound and the length, which is why compilers implement targeted forms such as LLVM's inductive range check elimination rather than a general relational abstract domain. The JIT variant is different in kind: loop predication hoists the check into a guard and, if it fails, deoptimizes instead of taking a slow path — which means the compiled code contains no check *and* no fallback, at the cost of the state map that makes the return to the interpreter possible. That is a strictly stronger result than a static compiler can produce, obtained by having somewhere to fall back to rather than by proving more.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationHotSpot uses loop predication, hoisting the check into a guard and deoptimizing when it fails — a route unavailable to an ahead-of-time compiler. Rust and Go rely on static range analysis (LLVM's and the Go SSA backend's respectively) and must prove it or keep the check. The same source pattern therefore has different outcomes across the three.

typicalMainstream implementations eliminate checks in counted loops whose bound is the container's own length, and generally do not for indirect indexing or for arithmetic they cannot bound. The specific set of provable patterns differs by compiler and version, so the reliable method is to look at the generated code rather than to reason from the rule.

specRust, Java, C# and Go all define out-of-bounds access as a trapping error, so the check is part of the language semantics rather than an implementation choice; the optimizer may only remove checks it proves cannot fail. C and C++ define it as undefined behavior instead, which is precisely the difference this lesson is about.

If you were asked this in an interview

Why is a Rust iterator loop often faster than the equivalent indexed loop, given both are memory-safe?
What can a JIT do about a bounds check that an ahead-of-time compiler cannot?
A hot Rust loop will not vectorize. How would bounds checks be involved, and how would you confirm it?

Connections

Computer Architecturebranch-prediction simd instruction-level-parallelism

Performancecpu-profiling benchmarking

Securityinput-validation owasp-reference

Domains that do not exist yet

Programming Languages & Runtime Internals — Array object layout: where the length lives and what an access costs at run time
Whether the length is a field load, an immediate in the slice, or a capability bound decides whether the check can be proved invariant. The layout is the runtime's decision and the optimizer's input.