Loop and idiom rewrites

The compiler runs a set of source-level rewrites before any machine code is emitted. Most of them are tiny — a peephole, which swaps a small fixed pattern for a cheaper equivalent one (x * 1 → x) — but a few are idiom recognition : the compiler spots that a whole loop you wrote by hand is a well-known operation (filling an array with a constant, copying one buffer to another) and replaces it with the single, hand-tuned machine routine for that operation. None of these rewrites changes the program’s observable behaviour ; they exist so the optimiser sees the simplest equivalent shape.

A quick vocabulary for the sections below:

• peephole — a local pattern → cheaper-pattern swap on a small window of code (x + 0 → x).
• idiom recognition — spotting that a larger construct (a loop) matches a known operation and emitting the specialised form.
• hoisting — moving a computation out of a loop when its result is the same on every iteration, so it runs once.
• strength reduction — replacing an expensive op with a cheaper one that gives the same answer (x * 8 → x << 3).

Axle integer arithmetic wraps. The compiler adds LLVM’s nsw / nuw to a + or - only where a hoisted bounds precheck proves the result cannot leave its width — the flag turns an overflow into poison, and a branch on poison is undefined, so the default is to claim nothing. The proof is about the operation, not the value: a sum that lands back in range can still have wrapped, so the flag needs the operands’ signs, not just the result’s range.

memset / memcpy recognition

A for-of loop whose body is a single element assignment can collapse into one library call. The clearest case is a buffer-to-buffer copy:

use std::sys::process::argc;

fn main() : i32 {
    let n : i32 = argc() + 1;
    let a : i32[] = malloc<i32>(n + 1);
    let b : i32[] = malloc<i32>(n + 1);
    for (i of 0..n) { b[i] = a[i]; }
    return b[0];
}

The recogniser is a sema pass, not an LLVM heuristic : it rewrites the loop into a single range copy (b[0..n] = a[0..n] in the HIR), which codegen lowers to @llvm.memcpy. A constant fill (arr[i] = <byte-replicable literal>) is rewritten the same way and lowers to @llvm.memset.

Whether the bulk call reaches the module depends on the optimisation level. At -O0 no rewrite runs, and the loops are emitted as written — the increment / compare / branch / store sequence is still there, one turn per element. From -O1 a recognised copy is a @llvm.memcpy in the emitted module, and a fill that clears the gates below is a @llvm.memset. If you are reading --emit=llvm output and expecting a bulk call, check the optimisation level first : it is the usual reason the intrinsic is absent.

Why it pays off is the shape of the emitted code. The hand-written loop runs the whole increment / compare / branch / store machinery n times ; the rewrite hands the same work to one call the C library already implements with word-at-a-time stores and SIMD:

   for (i of 0..n) { arr[i] = 0; }          →   memset(arr, 0, n * 4)

   BEFORE  (n turns of the loop)                AFTER  (one bulk call)
   ┌──────────────────────────┐                ┌──────────────────────────┐
   │ i = 0                     │                │ memset(arr, 0, n*4)      │
   │ loop:                     │                │  → word/SIMD stores,     │
   │   cmp  i, n  ; branch     │  n iterations  │    zero branches in user │
   │   store 0 → arr[i]        │  ───────────>  │    code                  │
   │   i = i + 1 ; jump loop   │                └──────────────────────────┘
   └──────────────────────────┘
   per-element: compare+branch+index+store       one call, hardware-tuned

The observable result is identical — the buffer ends up filled with the same bytes — but the induction-variable bookkeeping that dominated the scalar loop is gone.

The recognised body shape is tight : exactly one assignment per iteration, the index is the loop induction variable (an affine shift a[i + d] = a[i + s] with d < s is recognised as a @llvm.memmove), and for a copy the two buffers must be provably distinct. Anything more general — strided writes, multiple stores per iteration, computed indices — stays as a scalar loop and the auto-vectoriser decides.

Limitations

The bulk rewrite is gated, and the gates decide whether the call appears at all:

• A copy needs the two buffers provably distinct. @llvm.memcpy is undefined on overlapping operands, and an array value is a pointer, so let b = a; for i { b[i] = a[i]; } would copy a buffer onto itself. The recogniser requires each side to be a bare local rooted at its own fresh allocation and never re-bound. A loop over a buffer taken as a parameter does not qualify — it stays an element loop.
• A fill needs the whole written range provably inside the destination. Collapsing the loop replaces a per-iteration bounds-checked store with one bulk write that carries no guard, so the rewrite fires only over a buffer whose extent the compiler knows statically. A fill over a buffer of runtime length keeps its scalar form and its per-element check.

