Lesson 22.4 — Coalescing: aggressive, conservative (Briggs, George) and iterated

Techniques: aggressive coalescing; conservative coalescing (the Briggs and George tests); iterated register coalescing (George–Appel) · Lab: labs/ch22-regalloc E2 (allocateChaitinBriggs coalesces phi moves) · Prerequisites: Lesson 22.3, Lesson 16.7 (coalescing during SSA destruction) · Time: 4–5 hours

Leaving SSA (Ch 16) and two-address instruction sets create copies: x ← y on every edge into a phi, and %9 = COPY %1 before every x86 IMUL64rr whose first operand is still live. A copy whose two sides get the same register is a no-op and disappears. Coalescing merges the two nodes of such a move in the interference graph, forcing them to the same colour. Merging is easy; the risk is that the merged node has more neighbours than either half and the graph stops being colourable. Chaitin coalesced every non-interfering copy (aggressive coalescing). Briggs, and later George, found tests that merge only when colourability is preserved (conservative coalescing). George and Appel interleaved those tests with simplification so that they succeed more often (iterated register coalescing, IRC) [GA96]. This lesson proves the two tests safe and traces IRC on the running example.

1. Problem and motivation

Input: an interference graph \(G\), \(k\) registers, and a list of move pairs (affinities), each with a weight (how often the copy executes). Output: a partition of the nodes into merged classes such that no class contains two interfering nodes, maximizing the total weight of moves inside classes, and such that the merged graph is still \(k\)-colourable, or at least no harder to colour than before.

Aggressive coalescing

Chaitin's allocator merges the ends of every copy whose nodes do not interfere, repeatedly, before colouring [CACCHM81]. It removes the most copies, but can turn a colourable graph into one that must spill (§3). LLVM's RegisterCoalescer is aggressive in this sense: it joins the live intervals of a copy's source and destination whenever they do not overlap, and relies on the greedy allocator's live-range splitting to undo harmful merges later (Lesson 22.8).

Conservative coalescing (Briggs and George)

Briggs, Cooper and Torczon made coalescing safe: merge only if the merged node has fewer than \(k\) neighbours of significant degree [BCT94]. George and Appel added a second, asymmetric test that also works when one of the nodes is a pre-coloured physical register, whose neighbour list is too large to enumerate [GA96]. Both are sufficient conditions: they never make simplification fail, but they refuse many harmless merges.

Iterated register coalescing

Applied once, before simplification, the conservative tests refuse most moves: at that time many nodes are still significant. George and Appel's insight was to interleave them with simplification: removing low-degree nodes lowers the degrees of their neighbours, after which a refused move may pass. When neither simplification nor coalescing can make progress, a move-related node is frozen: its moves are given up so that it can be simplified [GA96]. Bouchez, Darte and Rastello proved that optimal coalescing is NP-complete in all these variants, even for SSA programs, so heuristics like IRC are the practical answer [BDR07].

2. Definitions and algorithms

Aggressive coalescing

Definition 22.4.1 (Coalescing)

Let \(\{u, v\}\) be a move pair with \(\{u, v\} \notin E\). Coalescing \(u\) and \(v\) produces the graph \(G / uv\) in which \(u\) and \(v\) are replaced by a single node \(uv\) with \(N(uv) = N(u) \cup N(v)\) (\(N\) = set of neighbours); all other adjacencies are unchanged. For a node \(t \in N(u) \cap N(v)\), \(\deg_{G/uv}(t) = \deg_G(t) - 1\); for every other \(t\) the degree is unchanged. A colouring of \(G / uv\) gives \(u\) and \(v\) the colour of \(uv\), and is then a colouring of \(G\) in which the move \(u \gets v\) is a no-op.

Algorithm 22.4.2 (Aggressive coalescing, union–find form)

• Input: \(G\); move pairs \(M\) in priority order (highest weight first).
• Output: a partition of \(V\) into classes (the representative of each node).
• Precondition: \(G\) is an interference graph (Definition 22.1.5).
• Postcondition: no class contains two interfering nodes; no remaining move could be merged without violating that.
• Invariant: for every class \(X\), \(N(X) = \bigcup_{x \in X} N(x)\) is maintained and \(X \cap N(X) = \emptyset\).

