Lesson 20.8 — Tail calls: tail-call elimination and tail-recursion elimination with accumulators¶

Techniques: tail-call elimination — a call in tail position reuses the caller's frame (Steele 1977; LLVM's tail/musttail markers and the code generator's sibling-call optimization); tail-recursion elimination — a self-call in tail position becomes a loop, and with an accumulator also calls followed by one associative operation (Burstall & Darlington 1977; LLVM tailcallelim, GCC tailr) · Pebble implements: pebble-tre, ★ with accumulator introduction (E4) · Prerequisites: SSA and phis (Ch 16); Lesson 20.3 (why a recursive call cannot be inlined) · Time: 4–6 hours

A call is in tail position if the caller returns the call's result without doing anything else. Such a call does not need a new stack frame: the caller's frame is dead the moment the call starts. Two transformations exploit this. Tail-call elimination (TCE) turns any tail call into a jump, so the callee reuses (or replaces) the frame. Tail-recursion elimination (TRE) turns a self-recursive tail call into a branch back to the function's entry — a loop — which then feeds every loop optimization of Ch 18. With an accumulator, TRE also handles the most common non-tail recursion, return n * fact(n - 1). The running example is fact and its variants from tests/ch20/lit/Inputs/equiv.c:

static unsigned fact(unsigned n) { return n <= 1 ? 1 : n * fact(n - 1); }   /* accumulator: *        */
static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }         /* plain tail call       */
static int nontail(int n) { return n == 0 ? 0 : 2 * nontail(n - 1) + 1; }  /* not a tail call       */
static int alt(int n) { return n == 0 ? 0 : n - alt(n - 1); }              /* − is not associative  */
static double fsum(const double *a, int n)                                  /* + on doubles: neither */
  { return n == 0 ? 0.0 : a[n - 1] + fsum(a, n - 1); }

1. Problem and motivation¶

Tail-call elimination¶

