Axle v0.22.0

Inlining and tail calls

The three terms, from scratch

Calling a function has a cost the arithmetic inside it doesn’t: the CPU pushes the arguments and a return address, jumps away, runs the body, then jumps back. For a one-line accessor like fn size(self) { return self.len; } that overhead can dwarf the actual work.

  • Inlining removes the call entirely by pasting the function’s body into the caller at the call site. x = size(p) becomes x = p.len — no jump, and the surrounding optimiser can now see through the body. The trade-off is code size: paste a big body into a thousand call sites and the binary balloons, so the compiler inlines small bodies eagerly and leaves large ones to a cost model.

    fn size(self) : i32 { return self.len; }   x = size(p)
    
    BEFORE  (a real call)                AFTER  (body pasted in)
      push p                               x = load p.len
      call size   ─┐  jump away                       ▲
      ...          │  run body            one load, no jump, and the
      ret         ◄┘  jump back           optimiser now sees x's provenance
      x = result                          straight through to the field

    The pasted load p.len isn’t just cheaper by one jump — it lets every later pass (constant-folding, dead-code elimination, the slot classifier) reason about x as the field itself, which a call boundary would have hidden.

  • A tail call is a call that is the very last thing a function does — return f(args), with nothing left to compute after f returns. Its result becomes the caller’s result directly. Because the caller has no more work, its stack frame is dead the moment the tail call starts.

  • Tail-call elimination / tail-recursion elimination (TRE) exploits that dead frame: instead of stacking a new frame for the call, reuse the current one. When a function tail-calls itself (self-recursion), this turns the recursion into a plain loop that runs at constant stack depth — the key reason a deep recursion doesn’t overflow the stack.

Three adjacent decisions the compiler makes on every function follow from these : should the body be inlined, can direct self-recursion be rewritten into a loop outright, and should the LLVM tail call qualifier be stamped on the matching return f(args) ?

Inline decision

Every function is classified as one of four inline hints (None, Hint, Always, Never):

None    — emit no inline attribute; the LLVM cost model decides
Hint    — emit `inlinehint`; the optimiser should prefer inlining
Always  — worth folding: `alwaysinline` at `-O0` (inert, no pass runs) or on a declared demand, `inlinehint` where the cost model runs
Never   — emit `noinline`; the optimiser must not inline

The classifier applies an ordered rule (the Never veto is checked first):

  • A small body → Always. A body of at most 8 statements takes it without being asked. A body of 9 to 16 statements takes it only while its expanded size times the call sites past the first stays under 512; otherwise it falls to Hint. What the verdict becomes depends on the level. At -O0 no pass runs, so the verdict is emitted as alwaysinline and nothing consumes it — a record of the offer in the unoptimised module. From -O1 the cost model runs, and it knows what the statement count cannot — how many sites call the body, how hot they are, how large the caller has grown — so the same verdict is emitted as inlinehint and the model decides. Forcing it there inlines functions into callers whatever those have become, and with no InstCombine or GVN in the -O1 pipeline the guard each inlined copy re-emitted is never folded back. @inline(always) is the exception: it is a demand, and stays alwaysinline at every level.
  • A body within a wider expanded budget → Hint. The count is the body’s size after its Always callees have landed in it, up to 32 statements, which is what LLVM’s cost model will see. A body the Always gates below refused lands here too.
  • @inline(always) → Always, @inline(never) → Never. The annotation overrides the size tiers: always takes the Always verdict whatever the body measures (the two gates below still refuse it), never emits noinline.
  • Anything else → None. Larger bodies get no attribute and let the LLVM cost model decide. extern "C" and async functions are always None — they have no inlinable Axle body.
  • A body that must stay out of line → Never. A function branch_outline split out of a caller, and a function the source declares @heat(cold) or @inline(never), all carry noinline. Folding a split-out body back into its caller undoes the split; folding a cold body puts the cold code back on the hot path. This veto is checked first.

Two gates refuse Always whatever the body measures : a function that calls itself, directly or through a cycle (alwaysinline on one is an LLVM hard error), and a body that uses the arena (folding it merges two arena scopes and defeats the callee’s per-call reset). Such a function falls to Hint when its body is within the small budget; a larger one falls to None.

The decision is stamped on every function at compile time. The code emitter reads it and attaches the matching LLVM attribute — no shape inspection at emit time.

Self-tail-recursion becomes a loop

Before any tail qualifier is stamped, the compiler rewrites a function’s direct self-recursive tail calls into an in-place loop — O(depth) stack frames become O(1) by construction, not by optimiser goodwill:

fn fact(n : i64, acc : i64) : i64 {
    if (n <= 1) { return acc; }
    return fact(n - 1, acc * n);
}

is rewritten (conceptually) into:

fn fact(n : i64, acc : i64) : i64 {
    while (true) {
        if (n <= 1) { return acc; }
        let next_n = n - 1;       // new arguments evaluated first …
        let next_acc = acc * n;
        n = next_n;               // … then committed together
        acc = next_acc;
    }
}

The two-phase update is the soundness crux : fact(n - 1, acc * n) reads the old n in both arguments, so the new values are computed into temporaries before either parameter is overwritten.

The rewrite happens in the HIR, so axle build fact.axle --emit=hir shows the rewritten body. The sketch below is illustrative: the compiler chooses the names of the shadow locals and temporaries, and the numbers are not a stable format.

