Lesson 22.9 — Spill weights, rematerialization and spill-code placement

Techniques: spill weights and block frequency; rematerialization; spill-code placement (hoisting and sinking spills on the dominator tree) · Lab: none new; the lab's spill-everywhere metric (SPEC §"Measurement") is the cost these techniques reduce · Prerequisites: Lessons 22.3 (spill cost, Definition 22.3.2), 22.6 (decoupled spilling), 22.8 (greedy, splitting); Ch 15 (dominator trees) · Time: 3–4 hours

Every allocator in this chapter eventually decides that some value does not get a register everywhere, and then three questions remain, whatever the allocator. Which value is cheapest to spill? Chaitin counted uses weighted by \(10^{\text{loop depth}}\) (Definition 22.3.2); LLVM uses block frequencies and divides by the size of the live range, so it knows both what spilling costs and what it frees. What does a use get instead of a register? Usually a reload from the stack, but a value that can be recomputed from values still in registers (a constant, an address) is cheaper to recompute: rematerialization [BCT92]. Where do the stores go? Spilling "everywhere" stores after every definition; a store placed at a cold dominator of all the reloads is executed less often. This lesson makes the three decisions precise, proves the two correctness conditions they rely on, and shows each in LLVM 23 and Go.

1. Problem and motivation

Spill weights and block frequency

Input: a live interval (or live range) \(v\), the instructions that define and use it, and an estimate of how often each block executes. Output: a number \(w(v)\) such that spilling the interval with the smallest weight among the candidates is a good choice. A spill decision trades executed memory operations (the cost) against register pressure relieved (the benefit). Counting uses alone ignores the benefit: a value defined at the top of a function and used once at the bottom has two references but blocks a register for the whole function. Loop depth ignores branch probabilities: a use on an error path inside a loop is not ten times as hot as the function entry.

Rematerialization

Input: a value \(v\) chosen for spilling and one of its uses. Output: an instruction sequence that makes \(v\) available in a register at the use. A reload costs a memory access; if \(v\)'s definition is a constant materialization (MOV64ri, LEA of a global, ADRP+ADD), recomputing it costs one cheap instruction and needs no store at the definition at all. The question is when recomputation gives the same value, and that is a correctness question, not only a cost question.

Spill-code placement

Input: a spilled value, the points where it is reloaded, the dominator tree and block frequencies. Output: the points where the value is stored. Storing after every definition is always correct, but when the value's reloads are all on a rare path (the call block of press.c, Lesson 22.8 §3) the store belongs on that path, and when a store sits in a loop whose value is already defined before the loop, the store belongs in the preheader. Both are placement problems on the dominator tree.

2. Definitions and algorithms

Spill weights and block frequency

Definition 22.9.1 (Block frequency, spill weight)

The relative block frequency \(f(B) \ge 0\) is the expected number of executions of block \(B\) per execution of the function's entry block (MachineBlockFrequencyInfo::getBlockFreqRelativeToEntryBlock), computed from branch probabilities; \(f(\mathit{entry}) = 1\). For a live interval \(v\) with instructions \(I_1, \dots, I_m\) that read or write it (identity copies and IMPLICIT_DEF excluded), let \(d_j, u_j \in \{0, 1\}\) say whether \(I_j\) writes, reads \(v\), and \(B_j\) its block. The use/def frequency and the spill weight of \(v\) are

\[ \mathrm{UD}(v) = \sum_{j=1}^{m} (d_j + u_j)\, f(B_j), \qquad w(v) = \frac{\mathrm{UD}(v) \cdot \alpha(v)}{\lvert v \rvert + 25\,\delta}, \]

where \(\lvert v \rvert\) is the total length of \(v\)'s segments in slot indexes, \(\delta\) = SlotIndex::InstrDist \(= 16\) (the slot distance between consecutive instructions), and \(\alpha(v)\) is a product of adjustments: \(\times 3\) for a write in a loop-exiting block while \(v\) is live out of it (an induction-variable update), \(\times 1.01\) if \(v\) has copy hints, \(\times 0.5\) if every definition of \(v\) is rematerializable, and the register class's scale factor (1 by default) [LLVM-SpillWeights]. An unspillable interval (a zero-length interval not live across a call or register mask, or an interval split from an unspillable one) has weight \(\infty\).

Proposition 22.9.2 (The numerator is the expected cost of spilling everywhere)

Suppose spilling \(v\) everywhere inserts one store after each instruction that writes \(v\) and one reload before each instruction that reads it, each costing 1, and \(f(B)\) is exactly the expected number of executions of \(B\) per call. Then the expected number of executed spill instructions per call is \(\mathrm{UD}(v)\).

Proof

