Lesson 22.6 — SSA-based allocation: chordal graphs, MaxLive, decoupled spilling¶

Techniques: chordal colouring in dominance order; decoupled spilling (MaxLive-driven); allocation before SSA destruction (phis as parallel copies of registers) · Lab: labs/ch22-regalloc E4 (allocateSSA) · Prerequisites: Lesson 22.1 (Lemma 22.1.11, MaxLive), Lesson 22.3, Ch 15 (dominator tree), Lesson 16.7 (parallel copies) · Time: 4–5 hours

Chaitin's allocators leave SSA first and then face an NP-complete colouring problem (Theorem 22.3.6). In 2005–2006 three groups noticed, independently, that if one allocates before leaving SSA the problem changes character: the interference graph of a strict SSA program is chordal, and chordal graphs are coloured optimally, in linear time, by a greedy walk [HGG06, BDMS05, BDGR06]. The number of colours needed is exactly MaxLive, so the two hard questions of allocation separate: spilling (lower the pressure to \(K\) everywhere; still NP-complete) and colouring (then always possible with \(K\) registers, no further spill). The phis left over are parallel copies between registers, which the edge-copy techniques of Chapter 16 implement. This lesson proves the chordality theorem, traces the colouring in dominance order and discusses the spilling and destruction steps.

1. Problem and motivation¶

Input: a strict SSA function, \(K\) registers per class. Output: a set of values to spill (with their spill code), a colouring of the rest with at most \(K\) colours, and the copies that implement the phis. Goal: few executed spill instructions and few copies.

Chordal colouring in dominance order¶

Hack, Grund and Goos proved that SSA interference graphs are chordal and that visiting the definitions in an order compatible with dominance yields a perfect elimination order, so greedy colouring in that order is optimal [HGG06]. Brisk et al. [BDMS05] and Bouchez et al. [BDGR06] reached the same conclusion; Pereira and Palsberg observed at the same time (2005) that most interference graphs of Java methods are chordal, SSA or not [PP05]. Chordal graphs were well understood: Gavril showed in 1972 how to colour them optimally in linear time [Gav72].

Decoupled spilling (MaxLive-driven)¶

Because the colouring step never spills when \(\mathrm{MaxLive} \le K\), spilling can run first, on its own: reduce the register pressure at every point to \(K\), then colour. This decoupled design avoids Chaitin's iterate-until-no-spill loop. Hack's allocator and libFirm use a global version of Belady's rule for the spilling phase [BH09]; the lab's E4 uses a simpler greedy (§2).

Allocation before SSA destruction¶

After colouring, each phi is still a parallel copy on each incoming edge, now between registers. Implemented as in Lesson 16.7, a parallel copy of registers needs at most one scratch register (or swap instructions), and the copies whose source and destination got the same register disappear: choosing colours that match across phis is coalescing on a chordal graph, which is polynomial for one affinity at a time [BDR07]. Cranelift's regalloc2 takes SSA with block parameters as input and emits these moves itself [RA2-Design].

2. Definitions and algorithms¶

Chordal colouring in dominance order¶

Definition 22.6.1 (Chordal graph, perfect elimination order)

A graph is chordal if every cycle of length \(\ge 4\) has a chord (an edge between two nodes of the cycle that are not consecutive on it). An ordering \(v_1, \dots, v_n\) of the nodes is a perfect elimination order (PEO) if for every \(i\), the neighbours of \(v_i\) among \(v_{i+1}, \dots, v_n\) form a clique.

Theorem 22.6.2 (Greedy colouring along a reversed PEO is optimal)

Let \(v_1, \dots, v_n\) be a PEO of \(G\). Colouring \(v_n, v_{n-1}, \dots, v_1\) in this order, each with the lowest colour not used by its already coloured neighbours, uses exactly \(\omega(G)\) colours. Moreover a graph has a PEO if and only if it is chordal [FG65]; hence \(\chi(G) = \omega(G)\) for chordal graphs.

Proof (the characterization: [FG65, Gav72])

