Register allocation

Deep dive

How it works

Parts:

• liveness sets — per block live-in/live-out bitsets from backward dataflow
• live ranges — per vreg, one interval or a list of ranges with holes
• allocator — linear scan, greedy splitting or graph coloring; assigns a physical register or spills
• spill slots and moves — stack slots, plus copies inserted at split points and block edges
• constraints — fixed registers (calling convention, instruction operands) and register classes

Operations:

1. Liveness. A virtual register is live at a point if some path from there reaches a use without a redefinition. Backward dataflow on the CFG: live_in(b) = use(b) ∪ (live_out(b) − def(b)), live_out(b) = ∪ live_in(succ). On SSA phi uses count at the end of the predecessor.
2. Live intervals. Number instructions in a linear block order. The interval of a vreg is [first def, last use) (one range, with holes ignored, in the simplest form); with lifetime holes a vreg gets a list of ranges.
3. Linear scan (Poletto-Sarkar). Sort intervals by start. Keep an active set sorted by end. For each new interval: expire actives that ended (free their register); if a register is free, take it; otherwise spill the interval (new or active) that ends last. One pass, no graph.
4. Second-chance binpacking / interval splitting (Traub et al., Wimmer-Mossenbock). Instead of spilling a whole interval, split it at a position: the first part stays in a register, the rest is spilled or gets another register, with a move inserted at the split (and at control-flow edges where the two sides disagree). HotSpot C1 and V8's linear-scan allocator split intervals this way, with splits placed outside loops and use-position hints so the interval is reloaded just before its next use.
5. Graph coloring (Chaitin-Briggs). Build: one node per vreg, an edge between vregs live together. Simplify: remove nodes with degree < k onto a stack. If none exists, pick a spill candidate by cost/degree and push it optimistically (Briggs). Select: pop and assign a color unused by colored neighbours; a node that finds none is spilled for real, spill code is inserted and the whole allocation restarts.
6. Coalescing. A mov a, b disappears when a and b get the same register. Aggressive coalescing (Chaitin) can make the graph uncolorable; conservative rules (Briggs: merged node has < k neighbours of degree ≥ k; George: every high-degree neighbour of one already interferes with the other) never turn a colorable graph uncolorable. Iterated register coalescing interleaves them with simplify.
7. SSA-based allocation. For a program in SSA form with strict dominance (a use is dominated by its def), the interference graph is chordal, so its chromatic number equals the maximum clique, i.e. the maximum register pressure max-live. So: (a) lower pressure to k everywhere by spilling or splitting, (b) color by walking the dominator tree in order, each def takes a free register, no backtracking, (c) lower phis to parallel moves.
8. Production allocators. LLVM greedy: live ranges in a priority queue (large ranges first); try to assign, else evict a cheaper range, else split the range (around loops, around uses, by region), else spill. Cranelift's regalloc2 is a backtracking allocator ported from IonMonkey: live ranges are grouped into bundles that are assigned, evicted, split and merged by the same principle, with a checker and fuzzing harnesses to validate output.

vregs ──liveness──► live ranges ──► allocator ──► assign reg
                                       │  └──► split range ──► moves at split points
                                       └──► spill ──► stack slot + load/store
              result: physical registers + spill code, ready for emission

Code

Poletto-Sarkar linear scan with whole-interval spilling, plus a checker asserting that overlapping intervals never share a register or a stack slot. Compiled and run with a randomized stress test.

#[derive(Clone, Copy, Debug)]
pub struct Interval { pub vreg: usize, pub start: u32, pub end: u32 } // live on [start, end)

#[derive(Clone, Copy, Debug, PartialEq)]
pub enum Loc { Reg(u8), Slot(u32) }