function AggressiveCoalesce(G, M):
    for each v in V: rep[v] ← v; nbrs[v] ← N(v)
    changed ← true
    while changed:
        changed ← false
        for each (a, b) in M:
            x ← Find(a); y ← Find(b)
            if x ≠ y and y ∉ nbrs[x]:
                rep[y] ← x; nbrs[x] ← nbrs[x] ∪ nbrs[y]      # Union
                for each t in nbrs[y]: replace y by x in nbrs[t]
                changed ← true
    return rep

Find is union–find with path compression.

Conservative coalescing (Briggs and George)

Definition 22.4.3 (Briggs test)

For a move pair \(\{u, v\}\) with \(\{u, v\} \notin E\), the Briggs test holds if the merged node has fewer than \(k\) significant neighbours in \(G / uv\):

\[ \bigl\lvert \{\, t \in N(u) \cup N(v) \mid \deg_{G/uv}(t) \ge k \,\} \bigr\rvert < k . \]

Definition 22.4.4 (Degeneracy)

\(G\) is \(k\)-simplifiable if every non-empty subgraph \(H\) of \(G\) (induced by any subset of nodes) has a node with \(\deg_H < k\). Equivalently, the Simplify of Algorithm 22.3.4 empties \(G\) without getting stuck, whatever insignificant node it picks at each step. By Lemma 22.3.3 a \(k\)-simplifiable graph is \(k\)-colourable.

(The equivalence: if Simplify gets stuck, the remaining nodes form a subgraph with all degrees \(\ge k\); conversely, if some subgraph \(H\) has all degrees \(\ge k\), no node of \(H\) can ever be removed, because removing nodes outside \(H\) does not lower degrees inside \(H\) below \(\deg_H\).)

Definition 22.4.5 (George test)

For a move pair \(\{a, b\}\) with \(\{a, b\} \notin E\), the George test for merging \(a\) into \(b\) holds if every neighbour of \(a\) already interferes with \(b\) or is insignificant:

\[ \forall t \in N(a) :\ t \in N(b) \ \lor\ \deg_G(t) < k . \]

It is asymmetric; it only inspects \(N(a)\), which is why it suits a pre-coloured \(b\) whose neighbour list is not stored.

Algorithm 22.4.6 (Iterated register coalescing, after [GA96] and [Appel, §11.4])

• Input: \(G\) with move pairs; \(k\); spill costs; optionally pre-coloured nodes.
• Output: a colour or "actual spill" for every node; the moves that were coalesced.
• Precondition: move pairs whose ends interfere are allowed (they become constrained).
• Postcondition: coloured nodes form a proper \(k\)-colouring; coalesced moves join nodes of the same colour (Theorem 22.4.10).
• Invariant (worklists): every node still in the graph is in exactly one of simplifyWL (degree \(< k\), not move-related), freezeWL (degree \(< k\), move-related), spillWL (degree \(\ge k\)); every move is in exactly one of worklistMoves, activeMoves, coalesced, constrained, frozen.

function IRC(G, M, k):
    MakeWorklist()
    repeat
        if simplifyWL ≠ ∅:        Simplify()
        else if worklistMoves ≠ ∅: Coalesce()
        else if freezeWL ≠ ∅:      Freeze()
        else if spillWL ≠ ∅:       SelectSpill()
    until all four are empty
    AssignColors()                                # Briggs's optimistic select, Algorithm 22.3.8

function Simplify():
    n ← take from simplifyWL; push n on selectStack
    for each m in Adjacent(n): DecrementDegree(m)

function DecrementDegree(m):
    d ← degree[m]; degree[m] ← d − 1
    if d = k:                                      # m just became insignificant
        EnableMoves({m} ∪ Adjacent(m))             # their moves may pass the tests now
        move m from spillWL to (freezeWL if MoveRelated(m) else simplifyWL)

function EnableMoves(nodes):
    for each n in nodes, each move mv of NodeMoves(n) in activeMoves:
        move mv to worklistMoves

function Coalesce():
    mv = (x, y) ← take from worklistMoves; u ← GetAlias(x); v ← GetAlias(y)
    if v is pre-coloured: swap u and v
    if u = v:                         mark mv coalesced; AddWorkList(u)
    else if v is pre-coloured or {u, v} ∈ E:
                                      mark mv constrained; AddWorkList(u); AddWorkList(v)
    else if (u pre-coloured and George(v into u)) or
            (u not pre-coloured and Briggs(u, v)):
                                      mark mv coalesced; Combine(u, v); AddWorkList(u)
    else:                             move mv to activeMoves  # retried after EnableMoves