149: fact {
  params: [n: i64, acc: i64]
  returns: i64
  body:
    let tre.n : i64 = param#0;
    let tre.acc : i64 = param#1;
    while (true) {
      if ((local#0 <= 1)) { return local#1; }
      let tre.tmp : i64 = (local#0 - 1);    // new n, from the old n
      let tre.tmp : i64 = (local#1 * local#0);  // new acc, also from old n
      local#0 = local#2;                    // … committed only now
      local#1 = local#3;
      continue;
    }
}

By the time LLVM sees the function there is no recursion left to optimise: the body is a single loop whose induction values are plain φ nodes, a compare, and a back-edge (illustrative):

while.header:
  %tre.n   = phi i64 [ %n0, %entry ], [ %sub, %if.merge ]
  %tre.acc = phi i64 [ %acc0, %entry ], [ %mul, %if.merge ]
  %done = icmp sle i64 %tre.n, 1
  br i1 %done, label %fact.exit, label %if.merge
if.merge:
  %sub = sub i64 %tre.n, 1
  %mul = mul i64 %tre.acc, %tre.n
  br label %while.header          ; no `call`, no `ret` per turn

Why it matters is the stack. The recursive form stacks one frame per call ; the loop form reuses one frame forever:

recursion (O(depth) frames)      loop rewrite (O(1) frame)
  fact(5, 1)                       ┌─────────────────┐
    fact(4, 5)                     │ n, acc          │ ← one frame,
      fact(3, 20)                  │ updated in place│   overwritten
        fact(2, 60)                └─────────────────┘   each turn
          fact(1, 120) → 120
  deep input → stack overflow      deep input → still fine

The rewrite fires only when it is provably equivalent : the function takes no implicit receiver, every parameter can be shadowed by a plain copy on each turn (an own parameter is refused, because overwriting its shadow would leak it), the body returns on every path, and the rewritten return fact(…) sits at the function’s top level or inside plain if branches — never inside an inner loop (the inserted back-jump would target the wrong loop) or inside try / synchronized / defer (jumping back would skip finalisation). Self-calls that don’t qualify stay ordinary calls, and the tail qualifier below is all the help LLVM gets for them — that also covers mutual recursion, which the rewrite never touches.

Tail call detection

A dedicated analysis collects every return f(args) whose arguments are all by-value scalars (no pointer-shaped arguments that could alias into the caller’s frame). At every such call site the compiler stamps the LLVM tail qualifier on the emitted call instruction. The analysis recognises only the return f(args) statement form: a call that is a block’s final expression, without a return, is not tagged.

By-value-scalar means the numeric scalars (i8 / i16 / i32 / i64 / u8 / u16 / u32 / u64 / f32 / f64), plus bool, char and the unit type. A String, a pointer, an array, a Shared<T> and a class all carry an address, so each is rejected — any of them could carry a stale address into the freed caller frame.

LLVM treats tail as a permission, not a requirement. The optimiser is free to reuse the caller’s frame for the tail jump, which collapses iterative recursion into a single-frame loop. The strict musttail variant — which requires LLVM to unconditionally tail-call — is not stamped: it requires matching ABIs and stack-frame discipline the front-end does not verify, and an incorrect musttail is a verification failure that aborts compilation.

Why arg safety matters

A pointer to a caller stack slot passed through a tail call would let LLVM deallocate the slot before the jump. The callee’s first stack push then clobbers the freed bytes. Refusing the qualifier whenever any argument is pointer-shaped keeps the contract sound ; the by-value-scalar predicate is the single gate.

What you’d notice

  • A recursive function whose recursive call is the last act of every branch (fn loop_step(state) : T { ... return loop_step(next); }) runs at constant stack depth. When every parameter is shadowable, the recursion is gone before LLVM even sees it — the emitted body is a plain loop. When the rewrite doesn’t apply, the tail qualifier still lets the disassembly show a jmp to the function entry instead of a call+ret pair, and the RSP register doesn’t grow across iterations.
  • A method body that’s a one-line forwarder (fn size(self) : i32 { return self.len; }) doesn’t show up as a call in the disassembly — LLVM inlines it everywhere. The generated IR contains the field load directly at every call site. Compiling a program whose main ends in return b.size(); and running --emit=llvm bears this out : the module defines only @main, with no @…size function and no call to one — the accessor has been folded into its single field load at the use site.
  • A folded body is compiled against the arguments each site actually passes: a callee that took a stride parameter is specialised on the literal its caller holds, and a sum whose terms are constants folds away entirely. An extern "C" fn (an FFI declaration with no Axle body) is always None — there is nothing to inline — and a function that calls itself or uses the arena falls to Hint, because folding is illegal or harmful there.

Limits / Uncabled

FeatureStateDetail / workaround
Size tiers under a vetoBy designA body the compiler splits out, or one marked @heat(cold) or @inline(never), is stamped Never whatever its size.
Self-tail-recursion rewrite for mutual recursionNot builtOnly direct self-calls become loops. A mutual recursion keeps its calls and gets the tail qualifier, which LLVM may or may not act on.
Self-tail call inside a loop, try, or deferNot rewrittenTurning the return into a continue would skip the loop’s or the block’s cleanup. Restructure so the recursive call sits in a plain if branch.
tail on a non-scalar argumentNot stampedA pointer, a Shared<T> or a class argument could point into the caller’s frame once it is reused. Pass scalars, or accept the ordinary call.
tail on a final-expression callNot stampedOnly the return f(args) form is recognised.
musttailNever stampedIt needs matching ABIs and stack discipline the front end does not verify; an incorrect one would abort the build.

See also

internalsinliningtail-callsoptimization