THE BOUNDS-CHECK ELIMINATION drop the check the proof already made
A safe language checks every array access: is the index in range? Most checks never fire — the index is a constant, or provably bounded by a prior test, or a loop counter already constrained by the loop. Bounds-check elimination removes a check only when the compiler has proven it can never fail, keeping the guarantee while paying nothing for it. This is the honest optimization: it does not make unsafe code fast, it makes safe code fast by discharging the check with a proof instead of a runtime test.
THE TECHNIQUE remove a check only where the index is proven in range
Several accesses into an array of length 4: some indices are literal constants (provably safe), one is a runtime value (must stay checked). The demo counts the checks a proof can remove: live demo
HISTORY & CREDIT Markstein-Cocke 1982 · Gupta 1993
“Safety costs a check on every access — pick safety or speed.” — a false choice. Where the index is provably in range, the check is dead code; removing it keeps the guarantee and drops the cost. Bounds-check elimination is safety and speed, bought with a proof. cited
1982 · Markstein, Cocke & Markstein — range analysis to eliminate redundant bounds checks in loops. 1993 · Rajiv Gupta — “Optimizing array bound checks using flow analysis”: check elimination and hoisting by dataflow. 2000 · Bodík, Gupta & Sarkar — ABCD: eliminating array-bounds checks on demand. now · the JVM, .NET, and Rust all lean on it — safe by default, fast where proven.
The check is removed only when it could never have fired — the proof is the permission. Every access that survives keeps its guard. Nothing unsafe is ever made faster; only the certain is made free. Gupta 1993
RECOMMEND FOR I-13 provably-removable checks, computed
On the canonical compiler, of five accesses into a length-4 array (four literal indices 0..3, one runtime index), 4 checks are provably removable — the runtime one stays guarded:
$ i13 run bce.i13 # count checks provable-safe, array length 4
removable = 4 -- indices 0,1,2,3 proven in range; the runtime index stays checked
Recommend: this is THE optimizer pass I-13 should want — the one whose logic is i13's logic. i13 already bounds-checks every access (E0501) and already runs a single-pass validator that proves things. Extending it to elide a check when the index is a literal in [0,len) keeps the guarantee and removes the cost — a rewrite that only deletes a test the validator has already discharged. It does not hide what runs (the access still happens); it removes a check that could never fail. Safety-preserving, proof-carrying, single-pass: it is the optimizer written in i13's own grain.