function AddWorkList(u):
    if u not pre-coloured and not MoveRelated(u) and degree[u] < k:
        move u from freezeWL to simplifyWL

function Combine(u, v):
    remove v from freezeWL or spillWL; mark v coalesced; alias[v] ← u
    moveList[u] ← moveList[u] ∪ moveList[v]; EnableMoves({v})
    for each t in Adjacent(v): AddEdge(t, u); DecrementDegree(t)
    if degree[u] ≥ k and u ∈ freezeWL: move u to spillWL

function Freeze():
    u ← take from freezeWL; add u to simplifyWL; FreezeMoves(u)

function FreezeMoves(u):
    for each mv = (x, y) in NodeMoves(u):
        v ← the alias of the other end; mark mv frozen
        if NodeMoves(v) = ∅ and degree[v] < k: move v from freezeWL to simplifyWL

function SelectSpill():
    m ← the node of spillWL with the least cost / degree
    move m to simplifyWL; FreezeMoves(m)          # pushed optimistically

# Adjacent(n) = neighbours of n not on selectStack and not coalesced;
# NodeMoves(n) = moves of n in activeMoves ∪ worklistMoves; MoveRelated(n) ⇔ NodeMoves(n) ≠ ∅;
# GetAlias follows alias[] while the node is coalesced; AddEdge adds an interference edge
# and increments the degrees of non-pre-coloured ends.

The lab's reference solution and the drills' oracle (regalloc.irc) also accept a merge of two virtual nodes when the George test holds in either direction; both tests are safe (Theorems 22.4.8 and 22.4.9), so the disjunction is safe.

Iterated register coalescing

IRC is Algorithm 22.4.6. Its selling point is visible in the worklist structure: a move refused by the conservative test waits in activeMoves, and DecrementDegree moves it back to worklistMoves exactly when one of its ends, or one of their neighbours, drops from significant to insignificant, the only event that can make a refused test pass.

3. Worked example

Aggressive coalescing

The running example has three move pairs: i–i2 and s–s2 (back-edge phi operands) and s–a (entry-edge phi operand). s and a interfere (a is live throughout the loop), so the third move can never be coalesced. Merging the other two gives the nodes ii2 and ss2: the graph shrinks from 9 to 7 nodes, and ii2 has the neighbours \(N(i) \cup N(i2) = \{a, c, s, s2, t, u\}\), where s and s2 are now the single node ss2. Here aggressive coalescing is harmless: MaxLive is still 4 and the merged graph is still 4-colourable (§3, IRC).

When aggressive coalescing hurts. The path \(a - b - c - d\) is 2-colourable. It is not a clique, so a and d do not interfere; suppose a copy joins them. Coalescing gives \(ad - b\), \(b - c\), \(c - ad\): a triangle, which needs 3 colours. With \(k = 2\) the merge forces a spill that the original graph did not need. The Briggs test refuses it: in \(G / ad\), b and c both have degree 2 \(\ge k\), so the merged node has 2 significant neighbours, not fewer than \(k = 2\).

Conservative coalescing (Briggs and George)

The two tests on the running example, from regalloc.briggs_test and regalloc.george_test (degrees after merging; a is a common neighbour of both ends in each case and loses one):

move	\(k\)	neighbours of the merged node (degree in \(G/uv\))	Briggs	George i2→i / s2→s	George i→i2 / s→s2
i–i2	3	a(6), c(3), s(3), s2(2), t(2), u(2)	no: 3 significant (a, c, s)	yes: N(i2) = {a, s2} ⊆ N(i)	no: c (degree 3) is not a neighbour of i2
s–s2	3	a(6), c(3), i(5), i2(2)	no: 3 significant (a, c, i)	yes: N(s2) = {a, i, i2}, a, i ∈ N(s), i2 has degree 2	no
i–i2	4	as above	yes: 1 significant (a)	yes	yes
s–s2	4	as above	yes: 1 significant (a)	yes	yes
s–a	any	—	no: s and a interfere	no	no

With \(k = 3\) Briggs refuses both loop moves but George accepts them (in one direction): the tests are incomparable, and using both merges more.

Try it

./course drill coalescing-test --seed 4 --difficulty hard --solution asks for both verdicts on three pairs, one interfering and one where only George succeeds.

Iterated register coalescing