Let \(X_j\) be the number of executions of \(I_j\) in one call. Spilling adds \(d_j + u_j\) executed memory operations per execution of \(I_j\), so the total is \(\sum_j (d_j + u_j) X_j\). By linearity of expectation its mean is \(\sum_j (d_j + u_j)\,\mathbb{E}[X_j] = \sum_j (d_j + u_j) f(B_j) = \mathrm{UD}(v)\), since an instruction executes exactly as often as its block.

The denominator is a heuristic, not a theorem: spilling an interval frees one register over its whole length, so \(\mathrm{UD}(v) / \lvert v \rvert\) is "cost per unit of pressure relieved", the value/size ratio of a greedy knapsack. The constant \(25\,\delta\) keeps tiny intervals from getting huge weights through accidental gaps in the slot numbering: for small intervals \(w\) is essentially proportional to \(\mathrm{UD}\), for long ones it approaches a use density (the comment on normalizeSpillWeight in CalcSpillWeights.h). Chaitin's cost of Definition 22.3.2 is \(\mathrm{UD}(v)\) with \(f(B) = 10^{d(B)}\), and his cost/degree divides by a different measure of the benefit.

Algorithm 22.9.3 (Spill weight of one interval: VirtRegAuxInfo::weightCalcHelper, LLVM 23.1.2)

• Input: live interval \(v\); block frequencies; loop info; the target's copy and rematerialization queries.
• Output: \(w(v)\) (Definition 22.9.1), or "unspillable"; allocation hints sorted by weight as a side effect.
• Precondition: live intervals and slot indexes are up to date.
• Postcondition: \(w(v) = \mathrm{UD}(v)\,\alpha(v) / (\lvert v \rvert + 25\delta)\).
• Invariant: after visiting \(j\) instructions, TotalWeight \(= \sum_{i \le j} (d_i + u_i) f(B_i)\) times the loop-exit factors applied so far.

function SpillWeight(v):
    total ← 0; hints ← {}
    for each instruction I reading or writing v (once per instruction):
        if I is an identity copy or IMPLICIT_DEF: continue
        (d, u) ← (I writes v, I reads v)
        x ← (d + u) · f(block(I))                 # LiveIntervals::getSpillWeight
        if d and block(I) exits a loop and v is live out of it: x ← 3x
        total ← total + x
        if I is a copy: hints[other register of I] += x
    if hints ≠ {}: total ← 1.01 · total           # hinted ranges weigh slightly more
    if v has length zero and crosses no call:    return unspillable
    if every definition of v is rematerializable: total ← 0.5 · total
    total ← total · ClassScale(regclass(v))
    return total / (|v| + 25 · InstrDist)          # normalizeSpillWeight

Rematerialization

Definition 22.9.4 (Rematerializable definition, available operands)

A definition \(d : x \leftarrow \mathit{op}(y_1, \dots, y_n)\) is rematerializable if \(\mathit{op}\) is deterministic and has no side effects, and reads no memory except memory that is invariant for the whole function (a constant pool, isReMaterializable in the target's instruction description). A rematerializable \(d\) can be rematerialized at a program point \(p\) if every operand \(y_i\) is available at \(p\): live at \(p\) in a register and holding the value it held at \(d\). In SSA form "the same value" is automatic for strict programs (Lemma 22.9.5); in MIR after PHI elimination LLVM checks that the operand's value number at \(p\) equals its value number at \(d\) (allUsesAvailableAt) [LLVM-SpillWeights, LLVM-InlineSpiller].

Lemma 22.9.5 (Last executions follow dominance)

Let \(a\), \(b\), \(c\) be program points with \(a\) dominating \(b\), \(b\) dominating \(c\), and \(a \ne b\). In any execution, at any time \(t\) when \(c\) executes, if \(a\) has executed before \(t\), then the last execution of \(b\) before \(t\) comes after the last execution of \(a\) before \(t\).

Proof

Let \(t_a < t\) be the last execution of \(a\) before \(t\). The part of the execution from \(t_a\) to \(t\) is a CFG path \(\pi\) from \(a\) to \(c\). Take any path from the entry to \(a\) and cut it at its first occurrence of \(a\); call it \(\rho\). The point \(b\) does not occur on \(\rho\): an occurrence of \(b\) on \(\rho\) would be preceded on \(\rho\) by an occurrence of \(a\) (because \(a\) dominates \(b\) and \(a \ne b\)), but \(\rho\) contains \(a\) only at its end. The concatenation \(\rho\pi\) is a path from the entry to \(c\), and \(b\) dominates \(c\), so \(b\) occurs on it, hence on \(\pi\) after its first point, that is, strictly after \(t_a\) and before \(t\) (or at \(t\) when \(b = c\)).

Theorem 22.9.6 (Rematerialization is sound in strict SSA)

Let the program be in strict SSA form, let \(d : x \leftarrow \mathit{op}(y_1, \dots, y_n)\) be rematerializable, and let \(p\) be a use of \(x\) (for a phi use, the end of the predecessor). Inserting \(x' \leftarrow \mathit{op}(y_1, \dots, y_n)\) immediately before \(p\) and replacing \(x\) by \(x'\) at \(p\) does not change the program's behaviour.

Proof

Strictness gives that \(d\) dominates \(p\) and that the definition \(e_i\) of each \(y_i\) dominates \(d\) (\(d\) uses \(y_i\)). Fix an execution reaching \(p\) at time \(t\) and let \(t_d\) be the last execution of \(d\) before \(t\); \(x\) holds at \(t\) the value computed at \(t_d\), since \(d\) is \(x\)'s only definition. For each \(i\), apply Lemma 22.9.5 with \(a = e_i\), \(b = d\), \(c = p\) (if \(e_i = d\) the operand would be \(x\) itself, impossible in SSA): the last execution of \(e_i\) before \(t\) precedes \(t_d\). So no definition of \(y_i\) executes in \((t_d, t)\) and \(y_i\) holds at \(t\) the value it held at \(t_d\). Because \(\mathit{op}\) is deterministic and reads no mutable state, \(x'\) gets at \(t\) the value \(x\) got at \(t_d\), which is the value of \(x\) at \(t\). The inserted instruction has no side effects, so nothing else changes.

