Arithmetic strength reduction

Some machine instructions are far more expensive than others. A hardware signed integer division (idiv) costs tens of cycles on x86-64; a multiply is a handful, and a shift is one. Strength reduction is the family of rewrites that swaps an expensive operation for a cheaper one that computes the exact same result.

Axle performs the reductions itself during lowering, not in a pass that runs later. That is what makes them present at -O0, where LLVM runs no optimisation passes at all — a debug build stays fast on div-heavy code instead of dropping to a hardware idiv per iteration. At -O1 and above the same lowering runs, and Axle’s job is also to hand LLVM the facts it needs to go further than it could on its own.

Everything here is exact: a strength-reduced operation returns bit-for-bit the same value as the operation it replaced, for every input.

Constant divide and modulo → multiply-shift

Dividing a signed value by a compile-time constant never needs a hardware divide. For a power of two it’s a shift; for any other constant it’s a “magic” multiply-and-shift — the standard Hacker’s Delight reciprocal trick — plus a small correction to round toward zero:

fn scale(x : i64) : i64 { return x / 100; }
fn wrap(x : i64)  : i64 { return x % 100; }

Compiled at -O0 and dumped with --emit=llvm, x % 100 contains no srem — it’s a high-multiply against a magic constant, a shift, and a sign fix-up:

  %mulhi.prod = mul i128 %l128, 5270498306774157605
  %mulhi.hi   = ashr i128 %mulhi.prod, 64
  %magic.mulhi = trunc i128 %mulhi.hi to i64
  ; … shift + signbit correction, then  l − q*100  for the remainder

That this holds at -O0 is the point: the reduction rides in during lowering, so you get it in a debug build too, where LLVM’s own reducer isn’t running. At -O2 and above the emitted shape is exactly what LLVM would have produced anyway, so there’s no double work and no pessimisation.

Powers of two → shift and mask

A power-of-two divisor is the cheapest case of all. Dividing by 2^k is a shift; taking % 2^k is a bitmask:

fn half(x : i64)   : i64 { return x / 16; }   // → x >> 4  (with a sign bias)
fn low4(x : i64)   : i64 { return x % 16; }   // → x & 15  (unsigned-safe cases)

For an unsigned-safe value the shift and mask are used directly. For a signed value that could be negative, the compiler inserts the small bias that makes the shift round toward zero — still branchless, still exact for every input including the minimum. When a separate analysis has proven the value non-negative, that bias drops out and you get the bare shift or mask.

Here is a complete, runnable program exercising all three shapes:

fn div_by(x : i32) : i32 { return x / 8; }
fn mod_by(x : i32) : i32 { return x % 100; }
fn shift_pow2(x : i32) : i32 { return x / 16; }

fn main() : i32 {
    let a : i32 = div_by(64);       //  8
    let b : i32 = mod_by(250);      // 50
    let c : i32 = shift_pow2(160);  // 10
    return a + b + c - 68;          //  0
}

Loop-invariant runtime divisor → hoisted multiply

The multiply-shift trick above needs the divisor to be a constant. LLVM will not apply it to a runtime divisor — a value only known when the program runs — so a / or % by a variable stays a hardware idiv even at -O3.

Axle closes part of that gap. When a compiler analysis proves the divisor is loop-invariant (it doesn’t change across the loop’s iterations), the compiler emits the magic-multiply prep as a pure, side-effect-free computation that LLVM’s loop-invariant-code-motion pass then lifts out of the loop. The idiv that ran once per iteration becomes a one-time setup plus a few-cycle multiply each turn.

fn digit_sum(n : i64, base : i64) : i64 {
    let sum : i64 = 0;
    let x : i64 = n;
    while (x > 0) {
        sum = sum + (x % base);   // `base` never changes in the loop …
        x = x / base;             // … so its magic prep is hoisted out
    }
    return sum;
}

Honest limits. This one is deliberately narrow: it fires for signed i64 divisors, and only at -O1 and above (at -O0 there’s no hoisting pass to lift the prep, so it would be a net loss and is switched off). A division whose result is immediately truncated to a narrower integer — the arr.get((x % len) as i32) index idiom — is not reduced this way, because that value is handled by the non-negativity path that elides a different guard. An un-reduced divisor simply keeps its hardware idiv: a missed speed-up, never a wrong answer.

Dropping the divide-by-zero guard

A signed division has two inputs that would be undefined behaviour in LLVM: dividing by zero, and computing INT_MIN / -1 (which overflows). Axle guards both — a bad divide aborts the process with a named runtime error instead of producing a poison value.

That guard is a branch on the hot path, so the compiler removes it whenever it’s provably dead:

when the divisor is a constant that isn’t 0 or -1 (the multiply-shift above has no division to guard in the first place);
when a value-range analysis has proven the divisor ≥ 1 — neither undefined shape can occur, so the check is pure overhead.

fn average(total : i64, count : i64) : i64 {
    if (count >= 1) {
        return total / count;   // divisor proven ≥ 1 → no guard emitted
    }
    return 0;
}

As everywhere in this chapter, the elision is one-directional: a divisor the analysis cannot bound keeps its guard. You lose the branch only when the safety it protected is provably unreachable.

The small stuff — peepholes

Alongside the division work, a bottom-up pass swaps small fixed arithmetic patterns for cheaper equivalents:

Pattern	Becomes
`x * 8`	a shift, `x << 3`
`x + 0`, `x * 1`	dropped
`x - x`	`0`
a constant-only expression	its value
a repeated pure subexpression in one block	computed once, reused
`?? constant` whose two branches are side-effect-free	a branchless `select` rather than a jump

These are documented with their exact soundness gates — including the abs-after-modulo idiom and dead-code elimination — in Loop and idiom rewrites.

Where it stops — honestly

A runtime divisor that isn’t loop-invariant keeps its hardware idiv. There’s no magic constant without a fixed value to compute it from.
An unsigned constant divisor that is not a power of two keeps its hardware udiv / urem: the reciprocal trick above is the signed form, and an unsigned divisor reduces only to a shift or a mask.
Floating-point division is not turned into a reciprocal multiply by default — that changes the last bit of the result, so it’s gated behind fast-math relaxation rather than done silently (see what the compiler tells LLVM).