Steele's "Debunking the expensive procedure call myth" argued that a procedure call in tail position is a goto that passes arguments, and that compilers should compile it as one [Ste77]; Scheme made proper tail calls a language requirement. In C-like languages tail calls are an optimization: the caller's frame is popped and the call becomes a jump (jmp instead of call + ret), saving stack and a return. In LLVM the IR marks a call tail (the callee does not access the caller's stack — a promise the optimizer checks) or musttail (the front end requires the jump, e.g. for Swift or for guaranteed tail calls in C with [[clang::musttail]]), and the code generator emits a sibling call when the calling conventions and stack layouts allow it [LLVM-LangRef-Call].

Tail-recursion elimination with accumulators¶

For a self-recursive tail call the jump can target the function's own entry and the arguments can be passed in the parameters' SSA values: the recursion becomes a loop inside one frame, and — unlike a sibling call — the loop is visible to the IR optimizer. Burstall and Darlington's program transformation system derived loops from recursive definitions by generalization: introduce an accumulating parameter that carries the pending work, using the associativity of the combining operation [BD77]. LLVM's tailcallelim does both: it first marks calls tail where it can prove the callee does not use the caller's frame, then eliminates self-recursive tail calls, introducing an accumulator when exactly one associative-and-commutative operation separates the call from the return [LLVM-TRE]. GCC's tailr pass does the same on GIMPLE [GCC-Tail]. pebble-tre (E4) implements TRE with accumulators on LLVM IR produced by clang -O0 + mem2reg, including its "shared return block" shape.

2. Definitions and algorithms¶

Definition 20.8.1 (Tail position, tail call)

A call instruction \(c\) in function \(f\) is in tail position if the only thing that follows it on every path to a return of \(f\) is that return, and the return returns \(c\)'s result (or \(f\) returns void). Concretely in SSA: \(c\) is immediately followed by ret c (ret void), or by br R where \(R\) holds only phi [c, …] and a ret of that phi. A self-recursive tail call has \(\mathrm{callee}(c) = f\).

Definition 20.8.2 (Frame escape)

A stack slot (alloca) of \(f\) escapes if its address is used other than as the address operand of a load or store (possibly through GEPs): passed to a call, stored as a value, compared, converted. If no alloca escapes, no callee can read or write \(f\)'s frame; LLVM's markTails marks a call tail only if no alloca it can see escapes to it.

Definition 20.8.3 (Accumulator form)

A self-recursive call \(c\) is in accumulator form if it is followed by exactly one instruction \(a = c \oplus x\) or \(a = x \oplus c\), with \(x\) not depending on \(c\), whose only use is the return (directly or through the shared return block's phi), and \(\oplus\) is associative and commutative with an identity \(e\): integer add, mul, and, or, xor (on two's-complement integers, with wrap-around, all five are), and fadd/fmul only with the reassoc and nsz flags (floating-point addition is not associative). Identities: \(0\) for add, or, xor; \(1\) for mul; all-ones for and; \(\pm 0.0\) / \(1.0\) for fadd / fmul.

Algorithm 20.8.4 (Tail-recursion elimination with accumulator, as in pebble-tre)

Input: a function \(f\).
Output: \(f\) with its eligible self-recursive calls replaced by branches to a loop header.
Precondition: \(f\) is not varargs; it has no dynamic alloca and no escaping alloca (Definition 20.8.2), no byval/inalloca/preallocated parameter (a call passes a fresh copy; a phi would pass the caller's object itself, and a store through the parameter would modify it) and no musttail call (it must stay right before its ret, which the accumulator rewrites); the calls are not notail.
Postcondition: \(f\) computes the same function (Theorem 20.8.5); every eliminated call was in tail position or in accumulator form with one common operation \(\oplus\).
Invariant: at the loop header, with argument phis \(\bar{x}\) and accumulator phi \(acc\), the value the original call \(f(\bar{x}_0)\) returns equals \(acc \oplus f(\bar{x})\) (Lemma in Theorem 20.8.5).

function TRE(f):
    if f is varargs, has a dynamic/escaping alloca, a byval parameter or a musttail call: return
    cands ← [c : c a self-call of f in tail position, or in accumulator form]
    ⊕ ← the operation of the first accumulator-form candidate (if any);
    drop the candidates whose operation differs from ⊕
    if cands = []: return
    H ← entry block, renamed "tailrecurse";  NewEntry ← a new entry block: static allocas + br H
    for each parameter p_i: φ_i ← phi in H [p_i, NewEntry]; replace all uses of p_i by φ_i
    if ⊕ exists:
        acc ← phi in H [identity(⊕), NewEntry]
        for each return `ret v` that is not part of a candidate: replace it by `ret (acc ⊕ v)`
    for each candidate c with arguments a_1 … a_k in block B:
        add (a_i, B) to φ_i for every i
        if ⊕ exists: add (c is in accumulator form with operand x ? acc ⊕ x : acc, B) to acc
        delete c, its accumulator instruction and B's terminator (removing B from the return block's phi)
        append `br H` to B

3. Worked example¶

Tail-call elimination¶

In wrapper(int x) { return helper(x + 1, x * 2); } the call to helper is in tail position (Definition 20.8.1) and wrapper has no stack slots, so the x86-64 code generator emits the arguments in the argument registers and jmp helper (box in §7): helper returns directly to wrapper's caller. In keep(int x) { int r = helper(x, x); return r + 1; } the + 1 follows the call: not a tail call, and not an accumulator either — keep is not recursive.

Tail-recursion elimination with accumulators¶

Algorithm 20.8.4 on the clang -O0 + mem2reg form of fact:

define i32 @fact(i32 %n) {
entry:
  %cmp = icmp ule i32 %n, 1
  br i1 %cmp, label %if.then, label %if.end
if.then:
  br label %return
if.end:
  %sub = sub i32 %n, 1
  %call = call i32 @fact(i32 %sub)
  %mul = mul i32 %n, %call
  br label %return
return:
  %retval.0 = phi i32 [ 1, %if.then ], [ %mul, %if.end ]
  ret i32 %retval.0
}

Candidates: %call is followed by %mul = mul i32 %n, %call whose only use is the return phi, and mul is associative and commutative with identity 1: accumulator form, \(\oplus = \mathrm{mul}\), \(x = \%n\).
entry becomes tailrecurse; the new entry branches to it; %n.tr = phi [%n, entry] replaces %n.
%accumulator.tr = phi [1, entry]; the remaining return (return's ret) becomes ret (acc * %retval.0).
In if.end: %n.tr gets [%sub, if.end]; %accumulator.next = mul %accumulator.tr, %n.tr and the accumulator phi gets [%accumulator.next, if.end]; the call, %mul and br label %return are deleted, br label %tailrecurse appended; return's phi loses its if.end entry and folds to 1.

Execution of fact(4) before and after — the loop state satisfies the invariant \(acc \cdot \mathrm{fact}(n) = \mathrm{fact}(4)\) at every visit of the header:

visit of `tailrecurse`	`n.tr`	`accumulator.tr`	\(acc \cdot \mathrm{fact}(n)\)
1	4	1	1 · 24 = 24
2	3	4	4 · 6 = 24
3	2	12	12 · 2 = 24
4	1	24	24 · 1 = 24 → base case: return 24 · 1 = 24

gcd needs no accumulator (plain tail call); nontail's call is followed by mul and add — not accumulator form (the pending work 2·r + 1 is not one associative operation), so it is kept; alt uses sub — not associative; fsum uses fadd without reassoc. tests/ch20/lit/tre.ll and tre-negative.ll check exactly these five cases, and the escaping-alloca case of Definition 20.8.2.

4. Invariants and correctness¶

Theorem 20.8.5 (TRE with an accumulator is correct)

Let \(f\) satisfy Algorithm 20.8.4's preconditions. Write each execution path of \(f\) as ending either in a base return ret b(\bar{x}), in a plain tail call ret f(\bar{g}(\bar{x})), or in accumulator form ret h(\bar{x}) ⊕ f(\bar{g}(\bar{x})) (or f(…) ⊕ h(…)), with \(\oplus\) associative and commutative with identity \(e\). Then the transformed \(f\) returns the same value as the original on every input on which the original terminates, and does not terminate when the original does not.

Proof

Invariant. Let \(\bar{x}_0\) be the original arguments. Claim: every time the header is entered with \((\bar{x}, acc)\), \(f(\bar{x}_0) = acc \oplus f(\bar{x})\) (where \(f\) denotes the original function). Initially \(acc = e\) and \(\bar{x} = \bar{x}_0\), and \(e \oplus y = y\). Suppose the claim holds and the body takes a path. (i) Plain tail call: the next state is \((\bar{g}(\bar{x}), acc)\), and \(f(\bar{x}) = f(\bar{g}(\bar{x}))\), so \(acc \oplus f(\bar{x}) = acc \oplus f(\bar{g}(\bar{x}))\). (ii) Accumulator form with \(f(\bar{x}) = h \oplus f(\bar{g}(\bar{x}))\) (the case \(f(\bar{g}(\bar{x})) \oplus h\) reduces to it by commutativity): the next state is \((\bar{g}(\bar{x}), acc \oplus h)\), and \(acc \oplus f(\bar{x}) = acc \oplus (h \oplus f(\bar{g}(\bar{x}))) = (acc \oplus h) \oplus f(\bar{g}(\bar{x}))\) by associativity. (iii) Base return: the transformed code returns \(acc \oplus b(\bar{x}) = acc \oplus f(\bar{x}) = f(\bar{x}_0)\).

Same values. The arguments are passed through phis instead of a call — the same values, because no parameter is byval (for which a call passes a copy, not the pointer); since no alloca escapes and static allocas are allocated once in the new entry, the loop body reads only its SSA values, its own stack slots (which no pending activation needs — none exists) and global memory, exactly as the recursive activation did; the operations on the path are executed in the same order except the accumulating ones, which is what the invariant accounts for.

Termination. Each loop iteration corresponds to one recursive activation of the original, so the loop runs as many iterations as the recursion is deep; a non-terminating recursion (without stack overflow) becomes a non-terminating loop. (The transformed program does not overflow the stack where the original would: a difference only in resource exhaustion, which the language semantics does not define as behavior.)

Where it breaks. Without associativity step (ii) fails: alt computes \(n - (n-1 - (\dots))\) but an accumulator would compute \(((n - (n-1)) - \dots)\). Without commutativity the case \(f(\dots) \oplus h\) needs the accumulator on the other side (a variant). Poison-generating flags (nsw) are dropped because the intermediate values differ.

Theorem 20.8.6 (Sibling-call optimization is correct when no frame escapes)

If a call \(c\) is in tail position in \(f\), no stack slot of \(f\) escapes to \(c\) (Definition 20.8.2), and the callee's stack arguments fit in \(f\)'s incoming argument area with a compatible calling convention, then replacing call; ret by deallocating \(f\)'s frame and jumping to the callee preserves behavior.

Proof

After \(c\) nothing of \(f\) executes except returning \(c\)'s result, so \(f\)'s frame is dead at the call except for what the callee might read through pointers — and no pointer into the frame escaped to it. The callee receives the same arguments (in registers, or in the reused argument area) and returns to \(f\)'s return address, delivering its result where \(f\)'s caller expects \(f\)'s result: the observable sequence of operations is the same, minus one call/return pair.

Floating point: not associative

fsum sums a[n-1] + (a[n-2] + (… + 0.0)); an accumulator sums ((−0.0 + a[n-1]) + a[n-2]) + … — a different order. For a = {1.0, 1e16, -1e16} the recursion returns -1e16 + (1e16 + (1.0 + 0.0)) = 0.0 (the 1.0 is lost when added to 1e16), the accumulator returns (-1e16 + 1e16) + 1.0 = 1.0. Only with reassoc (e.g. -ffast-math) may the compiler treat fadd as associative.

5. Complexity¶

\(n\) = instructions of \(f\), \(k\) = candidates.

Technique	Time (worst)	Time (typical)	Space	Justification
Tail-call elimination (sibling calls)	\(O(n)\) escape scan + \(O(1)\) per call	linear; the code generator checks conventions per call	none	one scan of the allocas' uses; per-call ABI checks
TRE with accumulator	\(O(n + k \cdot \lvert\text{params}\rvert)\)	linear	one phi per parameter + one accumulator	candidate search looks at one instruction after each self-call; each elimination adds phi entries

The program's complexity changes more than the compiler's: stack space drops from \(\Theta(d)\) frames for recursion depth \(d\) to \(O(1)\), and the time per iteration loses a call and a return.

Pathological family. Tree recursion fib(n) = fib(n-1) + fib(n-2) has two recursive calls on one path; at most one of them could be in accumulator form (the other's result is an operand of the add that is not the accumulating one), so TRE turns it into a loop with one recursive call left in the body — still \(\Theta(\varphi^n)\) calls, now \(\Theta(n)\) fewer frames at a time. For TCE, a frame with an escaping alloca (a local whose address is passed down) blocks every tail call in the function: one &x disables it all.

At scale. On tests/ch20/lit/Inputs/equiv.c (after clang -O1 -Xclang -disable-llvm-passes + sroa), pebble-tre removes the recursion from fact, gcd, tri and sum_acc and leaves nontail and alt (no accumulator form), fsum (strict fadd) and depth (its local array's address is passed down) alone — and also xorsum: C's integer promotions put a zext after the call and a trunc before the ret, so the call is not in tail position until InstCombine removes the pair; function(instcombine,simplifycfg,pebble-tre) then eliminates it. Phase ordering matters even for a pass this small.

Order-preserving accumulators: for an associative but non-commutative \(\oplus\) (string concatenation, matrix product), keep the accumulator on the correct side (prepend vs append) — Burstall and Darlington's generalization handles it [BD77]; LLVM requires commutativity to keep the pass simple.
Returning a phi of the accumulator (LLVM's RetPN/RetKnownPN): handles functions that return the call's result on some paths and a constant on others without a separate accumulator.
Guaranteed tail calls (musttail, Swift's swifttailcc, [[clang::musttail]]): the front end requires TCE; the backend fails compilation if it cannot comply — needed for interpreters written as tail-calling handlers.
Mutual tail recursion: is_even/is_odd call each other in tail position; TRE (self-calls only) does nothing, sibling-call optimization turns each call into a jump, and inlining one into the other exposes a self-recursive tail call.
Tail-recursion modulo cons (functional languages): allocate the result cell before the call and pass a destination pointer — the list-building analogue of accumulators.

7. In real compilers¶

Tail-call elimination¶

LLVM: calls are marked tail by TailRecursionEliminator::markTails (escape analysis of allocas, AllocaDerivedValueTracker) in llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp [LLVM-TRE]; the code generators decide sibling calls (X86TargetLowering::IsEligibleForTailCallOptimization, AArch64TargetLowering::isEligibleForTailCallOptimization). GCC: tree-tailcall.cc — find_tail_calls marks tail calls, the RTL expander emits sibcalls [GCC-Tail].

A sibling call on x86-64

Reproduce (clang 23.1.2):

cat > sib.c <<'EOF'
int helper(int, int);
int wrapper(int x) { return helper(x + 1, x * 2); }
int keep(int x) { int r = helper(x, x); return r + 1; }
EOF
clang-23 -O2 -S sib.c -o - | grep -vE '^\s*\.(cfi|p2align|type|size|file|ident|section|text|addrsig|globl)|^#|^\.Lfunc'

Output:

    .att_syntax
    .prefalign  4, .Lfunc_end0, nop
wrapper:                                # @wrapper
                                        # kill: def $edi killed $edi def $rdi
    leal    1(%rdi), %eax
    leal    (%rdi,%rdi), %esi
    movl    %eax, %edi
    jmp helper@PLT                      # TAILCALL
                                        # -- End function
    .prefalign  4, .Lfunc_end1, nop
keep:                                   # @keep
    pushq   %rax
    movl    %edi, %esi
    callq   helper@PLT
    incl    %eax
    popq    %rcx
    retq
                                        # -- End function

What to notice: wrapper sets up helper's arguments and jumps (# TAILCALL): no frame, no return to wrapper (Theorem 20.8.6). keep must add 1 after the call, so it calls, keeps a frame (the pushq aligns the stack) and returns.

Tail-recursion elimination with accumulators¶

LLVM: TailRecursionEliminator::eliminate, findTRECandidate, eliminateCall and canTransformAccumulatorRecursion (the associative-and-commutative test of Definition 20.8.3) in llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp; canTRE rejects dynamic allocas [LLVM-TRE]. GCC: tree-tailcall.cc — process_assignment recognizes the accumulating +/* (the add_acc/mult_acc of the dump), eliminate_tail_call builds the loop [GCC-Tail].

LLVM tailcallelim and GCC tailr on fact

Reproduce (clang 23.1.2, opt 23.1.2, gcc 14.2.0):

cat > fact.c <<'EOF'
unsigned fact(unsigned n) {
  if (n <= 1)
    return 1;
  return n * fact(n - 1);
}
EOF
clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm fact.c -o - | opt -passes=sroa,simplifycfg -S -o fact.ll
opt -passes=tailcallelim -S fact.ll | sed -n '/^define/,/^}/p'
gcc-14 -O2 -fdump-tree-tailr1-details -c fact.c
grep -E 'Eliminated|mult_acc|return' fact.c.*.tailr1

Output:

define dso_local i32 @fact(i32 noundef %n) #0 {
entry:
  br label %tailrecurse

tailrecurse:                                      ; preds = %if.end, %entry
  %accumulator.tr = phi i32 [ 1, %entry ], [ %mul, %if.end ]
  %n.tr = phi i32 [ %n, %entry ], [ %sub, %if.end ]
  %cmp = icmp ule i32 %n.tr, 1
  br i1 %cmp, label %return, label %if.end

if.end:                                           ; preds = %tailrecurse
  %sub = sub i32 %n.tr, 1
  %mul = mul i32 %n.tr, %accumulator.tr
  br label %tailrecurse

return:                                           ; preds = %tailrecurse
  %accumulator.ret.tr = mul i32 1, %accumulator.tr
  ret i32 %accumulator.ret.tr
}
Eliminated tail recursion in bb 4 : _2 = fact (_1);
Updating SSA information for statement return mul_tmp_12;
gimple_simplified to mul_tmp_12 = mult_acc_10;
  unsigned int mult_acc_10;
  unsigned int mult_acc_11;
  # mult_acc_10 = PHI <1(0), mult_acc_11(4)>
  // predicted unlikely by early return (on trees) predictor.
  mul_tmp_12 = mult_acc_10;
  return mul_tmp_12;
  mult_acc_11 = mult_acc_10 * n_5;

What to notice: both compilers build the loop of §3: an accumulator phi starting at the identity 1, one multiplication per iteration, and the base case's 1 multiplied by the accumulator (LLVM: mul i32 1, %accumulator.tr, which InstCombine folds). LLVM reuses the original %mul as the accumulator's update (with its nsw dropped); pebble-tre creates %accumulator.next instead — the same computation.

Find where LLVM does it. Open llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp and find the function that decides whether the instruction after a recursive call can be turned into an accumulator. What two properties of the instruction does it test first? (Quiz llvm-where-tre-accumulator.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Tail-call elimination	Any call in tail position whose frame does not escape; ABI permitting	\(O(n)\) · in the backend	`# TAILCALL` in assembly; `musttail` makes failure a compile error	Medium (per-target ABI checks)	Every C/C++ compiler at `-O2`; mandatory in Scheme, Swift `swifttailcc`
Tail-recursion elimination with accumulators	Self-recursion in tail position, or followed by one associative-commutative op	\(O(n)\) · cheap	A loop the IR optimizer can transform further	Low–medium (phis, the accumulator, return rewriting)	LLVM `tailcallelim` (in `default<O2>`), GCC `tailr`, `pebble-tre`

Choose TCE when calls in tail position are frequent (wrappers, dispatch, continuation-passing, interpreters) — it saves stack everywhere and needs only the escape check. Choose TRE when self-recursion expresses a loop (the common case in functional-style code and generated code): the loop then gets LICM, unrolling and vectorization; add the accumulator when the recursion combines results with +, *, &, |, ^.

9. Assessment¶

Quiz (./course quiz 20): tce-position, tce-escape (tag tce); tre-accumulator-trace, tre-must-not, llvm-where-tre-accumulator (tag tre).
Drill: none: TRE's decision is local to one instruction after the call (the quiz's tre-must-not asks it for five functions), and its execution is the trace of §3, which the quiz question tre-accumulator-trace asks for another input.
Flashcards: tags tce, tre.
Exercises: E4 pebble-tre.

References¶

See the chapter references.

Lesson 20.8 — Tail calls: tail-call elimination and tail-recursion elimination with accumulators¶

1. Problem and motivation¶

Tail-call elimination¶

Tail-recursion elimination with accumulators¶

2. Definitions and algorithms¶

3. Worked example¶

Tail-call elimination¶

Tail-recursion elimination with accumulators¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

7. In real compilers¶

Tail-call elimination¶

Tail-recursion elimination with accumulators¶

8. Comparison¶

9. Assessment¶

References¶