Flashcards — Chapter 22¶
79 cards. Review them with spaced repetition in the terminal (./course flash 22) or export them to Anki (./course flash export 22). Here, click a card to reveal its back.
interference¶
When do two SSA values interfere (Chaitin's rule, Definition 22.1.5)?
When one is defined at a point where the other is defined too or live just after it. A value that dies at an instruction does not interfere with that instruction's result (read before write); a dead definition still interferes with everything live after it.
Why is it enough to check interference only at definition points in strict SSA?
If u and v are live together at some point, the later-defined one (by dominance) is defined where the other is live (Lemma 22.1.11, Theorem 22.1.12). So every conflict shows up at a definition point.
What is MaxLive and why is it a lower bound?
The largest number of values live together at a point (Definition 22.1.7). Those values form a clique of the interference graph, so no valid assignment without spills uses fewer registers (Proposition 22.1.15).
What is a live interval with lifetime holes?
The set of slots where a value is live, as sorted maximal segments [s1,e1] ∪ … ∪ [sm,em]; the gaps are holes. LLVM's LiveInterval stores exactly this over SlotIndexes (Definition 22.1.8).
Cost of building the interference graph?
Θ(N·L): at each of N definition points add edges to the L values live there; up to Θ(n²) edges. This, not colouring, dominates the time of graph-colouring allocators.
regclass¶
What is a register unit in LLVM?
The smallest piece of register storage (e.g. al/ah on x86). Two registers overlap iff they share a unit, so LLVM checks interference per unit (TargetRegisterInfo::regunits, Definition 22.1.10).
How do sub-registers change the colouring model?
Registers of different classes may alias (eax ⊂ rax), so the colours are not interchangeable and a neighbour may block more than one register. Smith–Ramsey–Holloway generalize the degree test by counting how many registers each neighbour can block.
Why do values of different register classes never interfere in the lab?
The lab's machine is uniform with disjoint classes GPR and FPR (Definition 22.1.1): an FPR value can never take a GPR register, so only same-class pairs compete.
precolor¶
What does a call do to register allocation, and how is it modelled?
It clobbers the caller-saved registers. A value live across a call must be spilled or be in a callee-saved register; in a graph, connect it to pre-coloured nodes for all caller-saved registers (LLVM: regmask operands).
What is a regmask operand in LLVM MIR?
A call operand listing which physical registers survive the call; every register not in the mask is clobbered. Live intervals crossing it cannot be assigned a clobbered register.
Callee-saved vs caller-saved: what does using each cost?
Caller-saved: free until a value lives across a call (then spill around it). Callee-saved: survives calls, but the function must save and restore it once (prologue/epilogue, shrink-wrapped).
belady¶
Belady's MIN rule?
On a miss with all K registers full, evict the value whose next use is furthest in the future (never used again = infinitely far).
Why is MIN optimal for clean values?
Exchange argument (Theorem 22.2.6): any optimal schedule can be transformed step by step to agree with MIN's eviction without adding misses, because the value MIN evicts is needed no sooner than the other one.
When is MIN not optimal?
When evicting a dirty value costs a store: choosing between a clean and a dirty value changes the cost (Proposition 22.2.7); the problem with store costs is NP-hard \[[FCL00](references.md#ref-fcl00)\].
Belady on 'abcadbacd' with K = 3: how many loads? LRU?
MIN: 5 loads. LRU: 7 loads.
regallocfast¶
What does LLVM's RegAllocFast do?
Allocates one block at a time, walking it backwards, keeps no value in a register across block boundaries (spills live-outs, reloads live-ins), and evicts when needed. Used at -O0.
RegAllocFast's invariant at block boundaries?
Every virtual register live across a block boundary is in its stack slot at the boundary (Proposition 22.2.8), so blocks can be allocated independently.
Cost and quality of local allocation?
O(N), the fastest allocator; but every value live across blocks is in memory: in the lab ~4× the weighted spill cost of the global allocators.
chaitin¶
Chaitin's simplification lemma?
A node with degree < k can be removed: if G − v is k-colourable, so is G, because v's < k neighbours leave a colour free (Lemma 22.3.3).
Chaitin's spill metric?
Spill cost / degree, with cost = Σ over defs and uses of 10^(loop depth) (Definition 22.3.2). Cheap-to-spill, high-degree nodes go first.
Why does Chaitin's allocator iterate?
Spill code creates new short live ranges (reload temporaries) that need registers, so after inserting spill code the graph is rebuilt and coloured again (Algorithm 22.3.4).
Is k-colourability NP-complete?
Yes, for every fixed k ≥ 3 (Garey–Johnson GT4); Chaitin et al. showed every graph is the interference graph of some program, so register allocation by colouring is NP-complete in general.
briggs¶
Optimistic colouring (Briggs) in one sentence?
When simplification is stuck, push a potential spill node anyway and spill it only if select finds no free colour for it (an actual spill).
Smallest graph Chaitin spills but Briggs colours?
The square a–b–c–d–a with k = 2: every degree is 2, so Chaitin spills; Briggs pushes a node and select 2-colours it.
Why is Briggs never worse than Chaitin?
Its simplify order is the same; it only postpones the spill decision, and every node Chaitin would colour still gets a colour (Theorem 22.3.9).
aggressive-coalescing¶
What is coalescing?
Merging the two ends of a copy (a move pair) that do not interfere into one node, so they get the same register and the copy disappears (Definition 22.4.1).
Why can aggressive coalescing cause spills?
The merged node has the union of both neighbourhoods, so its degree can reach k and a colourable graph becomes uncolourable (Proposition 22.4.7 (ii)).
Where is aggressive coalescing used in practice?
LLVM's RegisterCoalescer (before allocation; greedy's splitting undoes harmful merges) and HotSpot C2's first coalescing phase.
conservative-coalescing¶
Briggs's conservative test?
Merge a and b if the merged node has fewer than k neighbours of significant degree (≥ k) (Definition 22.4.3).
George's conservative test?
Merge a into b if every neighbour t of a already interferes with b or has insignificant degree (< k) (Definition 22.4.5). Suited to pre-coloured b.
Why are the Briggs and George tests safe?
They preserve k-degeneracy/simplifiability: whatever simplification removed before still gets removed after the merge (Theorems 22.4.8, 22.4.9), so no new spills.
irc¶
What does iterated register coalescing add to conservative tests?
It interleaves them with simplification: removing low-degree nodes lowers degrees, so moves refused earlier can be accepted later; freeze gives up on a move only when nothing else works.
IRC's worklists?
simplifyWorklist, freezeWorklist, spillWorklist for nodes; worklistMoves, activeMoves, coalescedMoves, constrainedMoves, frozenMoves for moves (Algorithm 22.4.6).
Running example at K = 4 under IRC: spills and moves?
No spill; one move left (the entry copy s ← a, weight 1), because the back-edge pairs i–i2 and s–s2 are coalesced.
linear-scan¶
Poletto–Sarkar linear scan?
Sort intervals by start; expire those that ended; if no register is free, spill the interval (new or active) whose end is furthest (Algorithm 22.5.3). O(n log n).
Why can linear scan spill when colouring would not?
It uses hulls, which over-approximate liveness (false conflicts across holes), and spills by end point, not cost; the interval graph of the hulls may need more colours than the real interference graph.
Running example, K = 3: which value does Poletto–Sarkar spill?
s (interval [5, 20]): at i's start the furthest end among the active intervals and the new one is s's.
second-chance¶
What is second-chance binpacking?
Traub et al.: registers are bins; intervals are packed into lifetime holes of values already in a bin; a spilled value gets a register again at its next use (second chance), with resolution moves on edges.
What does resolution do?
After allocating pieces of a value independently, insert moves on CFG edges where the value's location at the end of the predecessor differs from its location at the start of the successor (Definition 22.5.2).
Who uses second-chance style allocation?
V8 TurboFan: linear scan with splitting, deferred-block spilling and gap moves (register-allocator.cc).
lifetime-holes¶
Wimmer–Mössenböck: free-until position?
For each register, the first position where it is needed by an interval that occupies it; if the new interval ends before it, the register is free for the whole interval, else split at the free-until position (Algorithm 22.5.8).
Wimmer–Mössenböck: when no register is free?
Take the register whose next use is furthest (Belady-like); spill the part of the current interval or of the intervals using it, splitting at optimal positions (e.g. outside loops).
Lab: how much do lifetime holes save over hull linear scan (K = 4)?
Weighted spill cost 77 647 vs 105 719 (spilled values 1914 vs 2499), on 414 functions.
ssa-linear-scan¶
Wimmer–Franz: why one pass on SSA?
In SSA with blocks in an order that keeps loops contiguous, a backward pass over blocks can build every interval, extending values live around a loop to the loop end (Algorithm 22.5.10, Theorem 22.5.11).
How does SSA linear scan remove phis?
During resolution: phi operands become moves on the incoming edges, like the moves between split pieces, so no separate out-of-SSA pass is needed.
Where is SSA-based linear scan used?
Graal (SSALinearScan in the lsra package), after Wimmer and Franz 2010.
chordal¶
Why are SSA interference graphs chordal?
Interfering SSA values are ordered by dominance of their definitions (Lemma 22.6.3); the reverse of the dominance order of definitions is a perfect elimination order (Theorem 22.6.5).
How many colours does dominance-order colouring use?
Exactly MaxLive = ω(G) = χ(G): at each definition the values live are a clique, so a free colour exists whenever K ≥ MaxLive (Theorem 22.6.7).
Colouring in dominance order: the order of operations at an instruction?
Release the colours of operands that die there, then give the result the lowest free colour; at block entry, live-in colours are taken, then phis are coloured (Algorithm 22.6.6).
decoupled-spilling¶
What does 'decoupled' spilling mean?
Spill first until the pressure is ≤ K at every point, then colour without ever spilling again (on SSA this suffices by Theorem 22.6.7).
Is spilling on SSA easy?
No: deciding whether spilling a set of cost ≤ C suffices is still NP-complete on SSA (Theorem 22.6.11, \[[BDR07b](references.md#ref-bdr07b)\]); only colouring became easy.
Which rule does libFirm use to choose spills?
A global Belady rule: next-use distances along the CFG, with loops counted as far away (Braun–Hack 2009).
ssa-destruction-after-ra¶
What happens to phis if you allocate before SSA destruction?
Each phi becomes a parallel copy of registers on each incoming edge: a permutation, implementable with moves and at most one scratch register or swaps (Theorem 22.6.12).
Why is coalescing phi-related values after SSA colouring still hard?
Optimal coalescing is NP-complete even on chordal graphs; incremental conservative coalescing (one affinity at a time) is polynomial \[[BDR07](references.md#ref-bdr07)\].
Which production allocators take SSA input?
Cranelift's regalloc2 (SSA with block parameters), libFirm, Graal's SSA linear scan.
pbqp¶
What is a PBQP instance for register allocation?
One cost vector per value (a cost per register plus a spill cost) and one cost matrix per interfering or affine pair (∞ for same register if interfering, negative/benefit for coalescing); minimize the total (Definitions 22.7.1–22.7.2).
PBQP reductions R0, RI, RII, RN?
R0: degree 0, pick min. RI: degree 1, fold into the neighbour's vector. RII: degree 2, fold into a matrix between the two neighbours. RN: heuristic choice for degree ≥ 3. R0–RII are exact (Theorem 22.7.4).
How does PBQP do on x86 in LLVM (press.c)?
21 spills / 14 reloads vs greedy's 12 / 11: good on irregular targets, but greedy's splitting wins on x86 (llc 23.1.2, -regalloc=pbqp).
ilp¶
What do ILP formulations of register allocation give?
Provably optimal allocation for the model (spills, copies, rematerialization), at compile times of seconds to minutes per function (Goodwin–Wilken 1996).
Appel–George's decomposition?
Decide optimally by ILP where each value is in a register or memory (spill placement), then assign registers by coalescing heuristics (Algorithm 22.7.7).
Core ILP constraint for interference?
x_{u,r} + x_{v,r} ≤ 1 for every interfering pair {u, v} and register r, with Σ_r x_{v,r} + s_v = 1 for each value (Definition 22.7.6).
greedy-eviction¶
LLVM greedy: in what order are intervals allocated?
By priority from a queue: global and split ranges by size, local ones by position, with hint/global bits (DefaultPriorityAdvisor); not by spill weight.
When may interval A evict B in greedy?
B's cascade is lower than A's, B is not a spill product, and A's spill weight is higher (or A wants the register as a hint and B can still be split) (Definition 22.8.1).
What are cascades for?
To guarantee termination: an evicted interval inherits the evictor's cascade and may only evict intervals of a strictly lower cascade, so eviction cycles cannot recur (Theorem 22.8.4).
splitting¶
Greedy's split kinds, in order?
Region split (SpillPlacement over edge bundles), block split, then within a block: local split around a gap and instruction split per use (Algorithm 22.8.3).
What does SpillPlacement minimize?
A Hopfield-network energy over edge bundles: frequency-weighted bias for register vs memory plus links through transparent blocks; converges to a local minimum.
How do split pieces stay correct?
Each piece is a new virtual register; lr-split COPYs connect pieces at split points and on edges, like resolution in linear scan (Proposition 22.8.7).
rewriter¶
What does VirtRegRewriter do?
Replaces every virtual register by its physical register from VirtRegMap (composing sub-registers), deletes identity copies, and adds block live-ins (Algorithm 22.8.8).
Why can an identity copy be deleted?
r ← r writes the value r already holds; only liveness facts are lost, which KILL pseudo-instructions keep where needed (Proposition 22.8.9).
What does MachineCopyPropagation do after RA?
Forwards copy sources into later uses and deletes copies made redundant, when the source is not clobbered in between (forwardUses, forwardCopyPropagateBlock).
spill-weights¶
LLVM's spill weight formula?
w(v) = UD(v)·α(v) / (|v| + 25·InstrDist), UD = Σ (def+use)·f(block); α: ×3 loop-exit IV update, ×1.01 hinted, ×0.5 all-remat, class scale (Definition 22.9.1).
What is the numerator of the spill weight, exactly?
The expected number of executed spill loads and stores per call if v is spilled everywhere (Proposition 22.9.2, linearity of expectation).
Loop entered with probability 0.625, back edge taken 31/32: loop body frequency?
0.625 · 1/(1 − 31/32) = 20, relative to the entry (the remat.ll remarks show cost 20 per spill in the loop).
remat¶
When is rematerialization correct?
The definition is pure and deterministic, reads no mutable memory, and its operands hold the same values at the use (automatic in strict SSA by Lemma 22.9.5 / Theorem 22.9.6).
Why does LLVM require the operands of a remat to be live at the use?
Recomputing with operands that are not live would extend their live ranges and add register pressure; LLVM checks value numbers (allUsesAvailableAt).
Where does LLVM rematerialize?
InlineSpiller::reMaterializeFor, before each use of a spilled interval; the original definition is deleted if no use needs it. Go rematerializes values whose operands are only SP/SB.
spill-placement¶
Bottom-up spill hoisting recurrence?
opt(n) = f(n) if n has a store; else min(f(n), Σ opt(children)) if n is a candidate, Σ opt(children) otherwise. Exact for μ = 1 (Theorem 22.9.10); LLVM uses μ = 0.9 to prefer merging.
Why is a hoisted spill correct?
The new store block h dominates the old store p and is dominated by the definition, so it executes after the last definition and before p (Lemma 22.9.5); the slot then holds the current value.
How does Go place spills?
It sinks: walks down the dominator tree through blocks that dominate all restores, never into a deeper loop, and stores in the deepest one where the value is in a register (placeSpills).