Lab 22 · Four register allocators behind one checker¶

Goal¶

Implement four register allocators for the same problem and compare them under one independent checker, one rewriter that runs your assignment, and one set of measurements:

E0 Belady's MIN on a reference string (Lesson 22.2), the warm-up;
E1 local allocation by furthest next use (Lesson 22.2);
E2 Chaitin–Briggs graph colouring with iterated register coalescing (Lessons 22.3–22.4);
E3 Poletto–Sarkar linear scan (Lesson 22.5), and ★ E3★ linear scan that packs into lifetime holes;
E4 SSA-based allocation: spill until the pressure fits, then colour in dominance order (Lesson 22.6).

The "virtual registers" are the SSA values of an LLVM IR function after mem2reg: every argument and every instruction with a result. The "machine" is the uniform machine of Definition 22.1.1 with two classes. You design every data structure (value numbering, liveness use, interference graphs, intervals, worklists); the tests only call the six functions of the contract.

Machine model¶

Two register classes (RegClass): FPR for float/double values, GPR for everything else (integers including i1, pointers). Values of different classes never compete.
Class \(C\) has registers \(0, \dots, K_C - 1\) (MachineModel::K). The highest CalleeSaved[C] of them are callee-saved; the others are caller-saved and are clobbered by every clobbering call (isClobberingCall: any call except an intrinsic).
A value either has one register for its whole lifetime or is spilled (Location::spill()): it then lives in its own stack slot, is stored after its definition and reloaded before each use through a scratch register that is not one of the \(K\) (the model of [PS99] and of Lesson 22.1). So spilling a value never needs a register, and spill-everywhere never changes the other values' liveness.
Phis are parallel copies on the incoming edges (Definition 22.1.2): a phi and an incoming value in different locations cost a copy on that edge; in the same register, nothing.

Requirements¶

Validity (all allocators; checked by checkAssignment, Lesson 22.1):

R1. The assignment has an entry for every value that needsLocation accepts (arguments and non-void instructions) and for nothing else, including values in unreachable blocks.
R2. Every register number is below \(K\) of the value's class.
R3. Two values of the same class that interfere (Definition 22.1.5, over the definition points of Definition 22.1.4: function entry, block entries with their phis and live-in values, each instruction with a result) are never in the same register.
R4. A value that is live across a clobbering call (live just after it and not defined by it) is spilled or in a callee-saved register.

Each allocator's policy (what the tests and the measurements expect):

R5 (E1, allocateLocal). A value that is live across a block boundary (live-out of some block, or used in a block other than its own, including as a phi operand) is spilled. Inside a block, values get registers in instruction order; when no allowed register is free, the value whose next use is furthest away is spilled (Algorithm 22.2.4). A value live across a call may only use callee-saved registers.
R6 (E2, allocateChaitinBriggs). Build the interference graph per class, treat phi copies as moves, and run iterated register coalescing (Algorithm 22.4.6): simplify, coalesce with a conservative test (Briggs's or George's; either is safe), freeze, potential spill (by cost/degree with the \(10^{\text{depth}}\) costs of Definition 22.3.2), select optimistically. Values live across a call must end up callee-saved: pre-coloured nodes for the caller-saved registers that interfere with every call-crossing value are one way. Actual spills leave the graph and the algorithm is repeated until nothing spills.
R7 (E3, allocateLinearScan). Number the instructions in one linear order of the blocks (Definition 22.1.8: instruction \(j\) reads at slot \(2j\) and writes at \(2j+1\)); give each value one interval, the hull of its live slots; scan by increasing start and spill, on a conflict, the interval whose end is furthest (Algorithm 22.5.3). An interval that covers a call slot may only take a callee-saved register.
R8 (★ E3★, allocateLinearScanHoles). As R7, but an interval is its list of live segments, and a register is free for it if no interval already in that register overlaps any of its segments (the packing half of second-chance binpacking, Algorithm 22.5.7).
R9 (E4 spilling, allocateSSA). Before colouring, spill values until, at every definition point, the values of each class that are defined there or live just after it number at most \(K\), and the values live across each call number at most the callee-saved count (Definition 22.6.8, Algorithm 22.6.9). You choose the heuristic; the lesson's is "most over-full points per unit of spill cost".
R10 (E4 colouring). Colour the remaining values greedily, visiting blocks in dominator-tree preorder (Algorithm 22.6.6): at block entry the colours of live-in values are taken, then phis, then each result after releasing the colours of operands that die at that instruction. For call-free functions with \(K \ge \mathrm{MaxLive}\) this must spill nothing and use at most \(\mathrm{MaxLive}\) registers per class (Theorem 22.6.7). Prefer a phi's colour for its operands (and vice versa) when it is free: the tests expect the back-edge phi moves of the running example to vanish.
R11 (E0, beladyMisses). \(K\) registers, empty at the start; a reference to a value not in a register is a miss; with all \(K\) full, evict the value whose next reference is furthest in the future (never referenced again = infinitely far; ties: the smallest value). Return the number of misses; if Evictions is non-null, resize it to the number of references and store the evicted value at each step, or \(-1\).

