Axle v0.22.0

Bounds-check elimination

Every array and container index in Axle is memory-safe: reading a[i] past the end of a traps instead of corrupting memory. That safety has a cost — a comparison against the length on every access — and for a hot loop that comparison can dominate the work.

The compiler removes that check whenever it can prove the index is already in range, and keeps it otherwise. The proof is conservative by construction: the analysis only ever upgrades an access from “checked” to “unchecked”, and it only does so when a chain of facts it has established forces 0 ≤ index < length. If it cannot prove that, the check stays. A wrong elision would be an out-of-bounds read, so doubt always resolves to keeping the check.

What it proves, from simplest to hardest

A constant or counted loop

The classic case needs no cleverness: a for … of loop whose counter ranges below the length.

fn main() : i32 {
    let a : i32[5] = [10, 20, 30, 40, 50];
    let mut total : i32 = 0;
    for (i of 0..a.length) {
        total = total + a[i];   // i < a.length by construction — no check
    }
    return total;
}

The loop bound is the length, so i is in range on every iteration and the per-access check disappears.

A chain of comparisons — reasoning between variables

The interesting case is when the bound is not a constant but another variable, related to the length by a guard:

fn first_n(a : i32[5], n : i64) : i32 {
    let mut total : i32 = 0;
    for (i of 0..n) {                 // i is not tied to a.length here
        if (i < a.length) {           // fact: i < a.length
            total = total + a[i];     // guarded — the access needs no check
        }
    }
    return total;
}

The loop counter itself carries no relation to a.length, so the trip count alone proves nothing. What discharges the check is the guard that dominates the access: on the path where a[i] is evaluated, i < a.length is a fact the compiler already holds, and a second test of the same predicate is dead. The emitted IR for this function contains no call to axle_panic_oob.

The condition to keep in mind is where the fact is established. A bound that reaches the function as a parameter — if (n <= a.length) around the loop, with n supplied by the caller — is not the same situation: the relation has to survive the call boundary, which is the subject of the next section.

Across a function call

The chain can cross a call boundary. When every call site of a function establishes the bound its body needs, the body may assume it at entry. The rule applies only to a function whose every call is a recorded direct call: a function that is also used as a value, reached through a trait override, or exported under a symbol name is not analysed this way, because a caller the analysis cannot see would break the proof:

use std::collections::arraylist::ArrayList;

fn sum_first(h : ArrayList<i64>, n : i32) : i64 {
    let mut total : i64 = 0;
    let mut i : i32 = 0;
    while (i < n) {
        total = total + (h.get(i) ?? 0);  // bound comes from the caller
        i = i + 1;
    }
    return total;
}

fn main() : i32 {
    let v : ArrayList<i64> = new ArrayList<i64>();
    v.add(10); v.add(20); v.add(30);
    let n : i32 = 2;
    if (n <= v.size()) {                  // the caller guarantees n ≤ v.size()
        return sum_first(v, n) as i32;    // so the body's h.get(i) needs no box
    }
    return 0;
}

The ?? 0 fallback and its nullable result — the checked-access machinery — fold away inside sum_first, because the compiler proved at the call site that n is within v’s size and carried that fact into the callee. If a single call site cannot establish it (passes an unrelated value, or an unguarded one), the bound is dropped for the whole function — again, fail-closed.

From how a container was built

The bound can also come from the container’s own history. A freshly constructed container starts empty, and each append grows its size by one — facts the compiler tracks. So an index it can relate to that concrete size is provably in range even without a guard:

use std::collections::ArrayList;

fn build() : ArrayList<i64> {
    let v : ArrayList<i64> = new ArrayList<i64>();
    v.add(10); v.add(20); v.add(30);   // the compiler knows v.size() ≥ 3
    return v;
}

This rests on one always-true fact the compiler injects for every container — a size is never negative — which lets size == 0 of a fresh container and size ≥ 3 after three appends compose into the bounds a later access needs.

A container built up inside a loop

The hardest shape of the previous case is a container grown inside the same loop that indexes it, where the index tracks the growing size:

use std::collections::arraylist::ArrayList;

fn build_sum(n : i32) : i64 ! IndexOutOfBoundsException {
    let buf : ArrayList<i64> = new ArrayList<i64>();
    let mut size : i32 = 0;
    let mut acc : i64 = 0;
    while (size < n) {
        if (size < buf.size()) {
            buf.set(size, 7);                 // in range: size < buf.size()
        } else {
            buf.add(7);                       // grows buf.size() by one
        }
        acc = acc + (buf.get(size) ?? 0);     // size ≤ buf.size() every iteration
        size = size + 1;
    }
    return acc;
}

At the if, one branch writes an existing slot and the other appends — and after they rejoin, size ≤ buf.size() holds on both paths. The compiler carries that relationship around the loop, so the following buf.set(size, …) and buf.get(size) are provably in range: the bounds check, the nullable ?? 0 box, and the internal out-of-range branch all fold away, leaving a bare store and load — even though there is no single dominating size < buf.size() guard written above them. Keeping a loop-carried relationship like this alive across the merge point is what lets a container you fill and read in one pass cost nothing for its safety.

Inside the standard library’s containers

HashMap, HashSet and friends index their internal storage with expressions like slot = hash & (capacity − 1). That an internal slot is in range rests on an invariant spanning the constructor, the grow path and every accessor (mask == capacity − 1, storage.length == capacity, capacity ≥ 1). The compiler infers and verifies such a class invariant — it keeps only the relations every method re-establishes at every exit — and uses it to remove the internal probe-loop checks. This is why the built-in containers pay for their safety only where the compiler could not discharge it.

