Register allocation is a core optimization step in compiler backends. In this chapter, we outline liveness analysis and interference graph coloring.
Liveness Analysis
Before allocating registers, we must compute variable lifetimes. A variable is live at a program point if its current value will be read in the future before it is redefined.
Interference Graphs & Coloring
We construct an undirected Interference Graph where nodes represent variables. An edge connects two variables if they are live concurrently.
We must assign each node a physical register (color) from a set of size $K$ (the hardware limit). If a node has a degree $< K$ in the interference graph, we are guaranteed to find a valid coloring for it.
// Simplify node with degree < K
bool CanColorNode(int degree, int K) {
return degree < K;
}