The theorem is about correctness only. It does not say that rematerializing is free: if some \(y_i\) is not live at \(p\), recomputing \(x\) there extends \(y_i\)'s live range, which may cost more registers than it saves. LLVM therefore requires the operands to be live already (Definition 22.9.4), and Go rematerializes only instructions whose operands are the stack and static-base pointers (rematerializeable in regalloc.go) [Go-regalloc].

Algorithm 22.9.7 (Spilling with rematerialization: InlineSpiller::spill)

• Input: interval \(v\) to spill (with its sibling intervals from splitting).
• Output: \(v\) replaced by tiny intervals around its remaining uses; stores and reloads or recomputations inserted.
• Precondition: \(v\) is spillable; its original definitions are known (VirtRegMap::getOriginal).
• Postcondition: every use of \(v\) reads a value equal to \(v\)'s (Theorem 22.9.6 for recomputed uses, the stack slot for reloaded ones).
• Invariant: a definition is deleted only if no remaining use reads its value.

function Spill(v):
    for each use I of v (reMaterializeAll):
        D ← the original defining instruction of the value v has at I
        if D is rematerializable and its operands are available at I (Definition 22.9.4):
            if D is a foldable load: fold it into I as a memory operand
            else: insert v' ← copy of D before I, replace v by v' in I
        else: mark v's value at I as used            # it needs the stack slot
    delete definitions whose values are no longer used (dead remat originals)
    for each remaining use I: fold a stack access into I if the target can,
                               else insert v'' ← reload before I
    for each remaining definition I: fold a store into I, or insert a store after I
    record every store for hoisting (Algorithm 22.9.9)

Spill-code placement

Definition 22.9.8 (Spill placement on the dominator tree)

Fix a spilled value \(v\) with definition in block \(r\), and let \(T\) be the dominator tree restricted to the blocks it dominates. Let \(P \subseteq V(T)\) be the blocks that contain a store of \(v\) in a correct initial placement (every reload is preceded, on every path since the last definition of \(v\), by a store), and \(C \supseteq P\) the candidate blocks, where \(v\) is in a register at the insertion point. A placement is a set \(H \subseteq C\) such that every \(p \in P\) has an ancestor-or-self in \(H\); its cost is \(\sum_{h \in H} f(h)\). An optimal placement minimizes the cost.

Algorithm 22.9.9 (Bottom-up hoisting: HoistSpillHelper::runHoistSpills)

• Input: \(T\), \(P\), \(C\), block frequencies \(f\); a margin \(\mu \in (0, 1]\).
• Output: a placement \(H\).
• Precondition: stores in \(P\) dominated by another store in \(P\) have been removed (they are redundant: rmRedundantSpills, getVisitOrders).
• Postcondition: \(H\) is a placement (Definition 22.9.8).
• Invariant: after node \(n\) is processed, \(S(n)\) is a set of nodes in \(n\)'s subtree that covers every store of \(P\) in that subtree, and \(\mathrm{cost}(n) = \sum_{h \in S(n)} f(h)\).

function Hoist(T, P, C, f, μ):
    for n in T bottom-up (children before parents):
        if n ∈ P:
            S(n) ← {n}; cost(n) ← f(n); continue
        S(n) ← ⋃ S(c) over children c; cost(n) ← Σ cost(c)
        if S(n) = ∅ or n ∉ C: continue
        m ← (μ if |S(n)| > 1 else 1)               # LLVM: μ = 9/10, a bias to merge
        if cost(n) > m · f(n):
            S(n) ← {n}; cost(n) ← f(n)              # one store in n replaces those below
    return S(root)