Robustness. Every allocator must return a valid assignment for any supported function (unsupportedReason(F) empty) and any model with \(K_C \ge 1\) and at most \(K_C\) callee-saved registers, including \(K = 1\) and functions with calls where no register is callee-saved. The contract returns plain values: never abort on valid input.

Complexity targets. E0: \(O(m \log K)\) or \(O(mK)\) for \(m\) references. E1, E3, E3★: near-linear in the function size. E2: polynomial (the worklist algorithm is \(O(n \cdot e)\) per round in the worst case). E4: polynomial. ch22-compare over 414 functions and four register counts should finish in seconds.

The contract¶

include/regalloc/Allocate.h declares the six functions (beladyMisses, allocateLocal, allocateChaitinBriggs, allocateLinearScan, allocateLinearScanHoles, allocateSSA) and the types RegClass, MachineModel, Location, Assignment (DenseMap<const Value *, Location>). src/Stub.cpp defines each with a PEBBLE_TODO("ch22", …) naming its exercise. Your code goes anywhere under src/; every *.cpp there is compiled. For liveness, use the Chapter 14 contract pebble::dataflow::computeLiveness (pebble/Analysis/Liveness.h); configure with -DPEBBLE_USE_SOLUTION=dataflow if you skipped Chapter 14.

Command-line contract¶

build/linux/bin/ch22-regalloc FILE.ll [--method=local|irc|ls|ls-holes|ssa] [--gpr=K] [--fpr=K] \
    [--gpr-callee-saved=C] [--fpr-callee-saved=C] [--function=NAME] [--print] [--metrics] \
    [--no-check] [--rewrite -o OUT.ll]
build/linux/bin/ch22-compare [FILE.ll ...] [--random=N] [--callee-saved=C] [--quick]

ch22-regalloc allocates every supported function (default: --method=ssa, 4 registers per class, none callee-saved), prints @f: valid or the checker's messages (one per violation, each starting with R1–R4), with --print the location of every value (%a -> r2, %b -> spill), with --metrics one line of measurements, and with --rewrite a module in which each allocated function is replaced by its rewritten copy. Errors: an unknown method, \(K = 0\) or more callee-saved registers than \(K\), and a missing --function exit non-zero with error: ….

Input¶

inputs/running.ll: the chapter's running example (@run: the loop of Lesson 22.1 with values a, i, s, c, t, u, s2, i2, r; MaxLive 4) and a @main that prints its results.
inputs/corpus.c / corpus.ll: 14 functions (gcd, fib, recursive fact, the 14-accumulator loop pressure with a call, across_calls, the double-precision horner and dmix, bubble, classify, many_args, swapper, nested, the hash mix) and main, which prints one checksum per function; regen.sh regenerates the .ll with clang-23 (triple and CPU attributes removed so that lli runs it anywhere).
Random terminating programs (randomProgram): i64 @f(i64, i64) with if/else and counted loops over a few variables, promoted to SSA, optionally with doubles and calls to @h.

