Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 61 ยท Code Generation and Runtimes

Register Allocation

Learn register allocation: live ranges, interference graphs, graph coloring, spilling and linear scan, with runnable Python allocators.

Registers are the fastest storage a CPU has, but there are very few of them: 16 general-purpose registers on x86-64, 31 on ARM64. A program, on the other hand, can have thousands of values alive during one function. Register allocation decides which values get a register and which must wait in memory. It is one of the most influential optimizations, because a memory access can be dozens of times slower than a register access.

The input is intermediate code that pretends to have unlimited virtual registers (every variable and temporary has its own). The output assigns each virtual register to one of k machine registers, or to a stack slot when k are not enough. This lesson explains live ranges, the interference graph, graph coloring with spilling, and the faster linear scan method, all with runnable code.

Live ranges and interference

Two values need different registers only if they are alive at the same time. A value is live from its definition up to its last use (the exact definition is the one from data-flow analysis). Its live range is the set of program points where it is live. If the live ranges of x and y overlap, they interfere: the same register cannot hold both. If they do not overlap, they can share.

In straight-line code the live range is a simple interval. In code with branches and loops it can have holes and several pieces, which is why compilers compute it with liveness analysis over the control flow graph. The rule for building interference: at each instruction that defines d, add an edge between d and every other variable that is live right after the instruction.

flowchart LR
    A["a"] --- B["b"]
    A --- C["c"]
    B --- C
    B --- D["d"]
    C --- D
    C --- E["e"]
    D --- E
    D --- F["f"]

A small interference graph. Connected variables are live together and need different registers. Variables with no edge between them may share a register.

Allocation as graph coloring

Now the problem becomes classic: color the graph with k colors so that adjacent nodes get different colors. Each color is a machine register. Deciding whether an arbitrary graph is k-colorable is NP-complete, but a practical heuristic from Chaitin (extended by Briggs) works well:

  1. Simplify. Find a node with fewer than k neighbors. It can always be colored later, whatever its neighbors choose, because at least one color will remain. Remove it from the graph and push it on a stack.
  2. Repeat until the graph is empty. If every remaining node has k or more neighbors, pick one as a spill candidate (typically a node with high degree and low use cost), push it optimistically, and continue.
  3. Select. Pop the nodes in reverse order. Give each one a color that none of its already-colored neighbors uses. An optimistically pushed node often still finds a free color, because its neighbors may have ended up sharing colors.
  4. If a node finds no color, it is an actual spill: it will live in memory. The compiler rewrites the code to store it after each definition and reload it before each use, then runs the whole process again, because the new, tiny live ranges change the graph.

The first example computes liveness for a short straight-line program, builds the interference graph and colors it with 4, 3 and 2 registers.

Python Liveness, interference graph and coloring

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the liveness lines. At most three variables are live at the same time (for example {a, b, c} after c = a + b), which is why three registers suffice and two do not. With three registers the allocator colors everything: a and d share R1, because a's last use is the instruction that defines d. With two registers the simplification stalls, since every remaining node has two or more neighbors. The allocator picks c, the busiest node (degree 4), and in the select phase c conflicts with a and b on both colors. So c is spilled, and g, which interferes with nothing, simply reuses R0.

Spilling and iterating

Spilling is not free: each store and reload is a memory access. Good allocators choose the victim carefully. A cost estimate counts how often each variable is used and defined, weighted by loop depth (a use inside a loop nested three deep counts about 1000 times), and divides by the node's degree. A rarely used value with many conflicts is the ideal victim.

After choosing a victim, the compiler inserts a store after each definition and a load before each use, giving each reload its own short-lived temporary. Those temporaries are never worth spilling again (their live range is just an instruction or two), so allocators mark them as unspillable. Then coloring runs again, until it succeeds. The next example does exactly that for the same program with only two registers, and finally runs the original and the allocated programs to check they print the same value.

Python Spill code and the allocate-again loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop needs three rounds. Round one spills c. Round two finds that the new code is still too tight and spills d and b. Round three succeeds. The final listing uses only R0 and R1, plus the LOAD[...]/STORE[...] pairs, and the check at the end shows that both programs print 5. Real allocators spill far less because they have 16 or 32 registers, but the structure is the same.

Linear scan

Graph coloring gives good code but costs time: building a graph and coloring it is expensive for huge functions. JITs, which must compile while the user waits, prefer linear scan allocation. It treats each live range as one interval from first definition to last use, sorts the intervals by start point and sweeps through them once:

  1. For each interval in order of start: first expire the active intervals that ended, returning their registers to the free pool.
  2. If a register is free, assign it and mark the interval active.
  3. Otherwise a spill is needed. Spill the interval, among the active ones and the new one, that ends furthest in the future, since it would block a register for the longest time.

The sweep runs in roughly O(n log n) (or O(n) with a good data structure) and produces code that is a bit worse than coloring, which is often an acceptable trade. HotSpot's C1 compiler, LuaJIT and V8's TurboFan use variants of it. The following example prints the intervals and runs linear scan with three and two registers.

Python Linear scan allocation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With three registers every interval fits, and the sweep reuses a register as soon as its owner expires (for example d takes over R0 at instruction 3, where a ends). With two registers c, whose interval ends last (instruction 5), is the one sent to memory. The result agrees with the graph coloring in the previous example, which spilled c too, although in bigger programs the two methods often disagree.

Real-world refinements

  • Coalescing. If x = y is a plain copy and x and y do not interfere, give them the same register and delete the copy.
  • Precoloring. Some values must sit in specific registers because of the calling convention (arguments, return value, a division instruction that uses fixed registers). Their nodes start out colored.
  • Caller-saved vs callee-saved registers. A value that lives across a call should go to a callee-saved register, or it must be saved around the call.
  • Live-range splitting. Instead of spilling a variable everywhere, keep it in a register for the hot loop and in memory elsewhere.
  • SSA-based allocation. Interference graphs of SSA programs are chordal, which means they can be colored optimally in polynomial time, and spilling can be separated from coloring.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. When do two variables interfere?

    Interference means overlapping live ranges. Only such variables need different registers.
  2. 2. In the simplify step, why can a node with fewer than k neighbors be removed safely?

    With fewer than k neighbors, they cannot use all k colors, so the node can be colored last, after its neighbors.
  3. 3. What does the linear scan allocator spill when no register is free?

    Spilling the longest-lasting interval frees a register for the longest time. This heuristic is cheap and works well in practice.
  4. 4. Why are the reload temporaries created by spill code never chosen as spill candidates?

    A reload is needed right before its use. Spilling it again would just add another load and store without freeing anything.

Summary

  • Register allocation maps unlimited virtual registers onto a few machine registers, spilling to memory when needed.
  • Two values interfere when they are live at the same time; interference is recorded in a graph built from liveness information.
  • Graph coloring (simplify, push, select) assigns registers; values that cannot be colored are spilled, spill code is inserted and the process repeats.
  • Spill choices use costs weighted by loop depth; reload temporaries are never spilled again.
  • Linear scan sweeps over sorted live intervals in one pass, which is fast enough for JIT compilers at a small quality cost.
  • Coalescing, precoloring, live-range splitting and SSA-based methods improve the result in real compilers.

Next: Memory Management and Garbage Collection