Theorem 22.9.10 (Bottom-up hoisting is sound, and optimal for μ = 1)

(a) Replacing the stores at \(P\) by stores at the placement \(H\) returned by Algorithm 22.9.9 keeps every reload correct. (b) With \(\mu = 1\) the returned placement has minimum cost.

Proof

(a) Consider a reload at time \(t\). In the initial placement some store \(p \in P\) executes after the last definition of \(v\) before \(t\), at time \(t_p < t\). The block \(p\) has an ancestor-or-self \(h \in H\), so \(h\) dominates \(p\), and \(r\) dominates \(h\). If \(h = p\) the store is unchanged. If \(h = r\) the new store sits after the definition in \(r\) and executes after the last definition, done. Otherwise apply Lemma 22.9.5 with \(a = r\), \(b = h\), \(c = p\) at time \(t_p\): \(h\) executes after the last definition of \(v\) and before \(t_p < t\). At that moment \(v\) is in a register (\(h \in C\)) and holds its current value, so the slot holds that value at \(t\) (the slot is only written by stores of \(v\), which all store the current value).

(b) Write \(\mathrm{opt}(n)\) for the minimum cost of a set \(H_n \subseteq C \cap \mathrm{subtree}(n)\) covering \(P \cap \mathrm{subtree}(n)\). We show by induction on the height of \(n\) that \(\mathrm{cost}(n) = \mathrm{opt}(n)\) with \(\mu = 1\). If \(n \in P\), any cover contains \(n\) (no other node of the subtree is an ancestor of \(n\)), and \(\{n\}\) covers the whole subtree, so \(\mathrm{opt}(n) = f(n)\). Otherwise, a cover \(H_n\) either contains \(n\), costing at least \(f(n)\), and then \(\{n\}\) alone is a cover (if \(n \in C\)); or it does not, and then its restrictions to the children's subtrees are covers of those subtrees (a store in child \(c\)'s subtree can only be covered from inside that subtree or by \(n\)), costing at least \(\sum_c \mathrm{opt}(c)\), and the union of optimal child covers achieves that. So \(\mathrm{opt}(n) = \min(f(n), \sum_c \mathrm{opt}(c))\) if \(n \in C\) and \(\sum_c \mathrm{opt}(c)\) otherwise, which is what the loop computes (it hoists exactly when \(\sum_c \mathrm{cost}(c) > f(n)\)). At the root, \(\mathrm{cost}(r) = \mathrm{opt}(r)\).

With \(\mu = 9/10\) LLVM prefers one store to several when it costs at most \(10/9\) times as much: fewer instructions for a small expected-cost increase. Go solves the dual problem, sinking: it starts from the definition and walks down the dominator tree through blocks that dominate all the restores, and puts the one store in the deepest such block that is not in a deeper loop than the definition and has the value in a register at its start (placeSpills) [Go-regalloc]. For a single store the two agree on the goal: the store must dominate every reload and should be as cold as possible.

Theorem 22.9.11 (Optimal spilling is hard)

Minimizing the number of loads and stores for straight-line code with \(K\) registers (the paging problem with write-back costs) is NP-hard [FCL00]; deciding whether spilling everywhere a set of total cost \(\le C\) suffices is NP-complete even for SSA programs (Theorem 22.6.11) [BDR07b].

Proof sketch (full proofs: [FCL00], [BDR07b])

Farach-Colton and Liberatore reduce an NP-complete problem to the choice of which dirty values to evict in a straight-line block; Bouchez, Darte and Rastello reduce known NP-complete problems to spill-everywhere on SSA programs. Hence weights (Algorithm 22.9.3) and bottom-up placement (Algorithm 22.9.9) are heuristics for the whole problem, while Theorem 22.9.10 makes one sub-step, the placement of a given value's stores on the tree, exact.

3. Worked example

Spill weights and block frequency

