Chapter 22 exercises

pebblec does not allocate registers itself: llc runs LLVM's greedy allocator (Lesson 22.8) on the code it emits. So this chapter's exercises build the classic allocators yourself, on a problem where every decision is visible and checkable: the comparison lab labs/ch22-regalloc/SPEC.md treats the SSA values of LLVM IR as virtual registers and judges four allocators with one independent checker and one rewriter that runs the assignment.

The contract

Function	Exercise	What it is
regalloc::beladyMisses(Refs, K, Evictions) in labs/ch22-regalloc/include/regalloc/Allocate.h	E0	Belady's MIN on a reference string (SPEC R11)
regalloc::allocateLocal(F, M)	E1	local allocation by furthest next use (R5)
regalloc::allocateChaitinBriggs(F, M)	E2	Chaitin–Briggs with iterated register coalescing (R6)
regalloc::allocateLinearScan(F, M)	E3	Poletto–Sarkar linear scan (R7)
regalloc::allocateLinearScanHoles(F, M)	E3★	linear scan with lifetime holes (R8), optional
regalloc::allocateSSA(F, M)	E4	spill to MaxLive, colour in dominance order (R9–R10)
compare.md (your notes)	E5	measurements and estimates, not tested

Your code goes anywhere under labs/ch22-regalloc/src/ (every *.cpp there is compiled); src/Stub.cpp defines the six functions with PEBBLE_TODO until you replace them. Provided (not exercises): the value model, the checker, the rewriter, the measurements and the random programs (include/regalloc/Infra.h), and the drivers ch22-regalloc and ch22-compare.

./course test 22                                    # builds, then runs every test labelled ch22
ctest --preset linux -L '^ch22$' -R Belady          # one suite while iterating (macos: --preset macos)
ctest --preset linux -L star                        # the optional E3★
build/linux/bin/ch22-regalloc labs/ch22-regalloc/inputs/running.ll --function=run \
  --method=irc --gpr=3 --print --metrics

Before you start, every ch22 test that calls your code fails with TODO(ch22): E<n>: …, naming the exercise that fixes it. Inside ch22.lit, checker.test tests provided code and passes from the start; ch22.Checker.* corrupt a valid assignment produced by your E4, so they pass once E4 does.

Stuck? Work through the hints in order. The reference solution is in solutions/labs/ch22-regalloc/src/; look only after passing the tests, or after an honest hour.

---

E0 — Belady's MIN

Contract: beladyMisses · Tests: ch22.Belady.* · Lesson: 22.2, Algorithm 22.2.2, Theorem 22.2.6

Replay a reference string with \(K\) registers and evict, on a miss with all registers full, the value referenced furthest in the future (SPEC R11). Record the evicted value per step.

Requirements: SPEC R11; \(O(m \log K)\) or \(O(mK)\) for \(m\) references.

What the tests check: fixed strings with their miss counts and eviction sequences (ties go to the smallest value), optimality against exhaustive search on 400 random strings, that each eviction removes a value that is in a register, and the empty and one-register edge cases.

Hint 1 — where to start

Precompute, for each position, the next position at which the same value is referenced (one backward pass with a map from value to "last seen").

Hint 2 — the key idea

At a miss, the victim is the register value with the largest next-reference position; "never again" is infinity. Ties can only happen between values never referenced again.

Hint 3 — a design sketch

A set of (next reference, value) pairs ordered by next reference, updated at every hit and miss, gives \(O(\log K)\) per step. The common bug: forgetting to update the next reference of a value on a hit.

Done when: ch22.Belady.* passes. Then try ./course drill belady.

---

E1 — Local allocation

Contract: allocateLocal · Tests: ch22.Valid/Alloc.*/Local, ch22.RunningExample.*, corpus-lli.test (local lines) · Lesson: 22.2, Algorithm 22.2.4

Build the shared per-function facts first (SPEC milestone 2): value numbers, live-after sets, call crossings. Then allocate each block by itself: values that are live across a block boundary live in memory, the rest get registers in order, and when none is free the furthest-next-use value is spilled.

Requirements: SPEC R1–R5.

What the tests check: validity on the corpus, the running example and 100 random programs for many \(K\), and that the rewritten programs compute the original results; at least 5 spilled values on the running example at \(K = 4\).

Hint 1 — where to start

Use pebble::dataflow::computeLiveness(F) from Chapter 14 for live-in/live-out sets, then walk each block backward to get the values live just after each instruction.

Hint 2 — the key idea

Because a value has one location for its whole life, "spilling" a value in the middle of a block is retroactive: its register is simply never written. So allocate forward, and when you must spill, choose among the new value and the values currently holding allowed registers.

Hint 3 — a design sketch

A per-block array "register → value or free", released when a value's last use in the block passes. Values live across a call see only callee-saved registers. The common bug: a phi operand is used at the end of the predecessor, so it is live out of that block.

Done when: the Local instances of ch22.Valid/Alloc.* pass.

---

E2 — Chaitin–Briggs with iterated register coalescing

Contract: allocateChaitinBriggs · Tests: ch22.Valid/Alloc.*/ChaitinBriggs, ch22.RunningExample.*, ch22.Quality.*, corpus-lli.test (irc lines) · Lessons: 22.3, 22.4, Algorithms 22.1.9, 22.3.4, 22.3.8, 22.4.6

Build the interference graph per class (Definition 22.1.5), then colour it. Do it in two steps: first Chaitin–Briggs without coalescing (simplify, potential spill by cost/degree, optimistic select, spill and repeat), then IRC with the phi copies as moves and a conservative test.

