CD Notes
Complete guide to register allocation covering liveness analysis, interference graphs, graph coloring, linear scan allocation, spilling strategies, and practical implementation approaches.
Introduction
Register allocation is the process of assigning program variables and temporaries to a limited number of CPU registers. Since registers are the fastest storage (single-cycle access vs 4-100 cycles for memory), effective allocation dramatically impacts program performance. This is one of the most studied problems in compiler design.
The Problem
| Variables live simultaneously (at line 3): t1, t2 | 2 registers |
| Variables live simultaneously (at line 5): t3, t4, t1 | 3 registers |
| Maximum simultaneously live | 3 |
| If machine has only 2 registers | must SPILL some to memory. |
Liveness Analysis
A variable is live at a point if its current value will be used in the future.
| Algorithm | Compute live-in and live-out for each statement |
| 1 | t1 = a + b DEF={t1}, USE={a,b} |
| 2 | t2 = c - d DEF={t2}, USE={c,d} |
| 3 | t3 = t1 * t2 DEF={t3}, USE={t1,t2} |
| 4 | t4 = e + f DEF={t4}, USE={e,f} |
| 5 | x = t3 + t4 DEF={x}, USE={t3,t4} |
| After 5 | nothing live (x is result) |
| Before 5 | t3, t4 live |
| Before 4 | t3, e, f live |
| Before 3 | t1, t2, e, f live |
| Before 2 | t1, c, d, e, f live |
| Before 1 | a, b, c, d, e, f live |
| t1 | [1, 3] (defined at 1, last used at 3) |
| t2 | [2, 3] (defined at 2, last used at 3) |
| t3 | [3, 5] (defined at 3, last used at 5) |
| t4 | [4, 5] (defined at 4, last used at 5) |
Interference Graph
Two variables interfere if they are simultaneously live at some point. They cannot share a register.
From live ranges above
t1 [1-3] overlaps t2 [2-3] → interfere
t1 [1-3] does NOT overlap t3 [3-5] → t1 dead after t3 defined
Actually t1 last used at 3, t3 defined at 3.
Convention: t1 is live at entry of 3, t3 live at exit.
They interfere at statement 3.
t2 [2-3] does NOT overlap t4 [4-5] → don't interfere
t3 [3-5] overlaps t4 [4-5] → interfere
Interference Graph
t1 ─── t2
|
t3 ─── t4
Adjacency
t1: {t2, t3}
t2: {t1}
t3: {t1, t4}
t4: {t3}
Graph Coloring Register Allocation
k-coloring the interference graph = allocating k registers.
Algorithm (Chaitin's)
1. Build interference graph
2. Simplify: Remove nodes with degree < k
(they can always be colored — push onto stack)
3. If all nodes removed: Pop stack, assign colors (registers)
4. If stuck (all nodes have degree ≥ k):
Choose a node to SPILL (mark for memory)
Remove it and continue simplifying
Example with k=2 registers (R0, R1):
Graph: t1-t2, t1-t3, t3-t4
Simplify
t2 has degree 1 < 2 → remove t2, push to stack
t4 has degree 1 < 2 → remove t4, push to stack
t1 has degree 1 < 2 → remove t1, push to stack
t3 has degree 0 < 2 → remove t3, push to stack
Color (pop stack)
t3: no neighbors colored yet → assign R0
t1: neighbor t3=R0 → assign R1
t4: neighbor t3=R0 → assign R1
t2: neighbor t1=R1 → assign R0
Result: t1=R1, t2=R0, t3=R0, t4=R1
Verify: no interfering pair shares a register ✓
Spilling
When the graph cannot be k-colored, some variables must be spilled to memory:
Spill heuristics (choose variable to spill)
1. Spill the variable with highest degree (most interference)
2. Spill the variable used least frequently
3. Spill the variable with the cheapest spill cost
4. Avoid spilling variables inside loops
Spill cost estimation
cost(v) = Σ (10^depth × frequency_of_use)
where depth = loop nesting depth
After spilling variable v
- Insert STORE after each definition of v
- Insert LOAD before each use of v
- Remove v from interference graph
- Re-run allocation (new temporaries for loads are short-lived)
Example - spilling t1
Original: After spill:
t1 = a + b t1' = a + b
STORE t1', [t1_mem]
... ...
t3 = t1 * t2 LOAD t1'', [t1_mem]
t3 = t1'' * t2
t1' and t1'' have very short live ranges → easy to color
Linear Scan Register Allocation
Faster than graph coloring, used in JIT compilers:
Algorithm
1. Compute live intervals [start, end] for each variable
2. Sort intervals by start point
3. Maintain list of active intervals (currently in registers)
4. For each interval i:
a. Expire old intervals (end < i.start) → free their registers
b. If free register available → assign it to i
c. Else: spill (i or the active interval ending latest)
Example with 2 registers
Intervals: t1=[1,4], t2=[2,3], t3=[3,6], t4=[5,7]
Sorted by start: t1, t2, t3, t4
Process t1[1,4]: active=[], R0 free → assign R0. active=[t1:R0]
Process t2[2,3]: active=[t1:R0], R1 free → assign R1. active=[t1:R0, t2:R1]
Process t3[3,6]: Expire: t2 ends at 3 ≤ 3 → free R1
active=[t1:R0], R1 free → assign R1. active=[t1:R0, t3:R1]
Process t4[5,7]: Expire: t1 ends at 4 < 5 → free R0
active=[t3:R1], R0 free → assign R0. active=[t3:R1, t4:R0]
Result: t1=R0, t2=R1, t3=R1, t4=R0 (no spills needed)
Live Range Splitting
Register Coalescing
| If | MOV R1, R0 and R0 and R1 don't interfere elsewhere |
| Then | Merge R0 and R1 into single register, eliminate MOV |
| Before coalescing | After coalescing: |
| MOV R1, R0 | (eliminated) |
| Conservative coalescing | only coalesce if combined degree < k. |
Interview Questions
- Q: Why is optimal register allocation NP-complete?
A: Optimal register allocation is equivalent to graph k-coloring, which is NP-complete for k ≥ 3. The interference graph can have arbitrary structure, and finding the minimum number of colors (registers) needed is computationally hard. Heuristics like Chaitin's algorithm work well in practice.
- Q: What is the difference between graph coloring and linear scan?
A: Graph coloring builds an interference graph and colors it optimally — better code quality but O(n²) time. Linear scan processes sorted intervals in one pass — faster (O(n log n)) but may miss opportunities. Graph coloring is used in ahead-of-time compilers; linear scan in JIT compilers where compile time matters.
- Q: How do calling conventions affect register allocation?
A: Calling conventions split registers into caller-saved (must be saved before calls if live across call) and callee-saved (must be saved/restored by called function if used). The allocator prefers caller-saved registers for values not live across calls, and callee-saved for long-lived values to avoid repeated save/restore.
- Q: What is register pressure and how is it measured?
A: Register pressure at a program point is the number of simultaneously live variables. If pressure exceeds available registers, spilling is necessary. The allocator tries to minimize maximum pressure through instruction scheduling and live range splitting.
- Q: How does SSA form help register allocation?
A: In SSA form, each variable is defined exactly once, making live ranges simpler (no need to track multiple definitions). The interference graph has special structure (chordal for strict SSA programs) that can be optimally colored in polynomial time. This is why modern compilers convert to SSA before allocation.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Register Allocation in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, code, generation, register, allocation
Related Compiler Design Topics