The running example of Lesson 22.1 with \(f(B) = 10^{\text{loop depth}}\) (so \(\mathrm{UD}\) is the lab's spill cost, Definition 22.3.2) and the slot numbering of Lesson 22.5 (two slots per instruction, so \(25\,\delta\) becomes \(25 \cdot 2 = 50\)). Lengths are the sums of the live segments (with holes, Lesson 22.5), as LiveInterval::getSize computes them. Interference degrees are from Lesson 22.1.

value	\(\mathrm{UD}\) (cost)	degree	cost / degree (Chaitin)	\(\lvert v \rvert\)	\(w = \mathrm{UD} / (\lvert v \rvert + 50)\)
a	13	7	1.86	19	0.188
i	50	6	8.33	11	0.820
s	21	3	7.00	5	0.382
c	20	3	6.67	1	0.392
t	20	2	10.00	1	0.392
u	20	2	10.00	1	0.392
s2	20	3	6.67	4	0.370
i2	20	2	10.00	2	0.385
r	2	0	∞	1	0.039

Both metrics pick a among the values that interfere, for different reasons: Chaitin's because a interferes with everything, LLVM's because a is long and used rarely. r has the lowest weight of all, but it interferes with nothing, so no allocator ever needs to spill it: the weight only ranks candidates that block an assignment. i is the most expensive to spill under both: it is read three times and written once per iteration.

Rematerialization

B0:  (f = 1)
     p  = arg
     k  = const 0x123456789abc      # rematerializable, no operands
     x  = add p 4                   # rematerializable, operand p
     jmp B1
B1:  (loop body, f = 10)
     y  = mul k p                   # use of k
     z  = add x y                   # use of x; p is live and unchanged here
     br z B1 B2
B2:  (f = 1)
     p  = sub p 1                   # MIR after PHI elimination: p redefined in place
     w  = add x p                   # use of x
     ret w

Suppose k and x are spilled. Spilling k everywhere costs, per call, one store in B0 and one reload before its use in B1: \(1 + 10 = 11\) memory operations. Rematerializing k costs 10 executions of a register-only MOV64ri and no store, and its original definition becomes dead and is deleted (Algorithm 22.9.7). For x inside the loop p is live and unchanged, so x = add p 4 is recomputed before the use. At the use in B2 after MIR has overwritten p in place (two-address code, no SSA), p's value number differs from the one at x's definition: recomputation would add 4 to the wrong value, so x is reloaded there (Definition 22.9.4). In SSA form p' would be a new name and p itself would still be the right operand, but only if it is still live, which is the availability condition.

Spill-code placement

Two dominator trees with block frequencies; stores of \(v\) in the initial placement are marked \(P\); all blocks are candidates.

A diamond with a cold arm. \(r\) (\(f = 1\)) has children \(L\) (\(0.6\)) and \(R\) (\(0.4\), \(P\)); \(L\) has children \(L_1\) (\(0.1\), \(P\)), \(L_2\) (\(0.2\), \(P\)) and \(L_3\) (\(0.3\)). Bottom-up: \(L\) gets \(\mathrm{cost} = 0.1 + 0.2 = 0.3\), which does not exceed \(0.9 \cdot 0.6 = 0.54\): keep. \(r\) gets \(0.3 + 0.4 = 0.7 \le 0.9 \cdot 1\): keep. Result \(H = \{L_1, L_2, R\}\), expected \(0.7\) stores per call instead of \(1\) for a store at the definition.

A loop. \(r\) (\(1\)) → preheader \(Q\) (\(1\)) → header \(H\) (\(10\)) with children \(B_1\) (\(4\), \(P\)) and \(B_2\) (\(5\), \(P\)). At \(H\): \(9 \le 0.9 \cdot 10 = 9\): keep (not strictly greater). At \(Q\): \(9 > 0.9 \cdot 1\): hoist, \(S(Q) = \{Q\}\), cost 1. At \(r\): \(1 \not> 1 \cdot 1\) (one store, margin 1): keep. Result: one store in the preheader, expected cost 1 instead of 9.

Try it

There is no drill for this lesson: spill weights depend on LLVM's frequency estimates, and the placement rule is a three-line recurrence. Recompute the loop example with \(f(H) = 8\) (does the store move to \(H\) or to \(Q\)?), then answer the quiz questions hoist-dp and spill-weight-running.

4. Invariants and correctness

Spill weights and block frequency

Weights do not affect correctness: any choice of spilled intervals is correct because spill code preserves values (Theorem 22.1.14 for spill-everywhere). What must hold is termination: a spill product must not be spilled again. Algorithm 22.9.3 makes tiny intervals unspillable (weight \(\infty\)), and greedy marks spill products RS_Done (Definition 22.8.1), so each round of spilling strictly shrinks the set of spillable intervals.

Frequencies are relative to the entry, not absolute

-pass-remarks-missed=regalloc reports costs as sums of \(f(B)\), which is relative to one execution of the entry block. A cost of 20 means "20 memory operations per call", not per loop iteration, and the same loop has a different frequency when the branch into it has a different probability (§7).

Rematerialization

Theorem 22.9.6 is the correctness argument; in MIR it is enforced by the value-number check of allUsesAvailableAt, which also refuses to recompute at the defining instruction itself (PR14098 in the source comment: the original instruction may redefine an operand) [LLVM-SpillWeights]. After rematerializing, a definition with no remaining uses is deleted; the invariant of Algorithm 22.9.7 (markValueUsed for every use that could not be rematerialized) guarantees that no deleted definition is still needed.

Spill-code placement

Theorem 22.9.10(a) is the correctness condition, and it needs both the dominance chain \(r \to h \to p\) and \(h \in C\) (the value is in a register at the new store). The precondition matters: all stores that are merged must store the same value (the same original definition, MergeableSpills is keyed by stack slot and value number). Stores of different values into the same slot are never merged.

5. Complexity

\(N\) = instructions, \(n\) = intervals, \(b\) = blocks.

Algorithm	Time (worst)	Time (typical)	Space	Justification
Block frequencies	\(O(b \cdot \text{loop depth})\)	linear	\(O(b)\)	BlockFrequencyInfoImpl propagates mass per loop, innermost first
Spill weights, all intervals (Alg. 22.9.3)	\(O(N)\)	linear	\(O(n)\)	each operand is visited once, frequency lookup \(O(1)\)
Rematerialization per use	\(O(k \log s)\)	constant	\(O(1)\)	\(k\) operands, each an interval query over \(s\) segments
Bottom-up hoisting (Alg. 22.9.9), one value	\(O(b)\)	small (only the dom-tree paths from stores to the definition)	\(O(b)\)	each tree node visited once; the child sets are merged into the parent (small-to-large)
Go's placeSpills, one value	\(O(\min(b, 100))\)	small	\(O(1)\)	walks one dom-tree path, capped by maxSpillSearch = 100

Pathological family. Quality: a value defined in a loop of frequency \(F\) whose only reload is in a block of frequency \(\varepsilon\) inside the loop (an error path). Spilling everywhere stores after the definition, \(F\) stores per call; the placement of Definition 22.9.8 stores in the cold block, \(\varepsilon\) per call. The ratio \(F / \varepsilon\) is unbounded, which is why placement matters more than the choice of the spilled value in such code. Time: a chain-shaped dominator tree of \(b\) blocks with a store of each of \(n\) values in the deepest block makes Algorithm 22.9.9 walk \(b\) nodes per value, \(O(nb)\) in total; Go caps its walk at 100 blocks for this reason (the TODO next to maxSpillSearch).

6. Variants and refinements

Spill weights and block frequency

• Loop depth instead of frequency (\(10^{d}\), Chaitin [Cha82]; the lab uses it). Trade-off: no profile or branch probabilities needed; wrong for loops with rare bodies.
• Profile-guided frequencies (PGO, -fprofile-use): the same formula with measured frequencies. Trade-off: better decisions, needs a training run.
• Area-based metrics (HotSpot's LRG::score, Lesson 22.3 §7) and best-of-three simplification [BGG+89]. Trade-off: extra compile time.

Rematerialization

• Briggs–Cooper–Torczon rematerialization [BCT92]: propagate a "rematerializable instruction" tag through SSA with a sparse constant-propagation-like analysis, split each live range where its tag changes, and let the Chaitin–Briggs allocator spill the pieces separately (recomputing the tagged pieces). Trade-off: more live ranges and copies, in exchange for recomputing even parts of phi-merged values.
• GCC LRA's rematerialization sub-pass (gcc/lra-remat.cc): a dataflow analysis of available candidate instructions over the CFG, excluding instructions with memory operands [GCC-LRARemat]. Trade-off: finds recomputations after reload, costs a global dataflow pass.
• Rematerialization through copies: LLVM follows lr-split copies back to the original definition. Trade-off: splitting does not hide rematerialization opportunities.

Spill-code placement

• Shrink-wrapping places callee-saved saves and restores, the same problem for the save of a register that is used only on some paths [Cho88]. Trade-off: better fast paths; the prologue is no longer a single block (LLVM ShrinkWrap).
• Region-based placement: move spill code to the borders of loops and regions (Callahan–Koblenz [CK91], GCC IRA, fusion-based allocation [LGA00]). Trade-off: more copies at region borders.
• Optimal placement by ILP (Lesson 22.7) [AG01]. Trade-off: optimal stores and loads, solver time.

7. In real compilers

CalcSpillWeights.cpp computes Definition 22.9.1 when greedy starts and after each split (VirtRegAuxInfo::calculateSpillWeightAndHint) [LLVM-SpillWeights]; InlineSpiller.cpp performs Algorithm 22.9.7 (reMaterializeAll, reMaterializeFor, spillAroundUses) and, after allocation, Algorithm 22.9.9 (HoistSpillHelper::hoistAllSpills, runHoistSpills) [LLVM-InlineSpiller]. Go's SSA back end rematerializes in allocValToReg and places spills in placeSpills [Go-regalloc]. GCC's LRA recomputes in lra-remat.cc [GCC-LRARemat].

Spill weights and block frequency

Spill costs are frequency-weighted: -pass-remarks-missed=regalloc

Reproduce (clang-23 / llc 23.1.2; remat.c is press.c from Lesson 22.3 with the call replaced by a[i] = x * 0x123456789abcL):

clang-23 --target=x86_64-linux-gnu -O2 -fno-unroll-loops -fno-vectorize -fno-slp-vectorize \
  -S -emit-llvm remat.c -o remat.ll
llc -O2 -pass-remarks-missed=regalloc remat.ll -o /dev/null
llc -O2 -stop-after=greedy,1 remat.ll -o - | grep successors

Output (complete):

remark: <unknown>:0:0: 1 spills 2.000000e+01 total spills cost 3 folded spills 6.000000e+01 total folded spills cost 1 reloads 2.000000e+01 total reloads cost 1 folded reloads 2.000000e+01 total folded reloads cost 19 virtual registers copies 3.800000e+02 total copies cost generated in loop
remark: <unknown>:0:0: 4 spills 2.187500e+01 total spills cost 4 folded spills 6.062500e+01 total folded spills cost 2 reloads 2.062500e+01 total reloads cost 3 folded reloads 2.125000e+01 total folded reloads cost 20 virtual registers copies 3.810000e+02 total copies cost generated in function
    successors: %bb.2(0x50000000), %bb.1(0x30000000)
    successors: %bb.4(0x80000000)
    successors: %bb.5(0x80000000)
    successors: %bb.4(0x80000000)
    successors: %bb.3(0x04000000), %bb.5(0x7c000000)

What to notice: each spill instruction in the loop costs exactly 20. The loop is entered with probability \(\mathtt{0x50000000}/2^{31} = 0.625\) (n > 0) and its back edge is taken with probability \(\mathtt{0x7c000000}/2^{31} = 31/32\), so the loop body runs \(0.625 \cdot 1/(1 - 31/32) = 0.625 \cdot 32 = 20\) times per call: that is \(f(B)\) of Definition 22.9.1, not \(10^{1}\). The three spills outside the loop cost \(21.875 - 20 = 1.875\) together, \(0.625\) each: they sit in the preheader, whose frequency is the entry probability. The remark's costs are exactly the numerator \(\mathrm{UD}\) of the weights, summed over the spill code actually inserted.

Rematerialization

A spilled 64-bit constant is recomputed in the loop, not reloaded

Reproduce (llc 23.1.2; remat.ll from the previous box):

llc -O2 -stop-before=greedy,1 remat.ll -o - | grep -n 'MOV64ri\|^  bb\.[0-9]'
llc -O2 -stop-after=greedy,1 remat.ll -o - | grep -n 'MOV64ri\|^  bb\.[0-9]'
llc -O2 -stop-after=greedy,1 remat.ll -o - | grep -B1 -A1 ' = MOV64ri'
llc -O2 remat.ll -o remat.s && grep -n 'movabsq\|^\.LBB0_5\|jne' remat.s

Output (complete):

266:  bb.0 (%ir-block.2):
275:  bb.1:
281:  bb.2..preheader:
298:    %59:gr64 = MOV64ri 20015998343868
302:  bb.3 (%ir-block.4):
319:  bb.4 (%ir-block.18):
323:  bb.5 (%ir-block.20):
338:  bb.0 (%ir-block.2):
347:  bb.1:
353:  bb.2..preheader:
376:  bb.3 (%ir-block.4):
394:  bb.4 (%ir-block.18):
398:  bb.5 (%ir-block.20):
439:    %116:gr64 = MOV64ri 20015998343868
    %118:gr64 = lr-split COPY %119
    %116:gr64 = MOV64ri 20015998343868
    %60:gr64_nosp = nsw IMUL64rr %60, %116, implicit-def dead $eflags
51:.LBB0_5:                                # =>This Inner Loop Header: Depth=1
90: movabsq $20015998343868, %r8            # imm = 0x123456789ABC
102:    jne .LBB0_5

What to notice: before allocation the constant 0x123456789abc is materialized once in the preheader (bb.2, where early MachineLICM hoisted it out of the loop; -stop-before=early-machinelicm still shows it in the loop body) and its interval spans the whole loop. Under fourteen live accumulators it is the cheapest interval to give up (its weight is halved because its only definition is rematerializable, Algorithm 22.9.3). The inline spiller does not store it: it recomputes it right before its only use, the IMUL64rr in the loop body bb.5, and deletes the preheader copy (Algorithm 22.9.7). In the final code the movabsq is inside the loop (lines 51–102): ten bytes of instruction per iteration instead of a store plus a reload. Allocation undoes loop-invariant code motion exactly where registers run out.

GCC's LRA does the same after reload, from a different angle; its header comment (gcc-15.1.0, quoted, not run) says: "This code objective is to rematerialize spilled pseudo values. To do this we calculate available insn candidates. The candidate is available at some point if there is dominated set of insns with the same pattern, the insn inputs are not dying or modified on any path from the set, the outputs are not modified." and excludes "insns containing memory or spilled pseudos" [GCC-LRARemat]. That is Definition 22.9.4 as a dataflow problem.

Spill-code placement

Where Go puts a spill: sunk into the cold block, never into a loop

Reproduce (go 1.24.7 linux/amd64; sp.go below):

package sp

//go:noinline
func g(x int) int { return x + 1 }

func Sp(a []int, x int) int {
    y := x * 3
    s := 0
    for i := range a {
        s += a[i] ^ y
        if a[i] == 42 {
            s = g(s)
        }
    }
    return s + y
}

go tool compile -p sp -trimpath="$PWD" -S sp.go | sed -n '/^sp.Sp STEXT/,/morestack/p' \
  | grep -v FUNCDATA | grep -v PCDATA | sed -E 's/^\t0x[0-9a-f]+ //' | sed -n '8,34p'

Output (complete):

00014 (sp.go:9) MOVQ    BX, sp.a+48(SP)
00019 (sp.go:9) MOVQ    AX, sp.a+40(SP)
00024 (sp.go:7) LEAQ    (DI)(DI*2), CX
00028 (sp.go:7) MOVQ    CX, sp.y+8(SP)
00033 (sp.go:7) XORL    DX, DX
00035 (sp.go:7) XORL    SI, SI
00037 (sp.go:9) JMP 42
00039 (sp.go:9) INCQ    DX
00042 (sp.go:9) CMPQ    BX, DX
00045 (sp.go:9) JLE 108
00047 (sp.go:10)    MOVQ    (AX)(DX*8), DI
00051 (sp.go:10)    MOVQ    DI, R8
00054 (sp.go:10)    XORQ    CX, DI
00057 (sp.go:10)    ADDQ    DI, SI
00060 (sp.go:10)    NOP
00064 (sp.go:11)    CMPQ    R8, $42
00068 (sp.go:11)    JNE 39
00070 (sp.go:9) MOVQ    DX, sp.i+16(SP)
00075 (sp.go:12)    MOVQ    SI, AX
00078 (sp.go:12)    CALL    sp.g(SB)
00083 (sp.go:10)    MOVQ    sp.y+8(SP), CX
00088 (sp.go:9) MOVQ    sp.i+16(SP), DX
00093 (sp.go:9) MOVQ    sp.a+48(SP), BX
00098 (sp.go:15)    MOVQ    AX, SI
00101 (sp.go:10)    MOVQ    sp.a+40(SP), AX
00106 (sp.go:12)    JMP 39
00108 (sp.go:15)    LEAQ    (CX)(SI*1), AX

What to notice: all Go registers are caller-saved, so y, i and the slice a must be in memory across the call to g, and every restore is in the call block (offsets 83–101). i is defined in the loop header (it is a phi), and placeSpills sinks its store down the dominator tree into the call block itself (offset 70): the store runs only when a[i] == 42. y is defined before the loop; the call block is also the deepest block dominating its restores, but it is inside the loop, and placeSpills never moves a store into a deeper loop, so y is stored once, right after its definition (offset 28). The slice header a is an argument and is stored at entry. Two rules of §2, visible in 27 lines: stores dominate their restores, and are placed where they execute least often.

LLVM reaches a similar result on the same shape (press.c, Lesson 22.8 §3) by region splitting before spilling and by hoisting after it: in the llc -O2 output the spill code for the values that cross the call is in the call block .LBB0_7 (1 store, 3 reloads), not around the definitions (Lesson 22.8 §7 shows the split MIR).

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Spill weights and block frequency	ranks candidates by expected spill cost per unit of pressure	linear · negligible	only as good as the frequency estimate	small (formula) plus block frequency analysis	LLVM (CalcSpillWeights), GCC IRA costs, every allocator's spill choice
Rematerialization	removes stores and reloads of recomputable values	per use, constant · negligible	a spilled constant costs one ALU instruction per use	moderate (availability checks)	LLVM InlineSpiller, GCC lra-remat, Go, HotSpot C2
Spill-code placement	stores where they execute least often; optimal per value on the tree	linear per value · small	fewer executed stores on cold paths and outside loops	moderate	LLVM HoistSpillHelper, Go placeSpills, V8 deferred spills

Choose frequency-based weights whenever branch probabilities are available (they always are in LLVM; with PGO they are measured). Always rematerialize constants and addresses; recompute more complex instructions only when their operands are live anyway. Place stores by the dominator-tree recurrence (hoisting, LLVM) or by sinking toward the restores (Go); both beat storing after every definition when the reloads are on cold paths.

9. Assessment

• Quiz (./course quiz 22): spill-weight-running, loop-frequency, remat-when, find-remat, hoist-dp, go-spill-sink (tags spill-weights, remat, spill-placement).
• Drill: none (see the tip in §3); the quiz's computation questions use the recurrence of Algorithm 22.9.9 and the formula of Definition 22.9.1 on fresh instances.
• Flashcards: tags spill-weights, remat, spill-placement.
• Lab: the lab's allocators spill everywhere, so their --metrics spill cost is \(\sum \mathrm{UD}\) over spilled values with \(f = 10^{d}\) (Proposition 22.9.2); exercise E5 asks you to estimate what rematerialization and placement would save on the corpus.

References

See the chapter references.