A function is supported if unsupportedReason is empty: scalars of at most 64 bits, pointers, float/double; no invoke, callbr, landingpad, token values or indirectbr.

Provided infrastructure¶

provided/ (library pebble_ch22_infra, header include/regalloc/Infra.h) is not the learning objective:

needsLocation, regClassOf, isClobberingCall, unsupportedReason — the value model;
checkAssignment — the independent checker of R1–R4, with its own liveness so that it judges your code independently of your Chapter 14 liveness;
maxLive, hasCalls, measure — the measurements below;
rewriteWithAssignment — a copy of the function that runs through the assignment: every register is a stack slot of a "register file", every spilled value has its own slot, operands are loaded right before each use and results stored right after each definition, phis become parallel copies on the edges (critical edges are split), and after every clobbering call all caller-saved registers are overwritten with 0x7EADBEEFDEADBEEF. A valid assignment preserves the function's behaviour (Theorem 22.1.14); an invalid one usually computes garbage;
randomProgram, loadModule.

What the tests check¶

Test	What it asserts
`ch22.Valid/Alloc.CorpusIsValid/*` (Local, ChaitinBriggs, LinearScan, SSA)	`checkAssignment` reports nothing for every function of the corpus and the running example, \(K \in \{1, 2, 3, 4, 6, 16\}\) in both classes, with 0, 1, \(K/2\) and \(K\) callee-saved registers
`ch22.Valid/Alloc.RandomProgramsIntegers/`, `…WithDoubles/`	60 integer and 40 mixed random programs, most with calls: for \(K \in \{2, 3, 5\}\) and 0 or 1 callee-saved registers the assignment is valid and the rewritten copy returns what the original returns on four inputs (ORC LLJIT)
`ch22.Valid/Alloc.SpillsWhenKBelowMaxLive/*`	with \(K = \mathrm{MaxLive} - 1\) every allocator spills at least one value on every corpus function
`ch22.SSAOptimal.NoSpillAtMaxLive`	R10: E4 spills nothing and uses at most MaxLive registers per class when \(K = \mathrm{MaxLive}\) (call-free functions; at least 60 checked)
`ch22.RunningExample.SpillsAndColours`	MaxLive 4; every allocator spills at \(K = 3\); E4 spills exactly one value at \(K = 3\), none at \(K = 4\) and leaves one phi move (weight 1, the entry copy `s ← a`, which is constrained because `a` and `s` interfere); E2 at \(K = 4\): no spill, one move of weight 1; E1 at \(K = 4\) spills at least 5 values
`ch22.Quality.GlobalAllocatorsBeatLocal`	on the corpus with \(K \in \{4, 8\}\) (half callee-saved): E2, E3 and E4 each have a smaller weighted spill cost than E1, and E2 leaves no more weighted moves than E3
`ch22.Checker.*`	starting from your E4 assignment of the running example, the provided checker catches corrupted assignments (R1, R2, R3, R4) and the rewriter makes them compute wrong results (tests the infrastructure; passes once E4 does)
`ch22.Checker.CatchesEveryKindOfConflict`	on a small function with dead phis, a dead definition and phi-only uses, the checker flags hand-corrupted assignments at every kind of definition point (Definition 22.1.5) and accepts a legal register sharing and a call result in a caller-saved register; every allocator's assignment of that function is valid for \(K \in \{1, 2, 3, 4\}\)
`ch22.IRCConservative.*`	R6: E2 refuses a merge that the Briggs and George tests both reject (Proposition 22.4.7 (ii): merging would make a triangle at \(K = \mathrm{MaxLive} = 2\)), and spills nothing when \(K = \mathrm{MaxLive}\) on call-free functions (Theorems 22.4.8, 22.4.9 and 22.6.5)
`ch22.Belady.Goldens`, `.OptimalAgainstBruteForce`, `.EdgeCases`	R11: misses and evictions on fixed strings; the miss count equals exhaustive search on 400 random strings; the evictions replay to the same count; empty and one-register strings
`ch22.lit` (`running.test`, `corpus-lli.test`, `checker.test`)	the driver's output on the running example; every allocator's rewritten corpus prints exactly what the original prints under `lli`, with few registers and with callee-saved registers; driver errors
`ch22.lab.compare-smoke`	`ch22-compare --quick` runs and every assignment is valid
★ `ch22.Star/Alloc.*`, `ch22.lit-star` (label `star`)	E3★: the same validity, random-program and `lli` checks

