Register Allocation
1. Problem
Machines have 16-32 registers, programs have unbounded temporaries. Register allocation maps temps to registers, spilling excess to stack — biggest single performance lever (memory is 10× slower).
2. Graph-Coloring Method (standard)
1. liveness: live ranges (def→last use)
2. interference graph: edge if live at same time
3. try k-color (k=regs): order by degree (simplify), assign colors
4. uncolorable → spill (store/load around uses), repeat
Example: a,b live together + b,c live → triangle needs 3 regs; with 2 regs spill one (cheapest: least-used / innermost).
3. Alternatives
| Method | How |
|---|---|
| Linear scan | sort intervals by start, expire old, assign — fast (JIT) |
| Top-down (frequency) | hottest vars to regs first |
| Bottom-up (coloring) | best quality (GCC/LLVM -O2) |
Coalescing merges move-related nodes (a=b → same reg, delete move); splitting cuts long ranges.
4. Spill Cost
Spill = ST after def + LD before each use. Choose least frequently executed (outside loops) victim.
5. Exam Points
- Explain graph coloring + spill — 7 marks, very frequent.
- Build interference graph + color for snippet — 7 marks, frequent.
- Linear scan vs coloring — 3 marks, frequent.