Requirements: SPEC R1–R4, R6.

What the tests check: validity and run-time equivalence as for E1; on the running example at \(K = 4\), no spill and exactly one remaining move (weight 1); on the corpus, less weighted spill cost than E1 and no more weighted moves than E3.

Hint 1 — where to start

Check your graph against the drill: ./course drill interference-graph --solution uses the same interference rule. The running example has 14 edges (Lesson 22.1 §3).

Hint 2 — the key idea

Calls: add \(K - C\) pre-coloured nodes (the caller-saved registers) and connect every call-crossing value to all of them; select then cannot give it a caller-saved register. Pre-coloured nodes are never simplified or spilled, and the George test is the one to use when one side is pre-coloured.

Hint 3 — a design sketch

Appel's worklists (simplify, freeze, spill; moves: worklist, active, coalesced, constrained, frozen) with an alias function (union–find). After an actual spill, remove the spilled nodes, un-coalesce everything that was merged into them, and rerun from the build step. The common bug: forgetting to recompute degrees after a merge, which makes the Briggs test unsafe.

Done when: the ChaitinBriggs instances and ch22.RunningExample.SpillsAndColours pass.

---

E3 — Linear scan (★ E3★ with lifetime holes)

Contract: allocateLinearScan (★ allocateLinearScanHoles) · Tests: ch22.Valid/Alloc.*/LinearScan (★ ch22.Star/Alloc.*, ch22.lit-star) · Lesson: 22.5, Algorithms 22.5.3, 22.5.7

Number the instructions in one linear block order with two slots per instruction (Definition 22.1.8), build one interval per value, and scan (SPEC R7). For ★ E3★ keep the list of segments and pack into holes (R8).

Requirements: SPEC R1–R4, R7 (★ R8).

What the tests check: validity and run-time equivalence as for E1; with \(K = \mathrm{MaxLive} - 1\) at least one spill.

Hint 1 — where to start

Reverse postorder keeps loop bodies together. A value live into a block covers that block's slots from its start; a value live out covers them to its end.

Hint 2 — the key idea

A hull is an over-approximation: two values whose hulls overlap may never be live together, but if they are, their hulls overlap. So the hull scan is always safe, only pessimistic (Theorem 22.5.4).

Hint 3 — a design sketch

An active list sorted by end. Expire intervals that end before the new start; if no register is free, compare the new interval's end with the furthest active end. Calls: an interval covering a call slot may only take a callee-saved register, and must be spilled if none is free. The common bug: ending an interval at the last use in layout order instead of at the last slot where the value is live; a value used in a loop header and live around the back edge must cover the whole loop body.

Done when: the LinearScan instances pass (★ and ctest -L star).

---

E4 — SSA-based allocation

Contract: allocateSSA · Tests: ch22.Valid/Alloc.*/SSA, ch22.SSAOptimal.*, ch22.RunningExample.*, running.test · Lesson: 22.6, Algorithms 22.6.6, 22.6.9, Theorem 22.6.7

Spill first, until the pressure at every definition point fits (R9); then colour in dominator-tree preorder (R10). With the pressure fitting, the colouring cannot fail on call-free functions, which is Theorem 22.6.7, and the tests hold you to it.

Requirements: SPEC R1–R4, R9–R10.

What the tests check: validity and equivalence as for E1; no spill and at most MaxLive registers when \(K = \mathrm{MaxLive}\) (at least 60 call-free functions); on the running example one spill at \(K = 3\), none at \(K = 4\), and one phi move of weight 1 at \(K = 4\).

Hint 1 — where to start

./course drill ssa-coloring traces the colouring step by step; make your implementation print the same trace for the running example first.

Hint 2 — the key idea

Release the colours of operands that die at an instruction before choosing its result's colour; the result and a dying operand do not interfere (Definition 22.1.5).

Hint 3 — a design sketch

Spilling: for every point, the list of values present; while some point exceeds its limit (\(K\), or the callee-saved count at a call), spill the value that is in the most over-full points per unit of cost. Colouring: prefer, among free colours, the colour of a phi-related value (the phi for its operands, an operand for its phi). The common bug: forgetting that the values live into a block keep the colours they got in a dominator.

Done when: ch22.SSAOptimal.*, ch22.RunningExample.* and the SSA instances pass.

---

E5 — Measure and explain (not tested)

Tools: build/linux/bin/ch22-compare, llc · Lessons: 22.8, 22.9

Run ch22-compare and write compare.md answering:

1. For \(K = 3, 4, 6, 8\): which allocator has the lowest weighted spill cost, and which the fewest weighted moves? Compare with the README's table and explain each difference with a theorem or a design decision of the lessons.
2. Holes (★): how much of linear scan's extra spill cost do lifetime holes recover at \(K = 4\)?
3. Rematerialization estimate. For the corpus, count the spilled values whose definition is a rematerializable instruction in the sense of Definition 22.9.4 (a constant, or a pure instruction whose operands are live at every use). How much of the weighted spill cost would recomputing them save, if a recomputation costs as much as one load?
4. Placement estimate. For one spilled value of pressure whose reloads are all in the call block, compute the expected cost of storing at the definition versus in the call block (use \(10^{d}\) frequencies, then the frequencies llc reports with -pass-remarks-missed=regalloc).

Hint — where the numbers come from

ch22-regalloc --metrics --print gives per-function locations and costs; measure weights a copy on an edge by the shallower of its two blocks.

Done when: you can defend each number in front of the comparison table of the README.