IRC with \(k = 4\) on the running example (costs from Lesson 22.3; regalloc.irc, one row per step; the move worklist is in program order i–i2, s–a, s–s2):

step	action	node / move	detail	stack after
0	MakeWorklist	—	simplifyWL {c, r, t, u}; freezeWL {i2, s, s2}; spillWL {a, i}	—
1	simplify	c	degree 3 < 4, not move-related	c
2	simplify	r	degree 0	c r
3	simplify	t	degree 2	c r t
4	simplify	u	degree 2; a and i drop to degree 3 < 4 → freezeWL	c r t u
5	coalesce	i–i2	Briggs: 0 significant neighbours; merge i2 into i	c r t u
6	simplify	i	now not move-related, degree 3	c r t u i
7	constrained	s–a	s and a interfere: the move stays	c r t u i
8	simplify	a	no active moves left, degree 2	c r t u i a
9	coalesce	s–s2	Briggs: 0 significant neighbours; merge s2 into s	c r t u i a
10	simplify	s	degree 0	c r t u i a s
11	select	s, a, i, u, t, r, c	colours 0, 1, 2, 0, 0, 0, 3	—

Result: s, s2, t, u, r in register 0, a in 1, i, i2 in 2, c in 3. Both back-edge moves are gone; the entry move s ← a remains (it is outside the loop, weight 1).

With \(k = 3\) the trace is: simplify r, t, u; coalesce i–i2 (George, i2 into i); s–a constrained; coalesce s–s2 (George); then the remaining a, c, i, s form a 4-clique with every degree 3: SelectSpill picks a (cost/degree 13/3, the smallest), then c, i, s simplify, and select finds no colour for a: an actual spill. After spilling a, no move is left in the loop; only the entry-edge copy s ← a remains. The ILP of Lesson 22.7, which charges spill cost plus the weight of every remaining copy, finds the same solution as optimal for \(k = 3\): objective \(13 + 1 = 14\).

4. Invariants and correctness

Aggressive coalescing

Proposition 22.4.7 (Coalescing preserves validity, not colourability)

(i) If \(\{u, v\} \notin E\), every \(k\)-colouring of \(G / uv\) induces a \(k\)-colouring of \(G\) with \(\mathrm{col}(u) = \mathrm{col}(v)\). (ii) There are graphs \(G\) with \(\chi(G) = 2\) and a move pair \(\{u, v\} \notin E\) with \(\chi(G / uv) = 3\).

Proof

(i) Every edge of \(G\) at \(u\) or \(v\) becomes an edge of \(G / uv\) at \(uv\), whose colour differs from the neighbour's; other edges are unchanged; \(u\) and \(v\) are not adjacent, so giving both the colour of \(uv\) is proper. (ii) The path \(a - b - c - d\) is bipartite; \(a\) and \(d\) are not adjacent; \(G / ad\) is the triangle \(\{ad, b, c\}\) (§3).

Conservative coalescing (Briggs and George)

Theorem 22.4.8 (The Briggs test is safe)

If \(G\) is \(k\)-simplifiable (Definition 22.4.4), \(\{u, v\} \notin E\), and the Briggs test holds for \(\{u, v\}\), then \(G / uv\) is \(k\)-simplifiable.

Proof

Let \(H\) be a non-empty subgraph of \(G / uv\); we must find a node of \(H\) with degree \(< k\) in \(H\). If \(uv \notin H\), then \(H\) is also a subgraph of \(G\) (its nodes and edges are nodes and edges of \(G\)), and \(G\) is \(k\)-simplifiable. Otherwise \(uv \in H\). If some \(w \in H\), \(w \ne uv\), has \(\deg_H(w) < k\), we are done. If not, every neighbour \(w\) of \(uv\) in \(H\) has \(\deg_{G/uv}(w) \ge \deg_H(w) \ge k\), so it is a significant neighbour of \(uv\) in \(G / uv\). By the Briggs test there are fewer than \(k\) of those, so \(\deg_H(uv) < k\). In both cases \(H\) has a node of degree \(< k\).

Theorem 22.4.9 (The George test is safe)

If \(G\) is \(k\)-simplifiable, \(\{a, b\} \notin E\), and the George test holds for merging \(a\) into \(b\), then \(G / ab\) is \(k\)-simplifiable.

Proof

