Lesson 22.1 — The problem: live ranges, interference and constraints¶

Techniques: live ranges and interference graphs; register classes and sub-registers; pre-coloured registers and calling conventions · Lab: labs/ch22-regalloc (the checker and rewriter implement this lesson) · Prerequisites: Ch 14 (liveness of SSA values, Definition 14.3.9), Ch 15 (dominance), Ch 16 (strict SSA, phis as parallel copies), Ch 21 (MIR, calling conventions) · Time: 4–5 hours

After instruction selection (Ch 21) every value lives in a virtual register: %12:gr64 in LLVM's MIR, an SSA value in LLVM IR, a "pseudo" in GCC's RTL. There are as many virtual registers as the program needs. The machine has a fixed, small set of physical registers: 16 general-purpose ones on x86-64, 31 on AArch64, some reserved (stack pointer, frame pointer). Register allocation maps the first onto the second. When two values are needed at the same time they must sit in different registers. When more values are needed at once than there are registers, some of them must live in memory, which costs a store when they are defined and a load before each use: they are spilled. The allocator must also respect the machine's irregularities: values of different kinds need different registers, some instructions demand particular registers, and a call destroys some registers but not others. This lesson states the problem precisely. The rest of the chapter surveys the ways to solve it.

The running example of the whole chapter is the loop below: s accumulates a value, i counts to ten.

define i64 @run(i64 %a) {
entry:
  br label %loop
loop:
  %i = phi i64 [ 0, %entry ], [ %i2, %body ]
  %s = phi i64 [ %a, %entry ], [ %s2, %body ]
  %c = icmp slt i64 %i, 10
  br i1 %c, label %body, label %exit
body:
  %t = mul i64 %s, %i
  %u = add i64 %t, %a
  %s2 = xor i64 %u, %i
  %i2 = add i64 %i, 1
  br label %loop
exit:
  %r = add i64 %s, %a
  ret i64 %r
}

In the chapter's small text format (tools/course/lib/regalloc.py, used by the drills) the same program is:

B0:                      # entry
  a = arg
  jmp B1
B1:                      # loop
  i = phi B0:0 B2:i2
  s = phi B0:a B2:s2
  c = lt i 10
  br c B2 B3
B2:                      # body
  t = mul s i
  u = add t a
  s2 = xor u i
  i2 = add i 1
  jmp B1
B3:                      # exit
  r = add s a
  ret r

1. Problem and motivation¶

Input: a function in which every value lives in its own virtual register, and a description of the machine: its registers, how they are grouped into classes, which ones overlap, and what the calling convention says about them. Output: for every virtual register, a physical register or a stack slot, plus the extra instructions (spill stores, reloads, copies) that the choice requires. The result must compute the same thing as the input, and it should execute as few extra instructions as possible, weighted by how often they execute.

Allocation matters more than almost any other back-end decision. A load from the stack costs several cycles even when it hits the L1 cache, and a loop that reloads a value on every iteration can run at half speed. The first systematic treatment, by Chaitin and his colleagues at IBM for the PL.8 compiler, modelled it as colouring an interference graph [CACCHM81]: values are nodes, an edge joins two values that must not share a register, and registers are colours. Every later technique either refines that model (Lessons 22.3 and 22.4), replaces the graph with a cheaper structure (live intervals, Lesson 22.5), exploits the structure SSA gives the graph (Lesson 22.6) or states the whole problem as an optimization problem (Lesson 22.7).

Live ranges and interference graphs¶

A value needs a register from its definition until its last use: its live range. Two values whose live ranges overlap interfere. Liveness is the Chapter 14 analysis (Definition 14.3.9); this lesson turns it into interference and into the per-point register demand, called register pressure. LLVM stores live ranges as live intervals: lists of segments over a numbering of the instructions (LiveIntervals, [LLVM-LiveIntervals]).

Register classes and sub-registers¶

Real register files are not uniform. Floating-point values go in xmm or v registers, integers in general-purpose ones: these are register classes. Registers overlap: on x86-64, eax is the low half of rax, and al the low byte of eax. On AArch64 w0 is the low half of x0. A value of class "32-bit GPR" conflicts with a value in any register that overlaps the one it is given. LLVM describes all of this in TableGen (Lesson 21.8) and splits each register into register units so that an overlap test is a set intersection.

Pre-coloured registers and calling conventions¶

Some values must be in particular registers: the first argument arrives in rdi (System V) or x0 (AAPCS64), a result is returned in rax/x0, and x86 division writes rdx:rax. Such constraints make parts of the problem pre-coloured. A call also clobbers the caller-saved registers, so a value that is live across a call must be in a callee-saved register or on the stack. The callee-saved registers are not free either: a function that uses one must save and restore it in its prologue and epilogue (Lesson 21.9).

In pebblec all of this is LLVM's job (llc runs LiveIntervals, the RegisterCoalescer and the greedy allocator, Lesson 22.8). The chapter's lab (labs/ch22-regalloc) uses the SSA values of LLVM IR as virtual registers, with a machine model of $K$ registers per class and a configurable number of callee-saved ones. Its checker implements Definitions 22.1.4–22.1.6 and its rewriter implements the semantics of Theorem 22.1.14.

2. Definitions and algorithms¶

Live ranges and interference graphs¶

Definition 22.1.1 (Machine model)

A machine has a finite set $\mathcal{R}$ of physical registers, partitioned into register classes $\mathcal{R}_c$ for classes $c \in \mathcal{C}$, with $K_c = \lvert \mathcal{R}_c \rvert$. An alias relation $\asymp$ on $\mathcal{R}$ is reflexive and symmetric: $r \asymp r'$ when the two registers share storage (eax $\asymp$ rax). A subset $\mathcal{R}^{\mathrm{cs}} \subseteq \mathcal{R}$ is callee-saved; the rest are caller-saved and are clobbered by every call. When every class has pairwise non-aliasing registers and $\asymp$ is the identity, the machine is uniform; the lab's machine is uniform with classes $\mathrm{GPR}$ and $\mathrm{FPR}$ and registers $r_0, \dots, r_{K_c - 1}$, the top $C_c$ of which are callee-saved.

