Lesson 22.3 — Graph colouring: Chaitin's allocator and Briggs's optimistic colouring¶

Techniques: Chaitin's allocator (build, simplify, spill, select; spill costs); Briggs's optimistic colouring · Lab: labs/ch22-regalloc E2 (allocateChaitinBriggs) · Prerequisites: Lesson 22.1 (interference graph, Definition 22.1.5) · Time: 4–5 hours

Chaitin's insight was that register allocation for a whole function is graph colouring [CACCHM81]: registers are colours, and the interference graph must be coloured so that neighbours differ. Colouring is NP-complete, but a simple observation makes a fast heuristic work well: a node with fewer than \(k\) neighbours can always be coloured last, whatever its neighbours get, so it can be set aside. Repeating this simplification either empties the graph (and colouring succeeds) or gets stuck, and then some value is spilled. Chaitin's 1982 paper made spilling part of the loop [Cha82]. Briggs, Cooper and Torczon noticed that getting stuck does not mean the graph cannot be coloured, and made the spill decision optimistic: postpone it until colouring actually fails [BCT94]. This lesson develops both, with their proofs.

1. Problem and motivation¶

Chaitin's allocator¶

Input: the interference graph \(G_I\) of a function (Lesson 22.1), the number \(k\) of registers, and a spill cost for each value. Output: a colour in \(\{0, \dots, k - 1\}\) for as many values as possible, and spill code for the rest, such that the resulting function's new interference graph is \(k\)-coloured. Chaitin et al. built the first global allocator of this kind for the IBM PL.8 compiler; before it, allocators assigned registers to the most frequently used variables of each loop and hoped for the best. Chaitin's allocator treats all values of the function together, spills by estimated cost, and coalesces copies before colouring (Lesson 22.4).

Briggs's optimistic colouring¶

Chaitin's allocator spills as soon as simplification gets stuck. But a node of degree \(\ge k\) may still be colourable: its neighbours can share colours. The square \(a - b - c - d - a\) with \(k = 2\) is the smallest example: every node has degree 2, simplification cannot start, yet the square is 2-colourable. Briggs's allocator pushes the stuck node onto the stack anyway, as a potential spill, and spills it only if no colour is free when it is popped [BCT94]. It never spills more than Chaitin's with the same choices, and Briggs et al. measured significantly less spill code on their benchmarks [BCT94]. Their paper also introduced a general treatment of rematerialization (Lesson 22.9).

Both algorithms run in pebblec only through the lab: LLVM does not colour graphs (Lesson 22.8). GCC's IRA and HotSpot's C2 compiler do.

2. Definitions and algorithms¶

Chaitin's allocator¶

Definition 22.3.1 (Colouring, degree, chromatic number)

A \(k\)-colouring of an undirected graph \(G = (V, E)\) is a map \(\mathrm{col} : V \to \{0, \dots, k - 1\}\) with \(\mathrm{col}(u) \ne \mathrm{col}(v)\) for every \(\{u, v\} \in E\). \(G\) is \(k\)-colourable if one exists; \(\chi(G)\) is the least such \(k\) and \(\omega(G)\) the size of a largest clique, so \(\omega(G) \le \chi(G)\). \(\deg_G(v)\) is the number of neighbours of \(v\) in \(G\); \(G - v\) removes \(v\) and its edges. A node is significant if \(\deg_G(v) \ge k\), insignificant otherwise.