When \(v_i\) is coloured, its coloured neighbours are among \(v_{i+1}, \dots, v_n\), which by the PEO property form a clique \(C\). \(C \cup \{v_i\}\) is a clique of \(G\), so \(\lvert C \rvert \le \omega(G) - 1\), and one of the colours \(0, \dots, \omega(G) - 1\) is free. So at most \(\omega(G)\) colours are used, and at least \(\omega(G)\) are needed for the largest clique. The equivalence "PEO exists ⇔ chordal" (Fulkerson and Gross) is only needed for the name; the SSA argument below constructs the order directly.

Lemma 22.6.3 (Interfering SSA values are ordered by dominance)

In a strict SSA function, if \(u \mathbin{\text{—}} v\) then \(\mathrm{def}(u)\) dominates \(\mathrm{def}(v)\) or \(\mathrm{def}(v)\) dominates \(\mathrm{def}(u)\) (as program points: the two definitions may be in the same block, and a block's phis are defined at its start).

Proof

By Theorem 22.1.12 there are three cases. If both are live at some point, Lemma 22.1.11 gives the dominance relation between their definitions. If \(u\) is defined at a point \(p\) where \(v\) is live, then \(\mathrm{def}(v)\) dominates \(p = \mathrm{def}(u)\), because in a strict program a value is live only at points its definition dominates (first step of the proof of Lemma 22.1.11). Values defined at the same point (the arguments, the phis of one block) dominate each other in the sense of program points.

Definition 22.6.4 (Dominance order of definitions)

A dominance order lists all values such that whenever \(\mathrm{def}(u)\) strictly dominates \(\mathrm{def}(v)\), \(u\) comes before \(v\). The preorder walk of the dominator tree, listing in each block first its phis, then its instructions in order, is one (the arguments come first).

Theorem 22.6.5 (SSA interference graphs are chordal [HGG06, BDMS05, BDGR06])

Let \(F\) be strict SSA and \(v_1, \dots, v_n\) a dominance order of its values. For every \(i\), the neighbours of \(v_i\) among \(v_1, \dots, v_{i-1}\) form a clique of \(G_I\). Consequently the reverse order \(v_n, \dots, v_1\) is a PEO, \(G_I\) is chordal, and \(\chi(G_I) = \omega(G_I) = \mathrm{MaxLive}\).

Proof

Let \(w\) be a neighbour of \(v_i\) that comes earlier in the order. By Lemma 22.6.3 their definitions are ordered by dominance, and since \(w\) comes first, \(\mathrm{def}(w)\) dominates \(\mathrm{def}(v_i)\). If both are defined at the same point \(p\) (arguments, phis of one block), \(w \in \mathrm{defs}(p)\). Otherwise \(\mathrm{def}(w)\) strictly dominates \(\mathrm{def}(v_i)\), and \(w \in \mathrm{live}(p)\) for the definition point \(p\) of \(v_i\): by Theorem 22.1.12 either both are live at some point, and Lemma 22.1.11 puts \(w\) in \(\mathrm{live}(p)\); or one is defined where the other is live, and it cannot be \(w\) (then \(\mathrm{def}(v_i)\) would dominate \(\mathrm{def}(w)\)), so \(v_i\) is defined at \(p\) with \(w\) live there. So every earlier neighbour of \(v_i\) lies in \(\mathrm{defs}(p) \cup \mathrm{live}(p)\), which is a clique (Proposition 22.1.15). The earlier neighbours of \(v_i\) therefore form a clique: in the reversed order \(v_n, \dots, v_1\), the neighbours of \(v_i\) that come after it are exactly these, which is the PEO property. By Theorem 22.6.2, \(\chi(G_I) = \omega(G_I)\). Finally \(\omega(G_I) = \mathrm{MaxLive}\): every set \(\mathrm{defs}(p) \cup \mathrm{live}(p)\) is a clique (so \(\omega \ge \mathrm{MaxLive}\)), and the largest clique \(Q\) is contained in such a set: let \(v\) be the last member of \(Q\) in the dominance order; all other members are earlier neighbours of \(v\), hence in \(\mathrm{defs}(p) \cup \mathrm{live}(p)\) for \(v\)'s point \(p\), and \(v \in \mathrm{defs}(p)\) (so \(\omega \le \mathrm{MaxLive}\)).

Algorithm 22.6.6 (Colouring in dominance order)

Input: a strict SSA function in which \(\mathrm{MaxLive}_c \le K_c\) for every class \(c\) (after spilling); \(\mathrm{live\text{-}in}(B)\) for every block.
Output: a colour in \(\{0, \dots, K_c - 1\}\) for every value of class \(c\).
Precondition: strict SSA; every block reachable.
Postcondition: interfering values have different colours; at most MaxLive colours are used (Theorem 22.6.7).
Invariant: at every point of the walk, taken is exactly the set of colours of the values live at that point (plus those just defined there).

function ColourDominance(F):
    colour the arguments 0, 1, 2, … in order
    for each block B in preorder of the dominator tree:
        taken ← { col[v] | v ∈ live-in(B) }                   # all dominate B: already coloured
        for each phi φ of B: col[φ] ← min(ℕ \ taken); taken ← taken ∪ {col[φ]}
        for each phi φ of B not used in B and not live-out: taken ← taken \ {col[φ]}
        for each instruction I of B in order:
            for each operand u of I whose last use in B is I and u ∉ live-out(B):
                taken ← taken \ {col[u]}                       # read before write
            if I defines d:
                col[d] ← min(ℕ \ taken); taken ← taken ∪ {col[d]}
                if d is dead: taken ← taken \ {col[d]}
    return col

Biased choice: if a phi partner's colour is free, take it instead of the minimum (this keeps the colour count bound, since any free colour will do). In the allocator, spilling (Algorithm 22.6.9 below) runs first.

Theorem 22.6.7 (Dominance-order colouring is optimal and never spills)

Algorithm 22.6.6 gives interfering values different colours and uses at most MaxLive colours per class. In particular, after a sufficient spill (Definition 22.6.8), it colours every remaining value with at most \(K_c\) colours.

Proof

Invariant. At the start of \(B\), the values live are \(\mathrm{live\text{-}in}(B)\); each is defined at a point dominating \(B\)'s start, hence in a block visited earlier in the dominator preorder (or earlier in \(B\)'s dominator chain), so it already has a colour, and taken is set to their colours. Phis are defined at the block start and get free colours. Walking the instructions, a colour is released exactly when its value stops being live (its last use in \(B\), and it is not live-out), and added when a value is defined: so taken is always the set of colours of the values live at the current point, plus the one just defined. Distinct colours. If \(u \mathbin{\text{—}} v\), one of them, say \(v\), is defined at a point where the other is live or defined (Definition 22.1.5); when \(v\) is coloured, \(u\) is live there, so \(\mathrm{col}(u) \in\) taken and \(v\) receives a different colour. (If both are phis of one block or arguments, they are coloured one after the other with the earlier one's colour taken.) Colour count. At the definition point \(p\) of \(v\), taken holds the colours of \((\mathrm{defs}(p) \cup \mathrm{live}(p)) \setminus \{v\}\) as far as already coloured: at most \(P(p) - 1 \le \mathrm{MaxLive} - 1\) colours. So \(\mathrm{min}(\mathbb{N} \setminus \texttt{taken}) \le \mathrm{MaxLive} - 1\). After a sufficient spill, the MaxLive of the remaining values is at most \(K_c\), and removing values from an SSA program's graph keeps it an induced subgraph, to which the same argument applies (Proposition 22.6.10).

Decoupled spilling (MaxLive-driven)¶

Definition 22.6.8 (Spill-everywhere, pressure after spilling)

Spilling a set \(S \subseteq V\) everywhere keeps every \(v \in S\) in memory for its whole life (reloaded before each use through a register outside the \(K\), as in the lab's model; or into a register for a one-instruction live range in production allocators). The pressure after spilling is \(P^S_c(p) = \lvert \{ v \in (\mathrm{defs}(p) \cup \mathrm{live}(p)) \setminus S \mid \mathrm{cls}(v) = c \} \rvert\). \(S\) is sufficient if \(P^S_c(p) \le K_c\) for every point \(p\) and class \(c\). The spill cost of \(S\) is \(\sum_{v \in S} \mathrm{cost}(v)\) (Definition 22.3.2).

Algorithm 22.6.9 (Greedy MaxLive-driven spilling, the lab's E4)

Input: the points \(\mathcal{P}\) with their sets \(\mathrm{defs}(p) \cup \mathrm{live}(p)\); spill costs; \(K_c\).
Output: a sufficient spill set \(S\).
Precondition: none.
Postcondition: \(P^S_c(p) \le K_c\) for all \(p\), \(c\).
Invariant: excess[p] \(= \max(0, P^S_c(p) - K_c)\) for the current \(S\).

function SpillToPressure(points, cost, K):
    S ← ∅
    excess[p] ← max(0, P(p) − K) for each point p
    while some excess[p] > 0:
        v ← argmax over v ∉ S of |{ p | v present at p, excess[p] > 0 }| / cost(v)
        S ← S ∪ {v}
        for each p where v is present and excess[p] > 0: excess[p] ← excess[p] − 1
    return S

Braun and Hack's spiller instead walks the blocks and applies Belady's rule (Algorithm 22.2.2) inside each block, choosing at block entries which values to keep in registers from the predecessors' states and loop-aware next-use distances [BH09]. Their values can be in a register for part of their life and in memory for another part, which the whole-value location of the lab cannot express.

Proposition 22.6.10 (Spilling preserves the structure)

For any \(S \subseteq V\), the interference graph of the values \(V \setminus S\) (with the spill-everywhere model) is the induced subgraph \(G_I[V \setminus S]\); it is chordal, and its MaxLive is \(\max_p P^S(p)\).

Proof

Spilling everywhere does not change the liveness of the other values (the reloads use scratch registers outside the \(K\)), so their definition points and live sets are unchanged, minus the spilled values: interference among them is unchanged. Induced subgraphs of chordal graphs are chordal (a chordless cycle in the subgraph would be one in \(G\)), and the pressure at each point counts only the remaining values.

Theorem 22.6.11 (Spilling is still NP-complete on SSA)

Deciding whether some set \(S\) with total cost at most \(C\) is sufficient (Definition 22.6.8) is NP-complete for SSA programs, even with unit costs [BDR07b]. Optimal coalescing of the phi-related values under a colouring with \(K\) colours is NP-complete too [BDR07].

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

Membership in NP: check \(P^S(p) \le K\) at every point. For hardness, Bouchez, Darte and Rastello reduce known NP-complete problems to spill everywhere on programs in SSA form (whose interference graphs are chordal, and interval graphs for straight-line code), and they delimit which restrictions of the problem (number of registers, costs, program shape) become polynomial [BDR07b]. The coalescing statement is Theorem 22.4.11 [BDR07].

Allocation before SSA destruction¶

Theorem 22.6.12 (Phis become register permutations)

Let every value be coloured by Algorithm 22.6.6. On each edge \(P \to B\), the phis of \(B\) define a parallel copy \((r_{\varphi_1}, \dots, r_{\varphi_m}) \gets (r_{a_1}, \dots, r_{a_m})\) among registers (spilled operands and phis become loads and stores). Its destinations are distinct, and no destination is the register of a value live-in to \(B\). It can be implemented with at most (number of non-trivial copies + number of cycles) moves using one register not live on the edge, or with swaps and no extra register.

Proof

The destinations are distinct because the phis of \(B\) pairwise interfere (they share the block-entry point). A value \(w\) live-in to \(B\) interferes with every phi of \(B\), so its register is no phi's destination: the copy does not overwrite live values. The sources are live at the end of \(P\) and readable. The move count and the one-temporary / swap implementations are Lesson 16.7, Theorem 16.7.6 applied to a parallel copy whose locations are registers. A register not live on the edge exists whenever the pressure on the edge is below \(K\); otherwise swaps (x86 xchg) or a stack temporary are used.

3. Worked example¶

Chordal colouring in dominance order¶

The running example's dominator tree is the chain B0 → B1 → {B2, B3} (B1 dominates both), so the preorder is B0, B1, B2, B3. MaxLive = 4 (at c = lt i 10). A dominance order of the values: a, i, s, c, t, u, s2, i2, r. Checking Theorem 22.6.5: the earlier neighbours of c are a, i, s (a clique); of t: a, i (adjacent); of i2: a, s2 (adjacent). Colouring with \(K = 4\) (regalloc.ssa_color):

block	at	freed first	colour	taken after
B0	`a = arg`	—	a → 0	{0}
B1	`i = phi …`	(live-in {a} → taken {0})	i → 1	{0, 1}
B1	`s = phi …`	—	s → 2	{0, 1, 2}
B1	`c = lt i 10`	— (`i` is live-out)	c → 3	{0, 1, 2, 3}
B2	`t = mul s i`	s (last use; live-in {a, i, s} → taken {0, 1, 2})	t → 2	{0, 1, 2}
B2	`u = add t a`	t	u → 2	{0, 1, 2}
B2	`s2 = xor u i`	u	s2 → 2	{0, 1, 2}
B2	`i2 = add i 1`	i	i2 → 1	{0, 1, 2}
B3	`r = add s a`	a, s (live-in {a, s} → taken {0, 2})	r → 0	{0}

Four colours = MaxLive. In B1, c is not freed after c = lt i 10 because the branch uses it; it is not live-in to B2 or B3, so it disappears from taken at their starts. s2 got the same colour as s (2) and i2 the same as i (1) without any coalescing effort: the back-edge copies vanish. Only s ← a (0 → 2) on the entry edge remains.

Try it

./course drill ssa-coloring --seed 5 --difficulty hard --solution asks for MaxLive, the dominator-tree preorder and every colour.

Decoupled spilling (MaxLive-driven)¶

With \(K = 3\) the only over-full point is c = lt i 10, with \(\{a, c, i, s\}\) (\(P = 4\), excess 1). Algorithm 22.6.9 compares 1/cost for the four candidates: a 1/13, c 1/20, s 1/21, i 1/50: spill a. Now the pressure is at most 3 everywhere and Algorithm 22.6.6 colours without spilling: i 0, s 1, c 2 in B1; in B2 t, u, s2 1 (after s dies) and i2 0; r 0 in B3. The phi copies of the back edge are again trivial; s ← a becomes a load of a on the entry edge. This matches graph colouring (Lesson 22.3), which also spilled a, but without iterating.

Allocation before SSA destruction¶

With the \(K = 4\) colouring above, the parallel copies are: on B0 → B1, (r1, r2) ← (0, r0) (i ← 0, s ← a), implemented as r1 ← 0; r2 ← r0; on B2 → B1, (r1, r2) ← (r1, r2): both trivial, no code. In LLVM terms the loop has no copies at all, exactly what the greedy allocator produced in Lesson 22.2's -O2 listing.

4. Invariants and correctness¶

Chordal colouring in dominance order¶

Theorems 22.6.5 and 22.6.7 in §2. The invariant of Algorithm 22.6.6 ("taken = colours of the values live now") is what makes the colour count exact.

Chordality needs strictness, and copies spoil nothing but it

The theorem uses strict SSA: every use dominated by its definition. Outside SSA, or after copy propagation merges the names of an SSA program, the graph can contain chordless cycles (Chaitin's construction produces any graph). Inserting copies keeps a program in SSA and keeps the graph chordal; coalescing the copies (merging names) can destroy chordality, which is why SSA allocators colour first and coalesce by recolouring [Hack07].

Decoupled spilling (MaxLive-driven)¶

Algorithm 22.6.9 terminates because each iteration adds a value to \(S\) and there are finitely many; it ends only when no point has excess, which is the postcondition. It is a heuristic for an NP-complete problem (Theorem 22.6.11).

Allocation before SSA destruction¶

Theorem 22.6.12, together with Theorem 22.1.14 (the register-file semantics), shows that the coloured program with parallel copies on its edges computes what the SSA program computes; the lab's rewriter executes exactly this.

5. Complexity¶

\(n\) values, \(N\) instructions, \(b\) blocks, \(L\) = maximum live-set size, \(\lvert\mathcal{P}\rvert = O(N)\) points.

Algorithm	Time (worst)	Time (typical)	Space	Justification
Liveness	as Ch 14	2–3 passes, or fast SSA liveness checks [BHG+08]	\(O(b \cdot n)\) bits
Colouring in dominance order	\(O(N \cdot K)\), or \(O(N + n)\) with a free-colour list	linear	\(O(K)\)	each instruction frees and takes a constant number of colours; finding the minimum free colour costs \(O(K)\) or \(O(1)\) with a bitmask
Greedy spilling (Algorithm 22.6.9)	\(O(n \cdot \lvert\mathcal{P}\rvert \cdot L)\)	fast (few over-full points)	\(O(\lvert\mathcal{P}\rvert L)\)	\(\le n\) iterations, each scoring every value over its points
Belady-based spilling [BH09]	\(O(N \cdot K \log K)\) per pass	linear	\(O(N)\) next-use distances	one walk per block with a sorted workset
Optimal spilling	NP-complete (Theorem 22.6.11)	—	—	[BDR07b]
Phi copies	\(O(\sum_{\text{edges}} m)\)	linear	\(O(K)\)	Lesson 16.7

Pathological family. Colouring cannot go wrong (it is optimal), but spilling can: a loop with \(K + 1\) values live around it and one short value that is used at every iteration has MaxLive \(K + 2\) at its uses. Spilling any of the \(K + 1\) long values everywhere costs a load per use per iteration; Algorithm 22.6.9 chooses by cost/pressure points, while spilling the long value only outside the loop's hot path (a partial spill, which spill-everywhere cannot express) would cost nothing in the loop. This is why production SSA allocators split live ranges at loop boundaries before or during spilling [BH09].

Chordal colouring in dominance order¶

Recolouring for coalescing. After colouring, change colours to satisfy phi affinities while keeping a valid colouring [Hack07]; incremental conservative coalescing on chordal graphs is polynomial [BDR07]. Trade-off: fewer copies, more compile time.
Register constraints. Pre-coloured operands break chordality at instructions with constraints; Hack handles them by splitting all live values around such instructions with a parallel copy [Hack07]. Trade-off: correctness for irregular ISAs at the price of copies.
Colouring interval graphs of a single block with Proposition 22.5.5 is the special case where the dominator tree is a path.

Decoupled spilling (MaxLive-driven)¶

Belady across blocks (Braun–Hack) [BH09]: global next-use distances with loops weighted as far away. Trade-off: near-optimal spills, needs careful handling of block entries.
Optimal spilling by ILP on SSA with the MaxLive constraint per point [AG01] (Lesson 22.7). Trade-off: optimal, slow.

Allocation before SSA destruction¶

Block parameters instead of phis (Cranelift, MLIR): the same parallel copies, attached to branch instructions (Lesson 16.5).
Destroy SSA first, allocate after (LLVM, GCC): simpler interfaces between passes, gives up chordality; LLVM's coalescer then recovers most copies aggressively (Lesson 22.4).

7. In real compilers¶

Chordal colouring in dominance order¶

libFirm (the research compiler behind the cparser C compiler, from Karlsruhe, where Hack's work was done) allocates on SSA: be_ra_chordal_color in ir/be/bechordal.c (libfirm-1.22.0) walks the dominator tree twice, once to compute pressure "borders" and once to assign colours [Firm-Chordal]. No mainstream production compiler uses chordal colouring as its main allocator; LLVM and GCC leave SSA before allocating.

libFirm's chordal allocator: colour along the dominator tree

Reproduce (libFirm tag libfirm-1.22.0; curl reads the pinned source):

curl -s https://raw.githubusercontent.com/libfirm/libfirm/libfirm-1.22.0/ir/be/bechordal.c \
  | sed -n '356,359p;393,411p'

Output (complete):

    /* Mind that the sequence of defs from back to front defines a perfect
     * elimination order. So, coloring the definitions from first to last
     * will work. */
static void be_ra_chordal_color(be_chordal_env_t *const chordal_env)
{
    ir_graph *const irg = chordal_env->irg;
    assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
    be_assure_live_sets(irg);

    /* Handle register targeting constraints */
    be_timer_push(T_CONSTR);
    dom_tree_walk_irg(irg, constraints, NULL, chordal_env);
    be_timer_pop(T_CONSTR);

    be_chordal_dump(BE_CH_DUMP_CONSTR, irg, chordal_env->cls, "constr");

    /* First, determine the pressure */
    dom_tree_walk_irg(irg, create_borders, NULL, chordal_env);

    /* Assign the colors */
    dom_tree_walk_irg(irg, assign, NULL, chordal_env);
}

What to notice: the comment is Theorem 22.6.5 ("the sequence of defs from back to front defines a perfect elimination order") and the three dom_tree_walk_irg calls are Algorithm 22.6.6 over the dominator tree, preceded by the constraint handling of §6 (splitting around pre-coloured operands). libFirm has no packaged binary here, so the source is quoted.

Decoupled spilling (MaxLive-driven)¶

libFirm's default spiller is Belady-based (ir/be/bespillbelady.c, displace): it computes next-use distances for the values in the current "workset" (the values in registers) and spills those used furthest away until the pressure fits [Firm-Belady]. Go's allocator uses the same rule (Lesson 22.2), but interleaved with assignment rather than decoupled.

libFirm's Belady spiller

Reproduce (libFirm tag libfirm-1.22.0):

curl -s https://raw.githubusercontent.com/libfirm/libfirm/libfirm-1.22.0/ir/be/bespillbelady.c \
  | sed -n '6,10p;337,352p'

Output (complete):

/**
 * @file
 * @brief       Beladys spillalgorithm.
 * @author      Daniel Grund, Matthias Braun
 * @date        20.09.2005

        /* calculate current next-use distance for live values */
        for (unsigned i = 0; i < len; ++i) {
            ir_node  *val  = workset_get_val(ws, i);
            unsigned  dist = get_distance(instr, val, !is_usage);
            workset_set_time(ws, i, dist);
        }

        /* sort entries by increasing nextuse-distance*/
        workset_sort(ws);

        for (int i = len - spills_needed; i < (int)len; ++i) {
            ir_node *val = ws->vals[i].node;

            DB((dbg, DBG_DECIDE, "    disposing node %+F (%u)\n", val,
                workset_get_time(ws, i)));

What to notice: the workset holds at most \(K\) values (the registers); before an instruction that needs spills_needed more registers, the values are sorted by next-use distance and the last spills_needed (furthest next use) are displaced: Algorithm 22.2.2 applied to reduce the pressure to \(K\), before and independently of colouring.

Allocation before SSA destruction¶

Cranelift's regalloc2 takes SSA input: "regalloc2 takes an SSA IR as input" with block parameters, and emits the moves for block parameters and splits itself (doc/GENERAL.md and src/ion/, regalloc2 0.15.2) [RA2-Design]. Its allocator is a backtracking allocator ported from IonMonkey rather than chordal colouring, but it shares the structure of this lesson's pipeline: SSA in, registers and edge moves out.

Cranelift 0.134 (regalloc2 0.15.2): block parameters become edge moves

Reproduce (a Rust program that calls cranelift_codegen 0.134.0 on CLIF text and prints the post-allocation VCode; source: clifra/src/main.rs below; rustc 1.94.1):

cargo new clifra && cd clifra
cat >> Cargo.toml <<'EOF'
cranelift-codegen = { version = "=0.134.0", default-features = false, features = ["std", "x86", "arm64", "host-arch"] }
cranelift-reader = "=0.134.0"
target-lexicon = "0.13"
EOF
cat > src/main.rs <<'EOF'
use cranelift_codegen::{control::ControlPlane, isa, settings, settings::Configurable, Context};
use std::{io::Read, str::FromStr};
fn main() {
    let triple = std::env::args().nth(1).unwrap_or_else(|| "x86_64".to_string());
    let mut src = String::new();
    std::io::stdin().read_to_string(&mut src).unwrap();
    let mut flags = settings::builder();
    flags.set("opt_level", "speed").unwrap();
    let isa = isa::lookup(target_lexicon::Triple::from_str(&triple).unwrap()).unwrap()
        .finish(settings::Flags::new(flags)).unwrap();
    for f in cranelift_reader::parse_functions(&src).unwrap() {
        let mut ctx = Context::for_function(f);
        ctx.set_disasm(true);
        let code = ctx.compile(&*isa, &mut ControlPlane::default()).unwrap();
        print!("{}", code.vcode.as_ref().unwrap());
    }
}
EOF
cat > loop.clif <<'EOF'
function %run(i64) -> i64 {
block0(v0: i64):
    v1 = iconst.i64 0
    jump block1(v1, v0)

block1(v2: i64, v3: i64):
    v10 = iconst.i64 10
    v4 = icmp slt v2, v10
    brif v4, block2, block3

block2:
    v5 = imul v3, v2
    v6 = iadd v5, v0
    v7 = bxor v6, v2
    v11 = iconst.i64 1
    v8 = iadd v2, v11
    jump block1(v8, v7)

block3:
    v9 = iadd v3, v0
    return v9
}
EOF
cargo run -q --release -- aarch64 < loop.clif

Output (complete):

block0:
  movz x2, #0
  mov x5, x0
  b label1
block1:
  subs xzr, x2, #10
  b.lt label3 ; b label2
block2:
  add x0, x5, x0
  ret
block3:
  add x12, x2, #1
  madd x13, x5, x2, x0
  eor x5, x13, x2
  mov x2, x12
  b label1

What to notice: the running example in CLIF: block1(v2, v3) are the phis i and s, and jump block1(v8, v7) is the back-edge parallel copy. regalloc2 gave v3 (s) and v7 (s2) the same register x5, so that copy vanished (Theorem 22.6.12, trivial copy), but put v8 (i2) in x12 and v2 (i) in x2, so one mov x2, x12 remains: i2 is computed (add x12, x2, #1) while i is still needed by madd, the scheduling order in Cranelift puts the increment first. The entry edge copies i ← 0 and s ← a are movz x2, #0 and mov x5, x0 (a stays in x0, the argument register). VCode numbers blocks in layout order, so block2/block3 here are CLIF's block3/block2.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Chordal colouring in dominance order	optimal: MaxLive colours (Theorem 22.6.7); needs strict SSA	\(O(N)\) · as fast as linear scan	no spills beyond what spilling decided; copies depend on biased choice/recolouring	small (after liveness and a dominator tree)	libFirm; the lab's E4
Decoupled spilling (MaxLive-driven)	heuristic for an NP-complete problem; exact target (pressure \(\le K\))	linear to quadratic	good with Belady-style global rules [BH09]; spill-everywhere is coarse	moderate	libFirm, Hack's allocator, the lab's E4
Allocation before SSA destruction	phis become register permutations; no out-of-SSA pass before RA	linear	copies only where colours differ	moderate (parallel copies, Lesson 16.7)	regalloc2 (Cranelift), libFirm, Graal SSA LSRA

Measured in the lab (ch22-compare, \(K = 4\)): SSA colouring spills 2528 values with the lowest weighted spill cost of the four allocators (68351) and leaves 758 moves (weighted 6365); with \(K \ge\) MaxLive it provably spills nothing on call-free functions, which the test SSAOptimal.NoSpillAtMaxLive checks on 100 random programs.

Choose SSA-based allocation when your IR stays in SSA until allocation and you want an optimal colouring step with a clean separation of spilling from assignment. Keep a classic pipeline when the IR leaves SSA early (LLVM MIR) or register constraints are pervasive.

9. Assessment¶

Quiz (./course quiz 22): ssa-chordal-why, ssa-color-trace, decoupled-spill-choice, maxlive-after-spill, phi-permutation, ssa-input-allocator (tags chordal, decoupled-spilling, ssa-destruction-after-ra).
Drill: ./course drill ssa-coloring (MaxLive, dominator-tree order, colours); ./course drill interference-graph (MaxLive).
Flashcards: tags chordal, decoupled-spilling, ssa-destruction-after-ra.
Lab: E4 allocateSSA (SPEC R9–R10).

References¶

See the chapter references.

Lesson 22.6 — SSA-based allocation: chordal graphs, MaxLive, decoupled spilling¶

1. Problem and motivation¶

Chordal colouring in dominance order¶

Decoupled spilling (MaxLive-driven)¶

Allocation before SSA destruction¶

2. Definitions and algorithms¶

Chordal colouring in dominance order¶

Decoupled spilling (MaxLive-driven)¶

Allocation before SSA destruction¶

3. Worked example¶

Chordal colouring in dominance order¶

Decoupled spilling (MaxLive-driven)¶

Allocation before SSA destruction¶

4. Invariants and correctness¶

Chordal colouring in dominance order¶

Decoupled spilling (MaxLive-driven)¶

Allocation before SSA destruction¶

5. Complexity¶

6. Variants and refinements¶

Chordal colouring in dominance order¶

Decoupled spilling (MaxLive-driven)¶

Allocation before SSA destruction¶

7. In real compilers¶

Chordal colouring in dominance order¶

Decoupled spilling (MaxLive-driven)¶

Allocation before SSA destruction¶

8. Comparison¶

9. Assessment¶

References¶