Definition 22.1.2 (Values and points)

Let $F$ be a function in strict SSA form (every use is dominated by its definition, Ch 16). Its values $V$ are its arguments and the results of its instructions. Each value $v$ has a class $\mathrm{cls}(v) \in \mathcal{C}$. A program point is a position between two consecutive instructions of a block, or at a block's start or end. An instruction reads its operands and then writes its result; the phis of a block are read on the incoming edges (at the end of the predecessor) and written together at the start of the block, as one parallel copy.

Definition 22.1.3 (Liveness)

A value $v$ is live at a point $p$ if some path from $p$ reaches a use of $v$ without passing its definition, with the phi convention of Definition 22.1.2 (a phi operand from $P$ is used at the end of $P$). $\mathrm{live\text{-}in}(B)$ and $\mathrm{live\text{-}out}(B)$ are the values live at the start and end of block $B$; they are the least solution of the equations of Ch 14, Definition 14.3.9, which is exactly pebble::dataflow::computeLiveness.

Definition 22.1.4 (Definition points and live-after sets)

The definition points $\mathcal{P}$ of $F$ are: the function entry, which defines all arguments; the start of each block with phis, which defines all its phis; and each instruction that has a result or is a call. For a point $p$, $\mathrm{defs}(p)$ is the set of values it defines and $\mathrm{live}(p)$ the set of values live just after it (for a block start: $\mathrm{live\text{-}in}(B)$ together with the phis still used in $B$).

Definition 22.1.5 (Interference)

Two distinct values $u, v$ with $\mathrm{cls}(u) = \mathrm{cls}(v)$ interfere, written $u \mathbin{\text{—}} v$, if there is a point $p \in \mathcal{P}$ with $u \in \mathrm{defs}(p)$ and $v \in \mathrm{defs}(p) \cup \mathrm{live}(p)$, or the same with $u$ and $v$ exchanged. The interference graph is $G_I = (V, E_I)$ with $E_I = \{\{u, v\} \mid u \mathbin{\text{—}} v\}$. A move pair (affinity) is a pair $\{\varphi, a\}$ where $a$ is an operand of phi $\varphi$ (or, in non-SSA code, the two sides of a copy $x \gets y$); giving both ends the same register removes the copy.

The definition is Chaitin's: "a value interferes with everything live where it is defined" [CACCHM81]. Two remarks. First, a value that dies at an instruction does not interfere with that instruction's result, because the instruction reads before it writes; they may share a register, which is how add r1, r1, r2 works. Second, a dead definition still interferes with everything live after it: it writes its register even if nobody reads it.

Definition 22.1.6 (Assignment and validity)

An assignment is a map $\rho : V \to \mathcal{R} \cup \{\bot\}$; $\rho(v) = \bot$ means $v$ is spilled: it lives in its own stack slot, is stored after its definition and reloaded before each use. $\rho$ is valid when (i) $\rho(v) \in \mathcal{R}_{\mathrm{cls}(v)} \cup \{\bot\}$ for every $v$; (ii) for every $u \mathbin{\text{—}} v$ with $\rho(u), \rho(v) \neq \bot$: $\neg(\rho(u) \asymp \rho(v))$; (iii) for every call point $p$ and every $v \in \mathrm{live}(p) \setminus \mathrm{defs}(p)$ with $\rho(v) \neq \bot$: $\rho(v) \in \mathcal{R}^{\mathrm{cs}}$; (iv) every pre-coloured value $v$ with required register $r_v$ has $\rho(v) = r_v$. On a uniform machine without pre-colouring, (ii) says that $\rho$ restricted to the registered values is a proper colouring of $G_I$.

The lab's model reloads a spilled value through a scratch register outside the $K$, as Poletto and Sarkar's and many textbook models do [PS99]. Production allocators spill into the $K$ registers: the reload's short live range needs a register too, which is why Chaitin's allocator rebuilds the graph and iterates (Lesson 22.3).

Definition 22.1.7 (Register pressure and MaxLive)

The pressure of class $c$ at a point $p$ is $P_c(p) = \lvert \{ v \in \mathrm{defs}(p) \cup \mathrm{live}(p) \mid \mathrm{cls}(v) = c\} \rvert$. $\mathrm{MaxLive}_c = \max_{p \in \mathcal{P}} P_c(p)$ (also taking $\lvert \mathrm{live\text{-}in}(B) \rvert$ for every block $B$). A function fits in the machine when $\mathrm{MaxLive}_c \le K_c$ for every class $c$.

Definition 22.1.8 (Live interval and lifetime hole)

Fix a linear order of the blocks and number the instructions $0, 1, 2, \dots$ in that order; instruction $j$ reads at slot $2j$ and writes at slot $2j + 1$. The live range of $v$ is the set of slots at which $v$ is live (or defined). Written as a sorted list of maximal segments $[s_1, e_1] \cup \dots \cup [s_m, e_m]$, it is $v$'s live interval; the gaps between segments are lifetime holes. The convex hull $[s_1, e_m]$ is the interval Poletto–Sarkar linear scan uses (Lesson 22.5).

Algorithm 22.1.9 (Build the interference graph)

Input: a strict SSA function $F$; $\mathrm{live\text{-}out}(B)$ for every block (Definition 22.1.3).
Output: $G_I$ (Definition 22.1.5) and the move pairs.
Precondition: liveness is the least solution; every value is defined once.
Postcondition: $\{u, v\} \in E_I$ iff $u \mathbin{\text{—}} v$.
Invariant: during the backward walk over block $B$, before instruction $I$ is processed, live $= \mathrm{live}(p_I)$, the values live just after $I$ (Lemma 22.1.13).