/// Poletto-Sarkar linear scan: one pass over intervals sorted by start.
/// On pressure, spill whichever of {new, active} ends last.
pub fn linear_scan(intervals: &[Interval], num_regs: u8) -> Vec<Loc> {
    let mut order: Vec<usize> = (0..intervals.len()).collect();
    order.sort_by_key(|&i| intervals[i].start);
    let mut loc = vec![Loc::Slot(0); intervals.len()];
    let mut free: Vec<u8> = (0..num_regs).rev().collect();
    let mut active: Vec<usize> = Vec::new(); // sorted by end ascending
    let mut slots = 0u32;
    for &i in &order {
        let cur = intervals[i];
        // expire: intervals that ended at or before cur.start release their register
        while let Some(&a) = active.first() {
            if intervals[a].end > cur.start { break; }
            if let Loc::Reg(r) = loc[a] { free.push(r); }
            active.remove(0);
        }
        if let Some(r) = free.pop() {
            loc[i] = Loc::Reg(r);
        } else {
            let last = *active.last().unwrap(); // active interval with the furthest end
            if intervals[last].end > cur.end {
                loc[i] = loc[last];                 // steal its register ...
                loc[last] = Loc::Slot(slots);       // ... and spill it for its whole life
                active.pop();
            } else {
                loc[i] = Loc::Slot(slots);
                slots += 1;
                continue;
            }
            slots += 1;
        }
        let pos = active.partition_point(|&a| intervals[a].end <= cur.end);
        active.insert(pos, i);
    }
    loc
}

fn check(intervals: &[Interval], loc: &[Loc], num_regs: u8) {
    for i in 0..intervals.len() {
        for j in i + 1..intervals.len() {
            let (a, b) = (intervals[i], intervals[j]);
            let overlap = a.start < b.end && b.start < a.end;
            if let (Loc::Reg(x), Loc::Reg(y)) = (loc[i], loc[j]) {
                assert!(!(overlap && x == y), "{a:?} and {b:?} share r{x}");
            }
            if let (Loc::Slot(x), Loc::Slot(y)) = (loc[i], loc[j]) {
                assert!(!(overlap && x == y), "{a:?} and {b:?} share slot {x}");
            }
        }
        if let Loc::Reg(r) = loc[i] { assert!(r < num_regs); }
    }
}

#[test]
fn no_overlap_shares_a_register() {
    let iv = |vreg, start, end| Interval { vreg, start, end };
    let v = vec![iv(0, 0, 10), iv(1, 1, 4), iv(2, 2, 12), iv(3, 3, 5), iv(4, 6, 8), iv(5, 9, 11)];
    let loc = linear_scan(&v, 2);
    check(&v, &loc, 2);
}

Complexity and constants

• Liveness: iterative dataflow, a few passes over the CFG in reverse postorder; bitset per block of vregs/64 words, so cost scales with blocks x vregs / 64.
• Linear scan: sort n intervals O(n log n), then each interval does O(1) expiry (amortized) plus O(log k) insertion into active (size <= k).
• Graph coloring: the interference graph can be quadratic in vregs in the worst case; the adjacency bit matrix costs n^2/8 bytes, so large functions need sparse adjacency lists too. Each spill round repeats build and color.
• Cost drivers: cache misses walking the graph/adjacency, number of vregs, number of rounds, and number of spill/reload instructions added (each is a memory op in the output).

Efficiency

• Cost: compile-time bound by memory access over liveness sets and the graph; runtime effect is the count of spill loads/stores and moves executed, weighted by block frequency. Concrete: regalloc2's author reports that its rework improved overall Cranelift compile time by about 20% (compile time was dominated by register allocation) and generated code by up to 10-20% on register-pressure-bound Wasmtime benchmarks (cfallin.org post below).
• Levers:
  • Linear scan instead of graph coloring — avoids building the graph; no graph to build or rebuild per spill round (Poletto-Sarkar) — JIT, large functions.
  • Bundles / coalescing live ranges up front — fewer ranges to process and fewer moves (regalloc2 design overview) — backtracking allocators.
  • Spill-weight by block frequency or loop depth — keeps reloads out of hot loops (LLVM CodeGen docs) — whenever profile or loop info exists.
  • Dense bitsets for liveness, one arena for ranges — fewer cache misses, no per-node allocation — always.
  • Splitting outside loops, with use hints — cheaper than whole-interval spills — interval-splitting allocators.