When a gate declines, the loop is emitted as written. The auto-vectoriser may still take it (see auto-vectorised loops), and LLVM can fold a vectorised fill into @llvm.memset at -O2 on its own. The rewrite is an optimisation, never a correctness requirement : an unrecognised loop runs element by element, which is always correct.

The check a declined rewrite keeps is not decoration : an out-of-range index traps through axle_panic_oob rather than scribbling past the allocation. A recognised copy keeps the trap as well — its bulk bounds are checked against both buffers’ lengths before the copy, in place of the two per-iteration guards it replaced.

Monotonic-break collapse

fn anyMatch(items : i32[], n : i32) : bool {
    let found = false;
    for i of 0..n {
        if (!found) {
            if (items[i] > 0) {
                found = true;
            }
        }
    }
    return found;
}

Loops whose body guard is a monotonic-flip bool (one that goes false → true and never back) are rewritten so the post-flip iterations exit at the top instead of running the body’s phi shuffles:

fn anyMatch(items : i32[], n : i32) : bool {
    let found = false;
    for i of 0..n {
        if (found) { break; }               // compiler-inserted
        if (items[i] > 0) { found = true; }
    }
    return found;
}

Same semantics, the compiler proves the body is a no-op after found = true.

Loop-invariant hoisting

A let at the top level of a loop body whose initialiser doesn’t depend on the iteration is computed once, in front of the loop:

fn shade(pixels : i32[], n : i32, w : i32, h : i32) {
    for i of 0..n {
        let area = w * h;    // w and h never change in the loop
        pixels[i] = area + i;
    }
}

becomes:

fn shade(pixels : i32[], n : i32, w : i32, h : i32) {
    let area = w * h;
    for i of 0..n {
        pixels[i] = area + i;
    }
}

The hoist fires only when it is provably invisible : the binding is a by-value scalar that is never reassigned in the body, and the initialiser is non-trapping with every operand defined outside the loop.

Nested loops hoist inside-out, so an invariant chain settles across the nesting. Only a whole top-level let moves — an invariant subexpression buried inside a larger term stays put.

Bounds-check and nullable elision

Every array or collection index is bounds-checked — an out-of-range access aborts the process rather than reading wild memory. The compiler carries an integer-interval analysis (a forward abstract interpreter with a loop fixpoint) that proves, where it can, that an index already sits in [0, N) — and drops the check when it does. Two things it can prove:

• A loop guard bounds the index. for (i of 0..n) and the counted while (i < arr.length) establish 0 <= i < n; a checked arr[i] in the body then compiles to a bare getelementptr with no trap.
• A computed index is provably non-negative. The analysis widens a loop-carried value against the bounds a modulus or a mask pins it to — x % C with a literal C, x & mask — instead of to infinity, so the interval stays tight through the loop fixpoint. A remainder is signed non-negative on its own when the divisor is a positive literal, so seed % length used as an index is known >= 0 and the index < 0 half of the guard folds too.

The second one has a nice knock-on effect on a nullable accessor like ArrayList.get, which returns T | null (null for an out-of-range index). When the analysis proves the index in range, the null branch is dead, so list.get(i) ?? fallback collapses: the T | null box, the ?? fallback select, and the conditional load all disappear, leaving a plain indexed load — the shape a hand-written arr[i] would emit.

The whole analysis is one-directional: it only ever removes a check it has proven redundant, never adds or weakens one. An index it cannot bound keeps its guard and its ?? fallback exactly as written — you lose the cost, never the safety.

The interval analysis here bounds each value on its own (against constants). A second, complementary analysis reasons between variables — composing i < n and n ≤ len into i < len, and carrying such a bound across a function call and out of how a container was built. It removes the checks this per-value pass cannot; see Bounds-check elimination.

abs idiom — absolute-value after modulo

fn slot(e : i32) : i32 {
    let v = e % 16;   // a positive literal divisor ; srem may still go negative
    if (v < 0) { v = -v; }
    return v;
}

The “modulo then absolute-value” shape — common in LCG-style PRNGs fed into a positive array index — collapses to a single abs(e % c) builtin call, which lowers to @llvm.abs.iN (one instruction, no branch). The assign-form v = e % c; if (v < 0) { v = -v; } (binding declared earlier) is recognised too. The negation form 0 - v is accepted in addition to the unary -v; an else arm on the if disqualifies the pattern (a different value could be written on the negative path).