function Build(F):
    E ← ∅; M ← ∅
    E ← E ∪ { {x, y} | x ≠ y arguments of F, cls(x) = cls(y) }       # function entry point
    for each block B:
        live ← live-out(B) ∪ { operands of B's terminator }
        for each non-phi instruction I of B, from last to first:
            if I defines d:
                for each w in live, w ≠ d, cls(w) = cls(d): E ← E ∪ {{d, w}}
                live ← live \ {d}
            live ← live ∪ { value operands of I }
        Φ ← the phis of B                                            # block-entry point
        for each φ in Φ:
            for each w in (Φ ∪ live-in(B) ∪ live), w ≠ φ, cls(w) = cls(φ): E ← E ∪ {{φ, w}}
            for each (P, a) incoming to φ with a a value: M ← M ∪ {{φ, a}}
    return (V, E), M

A dead definition $d$ is not in live, so it gets edges to everything live after it and is never added back: that is the "dead definitions interfere" rule. Chaitin's variant for non-SSA code skips the edge $\{d, y\}$ when $I$ is the copy $d \gets y$ [CACCHM81].

Register classes and sub-registers¶

Definition 22.1.10 (Register units)

A register unit is a minimal piece of storage. Each register $r$ covers a non-empty set $\mathrm{units}(r)$, and $r \asymp r'$ iff $\mathrm{units}(r) \cap \mathrm{units}(r') \neq \emptyset$. A sub-register index names the part of a register a value occupies: %7.sub_32bit in MIR is the low 32 bits of the 64-bit virtual register %7.

With units, validity condition (ii) becomes "no unit is used by two interfering values". LLVM keeps one interference structure per unit (LiveRegMatrix), so a check against rax also checks eax, ax and al.

Pre-coloured registers and calling conventions¶

A call instruction is modelled as a point that defines every caller-saved register: in MIR it carries a register mask listing the preserved registers. A value live across it therefore interferes with every caller-saved register, which is condition (iii) of Definition 22.1.6 phrased as interference with pre-coloured nodes. Graph-colouring allocators implement it exactly so: one pre-coloured node per physical register, with edges from every call-crossing value to the caller-saved ones [GA96]. Argument and return registers appear as copies from and to pre-coloured registers (%4:gr64 = COPY $rdi), which the coalescer and the allocator's hints try to make free.

3. Worked example¶

The running example as a CFG (successors in the order br lists them):

flowchart TD
  B0(["<b>B0</b><br/>a = arg<br/>jmp B1"])
  B1["<b>B1</b><br/>i = phi B0:0 B2:i2<br/>s = phi B0:a B2:s2<br/>c = lt i 10<br/>br c B2 B3"]
  B2["<b>B2</b><br/>t = mul s i<br/>u = add t a<br/>s2 = xor u i<br/>i2 = add i 1<br/>jmp B1"]
  B3["<b>B3</b><br/>r = add s a<br/>ret r"]
  B0 --> B1
  B1 --> B2
  B1 --> B3
  B2 --> B1

Liveness (Definition 22.1.3; computed by regalloc.liveness). The phi operands i2 and s2 are live-out of B2 but not live-in to B1; a is live-out of B0 both as the phi operand of s and because B2 and B3 use it.

block	LiveIn	LiveOut
B0	{}	{a}
B1	{a}	{a, i, s}
B2	{a, i, s}	{a, i2, s2}
B3	{a, s}	{}

Definition points (Definition 22.1.4), walked by Algorithm 22.1.9. One row per point; the last column is what the point adds to $E_I$:

point	instruction	defs	live after	pressure	new edges
B0.1	`a = arg`	a	{a}	1	—
B1 entry	`i = phi …; s = phi …`	i, s	{a, i, s}	3	a-i, a-s, i-s
B1.1	`c = lt i 10`	c	{a, c, i, s}	4	a-c, c-i, c-s
B2.1	`t = mul s i`	t	{a, i, t}	3	a-t, i-t
B2.2	`u = add t a`	u	{a, i, u}	3	a-u, i-u
B2.3	`s2 = xor u i`	s2	{a, i, s2}	3	a-s2, i-s2
B2.4	`i2 = add i 1`	i2	{a, i2, s2}	3	a-i2, i2-s2
B3.1	`r = add s a`	r	{r}	1	—

B2.1: s dies at t = mul s i (it is not live after), so t and s do not interfere and may share a register.
B2.4: i dies at i2 = add i 1; i and i2 do not interfere either, and neither do s and s2. These two move pairs can be coalesced (Lesson 22.4).
The third move pair, s–a (the phi operand on the entry edge), does interfere: a is live in the whole loop.
$\mathrm{MaxLive} = 4$, at B1.1, where a, c, i and s are all live.

The interference graph has 9 nodes and 14 edges (dotted: move pairs that do not interfere):

flowchart LR
  a((a)) --- c((c))
  a --- i((i))
  a --- i2((i2))
  a --- s((s))
  a --- s2((s2))
  a --- t((t))
  a --- u((u))
  c --- i
  c --- s
  i --- s
  i --- s2
  i --- t
  i --- u
  i2 --- s2
  r((r))
  i -.- i2
  s -.- s2

Degrees: a 7, i 6, c, s, s2 3, i2, t, u 2, r 0. The clique $\{a, c, i, s\}$ shows that 4 registers are needed without spilling; Lesson 22.6 shows that 4 also suffice.

Live intervals (Definition 22.1.8), with the blocks in the order B0, B1, B2, B3 and the phis of B1 as one point: a is [1, 20], i [5, 16], s [5, 20], c [7, 8], t [11, 12], u [13, 14], s2 [15, 19], i2 [17, 19], r [21, 22]. The interval of s has a lifetime hole: s dies inside B2 at slot 10 and is live again in B3 from slot 20, so the precise live range is [5, 10] ∪ [20, 20]; the convex hull [5, 20] hides the hole.

Try it

./course drill interference-graph --seed 3 --difficulty medium --solution builds the graph of a random SSA program with the same table; --difficulty hard adds copies and Chaitin's move rule.

4. Invariants and correctness¶

Live ranges and interference graphs¶