Definition 22.3.2 (Spill cost and Chaitin's spill metric)

The spill cost of \(v\) estimates the dynamic cost of spilling it everywhere: the number of definitions and uses of \(v\), each weighted by the frequency of its block, estimated as \(10^{d(B)}\) for loop depth \(d(B)\) [Cha82]:

\[ \mathrm{cost}(v) = \sum_{\text{def or use of } v \text{ in block } B} 10^{d(B)} . \]

Values whose spilling would not reduce pressure (for example the short reload ranges created by an earlier spill) get \(\mathrm{cost} = \infty\). When simplification is stuck, Chaitin spills the node minimizing \(\mathrm{cost}(v) / \deg_G(v)\): cheap, and removing many edges.

Lemma 22.3.3 (Simplification)

If \(\deg_G(v) < k\), then \(G\) is \(k\)-colourable if and only if \(G - v\) is. Moreover, any \(k\)-colouring of \(G - v\) extends to \(G\) by giving \(v\) a colour not used by its neighbours.

Proof

(\(\Rightarrow\)) A \(k\)-colouring of \(G\) restricted to \(G - v\) is a \(k\)-colouring. (\(\Leftarrow\)) Take a \(k\)-colouring of \(G - v\). The neighbours of \(v\) use at most \(\deg_G(v) \le k - 1\) colours, so at least one of the \(k\) colours is unused by them; give it to \(v\). Every edge at \(v\) joins two different colours, and the other edges were already fine.

Algorithm 22.3.4 (Chaitin's allocator)

Input: a function (not necessarily SSA); \(k\) registers; spill costs.
Output: a \(k\)-colouring of the final interference graph; spill code for the spilled values.
Precondition: every instruction needs at most \(k\) registers at once (operands and result), so that the tiny live ranges created by spilling can always be coloured.
Postcondition: when the loop exits, every value has a colour and neighbours differ (Theorem 22.3.5).
Invariant: in Simplify, every node on stack had degree \(< k\) in the graph that remained when it was pushed; spills holds the nodes removed without that guarantee.

function Chaitin(F, k):
    loop:
        G ← Build(F)                              # Algorithm 22.1.9 (webs for non-SSA code)
        Coalesce(G)                               # aggressive, Lesson 22.4
        cost ← SpillCosts(F)                      # Definition 22.3.2
        stack, spills ← Simplify(G, k, cost)
        if spills = ∅:
            return Select(G, stack, k)
        F ← InsertSpillCode(F, spills)            # store after each def, load before each use

function Simplify(G, k, cost):
    stack ← []; spills ← ∅; H ← G
    while H is not empty:
        if some v in H has deg_H(v) < k:
            push v on stack; H ← H − v            # the lab and drills: first such v by name
        else:
            v ← argmin over v in H of cost(v) / deg_H(v)
            spills ← spills ∪ {v}; H ← H − v      # pessimistic: spill now
    return stack, spills

function Select(G, stack, k):
    col ← {}
    while stack is not empty:
        v ← pop(stack)
        col[v] ← the lowest colour not in { col[u] | u neighbour of v in G, u coloured }
    return col

InsertSpillCode gives each spilled value a stack slot and creates a new, very short value for every definition and use; those get infinite spill cost, so the next round cannot choose them. In the lab's model (reload through a scratch register) no new values are created: the spilled nodes simply leave the graph and the loop runs again on the smaller graph.

Theorem 22.3.5 (Chaitin's allocator is correct)

If Simplify returns spills \(= \emptyset\), Select produces a \(k\)-colouring of \(G\). Under the precondition of Algorithm 22.3.4, the outer loop terminates.

Proof

Select. Let the stack be \(v_1, \dots, v_n\) from bottom to top and \(H_i\) the graph when \(v_i\) was pushed, so \(H_n = \{v_n\}\) and \(H_{i+1} = H_i - v_i\). By the invariant \(\deg_{H_i}(v_i) < k\). Select pops \(v_n, v_{n-1}, \dots, v_1\). We show by induction that after popping \(v_i\) the colouring is a \(k\)-colouring of \(H_i\). Base: \(H_n\) is one node. Step: when \(v_i\) is popped, the coloured nodes are \(v_{i+1}, \dots, v_n\), the nodes of \(H_{i+1}\), which are properly coloured by the induction hypothesis. The coloured neighbours of \(v_i\) are therefore its neighbours in \(H_i\), fewer than \(k\) of them, and Lemma 22.3.3 gives \(v_i\) a free colour. After the last pop, \(H_1 = G\) is coloured.

Termination. Each round with spills \(\ne \emptyset\) replaces every spilled value by values whose live ranges span a single instruction (a store right after the definition, a load right before a use). Such a value is live only across the instruction that defines or uses it, so its degree is bounded by the number of values live there, and it has infinite spill cost, so it is never chosen for spilling while any original value remains. Every round therefore strictly decreases the number of original values that are not yet spilled, or ends. When only short values remain, the precondition (at most \(k\) registers needed per instruction) makes each of them simplifiable, and the round ends with spills \(= \emptyset\). This is the argument of [Cha82]; without the precondition (an instruction needing \(k + 1\) registers) no allocation exists at all.

Theorem 22.3.6 (NP-completeness)

Deciding whether a graph is \(k\)-colourable is NP-complete for every fixed \(k \ge 3\) ([GJ79], problem GT4). Every undirected graph is the interference graph of some program [CACCHM81]; hence deciding whether a program can be allocated with \(k\) registers without spilling is NP-complete in general.

Proof sketch (full proofs: [GJ79] (problem GT4); [CACCHM81]; the refinement [BDGR06])

\(k\)-colourability is in NP (check a colouring). 3-colourability is NP-hard by reduction from 3-SAT (the classic gadget construction), and \(k\)-colourability for \(k > 3\) by adding a \((k-3)\)-clique joined to every node. For the second statement, given \(G = (V, E)\) Chaitin et al. construct a program with one variable per node whose control flow makes two variables simultaneously live exactly when their nodes are adjacent, so its interference graph is \(G\) and allocating it with \(k\) registers without spilling is \(k\)-colouring \(G\). Bouchez, Darte, Guillon and Rastello observed that this construction relies on critical edges: if live-range splitting on critical edges is allowed, the question of whether \(k\) registers suffice without spilling becomes polynomial (the SSA case of Lesson 22.6); what stays NP-complete is spilling and coalescing optimally [BDGR06].

Briggs's optimistic colouring¶

Definition 22.3.7 (Potential and actual spill)

During simplification a node removed while significant is a potential spill. In select, a node for which every colour is used by already coloured neighbours is an actual spill.

Algorithm 22.3.8 (Briggs's optimistic colouring)

Input, output, precondition: as for Algorithm 22.3.4.
Postcondition: every node is coloured or an actual spill; the coloured nodes form a \(k\)-colouring of the graph they induce (Theorem 22.3.9).
Invariant: every node on the stack is either insignificant when pushed or a potential spill; a coloured node's colour differs from the colours of all its coloured neighbours.

function Briggs(F, k):
    loop:
        G ← Build(F); Coalesce(G); cost ← SpillCosts(F)
        stack ← OptimisticSimplify(G, k, cost)
        col, actual ← OptimisticSelect(G, stack, k)
        if actual = ∅: return col
        F ← InsertSpillCode(F, actual)

function OptimisticSimplify(G, k, cost):
    stack ← []; H ← G
    while H is not empty:
        if some v in H has deg_H(v) < k: v ← that node
        else: v ← argmin over v in H of cost(v) / deg_H(v)      # potential spill
        push v on stack; H ← H − v
    return stack

function OptimisticSelect(G, stack, k):
    col ← {}; actual ← ∅
    while stack is not empty:
        v ← pop(stack)
        free ← {0, …, k−1} \ { col[u] | u neighbour of v, u coloured }
        if free ≠ ∅: col[v] ← min(free)
        else: actual ← actual ∪ {v}                              # leaves v uncoloured
    return col, actual

3. Worked example¶

Chaitin's allocator¶

The running example of Lesson 22.1 with \(k = 3\). Spill costs (Definition 22.3.2; B1 and B2 are at loop depth 1, weight 10; a phi operand is used in its predecessor): a 13 (def in B0, phi use on B0→B1, one use in B2 at weight 10, one use in B3), i 50, s 21, c t u s2 i2 20, r 2. Degrees as in Lesson 22.1: a 7, i 6, c s s2 3, i2 t u 2, r 0. Chaitin's Simplify (first insignificant node by name):

step	phase	node	why	result
1	simplify	i2	degree 2 < 3	push
2	simplify	r	degree 0 < 3	push
3	simplify	s2	degree 2 < 3 (its neighbour `i2` is gone)	push
4	simplify	t	degree 2 < 3	push
5	simplify	u	degree 2 < 3	push
6	blocked	a	remaining `a`, `c`, `i`, `s` form a 4-clique, all degree 3; cost/degree: a 13/3 = 4.33, c 20/3, i 50/3, s 21/3	spill `a`
7	simplify	c	degree 2 < 3	push
8	simplify	i	degree 1 < 3	push
9	simplify	s	degree 0 < 3	push

spills \(= \{a\}\): insert a store after a = arg and loads before its uses, and run again. In the lab's model the second round colours the graph without a (every node now has degree \(\le 2\) in the clique that remains), and Select pops s, i, c, u, t, s2, r, i2:

pop	node	colours of coloured neighbours	colour
1	s	—	0
2	i	{0}	1
3	c	{0, 1}	2
4	u	{1}	0
5	t	{1}	0
6	s2	{1}	0
7	r	—	0
8	i2	{0}	1

Result: a spilled, s, t, u, s2, r in register 0, i, i2 in 1, c in 2. Spilling a costs one store and three reloads, weighted 13, the cheapest choice: MaxLive is 4 at c = lt i 10, so something must be spilled with 3 registers (Proposition 22.1.15).

Briggs's optimistic colouring¶

On the running example Briggs pushes a at step 6 as a potential spill and continues identically; when a is popped (after s, i, c), its neighbours s, i, c hold colours 0, 1, 2, and a becomes an actual spill. Same result: the 4-clique really needs 4 colours. The square shows the difference (\(k = 2\), all costs 1):

flowchart LR
  a((a)) --- b((b))
  b --- c((c))
  c --- d((d))
  d --- a

step	Chaitin	Briggs
1	blocked: all degrees 2; cost/degree ½ for all; spill `a`	blocked; push `a` (potential spill)
2	push `b` (degree 1)	push `b`
3	push `c` (degree 1)	push `c`
4	push `d` (degree 0)	push `d`
5	pop `d` → 0	pop `d` → 0
6	pop `c` → 1	pop `c` → 1
7	pop `b` → 0	pop `b` → 0
8	— (`a` was spilled)	pop `a`: neighbours `b`, `d` both have colour 0 → 1

Chaitin spills a; Briggs colours all four with two colours because a's two neighbours happened to share a colour.

Try it

./course drill chaitin-briggs --seed 2 --difficulty hard --solution gives a graph on which Chaitin spills two nodes and Briggs none.

4. Invariants and correctness¶

Chaitin's allocator¶

Correctness and termination are Theorem 22.3.5 (§2); the NP-completeness of the underlying problem is Theorem 22.3.6. The invariant that makes Select work is that each node, when pushed, had fewer than \(k\) neighbours left: the order of Select is the reverse, so those neighbours are exactly the ones already coloured when it is popped.

Colouring order is the reverse of the removal order

Select must pop in the reverse of the push order. The guarantee "fewer than \(k\) neighbours" is about the neighbours that remained in the graph when the node was removed, which are the nodes pushed after it. Colouring in push order would colour a node while its guaranteed neighbours are still uncoloured, and colour the others later against it, so a node coloured late can find all \(k\) colours taken by neighbours it had no bound on.

Briggs's optimistic colouring¶

Theorem 22.3.9 (Optimistic colouring is correct and never worse)

(i) Algorithm 22.3.8 colours the non-spilled nodes properly. (ii) With the same deterministic choice rules, the actual spills of Briggs's OptimisticSimplify/Select are a subset of the nodes Chaitin's Simplify spills. (iii) A node that was pushed while insignificant is never an actual spill.

Proof

(i) OptimisticSelect gives \(v\) a colour only if it is not used by any coloured neighbour, and it never recolours; so coloured neighbours always differ. (ii) Both algorithms remove the same node at each step: when some node is insignificant both remove the first such node, and otherwise both remove the same argmin (the graphs \(H\) are equal because each removes the node it chose, pushed or spilled). So the potential spills of Briggs are exactly Chaitin's spills, and every actual spill is a potential spill. (iii) Let \(v\) be pushed when \(\deg_H(v) < k\). When \(v\) is popped, the coloured nodes are a subset of the nodes of \(H - v\) (the nodes pushed after it); so at most \(\deg_H(v) \le k - 1\) neighbours of \(v\) are coloured, and a colour is free.

The optimism can be improved further: when a potential spill is popped and no colour is free, biased colouring and spill choice at select time (spilling a cheaper already-coloured neighbour instead) are refinements discussed in §6.

5. Complexity¶

\(n\) = nodes, \(e\) = edges, \(k\) registers, \(R\) = rounds of the outer loop.

Algorithm	Time (worst)	Time (typical)	Space	Justification
Build	\(O(N \cdot L)\), \(e = O(n^2)\)	dominates	\(O(n^2)\) bits + \(O(e)\) lists	Lesson 22.1 §5
Simplify (Chaitin or Briggs)	\(O(n + e)\) with degree buckets; \(O(n^2)\) with a scan for the spill candidate	\(O(n + e)\)	\(O(n)\)	each removal decrements \(\le \deg\) counters: \(\sum \deg = 2e\); the cost/degree argmin is a scan over the stuck nodes
Select	\(O(n + e)\)	same	\(O(k)\) per node	each node inspects its neighbours once
Whole allocator	\(O(R \cdot (N L + n + e))\)	\(R \le 3\) in practice	as Build	rebuild each round

Pathological family. The complete graph \(K_n\) (the function of Lesson 22.1 §5 that defines \(n\) values and uses them all at the end) with \(k < n\) registers: simplification is stuck at once, and \(n - k\) times in a row it scans every remaining node to find the smallest cost/degree, \(\sum_{j=k+1}^{n} j = \Theta(n^2)\) work on top of the \(\Theta(n^2)\) edges. The outer loop runs at most once per original value that can be spilled, since every round spills at least one of them and never re-spills a spill product (Theorem 22.3.5), so \(R \le n + 1\); in practice \(R\) is two or three [BCT94]. Build dominates, which is why fast allocators avoid the graph (Lesson 22.5).

Chaitin's allocator¶

Priority-based colouring (Chow–Hennessy). Colour live ranges in order of a priority (savings per unit of range size), and split a live range that cannot be coloured instead of spilling it whole [CH90]. Trade-off: splitting keeps parts of a value in registers, at the price of copies; a precursor of LLVM's greedy allocator (Lesson 22.8).
Hierarchical / regional colouring. Callahan and Koblenz colour a tree of regions (loops) bottom-up, spilling at region boundaries [CK91]; GCC's IRA colours regions top-down and moves spill code to region borders [GCC-IRA]. Trade-off: spill code outside hot loops, more complex bookkeeping.
Spill-cost refinements. Cost/degree², or cost minus a multiple of the live range's area (HotSpot's LRG::score, §7); Bernstein et al. run simplification with three metrics and keep the colouring with the least spill cost [BGG+89]. Trade-off: more compile time for less spill code.

Briggs's optimistic colouring¶

Biased colouring. When several colours are free in select, prefer the colour of a move partner [BCT94]. Trade-off: removes copies without coalescing's risk; nearly free.
Iterated coalescing interleaves Briggs-style conservative coalescing with simplification (Lesson 22.4). Trade-off: more moves removed, more complex worklists.
Optimistic coalescing (Park and Moon): coalesce aggressively, then undo coalescing for nodes that end up actual spills [PM04]; Bouchez, Darte and Rastello improve both the conservative tests and the undo step [BDR08]. Trade-off: better copies, needs splitting of coalesced nodes.

7. In real compilers¶

Chaitin's allocator¶

HotSpot's C2 server compiler is a Chaitin–Briggs allocator: PhaseChaitin::Register_Allocate (src/hotspot/share/opto/chaitin.cpp, jdk-21+35) builds the interference graph (PhaseIFG), coalesces aggressively, then loops Simplify / Select / Split until nothing spills; C2 splits spilled live ranges instead of spilling them everywhere [HS-Chaitin]. GCC's IRA uses Chaitin–Briggs colouring per region (gcc/ira-color.cc, color_allocnos, gcc-15.1.0) [GCC-IRA].

HotSpot C2's simplify/select/split loop and its spill score

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/chaitin.cpp' \
  | sed -n '100,111p;529,541p'

Output (complete):

// Compute score from cost and area.  Low score is best to spill.
static double raw_score( double cost, double area ) {
  return cost - (area*RegisterCostAreaRatio) * 1.52588e-5;
}

double LRG::score() const {
  // Scale _area by RegisterCostAreaRatio/64K then subtract from cost.
  // Bigger area lowers score, encourages spilling this live range.
  // Bigger cost raise score, prevents spilling this live range.
  // (Note: 1/65536 is the magic constant below; I dont trust the C optimizer
  // to turn a divide by a constant into a multiply by the reciprical).
  double score = raw_score( _cost, _area);
  // Prepare for Simplify & Select
  cache_lrg_info();           // Count degree of LRGs

  // Simplify the InterFerence Graph by removing LRGs of low degree.
  // LRGs of low degree are trivially colorable.
  Simplify();

  // Select colors by re-inserting LRGs back into the IFG in reverse order.
  // Return whether or not something spills.
  uint spills = Select( );

  // If we spill, split and recycle the entire thing
  while( spills ) {

What to notice: Simplify and Select are Algorithm 22.3.4's two phases, and while( spills ) is its outer loop ("split and recycle the entire thing" = insert spill code, rebuild, recolour). The spill metric is a variant of Definition 22.3.2: C2 prefers to spill live ranges with a large area (length × pressure), not only a small cost per degree. (java -XX:+PrintOptoAssembly would show the result, but only in debug builds of the JVM, so the pinned source is quoted instead.)

Briggs's optimistic colouring¶

GCC's IRA says in its header comment that it "uses Briggs optimistic coloring which is a major improvement over Chaitin's coloring. Therefore IRA does not spill allocnos at this point" (gcc/ira.cc, gcc-15.1.0); push_allocnos_to_stack and pop_allocnos_from_stack in gcc/ira-color.cc are Algorithm 22.3.8's two phases [GCC-IRA]. HotSpot's PhaseChaitin::Select also colours optimistically and reports whether something spills [HS-Chaitin].

GCC IRA pushes potential spills and decides when popping

Reproduce (gcc 14.2.0, x86-64 Linux; the dump file number depends on the GCC version):

cat > press.c <<'EOF'
long g(long);
long press(long *a, long n) {
  long s0 = 0, s1 = 1, s2 = 2, s3 = 3, s4 = 4, s5 = 5, s6 = 6, s7 = 7;
  long s8 = 8, s9 = 9, s10 = 10, s11 = 11, s12 = 12, s13 = 13;
  for (long i = 0; i < n; i++) {
    long x = a[i];
    s0 += x; s1 ^= x; s2 += x * 3; s3 -= x; s4 += x >> 1; s5 |= x; s6 += x << 2;
    s7 &= x; s8 += x * 5; s9 ^= x << 1; s10 += x >> 3; s11 -= x * 7; s12 ^= x + 1; s13 += x - 2;
    if (x == 42) s0 = g(s0);
  }
  return s0 + s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8 + s9 + s10 + s11 + s12 + s13;
}
EOF
gcc-14 -O2 -fno-tree-vectorize -S -fdump-rtl-ira press.c
grep -c "Pushing" press.c.*r.ira
grep -E "potential spill|Popping.*spill" press.c.*r.ira | head -12
grep -A2 "^Disposition" press.c.*r.ira

Output (complete):

71
      Pushing a21(r111,l0)(potential spill: pri=63, cost=9967)
      Pushing a29(r138,l0)(potential spill: pri=76, cost=5770)
      Pushing a25(r109,l0)(potential spill: pri=80, cost=9967)
      Pushing a23(r110,l0)(potential spill: pri=84, cost=9967)
      Pushing a19(r112,l0)(potential spill: pri=89, cost=9967)
      Popping a19(r112,l0)  -- spill
      Popping a23(r110,l0)  -- spill
      Popping a25(r109,l0)  -- spill
      Popping a29(r138,l0)  -- spill
      Popping a21(r111,l0)  -- spill
      Pushing a35(r111,l1)(potential spill: pri=42, cost=6572)
      Pushing a48(r138,l1)(potential spill: pri=45, cost=3274)
Disposition:
   32:r107 l1     5   26:r107 l0     5   50:r108 l1     0   33:r109 l1   mem
   25:r109 l0   mem   34:r110 l1   mem   23:r110 l0   mem   35:r111 l1   mem

What to notice: an allocno is a pseudo-register in a region (l0 = the whole function, l1 = the loop). Fourteen accumulators plus the pointer, the counter and the bound need more than x86-64's 15 allocatable GPRs, so simplification gets stuck and IRA pushes nodes as potential spills with a priority (Definition 22.3.7); the decision is made at Popping. Here all five potential spills of region l0 really find no colour (-- spill) and end up in memory (mem in the final Disposition). The loop region l1 is coloured separately: regional colouring (§6) lets IRA keep a pseudo in a register inside the loop and in memory outside it.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Chaitin's allocator	colours whenever simplification succeeds; spills whole values; heuristic (NP-complete problem)	\(O(R(NL + n + e))\) · slow on large functions (graph build)	good; spills more than needed on graphs like the square	moderate: build, simplify, select, spill code, iterate	textbooks; historical PL.8; basis of all colouring allocators
Briggs's optimistic colouring	never more spills than Chaitin (Theorem 22.3.9); colours many graphs Chaitin gives up on	same as Chaitin	fewer spills than Chaitin [BCT94]	Chaitin + a few lines	GCC IRA, HotSpot C2, the lab's E2

Measured in the lab (ch22-compare, 414 functions, \(K = 4\), two callee-saved registers per class): the Chaitin–Briggs allocator with iterated coalescing spills 2269 values with weighted spill cost 68935, against 281309 for local allocation and 105719 for Poletto–Sarkar linear scan (full table: README).

Choose Chaitin's formulation when you teach or prototype: it is short and its correctness argument is one lemma. Choose Briggs's optimistic colouring whenever you implement graph colouring for real: it costs nothing extra and removes needless spills.

9. Assessment¶

Quiz (./course quiz 22): chaitin-simplify-order, chaitin-spill-choice, simplify-lemma, briggs-square, briggs-never-worse (tags chaitin, briggs).
Drill: ./course drill chaitin-briggs (stack order, Briggs's actual spills, Chaitin's spills, colours).
Flashcards: tags chaitin, briggs.
Lab: E2 allocateChaitinBriggs (SPEC R6).

References¶

See the chapter references.

Lesson 22.3 — Graph colouring: Chaitin's allocator and Briggs's optimistic colouring¶

1. Problem and motivation¶

Chaitin's allocator¶

Briggs's optimistic colouring¶

2. Definitions and algorithms¶

Chaitin's allocator¶

Briggs's optimistic colouring¶

3. Worked example¶

Chaitin's allocator¶

Briggs's optimistic colouring¶

4. Invariants and correctness¶

Chaitin's allocator¶

Briggs's optimistic colouring¶

5. Complexity¶

6. Variants and refinements¶

Chaitin's allocator¶

Briggs's optimistic colouring¶

7. In real compilers¶

Chaitin's allocator¶

Briggs's optimistic colouring¶

8. Comparison¶

9. Assessment¶

References¶