The same machinery works on a container you write. A class with a backing array data and a length field len, whose methods maintain len ≤ data.length, gets its self.data[i] access under a guard i < self.len elided by exactly the inferred invariant — no annotation, and nothing special about it being in the standard library. A hand-rolled RingBuffer or Matrix with the same shape drops the same checks.

A capacity fixed by the constructor

The invariant above is a relation between two fields. Its sibling is a field whose length is a whole-program constant, because every construction site gives it the same one. A buffer sized from the class’s own constructor parameter is the shape you meet most:

class Buffer {
    data : i32[];
    len : i32;

    constructor(capacity : i32) {
        self.data = new i32[capacity];
        self.len = capacity;
    }

    pub fn fill(mut self, v : i32) : void {
        let mut i : i32 = 0;
        while (i < self.len) {
            self.data[i] = v;    // no guard — len == data.length, a constant
            i = i + 1;
        }
    }
}

fn main() : i32 {
    let a : Buffer = new Buffer(8);
    let b : Buffer = new Buffer(8);
    a.fill(3);
    b.fill(4);
    return 0;
}

capacity is not a constant where it is read — it is one everywhere it is written: the class has two construction sites and both pass 8. The compiler collects those sites, proves len == data.length at every one of them, and both the header load and the per-index guard disappear.

The elision happens in the front end, before the LLVM optimiser runs. At -O1 the LLVM pipeline is only the canonicalisation passes and the cost-model inliner, and neither of them removes a bounds trap. So when the trap is absent from the -O1 module, the compiler’s own proof is the reason, and you can check it with --emit=llvm at -O1 and -O0.

The proof is only as good as its weakest site, and it is read conservatively. A site that omits the argument, passes a runtime value, or passes a different constant poisons the field, and the fold is declined for the whole class. That direction is not a preference: assuming a buffer is larger than the smallest one a construction site actually built is the one mistake that removes a guard from a genuine overrun, so a site the analysis cannot see must cost the optimisation rather than the safety.

Two consequences worth knowing:

  • A class with two constructors is declined outright. A construction site does not record which constructor it calls, so a count read from a second constructor’s parameter would be resolved through the first one’s sites — a whole-program claim read off the wrong list. The pass leaves the field unkeyed and the guards stay, which is the honest answer rather than a guess.
  • Only a write in the class’s own constructor counts. A method that stores the same field is not a construction site, and nothing states it stores the same count.

One proof, three costs

The check itself is often the smallest thing an elision removes. Look again at what a container accessor costs:

use std::collections::ArrayList;

fn read(h : ArrayList<i64>, i : i32, total : i64) : i64 {
    return total + (h.get(i) ?? 0);
}

get returns null when the index is out of range, so the callee builds a nullable box to carry “no value” and the caller unwraps it with ?? 0. A set that throws instead pays an exception poll after the call. And the accessor still runs its own bounds check inside.

All of that machinery hangs off one branch — the fault guard if (index < 0 || index >= self.len). Prove that guard false at the call site and the whole branch is dead, so the box, the unwrapping, the throwing status, the poll and the internal trap disappear together. “Elide null”, “elide exception” and “elide bounds” are not three optimisations; they are one proof consumed once.

Nothing about this is specific to the standard library’s containers. The rule is that a fault lives on a branch guarded by a relation — so a Matrix.at(r, c) that returns null when r >= self.rows, or a RingBuffer.peek() that returns null when self.count == 0, is treated identically. The compiler never asks what the type is called.

What it looks like on a real program

Take a Dijkstra shortest-path implementation — a binary heap, a CSR adjacency structure, an ArrayList of distances, the usual shape. Each ?? 0 unwrap or post-call exception check that guards an out-of-range case the caller has already ruled out is removed by the same proof that removes the bounds check, because they all hang off one branch.

The bounds traps that remain in it are instructive, because they are the honest ones. dist[node] where node was read out of the frontier array cannot be proven — nothing states the range of a value that came out of an i32[]. The CSR walk needs a fact about the contents of the offsets array. Those checks stay, and should.

What it costs to compile. The expensive whole-program stage only runs where a function offers it something to prove. A program that proposes nothing to prove pays nothing for it.

The point is not a headline ratio. It is that the elisions are the ones you could have argued for yourself, and the checks that remain are the ones you could not.

Where a heap-allocated structure is indexed through values read out of another array (an adjacency offset, a node read from a frontier), the analysis has no relation to prove, so those accesses keep their check.

Where it stops — honestly

Some bounds a local, per-function-and-summary analysis cannot recover, and there the check stays:

  • Data-dependent indices. dist[adj[k]] — an index read from another array — has no static relationship to the target’s length. The value could be anything the data holds.
  • Non-local structural invariants. A prefix-sum array where offsets[i] ≤ total for the whole structure, or a bit-mask wider than the array it indexes, needs a whole-program data invariant the compiler does not track.
  • A bound that outruns the proof chain. The analysis composes a bounded number of steps; a relationship that needs a longer chain is left unproven rather than guessed.

In every one of these cases the runtime check remains and your program stays safe. The point of this page is not that Axle removes all bounds checks — it is that it removes the ones it can prove redundant, and tells you plainly which ones it cannot.

See also

optimisationbounds-checkssafetyarrays