Lemma 22.1.11 (Simultaneous liveness in strict SSA)

Let $F$ be strict and let $x \ne y$ be values that are both live at a point $q$. Then $\mathrm{def}(x)$ dominates $\mathrm{def}(y)$ or vice versa, and if $\mathrm{def}(x)$ strictly dominates $\mathrm{def}(y)$ then $x$ is live just after $\mathrm{def}(y)$.

Proof

A value live at a reachable point $q$ has a use reachable from $q$; by strictness its definition dominates that use, and a definition that did not dominate $q$ could be avoided on a path entry $\leadsto q \leadsto$ use, contradicting strictness. So $\mathrm{def}(x)$ and $\mathrm{def}(y)$ both dominate $q$, and the dominators of $q$ form a chain (Ch 15, Theorem 15.1.2), which gives the first claim. Now let $\mathrm{def}(x)$ strictly dominate $\mathrm{def}(y)$. Since $x$ is live at $q$, there is a path $\pi_1 : q \leadsto \mathrm{use}(x)$ that avoids $\mathrm{def}(x)$. It remains to find a path $\pi_0 : \mathrm{def}(y) \leadsto q$ that avoids $\mathrm{def}(x)$; then $\pi_0 \cdot \pi_1$ shows that $x$ is live just after $\mathrm{def}(y)$. Suppose, for a contradiction, that every path from $\mathrm{def}(y)$ to $q$ passes through $\mathrm{def}(x)$. Take any path from the entry to $q$. It contains $\mathrm{def}(y)$, which dominates $q$; after the last occurrence of $\mathrm{def}(y)$ it contains $\mathrm{def}(x)$, and the part from that occurrence of $\mathrm{def}(x)$ to $q$ avoids $\mathrm{def}(y)$. Because $\mathrm{def}(x)$ strictly dominates $\mathrm{def}(y)$, $\mathrm{def}(y)$ does not dominate $\mathrm{def}(x)$, so some path entry $\leadsto \mathrm{def}(x)$ avoids $\mathrm{def}(y)$. Concatenating it with the part $\mathrm{def}(x) \leadsto q$ and with a path $q \leadsto \mathrm{use}(y)$ that avoids $\mathrm{def}(y)$ (it exists because $y$ is live at $q$) gives a path from the entry to a use of $y$ that avoids $\mathrm{def}(y)$, contradicting strictness. (This is the lemma behind Budimlić et al.'s interference test [BCH+02] and Hack's chordality proof [Hack07].)

Theorem 22.1.12 (Definition points capture every conflict)

In a strict SSA function, if $x \ne y$ of the same class are both live at some point, or one is defined at a point where the other is live, then $x \mathbin{\text{—}} y$ (Definition 22.1.5). Conversely, for every interfering pair, both are live at some point, or one is defined at a point where the other is live or also defined.

Proof

If one of them is defined where the other is live, this is Definition 22.1.5 with that definition point. Otherwise both are live at $q$; by Lemma 22.1.11, say $\mathrm{def}(x)$ dominates $\mathrm{def}(y)$. If the two definitions are the same point (two arguments, or two phis of one block) they are both in $\mathrm{defs}(p)$ and interfere. If $\mathrm{def}(x)$ strictly dominates $\mathrm{def}(y)$, Lemma 22.1.11 puts $x$ in $\mathrm{live}(p_y)$ where $p_y$ is $y$'s definition point, so $y \in \mathrm{defs}(p_y)$ and $x \in \mathrm{live}(p_y)$: they interfere. The converse is Definition 22.1.5 restated: $u \in \mathrm{defs}(p)$ and $v \in \mathrm{defs}(p) \cup \mathrm{live}(p)$ means both occupy a register just after $p$ (a dead $u$ is not live there, which is why the converse keeps the "defined at a point" cases).

Lemma 22.1.13 (Build is correct)

Algorithm 22.1.9 terminates, and its output edge set is exactly $E_I$.

Proof