Before you start, every test that calls your code stops with TODO(ch22): E<n>: …. There are no hidden requirements.

Measurement¶

measure (and --metrics, ch22-compare) report, per function and summed: values, spilled values, static loads and stores of spill code, register-to-register phi moves, and the weighted spill cost and move cost, where an instruction in a block at loop depth \(d\) (LoopInfo) weighs \(10^d\) and a copy on edge \(P \to B\) weighs \(10^{\min(d(P), d(B))}\) (Definition 22.3.2, Proposition 22.9.2). Run

build/linux/bin/ch22-compare > compare.txt

and compare your numbers with the chapter README's comparison-lab table (reference solution, \(K = 4\)). Expect local allocation to cost about four times as much spill code as the global allocators, linear scan to leave many more moves than IRC, and holes to recover much of linear scan's extra spill cost.

Milestones¶

E0 beladyMisses: the ch22.Belady.* tests.
Shared analysis (your design): number values, compute live-after sets per instruction from Chapter 14 liveness, the call crossings, the phi moves, loop depths. Check your MaxLive against maxLive.
E1: ch22.Valid/Alloc.*/Local and the local lines of corpus-lli.test.
E2: build the graph (Algorithm 22.1.9), then Chaitin–Briggs without coalescing, then add IRC; …/ChaitinBriggs and the running-example moves.
E3 (and ★ E3★): intervals and the scan; …/LinearScan.
E4: spilling to MaxLive, then dominance-order colouring; ch22.SSAOptimal.*, the running example.
Measure with ch22-compare and answer exercise E5.

Hints¶

Hint 1 — one analysis for four allocators

All four need the same facts: the values of each class, which values are live just after each instruction (and at each block entry), which values cross a call, the phi moves, and a cost per value. Compute them once per function in a small struct; the allocators differ only in how they use them.

Hint 2 — calls

A value live across a call may only use callee-saved registers. In the graph allocator, add one pre-coloured node per caller-saved register and an edge from each call-crossing value to all of them; in linear scan and local allocation, restrict the free-register search; in E4, count the values across each call against the callee-saved count before colouring.

Hint 3 — the common bugs the tests catch

Forgetting that a phi operand is used at the end of the predecessor (not in the phi's block); forgetting that a dead definition still interferes with everything live after it; freeing an operand's register before assigning the result when the operand is still live after the instruction; values in unreachable blocks (R1 still wants a location: spill them); in E2, nodes coalesced into a node that is then actually spilled must be un-coalesced and retried.

Hint 4 — dominance-order colouring

DominatorTree gives the preorder. At a block's entry, the colours in use are exactly those of its live-in values, which were coloured earlier because their definitions dominate the block. If a colour is ever missing when \(K \ge\) the pressure after spilling, your pressure count or your release order is wrong, not the theorem.

Stretch goals ★¶

E3★ lifetime holes (R8), then the full second chance: split a spilled interval and give it a register again at its next use (needs a rewriter that supports several locations per value; design your own).
Rematerialization and spill placement estimates for exercise E5 (Lesson 22.9).
A PBQP or ILP allocator (Lesson 22.7) behind the same contract, compared with E2 on small functions.