• Naive → standard → state of the art: spill everything to the stack, load/store around each use · trivial compile time, slow code (every use is a memory op) → linear scan with single ranges and whole-interval spills · near-linear time, moderate code → splitting allocator with bundles, hints and frequency-weighted costs (LLVM greedy, regalloc2) · more time, best code.

Implementation notes

• Pre-color fixed registers: ABI argument/return registers and clobbers at calls (calling conventions) become fixed intervals or constraints; instructions with two-address or fixed-register operands (x86 div, shifts by cl) add constraints the allocator must honour.
• Keep intervals in a flat sorted array and active in a small Vec; k is tiny, so no heap.
• Handle lifetime holes: a vreg with ranges [0,3) [8,12) can give its register away during the hole; single-range intervals waste it.
• Rematerialize cheap values (constants, frame addresses) instead of spilling them: recompute at the use.
• Parallel moves at block edges and phis need cycle breaking (scratch register or swap).
• Scheduling before allocation can raise pressure (instruction scheduling); clean leftover moves with peephole.
• Verify with a separate checker over the output (regalloc2 ships one).

Pitfalls

• Ignoring that a call clobbers caller-saved registers: every interval crossing a call must sit in a callee-saved register or be split around it.
• Aggressive coalescing that makes the graph uncolorable and forces new spills.
• Spilling by "longest interval" ignoring loop depth: reloads inside an inner loop.
• Wrong liveness at phis and loop back edges: values live around the loop are dropped early.
• Quadratic interference matrices on huge generated functions: fall back to linear scan.
• Mixing half-open and closed ranges: an operand dying at instruction i and a result born at i may share a register only if the instruction reads before it writes.

Variants and alternatives

In production

• Static compilers: LLVM (greedy at -O1+ and -O2, fast allocator at -O0), Cranelift/Wasmtime (regalloc2, post), GCC IRA/LRA.
• JITs in browsers and VMs: V8 TurboFan has a LinearScanAllocator (source); HotSpot C1 uses linear scan and C2 graph coloring; SpiderMonkey IonMonkey uses a backtracking allocator.
• GPU compilers: registers are partitioned among concurrent threads, so register pressure lowers occupancy and the CUDA guide shows -maxrregcount and launch bounds to cap it (guide); the AMDGPU back end exposes occupancy bounds (docs).
• Databases: PostgreSQL's JIT for expressions and tuple deforming generates code through LLVM, so LLVM's allocator runs on it (docs).

Implementations

Sources

• Massimiliano Poletto, Vivek Sarkar, Linear scan register allocation, ACM TOPLAS 1999. paper
• Omri Traub, Glenn Holloway, Michael D. Smith, Quality and speed in linear-scan register allocation, PLDI 1998. paper
• Christian Wimmer, Hanspeter Mossenbock, Optimized interval splitting in a linear scan register allocator, VEE 2005. paper
• Christian Wimmer, Michael Franz, Linear scan register allocation on SSA form, CGO 2010. paper
• Gregory J. Chaitin et al., Register allocation via coloring, Computer Languages 1981. paper
• Preston Briggs, Keith D. Cooper, Linda Torczon, Improvements to graph coloring register allocation, ACM TOPLAS 1994. paper
• Lal George, Andrew W. Appel, Iterated register coalescing, ACM TOPLAS 1996. paper
• Sebastian Hack, Daniel Grund, Gerhard Goos, Register allocation for programs in SSA-form, CC 2006. paper
• Chris Fallin, Cranelift's new register allocator (regalloc2), 2022. post · code
• LLVM, The LLVM Target-Independent Code Generator. docs