Termination is clear: each block is walked once. Invariant (the one stated in the algorithm): when instruction $I$ is about to be processed, live equals the set of values live just after $I$. Initialization: before the last instruction (the terminator's predecessor in the walk) live is $\mathrm{live\text{-}out}(B)$ plus the terminator's operands, which is exactly what is live after the last non-terminator. Maintenance: live-before$(I)$ $=$ (live-after$(I) \setminus \mathrm{defs}(I)) \cup \mathrm{uses}(I)$, which is the update. At the phis live is what is live just after the phis, and $\mathrm{live\text{-}in}(B) \subseteq$ live $\cup\, \Phi$ by the dataflow equations. So each point $p$ adds exactly the pairs $\{d, w\}$ with $d \in \mathrm{defs}(p)$, $w \in \mathrm{defs}(p) \cup \mathrm{live}(p)$, and every point of $\mathcal{P}$ is visited once: the output is $E_I$.

Pre-coloured registers and calling conventions¶

The next theorem is what the lab's rewriter relies on: validity is not only necessary, it is sufficient for correctness.

Theorem 22.1.14 (A valid assignment preserves the program's results)

Let $\rho$ be valid (Definition 22.1.6) on a uniform machine. Execute $F$ with a register file $\mathit{reg}[r]$ for each $r \in \mathcal{R}$ and one memory slot $\mathit{slot}[v]$ for each spilled $v$: every operand is read from its location, every result is written to its location, the phis of $B$ are executed on each incoming edge as a parallel copy (all reads, then all writes), and every call overwrites all caller-saved registers with arbitrary values. Then every instruction reads the same operand values as in the original execution, so the two executions compute the same results.

Proof

Let $\mathrm{val}(v)$ be $v$'s current value in the original execution. We prove by induction over the execution the invariant $J$: at every point, every value $v$ live there has $\mathit{loc}(v) = \mathrm{val}(v)$, where $\mathit{loc}(v)$ is $\mathit{reg}[\rho(v)]$ or $\mathit{slot}[v]$. Base: at the function entry all arguments are written; they pairwise interfere (they share the entry point), so registered arguments are in distinct registers and $J$ holds. Instruction $I$ defining $d$: its operands are live just before $I$, so by $J$ it reads the right values. It writes only $\mathit{loc}(d)$. A value $w \ne d$ live after $I$ either is spilled (its slot is untouched) or has $\rho(w) \ne \rho(d)$, because $w \in \mathrm{live}(p_I)$ makes $d \mathbin{\text{—}} w$; so $w$'s location still holds $\mathrm{val}(w)$. Calls: a value $w$ live after the call, other than its result, is in a callee-saved register by (iii) or spilled, so the clobber does not touch it. Edge $P \to B$: the phi operands are live at the end of $P$, so the reads are right. The writes go to $\mathit{loc}(\varphi)$ for the phis of $B$; the phis pairwise interfere and each interferes with every $w \in \mathrm{live\text{-}in}(B)$ (both are in the block-entry point), so no live-in value and no other phi is overwritten. Edges out of a block with two successors are split first, so the copies of $P \to B$ never run on the way to another successor. In every case $J$ holds again, and $J$ at the operands of each instruction is the claim.

Proposition 22.1.15 (MaxLive is a lower bound)

In a strict SSA function, the values of class $c$ in $\mathrm{defs}(p) \cup \mathrm{live}(p)$ form a clique of $G_I$ for every $p \in \mathcal{P}$. Hence $\mathrm{MaxLive}_c \le \omega(G_I^c) \le \chi(G_I^c)$, and no valid assignment without spills exists when $\mathrm{MaxLive}_c > K_c$.

Proof

Two values of the set are defined at $p$, or one is defined at $p$ and the other live after it, or both are live after $p$; in all three cases Theorem 22.1.12 gives an edge. A clique of size $m$ needs $m$ colours, and on a uniform machine a spill-free valid assignment is a proper colouring with $K_c$ colours (Definition 22.1.6 (ii)).

Interference is not 'live ranges overlap anywhere'

Two values whose live ranges merely touch do not interfere: in t = mul s i, s ends where t begins, and they can share a register. Computing interference from convex intervals ([start, end] overlap) instead of from definition points adds false edges: with the hull [5, 20] of s, linear scan believes s conflicts with t, u, s2, i2, which the real graph does not say. Lesson 22.5 shows what that costs.

5. Complexity¶

Let $n = \lvert V \rvert$ values, $N$ instructions, $b$ blocks, $L = \max_p \lvert \mathrm{live}(p) \rvert$, and $E = \lvert E_I \rvert$.

Task	Worst case	Typical	Space	Justification
liveness (Ch 14)	$O(b \cdot n)$ bit-vector operations per pass, $O(d + 2)$ passes	2–3 passes	$O(b \cdot n)$ bits	Ch 14, Lesson 14.4
Build (Algorithm 22.1.9)	$O(N \cdot L)$	$O(N \cdot L)$, $L \ll n$	$O(n^2)$ bits matrix + $O(E)$ lists	each point adds at most $L + \lvert\mathrm{defs}(p)\rvert$ edges; membership test $O(1)$ in a bit matrix
live intervals	$O(N + \sum_v \lvert \text{segments}(v) \rvert)$	linear	$O(N + n)$	one backward walk per block
MaxLive	$O(N \cdot L)$	linear	$O(L)$	pressure is $\lvert\mathrm{live}(p)\rvert$ at each point

Pathological family. The function that defines $n$ values in its entry block and then uses them all in one final instruction has $\mathrm{live}(p)$ of size $k$ after the $k$-th definition, so $E_I$ is the complete graph: $E = n(n-1)/2 = \Theta(n^2)$ edges, and Build does $\Theta(n^2)$ work however it is implemented. Colouring allocators therefore keep both a triangular bit matrix (for $O(1)$ membership) and adjacency lists (to enumerate neighbours) [EaC3, Ch. 13]. At scale the quadratic graph, not colouring, is what makes graph colouring expensive: Poletto and Sarkar report that building the graph dominated their colouring allocator's time on large functions [PS99], which motivated linear scan.

Live ranges and interference graphs¶

Webs instead of SSA values. For non-SSA code the nodes are webs: maximal unions of def-use chains that share a definition or a use [Muchnick, §16.3]. Trade-off: needs reaching definitions; the graph can be any graph (Lesson 22.3, NP-completeness).
Value-based interference. Two values that provably hold the same value (a copy and its source) need not interfere even if both are live; Boissinot et al. make this the rule for SSA destruction [BDR+09]. Trade-off: fewer edges and more coalescing, but needs value numbering; it is how LLVM's coalescer compares VNInfos (Lesson 16.7).
No graph at all. Interference can be tested on demand from dominance and fast liveness checks [BCH+02, BHG+08]. Trade-off: $O(1)$-ish queries with no quadratic structure, but only for SSA and only pairwise queries.

Register classes and sub-registers¶

Worst-case degree for aliasing registers. Smith, Ramsey and Holloway generalize "degree $< K$" to register files with pairs and overlaps by counting, for each neighbour, how many registers of the node's class it can block [SRH04]. Trade-off: correct simplification on irregular files, more complex bookkeeping.
Register units. LLVM decomposes registers into units and tracks interference per unit. Trade-off: aliasing becomes set intersection; the number of structures grows with the units, not with the classes.

Pre-coloured registers and calling conventions¶

Pre-coloured nodes in the graph (Chaitin; George–Appel) versus hints (LLVM, GCC): a hint asks for a register without forbidding others, so the allocator can still choose a different one and insert a copy. Trade-off: hints never make the problem infeasible; pre-colouring is exact but can force spills.
Callee-saved registers as values. Treat each callee-saved register as a value live from entry to exit, so using it has the cost of its save and restore; Chow's shrink-wrapping then places those saves [Cho88]. LLVM instead charges a "first use of a CSR" cost (-regalloc-csr-first-time-cost, Lesson 22.8).

7. In real compilers¶

Live ranges and interference graphs¶

LLVM computes live intervals in LiveIntervals (llvm/lib/CodeGen/LiveIntervals.cpp, LiveIntervals::computeVirtRegInterval) over slot indexes: every instruction gets an index NB and four sub-slots (B block/phi, e early-clobber, r register, d dead) [LLVM-LiveIntervals]. It never builds an interference graph; interference is a query against a LiveIntervalUnion per register unit (LiveRegMatrix::checkInterference). GCC's IRA builds conflict graphs per region ("allocnos", gcc/ira-conflicts.cc, gcc-15.1.0). Go's allocator computes, for each value, the distance to its next use (regAllocState.computeLive in src/cmd/compile/internal/ssa/regalloc.go, go1.24.7) [Go-regalloc].

The running example's live intervals in LLVM, before coalescing

Reproduce (llc 23.1.2; any OS):

cat > run.ll <<'EOF'
define i64 @run(i64 %a) {
entry:
  br label %loop
loop:
  %i = phi i64 [ 0, %entry ], [ %i2, %body ]
  %s = phi i64 [ %a, %entry ], [ %s2, %body ]
  %c = icmp slt i64 %i, 10
  br i1 %c, label %body, label %exit
body:
  %t = mul i64 %s, %i
  %u = add i64 %t, %a
  %s2 = xor i64 %u, %i
  %i2 = add i64 %i, 1
  br label %loop
exit:
  %r = add i64 %s, %a
  ret i64 %r
}
EOF
llc -O2 -mtriple=x86_64-linux-gnu -stop-before=register-coalescer run.ll -o run.mir
llc -mtriple=x86_64-linux-gnu -passes='print<live-intervals>' run.mir -o /dev/null

Output (abridged: the Live intervals for machine function header, the DIL/DIH/HDI register-unit lines, the empty RegMasks: line, blank lines and the successors/predecessors CFG comments removed):

********** INTERVALS **********
%0 [128r,304r:0) 0@128r  weight:0.000000e+00
%1 [112r,208r:0)[384B,400r:0) 0@112r  weight:0.000000e+00
%2 [272r,288r:1)[288r,352r:0) 0@288r 1@272r  weight:0.000000e+00
%3 [304r,320r:1)[320r,336r:0) 0@320r 1@304r  weight:0.000000e+00
%4 [16r,416r:0) 0@16r  weight:0.000000e+00
%5 [48r,64r:0) 0@48r  weight:0.000000e+00
%6 [32r,48r:0) 0@32r  weight:0.000000e+00
%8 [400r,416r:1)[416r,432r:0) 0@416r 1@400r  weight:0.000000e+00
%9 [208r,224r:1)[224r,240r:0) 0@224r 1@208r  weight:0.000000e+00
%10 [240r,256r:1)[256r,272r:0) 0@256r 1@240r  weight:0.000000e+00
%11 [64r,96B:1)[96B,128r:2)[336r,384B:0) 0@336r 1@64r 2@96B-phi  weight:0.000000e+00
%12 [80r,96B:1)[96B,112r:2)[352r,384B:0) 0@352r 1@80r 2@96B-phi  weight:0.000000e+00
********** MACHINEINSTRS **********
# Machine code for function run: NoPHIs, TracksLiveness, TiedOpsRewritten
Function Live Ins: $rdi in %4
0B  bb.0.entry:
      liveins: $rdi
16B   %4:gr64 = COPY $rdi
32B   %6:gr32 = MOV32r0 implicit-def dead $eflags
48B   %5:gr64 = SUBREG_TO_REG %6:gr32, %subreg.sub_32bit
64B   %11:gr64 = COPY %5:gr64
80B   %12:gr64 = COPY %4:gr64
96B bb.1.loop:
112B      %1:gr64 = COPY %12:gr64
128B      %0:gr64 = COPY %11:gr64
144B      CMP64ri32 %0:gr64, 9, implicit-def $eflags
160B      JCC_1 %bb.3, 15, implicit killed $eflags
176B      JMP_1 %bb.2
192B    bb.2.body:
208B      %9:gr64 = COPY %1:gr64
224B      %9:gr64 = IMUL64rr %9:gr64(tied-def 0), %0:gr64, implicit-def dead $eflags
240B      %10:gr64 = COPY %9:gr64
256B      %10:gr64 = ADD64rr %10:gr64(tied-def 0), %4:gr64, implicit-def dead $eflags
272B      %2:gr64 = COPY %10:gr64
288B      %2:gr64 = XOR64rr %2:gr64(tied-def 0), %0:gr64, implicit-def dead $eflags
304B      %3:gr64 = COPY %0:gr64
320B      %3:gr64 = INC64r %3:gr64(tied-def 0), implicit-def dead $eflags
336B      %11:gr64 = COPY %3:gr64
352B      %12:gr64 = COPY %2:gr64
368B      JMP_1 %bb.1
384B    bb.3.exit:
400B      %8:gr64 = COPY %1:gr64
416B      %8:gr64 = ADD64rr %8:gr64(tied-def 0), %4:gr64, implicit-def dead $eflags
432B      $rax = COPY %8:gr64
448B      RET 0, killed $rax
# End machine code for function run.

What to notice: %4 is a: one segment [16r, 416r) over the whole loop (Definition 22.1.8). PHI elimination turned the phis i and s into the copies %11 = COPY and %12 = COPY at the ends of both predecessors (64B/336B, 80B/352B), so %11 has three segments and two values (0@336r, 1@64r, the phi value 2@96B-phi) and a lifetime hole from 128r to 336r. %1 (the loop's copy of s) has a hole between the body and the exit: [112r, 208r) and [384B, 400r), exactly the hole of s in §3. The two-address pass added a COPY before each tied IMUL64rr/ADD64rr: x86 overwrites an operand, so its value must be copied if it is still live. All weights are 0 because spill weights are computed by the allocator (Lesson 22.9).

Register classes and sub-registers¶

LLVM's register classes and sub-register indices come from TableGen (llvm/lib/Target/X86/X86RegisterInfo.td, classes GR64, GR32, GR64_with_sub_8bit; sub-register indices sub_8bit, sub_32bit) and are queried through TargetRegisterInfo::regunits [LLVM-CodeGenDoc]. The coalescer can narrow a class: %7 below starts as a result of COPY $rax and must be in GR64_with_sub_8bit because one of its uses reads the 32-bit sub-register. GCC describes the same with REG_CLASS_CONTENTS and allocno classes (gcc/ira.cc, "allocno class", gcc-15.1.0) [GCC-IRA].

Classes, sub-registers and pre-coloured copies in MIR

Reproduce (llc 23.1.2; any OS):

cat > small.ll <<'EOF'
declare i64 @g(i64)
define i64 @f(i64 %a, i64 %b) {
entry:
  %c = call i64 @g(i64 %a)
  %s = add i64 %c, %b
  %t = trunc i64 %s to i32
  %u = zext i32 %t to i64
  %r = mul i64 %u, %a
  ret i64 %r
}
EOF
llc -O2 -mtriple=x86_64-linux-gnu -print-after=greedy,virtregrewriter small.ll -o /dev/null 2>&1 \
  | sed -n '/Greedy/,$p' | sed -n '1,18p;/Virtual Register Rewriter/,$p'

Output (abridged: the register-mask lists after $r15 are shortened to …, and the closing # End machine code line is cut):

# *** IR Dump After Greedy Register Allocator (greedy) ***:
# Machine code for function f: NoPHIs, TracksLiveness, TiedOpsRewritten, TracksDebugUserValues
Function Live Ins: $rdi in %0, $rsi in %1

0B  bb.0.entry:
      liveins: $rdi, $rsi
16B   %1:gr64_with_sub_8bit = COPY $rsi
32B   %0:gr64 = COPY $rdi
48B   ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
64B   $rdi = COPY %0:gr64
80B   CALL64pcrel32 target-flags(x86-plt) @g, <regmask $bh $bl $bp $bph $bpl $bx $ebp $ebx $hbp $hbx $rbp $rbx $r12 $r13 $r14 $r15 … >, implicit $rsp, implicit $ssp, implicit $rdi, implicit-def $rsp, implicit-def $ssp, implicit-def $rax
96B   ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
112B      %7:gr64_with_sub_8bit = COPY killed $rax
176B      %7.sub_32bit:gr64_with_sub_8bit = ADD32rr %7.sub_32bit:gr64_with_sub_8bit(tied-def 0), %1.sub_32bit:gr64_with_sub_8bit, implicit-def dead $eflags
224B      %7:gr64_with_sub_8bit = IMUL64rr %7:gr64_with_sub_8bit(tied-def 0), %0:gr64, implicit-def dead $eflags
240B      $rax = COPY %7:gr64_with_sub_8bit
256B      RET 0, killed $rax
…
# *** IR Dump After Virtual Register Rewriter (virtregrewriter) ***:
# Machine code for function f: NoPHIs, TracksLiveness, NoVRegs, TiedOpsRewritten, TracksDebugUserValues
Function Live Ins: $rdi, $rsi

0B  bb.0.entry:
      liveins: $rdi, $rsi
16B   renamable $rbx = COPY $rsi
32B   renamable $r14 = COPY $rdi
48B   ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
64B   $rdi = COPY renamable $r14
80B   CALL64pcrel32 target-flags(x86-plt) @g, <regmask $bh $bl $bp $bph $bpl $bx $ebp $ebx $hbp $hbx $rbp $rbx $r12 $r13 $r14 $r15 … >, implicit $rsp, implicit $ssp, implicit $rdi, implicit-def $rsp, implicit-def $ssp, implicit-def $rax
96B   ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
176B      renamable $eax = ADD32rr renamable $eax(tied-def 0), renamable $ebx, implicit-def dead $eflags, implicit killed $rbx, implicit killed $rax, implicit-def $rax
224B      renamable $rax = IMUL64rr killed renamable $rax(tied-def 0), killed renamable $r14, implicit-def dead $eflags
256B      RET 0, $rax

What to notice: the trunc/zext pair became a 32-bit ADD32rr on the sub-register %7.sub_32bit (writing a 32-bit register zeroes the upper half on x86-64), so %7 and %1 are in the class gr64_with_sub_8bit, a subclass of gr64 (Definition 22.1.10). After rewriting, %7 is $rax and its sub-register is $eax: one register, two names ($eax $\asymp$ $rax). The identity copies %7 = COPY $rax (112B) and $rax = COPY %7 (240B) disappeared, because the allocator followed the hints to $rax.

Pre-coloured registers and calling conventions¶

In the dump above, %0 (a) and %1 (b) are live across the call, and the <regmask …> on CALL64pcrel32 lists the registers the call preserves (rbx, rbp, r12–r15 and their sub-registers): the System V callee-saved set. The allocator therefore gave them $r14 and $rbx, both callee-saved (Definition 22.1.6 (iii)), and PEI saves those two in the prologue (Lesson 21.9). The pre-coloured argument registers appear as COPY $rdi/COPY $rsi and $rdi = COPY before the call. LLVM's mask comes from X86RegisterInfo::getCallPreservedMask (llvm/lib/Target/X86/X86RegisterInfo.cpp) and is tested by LiveRegMatrix::checkRegMaskInterference. Go's internal ABI has no callee-saved registers at all, so every value live across a call is spilled around it.

Go 1.24: no callee-saved registers, so values live across a call are spilled

Reproduce (go 1.24.7, linux/amd64):

cat > main.go <<'EOF'
package main

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

//go:noinline
func f(a, b int) int {
    c := g(a)
    s := c + b
    return s * a
}

func main() { println(f(2, 3)) }
EOF
go tool compile -d=ssa/regalloc/dump=f -o /dev/null main.go && cat f_01__regalloc.dump

Output (complete):

f func(int, int) int
  b1:
    (+10) v7 = ArgIntReg <int> {a+0} [0] : AX (a[int])
    (+10) v8 = ArgIntReg <int> {b+0} [1] : BX (b[int])
    (+10) v6 = StoreReg <int> v7 : a[int]
    (+10) v4 = StoreReg <int> v8 : b[int]
    (?) v1 = InitMem <mem>
    (+8) v10 = CALLstatic <int,mem> {AuxCall{main.g}} [8] v7 v1 : <AX>
    (+8) v12 = SelectN <int> [0] v10 : AX (c[int])
    (8) v11 = SelectN <mem> [1] v10
    (-9) v5 = LoadReg <int> v4 : CX
    (+9) v13 = ADDQ <int> v12 v5 : AX (s[int])
    (-10) v9 = LoadReg <int> v6 : CX
    (+10) v14 = MULQ <int> v13 v9 : AX
    (10) v15 = MakeResult <int,mem> v14 v11 : <>
    Ret v15
name a[int]: [v7]
name b[int]: [v8]
name c[int]: [v12]
name s[int]: [v13]

What to notice: the same function as small.ll. The arguments arrive pre-coloured in AX and BX (Go's register ABI), and the call result comes back in AX. a and b are live across CALLstatic, and with no callee-saved register (condition (iii) cannot be met by any register) they are spilled: StoreReg before the call and LoadReg after it. LLVM put them in rbx/r14 instead, at the price of saving those two in the prologue.

8. Comparison¶

This lesson's "techniques" are the representations of the problem that the allocators of the later lessons consume.

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Interference graph (Chaitin)	exact pairwise conflicts (Theorem 22.1.12); loses where they happen	$\Theta(N \cdot L)$ build, $\Theta(n^2)$ worst-case edges · the dominant cost of graph colouring	enables colouring, coalescing tests	moderate (bit matrix + lists)	Chaitin–Briggs, IRC, GCC IRA, HotSpot C2
Live intervals (segments, slot indexes)	exact with holes; hulls over-approximate	linear build · fast queries by segment search	enables linear scan, splitting	moderate	LLVM greedy, V8, HotSpot C1, Graal
Register classes and units	models overlap exactly	set intersection per unit	needed for any real ISA	TableGen-generated in LLVM	every production allocator
Pre-colouring and register masks	exact constraints	one query per call / constraint	may force spills (Go) or CSR saves (LLVM)	small, but pervasive	every production allocator

Choose the interference graph when you colour (Lessons 22.3–22.4, 22.7) and the functions are small enough that $\Theta(n^2)$ is fine. Choose live intervals when you need to split live ranges or allocate fast (Lessons 22.5, 22.8). Model classes by register units as soon as the ISA has overlapping registers. Model calls as clobbers (masks or pre-coloured nodes) rather than as special cases in each allocator.

9. Assessment¶

Quiz (./course quiz 22): interference-edges, dead-def-interferes, subreg-alias, maxlive-classes, caller-saved-crossing, regmask-meaning (tags interference, regclass, precolor).
Drill: ./course drill interference-graph (edges, MaxLive, coalescable move pairs). ./course drill ssa-coloring also asks for MaxLive.
Flashcards: tags interference, regclass, precolor in flashcards.
Lab: read labs/ch22-regalloc/SPEC.md §"Machine model"; the provided checker implements Definitions 22.1.4–22.1.6 and the rewriter Theorem 22.1.14.

References¶

See the chapter references.

Task	Worst case	Typical	Space	Justification
liveness (Ch 14)	\(O(b \cdot n)\) bit-vector operations per pass, \(O(d + 2)\) passes	2–3 passes	\(O(b \cdot n)\) bits	Ch 14, Lesson 14.4
Build (Algorithm 22.1.9)	\(O(N \cdot L)\)	\(O(N \cdot L)\), \(L \ll n\)	\(O(n^2)\) bits matrix + \(O(E)\) lists	each point adds at most \(L + \lvert\mathrm{defs}(p)\rvert\) edges; membership test \(O(1)\) in a bit matrix
live intervals	\(O(N + \sum_v \lvert \text{segments}(v) \rvert)\)	linear	\(O(N + n)\)	one backward walk per block
MaxLive	\(O(N \cdot L)\)	linear	\(O(L)\)	pressure is \(\lvert\mathrm{live}(p)\rvert\) at each point

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Interference graph (Chaitin)	exact pairwise conflicts (Theorem 22.1.12); loses where they happen	\(\Theta(N \cdot L)\) build, \(\Theta(n^2)\) worst-case edges · the dominant cost of graph colouring	enables colouring, coalescing tests	moderate (bit matrix + lists)	Chaitin–Briggs, IRC, GCC IRA, HotSpot C2
Live intervals (segments, slot indexes)	exact with holes; hulls over-approximate	linear build · fast queries by segment search	enables linear scan, splitting	moderate	LLVM greedy, V8, HotSpot C1, Graal
Register classes and units	models overlap exactly	set intersection per unit	needed for any real ISA	TableGen-generated in LLVM	every production allocator
Pre-colouring and register masks	exact constraints	one query per call / constraint	may force spills (Go) or CSR saves (LLVM)	small, but pervasive	every production allocator

Lesson 22.1 — The problem: live ranges, interference and constraints¶

1. Problem and motivation¶

Live ranges and interference graphs¶

Register classes and sub-registers¶

Pre-coloured registers and calling conventions¶

2. Definitions and algorithms¶

Live ranges and interference graphs¶

Register classes and sub-registers¶

Pre-coloured registers and calling conventions¶

3. Worked example¶

4. Invariants and correctness¶

Live ranges and interference graphs¶

Pre-coloured registers and calling conventions¶

5. Complexity¶

6. Variants and refinements¶

Live ranges and interference graphs¶

Register classes and sub-registers¶

Pre-coloured registers and calling conventions¶

7. In real compilers¶

Live ranges and interference graphs¶

Register classes and sub-registers¶

Pre-coloured registers and calling conventions¶

8. Comparison¶

9. Assessment¶

References¶