Soundness gates : the dividend must be a signed integer (i8 / i16 / i32 / i64) and the divisor must be a positive integer literal — signed srem is undefined on zero, and the srem(x, c) ∈ [-(|c|-1), |c|-1] range proof only holds for c > 0. The transform does not fire on a bare if (v < 0) { v = -v; } whose v came from somewhere other than srem against a positive literal.

The branch really does disappear. For let v = e % 100; if (v < 0) { v = -v; }, --emit=llvm ends the computation with a single intrinsic and no conditional jump over a negation:

  ; … the `e % 100` remainder, computed into a value (the literal
  ; divisor is itself a multiply-shift, not a real `srem`) …
  %abs = call i32 @llvm.abs.i32(i32 <that remainder>, i1 false)

There is no br i1 guarding a sub 0, v — the whole if (v < 0) { v = -v; } collapsed into that one @llvm.abs.i32.

Arithmetic peepholes

Constant folding and the peephole rewrites walk each expression bottom-up — inner subtrees are simplified before their parents are examined, so a cascade like (x * 1) + 0 collapses in one walk. They run before the safety walkers, which therefore analyse the simplest equivalent shape ; the two strength-reduction rows run after the walkers, alongside the other post-check passes:

The “pure leaf” constraint matters: rewrites that drop one operand can only fire when that operand has no observable side effect (a Call could still be load-bearing, even if its return value would have been multiplied by zero).

Strength reduction is visible in the smallest possible program : a function that returns x * 8 is rewritten to a shift rather than a multiply. The rewrite is a HIR transform, so it runs from -O1 up: at that level the body under --emit=hir reads x << 3, and the emitted module carries the matching instruction —

  %shl = shl i32 %x, 3        ; x * 8  →  x << 3

— with no mul left in that body.

Common-subexpression elimination

Within a single block, a pure-arithmetic subexpression that appears more than once is computed into a temporary and reused:

fn total(r : i32) : i32 {
    return (r * 3) + (r * 3);    // r * 3 written twice
}

becomes:

fn total(r : i32) : i32 {
    let t = r * 3;               // computed once
    return t + t;
}

A candidate must be a non-trivial pure-arithmetic tree over locals, parameters and literals — no memory reads, calls, or allocations — and must contain no division or modulo (materialising it early must not move a divide-by-zero trap). Its operands must be stable across the occurrences that are merged: a candidate is only merged among the occurrences that all precede the first write to any of its operands, so the reuse window is write-free. The sharing is per-block: a value repeated across two different blocks is not shared, and each nested block runs its own elimination. A temporary left with a single use is swept up by dead-code elimination right after.

Dead-code elimination

A fixed-point pass drops bindings whose initialiser is pure and whose reads were eliminated by earlier rewrites. Function calls are preserved (their side effects might be load-bearing) ; the walker only removes locals that the analysis proves contribute nothing observable.

Trivial inlining

Functions whose whole body is one return <leaf> are substituted at every call site. “Leaf” here means: a literal, a local, a parameter, a field access, or a pure arithmetic expression over those — anything where duplicating the body at the call site is no worse than the call overhead. A read that writes no memory and owns nothing (a struct built from field reads) qualifies too.

Two separate mechanisms fold these calls, and they run at different times. Codegen stamps alwaysinline off the function’s inline hint, so LLVM’s own AlwaysInliner opens the call sites from -O0 up whether this pass ran or not. This pass is the sema half — a post-check transform, off at the -O0 floor — and what it buys is not the call overhead but the shape the later passes see.

The inliner runs after the ownership and exception walkers so substituted bodies cannot bypass safety checks: the walkers see the user’s original indirection, then later passes (strength-reduction, dead-code elimination, slot classification) get to work on the post-inline shape. Multi-hop trivial chains (fn a(x) = b(x); fn b(x) = x + 1) collapse in one walk — substitution is iterative over the precomputed trivial-bodies map.

The LSP path disables trivial inlining (with_inline_trivial(false)) so hover / goto-definition still resolve to the original call shape — substituted bodies would erase the call site the user is asking about.

Auto-vectorised loops

An element-wise loop whose every read and write goes through the same index —

fn addInto(c : i32[], a : i32[], b : i32[], n : i32) {
    for i of 0..n {
        c[i] = a[i] + b[i];
    }
}