Suppose not: some non-empty subgraph \(H\) of \(G / ab\) has every degree \(\ge k\). \(H\) must contain \(ab\), otherwise it is a subgraph of \(G\). Let \(t\) be a neighbour of \(ab\) in \(H\). If \(t \notin N_G(b)\), then \(t \in N_G(a)\) and the George test gives \(\deg_G(t) < k\); merging never increases the degree of \(t\), so \(\deg_H(t) \le \deg_{G/ab}(t) \le \deg_G(t) < k\), contradicting the choice of \(H\). Hence every neighbour of \(ab\) in \(H\) is in \(N_G(b)\). Replace \(ab\) by \(b\): the subgraph \(H'\) of \(G\) induced by \((H \setminus \{ab\}) \cup \{b\}\) has the same edges as \(H\) (every edge \(t - ab\) of \(H\) is an edge \(t - b\) of \(G\), and edges not at \(ab\) are unchanged), so every node of \(H'\) has degree \(\ge k\) in \(H'\), contradicting the \(k\)-simplifiability of \(G\).

Both theorems say "safe for simplifiability", which is what Chaitin–Briggs colouring needs: a graph that Simplify would empty is still emptied after the merge. They do not preserve \(k\)-colourability in general, but for SSA interference graphs Lesson 22.6 shows simplifiability and colourability coincide.

Iterated register coalescing

Theorem 22.4.10 (IRC terminates and is correct)

Algorithm 22.4.6 terminates. Every node it colours has a colour different from all its coloured neighbours in \(G\), and the two ends of every coalesced move get the same colour.

Proof

Termination. Consider, lexicographically, the number of nodes still in the graph, the number of moves in worklistMoves ∪ activeMoves, the number in worklistMoves, and the size of spillWL. Simplify and a successful Coalesce remove a node (the first component drops; EnableMoves may raise the others, which is allowed). A constrained or already coalesced move leaves both move sets (second component). A refused move goes from worklistMoves to activeMoves (third component). Freeze takes a move-related node, so it freezes at least one move (second component). SelectSpill shrinks spillWL without adding to it (fourth component; spillWL grows only in Combine, which removes a node). So the measure decreases strictly in a well-founded order.

Colouring. AssignColors is Briggs's OptimisticSelect on the coalesced graph: by Theorem 22.3.9 (i) coloured nodes differ from coloured neighbours in the coalesced graph, whose edges include all edges of \(G\) between the representatives (Combine adds \(t - u\) for every \(t - v\)). A coalesced node's colour is copied to all its members, and members of one class never interfere (a move is coalesced only if the representatives are not adjacent, and adjacency is inherited by the representative), so by Proposition 22.4.7 (i) the colouring of \(G\) is proper and coalesced moves are no-ops. Pre-coloured nodes keep their colour; a virtual node adjacent to a pre-coloured one never receives its colour, because select treats pre-coloured neighbours as coloured.

Safety in IRC's sense is Theorems 22.4.8 and 22.4.9: a merge performed on the current graph (the nodes not yet simplified) keeps that graph simplifiable, so IRC never adds a potential spill by coalescing.

Theorem 22.4.11 (Optimal coalescing is NP-complete)

The following are NP-complete: aggressive coalescing (merge move pairs to maximize the removed weight, only forbidding merges of interfering nodes) even for interference graphs of SSA programs; conservative coalescing (maximize the removed weight so that the result is still \(k\)-colourable) even for chordal graphs; incremental conservative coalescing (can one given move be merged while keeping \(k\)-colourability) for general graphs.

Proof sketch (full proofs: [BDR07])

Membership in NP is clear (guess the partition, check interference and colourability, the latter in polynomial time for chordal graphs). Aggressive coalescing is shown NP-hard by a reduction from multiway cut: terminals become pre-coloured-like nodes that interfere with one another, and merging along affinities corresponds to cutting edges. Conservative coalescing on chordal graphs reduces from 3-SAT with gadgets whose merges must respect \(k\)-colourability. Bouchez et al. also show that incremental conservative coalescing is polynomial for chordal graphs, which is the case SSA-based allocators exploit.

5. Complexity

\(n\) nodes, \(e\) edges, \(m\) moves, \(k\) registers.

Algorithm	Time (worst)	Time (typical)	Space	Justification
Aggressive (union–find)	\(O((m + e) \cdot \alpha)\) per pass, \(\le m\) passes	1–2 passes	\(O(n + e)\)	each successful merge reduces the number of classes; each pass costs a union–find per move and a neighbour-set union
Briggs test	\(O(\deg(u) + \deg(v))\)	small	\(O(1)\)	one scan of both neighbour lists
George test	\(O(\deg(a))\) with an \(O(1)\) adjacency matrix	small	\(O(1)\)	one membership query per neighbour of \(a\)
IRC	\(O(n \cdot e + m \cdot (e + n))\) in the worst case	close to Chaitin–Briggs	\(O(n + e + m)\)	each move is retried at most once per DecrementDegree that crosses \(k\) at its ends or neighbours, and each test costs \(O(\deg)\)
Optimal coalescing	NP-complete (Theorem 22.4.11)	—	—	[BDR07]

Pathological family. A star with centre \(x\) and \(m\) leaves, each leaf also joined by a move to a node \(y_j\) that interferes with \(k - 1\) other significant nodes: each time a node of \(x\)'s neighbourhood is simplified, DecrementDegree re-enables the moves of \(x\)'s neighbours, and every re-enabled move is retested at cost \(\Theta(\deg)\): \(\Theta(m^2)\) tests in total. On real functions these retries are rare, and the time of an IRC allocator is dominated by building the graph, as for every colouring allocator (Lesson 22.3 §5).

6. Variants and refinements

Aggressive coalescing

• Coalescing with live-range splitting afterwards. Coalesce aggressively, then let the allocator split live ranges that cannot be coloured (LLVM). Trade-off: maximum copy removal; relies on a good splitter to repair harm.
• Value-based aggressive coalescing for SSA destruction [BDR+09] (Lesson 16.7). Trade-off: merges values that interfere only in name.

Conservative coalescing (Briggs and George)

• Brute-force / de-coalescing tests. Bouchez, Darte and Rastello give stronger conservative tests (test simplifiability of the merged node's neighbourhood directly) and improve optimistic de-coalescing [BDR08]. Trade-off: more merges, more compile time.
• Optimistic coalescing (Park–Moon): coalesce aggressively, then split merged nodes that would spill [PM04]. Trade-off: fewer moves than IRC, more complex select.

Iterated register coalescing

• Prioritized moves. SML/NJ's MLRISC keeps the move worklist and the freeze list as priority queues so that frequent moves are coalesced first (§7). Trade-off: \(O(\log m)\) per move operation.
• Coalescing on SSA before destruction. Hack's allocator colours the SSA graph first and then recolours to satisfy affinities, which is incremental conservative coalescing on a chordal graph [Hack07], polynomial by [BDR07]. Trade-off: needs the SSA-based framework of Lesson 22.6.

7. In real compilers

Aggressive coalescing

LLVM's RegisterCoalescer (llvm/lib/CodeGen/RegisterCoalescer.cpp, RegisterCoalescer::joinCopy, joinAllIntervals) joins the live intervals of a COPY's source and destination whenever their values do not conflict (JoinVals compares value numbers, so two intervals that overlap only while holding the same value can still merge) [LLVM-RegCoalescer]. It runs before the allocator, after PHIElimination and TwoAddressInstruction have created the copies. HotSpot C2 runs PhaseAggressiveCoalesce on its phi "virtual copies" first (src/hotspot/share/opto/coalesce.cpp) [HS-Coalesce].

LLVM's register coalescer on the running example: 13 copies become 3

Reproduce (llc 23.1.2; run.ll from Lesson 22.1 §7):

for s in before after; do
  llc -O2 -mtriple=x86_64-linux-gnu -stop-$s=register-coalescer run.ll -o rc-$s.mir
  echo "$s: $(grep -c '= COPY' rc-$s.mir) copies"
done
llc -mtriple=x86_64-linux-gnu -passes='print<live-intervals>' rc-after.mir -o /dev/null 2>&1 \
  | sed -n '/^%/p;/MACHINEINSTRS/,$p' | grep -v '^\s*$\|successors\|predecessors\|^#'

Output (complete):

before: 13 copies
after: 3 copies
%4 [16r,240r:0) 0@16r  weight:0.000000e+00
%11 [32r,64B:1)[64B,192r:2)[192r,224B:0) 0@192r 1@32r 2@64B-phi  weight:0.000000e+00
%12 [48r,64B:4)[64B,144r:5)[144r,160r:3)[160r,176r:2)[176r,224B:1)[224B,240r:5)[240r,256r:0) 0@240r 1@176r 2@160r 3@144r 4@48r 5@64B-phi  weight:0.000000e+00
********** MACHINEINSTRS **********
Function Live Ins: $rdi in %4
0B  bb.0.entry:
      liveins: $rdi
16B   %4:gr64 = COPY $rdi
32B   undef %11.sub_32bit:gr64_with_sub_8bit = MOV32r0 implicit-def dead $eflags
48B   %12:gr64 = COPY %4:gr64
64B bb.1.loop:
80B   CMP64ri32 %11:gr64_with_sub_8bit, 9, implicit-def $eflags
96B   JCC_1 %bb.3, 15, implicit killed $eflags
112B      JMP_1 %bb.2
128B    bb.2.body:
144B      %12:gr64 = IMUL64rr %12:gr64(tied-def 0), %11:gr64_with_sub_8bit, implicit-def dead $eflags
160B      %12:gr64 = ADD64rr %12:gr64(tied-def 0), %4:gr64, implicit-def dead $eflags
176B      %12:gr64 = XOR64rr %12:gr64(tied-def 0), %11:gr64_with_sub_8bit, implicit-def dead $eflags
192B      %11:gr64_with_sub_8bit = INC64r %11:gr64_with_sub_8bit(tied-def 0), implicit-def dead $eflags
208B      JMP_1 %bb.1
224B    bb.3.exit:
240B      %12:gr64 = ADD64rr %12:gr64(tied-def 0), %4:gr64, implicit-def dead $eflags
256B      $rax = COPY %12:gr64
272B      RET 0, killed $rax

What to notice: compare with the 13-copy MIR of Lesson 22.1. The coalescer merged %11 with the counter's copies (i, i2) and %12 with s, t, u, s2 and r: one interval with six value numbers, exactly the classes our IRC trace found (s, s2, t, u, r in one register, i, i2 in another). The three surviving copies are the pre-coloured COPY $rdi and $rax = COPY, and %12 = COPY %4: the entry-edge phi copy s ← a, which cannot be coalesced because s and a interfere (both live in the loop). No test was needed: with 16 registers, aggressive merging costs nothing here.

Conservative coalescing (Briggs and George)

HotSpot C2 runs PhaseConservativeCoalesce after every split round (src/hotspot/share/opto/coalesce.cpp, PhaseConservativeCoalesce::copy_copy): it merges two live ranges only if the union's degree stays below the number of registers both may use, a stricter form of Briggs's test [HS-Coalesce]. SML/NJ's MLRISC implements both the Briggs and George tests (MLRISC/ra/ra-core.sml, counters good-briggs, good-george) [MLRISC-RA]. GCC's IRA does not coalesce in the Chaitin sense: it forms threads of copy-connected allocnos and pushes them together, and relies on preferences (hints) [GCC-IRA].

HotSpot C2's conservative coalescing test

Reproduce (OpenJDK tag jdk-21+35; curl reads the pinned source):

curl -s 'https://raw.githubusercontent.com/openjdk/jdk/jdk-21%2B35/src/hotspot/share/opto/coalesce.cpp' \
  | sed -n '733,738p;755,758p'

Output (complete):

  // Union the two interference sets together into '_ulr'
  uint reg_degree = _ulr.lrg_union( lr1, lr2, rm_size, _phc._ifg, rm );

  if( reg_degree >= rm_size ) {
    record_bias( _phc._ifg, lr1, lr2 );
    return false;
  // ---- THE COMBINED LRG IS COLORABLE ----

  // YEAH - Now coalesce this copy away
  assert( lrgs(lr1).num_regs() == lrgs(lr2).num_regs(),   "" );

What to notice: lrg_union computes the neighbours of the merged live range and rm_size is the number of registers both live ranges may use (\(k\) for that pair). The merge happens only if the merged node's degree is below \(k\): then it is insignificant, and Lemma 22.3.3 alone shows the merge is safe. This implies the Briggs test (fewer than \(k\) neighbours at all, significant or not) and refuses more. When the test fails, record_bias remembers the pair so that select can still try to give both the same colour (biased colouring, Lesson 22.3 §6).

Iterated register coalescing

IRC is the allocator of Appel's textbook compilers [Appel, Ch. 11] and of SML/NJ's MLRISC back end (MLRISC/ra/ra-core.sml, iteratedCoalescingPhases), co-written by George [MLRISC-RA]. It is less common in today's industrial compilers: LLVM coalesces aggressively and splits, GCC uses IRA's threads and preferences, and HotSpot C2 alternates conservative coalescing with simplify/select rounds rather than interleaving them. The lab's E2 is IRC.

SML/NJ's MLRISC: iterated coalescing with prioritized worklists

Reproduce (SML/NJ tag v110.99.9; curl reads the pinned source):

curl -s https://raw.githubusercontent.com/smlnj/legacy/v110.99.9/MLRISC/ra/ra-core.sml | sed -n '1,20p'
curl -s https://raw.githubusercontent.com/smlnj/legacy/v110.99.9/MLRISC/ra/ra-core.sml \
  | grep -n 'good_briggs\|good_george\|fun iteratedCoalescingPhases'

Output (complete):

(* ra-core.sml
 *
 * COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies.
 *
 * Overview
 * ========
 * This implementation of iterated coalescing differ from the old one in
 * various substantial ways:
 *
 * 1. The move list is prioritized.  Higher ranking moves are coalesced first.
 *    This tends to favor coalescing of moves that has higher priority.
 *
 * 2. The freeze list is prioritized.  Lower ranking nodes are unfrozen
 *    first.  Since freeze disable moves, this tends to disable moves
 *    of low priority.
 *
 * 3. The simplify worklist is not kept explicitly during the
 *    simplify/coalesce/freeze phases.  Instead, whenever a non-move
 *    related node with degree < K is discovered, we call simplify
 *    to remove it from the graph immediately.
89:  val good_briggs   = MLRiscControl.getCounter "good-briggs"
91:  val good_george   = MLRiscControl.getCounter "good-george"
453:  fun iteratedCoalescingPhases
818:                       (*if tally then good_george := !good_george+1 else ();*)
832:                       (*if tally then good_briggs := !good_briggs+1 else ();*)

What to notice: iteratedCoalescingPhases is Algorithm 22.4.6's main loop, with the two refinements of §6: moves and freeze candidates in priority queues, and simplification done eagerly instead of through a simplifyWL. Lines 818 and 832 sit in the two branches of coalesce: when one end is already coloured (pre-coloured) the move is merged if safe holds, George's test; when neither is, if conservative holds, Briggs's test (Theorems 22.4.8 and 22.4.9). The counters' increments are commented out in this release, so they only mark the branches. SML/NJ ships no standalone tool that prints its allocator's decisions, so the pinned source is quoted.

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Aggressive coalescing	removes every removable copy; can create spills (Proposition 22.4.7 (ii))	near-linear (union–find) · fast	fewest copies, possibly more spills	small	LLVM RegisterCoalescer + splitting, HotSpot C2 phase 1
Conservative coalescing (Briggs, George)	never breaks simplifiability (Theorems 22.4.8, 22.4.9); refuses many harmless merges when applied once	\(O(\deg)\) per test	no new spills; more copies than aggressive	small	HotSpot C2 phase 2, MLRISC, IRC's tests
Iterated register coalescing	conservative, but retries after simplification: accepts far more merges	close to Chaitin–Briggs; \(O(m \cdot e)\) worst case	few copies and no coalescing-induced spills	large (five worklists, five move states)	Appel's compilers, MLRISC, the lab's E2

Measured in the lab (ch22-compare, \(K = 4\)): the IRC allocator leaves 22 register-to-register phi moves (weighted 112) in 414 functions; Poletto–Sarkar linear scan, which does not coalesce, leaves 1411 (weighted 21787), and SSA colouring with biased colour choice leaves 758 (6365).

Choose aggressive coalescing when a later phase can split live ranges (LLVM's design). Choose conservative tests when the allocator colours once and cannot undo a merge. Choose IRC when you implement a graph-colouring allocator and want copies removed without new spills.

9. Assessment

• Quiz (./course quiz 22): aggressive-harm, aggressive-llvm, briggs-verdict, george-verdict, irc-freeze, irc-moves-k4 (tags aggressive-coalescing, conservative-coalescing, irc).
• Drill: ./course drill coalescing-test (Briggs and George verdicts); ./course drill interference-graph --difficulty hard (which move pairs can be coalesced at all).
• Flashcards: tags aggressive-coalescing, conservative-coalescing, irc.
• Lab: E2 allocateChaitinBriggs with coalescing of phi moves; the tests check that it leaves at most as many weighted moves as linear scan on the corpus.

References

See the chapter references.