— is rewritten into a SIMD main loop that processes a full vector of elements per step, plus a scalar tail for the remainder. Because each lane reads and writes only its own column, the rewrite is sound even when the destination aliases a source, and the SIMD shape is guaranteed rather than left to the LLVM cost model.

The recognised shape is deliberately narrow : a single same-index store (d[i] = …) built from + - *, integer negation, and division by a non-trapping literal. Reductions (sum = sum + a[i]), shifted-index stencils (a[i-1]), %, and float negation are not covered by this guaranteed rewrite — they stay scalar and get unroll / vectorise hints that LLVM’s own pipeline may act on. The full story — the exact eligible shapes, the @vectorize / @unroll annotations, the CPU-dispatch machinery — lives in the vectorisation chapter.

SSA-vs-stack-slot classifier

Locals and parameters that are never reassigned and never have their address taken are kept as direct SSA values — they never materialise as a stack slot. The remaining (mutable or address-taken) bindings get one. The classifier runs last, after every other rewrite, so it sees the final post-inline shape — a binding that looked mutable before inlining may be proven single-write after the substituted body lands.

Result : the entry block’s slot count stays minimal, and LLVM’s mem2reg at -O1+ has almost nothing left to do. On the generated IR side, a tight loop that operates on local scalars shows up as pure SSA register traffic with no alloca in sight.

Upsert fusion — one probe where the source spends two

The counting idiom reads a key, then writes it back:

use std::collections::HashMap;

fn bump(counts : HashMap<string, i32>, w : string) {
    let c = counts.getOrDefault(w, 0);
    counts.put(w, c + 1);
}

Written that way it hashes w twice, walks the probe chain twice, and compares the key twice — for one logical update. On an update-heavy workload the second probe is a large share of the whole run, and no allocator work touches it, so nothing about allocation can remove it.

The compiler fuses the pair into a single probe plus a branch on whether the key was found:

let __slot = counts.<probe>(w);              // the only probe
let c      = counts.<slot_read>(__slot, 0);  // addresses the slot, no probe
let __upd  = c + 1;                          // evaluated once
if (__slot >= 0) { counts.<slot_write>(__slot, __upd); }
else             { counts.<insert>(w, __upd); }

c keeps its identity, so every later use of it goes on working unchanged.

Why your container gets this too

The rewrite matches no method names. A container declares which of its methods play the five parts — probe, slot_read, slot_write, lookup, insert — with @upsert("…") on each, and the compiler reads the declaration:

class MyMap<K, V> {
    @upsert("probe")      fn find(self, key : K) : i64 { … }
    @upsert("slot_read")  fn at(self, slot : i64, fallback : V) : V { … }
    @upsert("slot_write") fn store(mut self, slot : i64, value : V) : void { … }
    @upsert("lookup")     fn read(self, key : K, fallback : V) : V { … }
    @upsert("insert")     fn write(mut self, key : K, value : V) : void { … }
}

The standard library’s HashMap earns the fusion because it declares these, and so does any container of yours that declares them. Renaming getOrDefault changes nothing; removing the annotation costs a probe and nothing else.

The slot stays valid across the read and the write because the compiler proves it, not because the annotation says so. A declaration names which method plays a part; it carries no authority over whether that method rehashes, and one that did would have the fused form write through a stale index into a freed buffer. So the two methods that run with the slot live are checked: their bodies must store no whole field, allocate nothing, free nothing, and call nothing that fails the same test.

probe   ─▶ hands the index out          ─▶ free to rehash
slot_read  ─┐
            ├─ run with the index live  ─▶ must be proven
slot_write ─┘
insert  ─▶ runs on the arm with no index ─▶ free to rehash

A container whose slot_write writes a field is simply left alone — one probe instead of none, never a bad write. What the roles still assert on your word is semantic: that probe names the slot lookup would have read, and that slot_write targets an occupied one.

A second saving falls out without being aimed at. Inserting a string key into a container that takes ownership of it costs a copy; because the fusion leaves the insert in the else arm, the pass that inserts that copy places it there — on the miss path only. An update to a key already present stops paying for it.

See also

• Escape analysis and promotion — the other rewrite that moves allocations off the heap.
• Arithmetic strength reduction — the user-facing view of the division and peephole rewrites, in the optimisations census.
• Inlining and tail calls — when the compiler stamps alwaysinline / inlinehint / tail.
• Compiler internals overview — index of all internals pages.
• Concept index — every optimisation cross-linked.