Register Allocation and Spilling in C Compilers

This article explains how modern C compilers manage processor registers to produce fast, efficient machine code. It covers the core mechanisms of register allocation, the standard algorithms used to map program variables to hardware registers, and the concept of register spilling, which occurs when the demand for physical registers exceeds the available hardware resources.

The Need for Register Allocation

During the compilation of a C program, the front end transforms source code into an Intermediate Representation (IR), often structured in Static Single Assignment (SSA) form. At this stage, the compiler operates with an unbounded number of virtual (or pseudo) registers to hold intermediate values, local variables, and computed pointers.

Target processors (such as x86-64, ARM, or RISC-V) possess a strictly limited set of architectural registers. Accessing an architectural register takes a single CPU cycle, whereas fetching data from the memory hierarchy (L1 cache or RAM) introduces latency. Register allocation is the backend phase that maps this infinite set of virtual registers to the target architecture's finite physical registers while preserving program semantics.

Common Register Allocation Algorithms

Modern compilers such as GCC and Clang employ several distinct algorithmic strategies depending on the chosen optimization level.

1. Graph Coloring (Chaitin-Briggs)

The most common approach for high optimization levels (such as -O2 or -O3) treats register allocation as an NP-complete graph coloring problem:

  • Liveness Analysis: The compiler determines the "live range" of every virtual register—the interval between its first definition and its last read.
  • Interference Graph: The compiler constructs a graph where each node represents a variable's live range. An undirected edge connects two nodes if their live ranges overlap, meaning they cannot share the same physical register.
  • K-Coloring: If the target CPU has \(K\) general-purpose registers, the compiler attempts to color the graph using \(K\) colors such that no two adjacent nodes share the same color.
  • Kempe's Heuristic: Nodes with fewer than \(K\) neighbors are iteratively removed from the graph and pushed onto a stack. Once empty, nodes are popped back and assigned a color not used by their neighbors.

2. Iterated Register Coalescing (IRC)

IRC extends Chaitin-Briggs graph coloring by aggressively combining (coalescing) nodes connected by copy instructions (such as x = y), provided doing so does not make the graph uncolorable. This eliminates redundant MOV instructions, which frequently appear after lowering C function calls and pointer arithmetic.

3. Linear Scan Register Allocation

Graph coloring can be computationally expensive with \(O(N^2)\) or \(O(N^3)\) complexity. Linear scan allocation simplifies this process to \(O(N \log N)\) by ordering live intervals chronologically by their start points.

As the allocator iterates through the sorted intervals, it assigns the next available physical register. When an interval expires, its register is returned to the pool. While linear scan produces slightly less optimal code than graph coloring, it is substantially faster and frequently used in Just-In-Time (JIT) compilers or low-optimization passes (such as -O0 or -O1).

What is Register Spilling?

Register pressure occurs when the number of concurrently live values exceeds the number of available physical registers (\(K\)). When an interference graph cannot be \(K\)-colored, or when a linear scan finds no free registers, the compiler must perform register spilling.

Spilling involves evicting a variable from the register set and allocating a slot for it in the current function's stack frame on the memory stack.

The Mechanics of a Spill

When a virtual register is spilled:

  1. Store Insertion: The compiler inserts a store instruction immediately after the value is defined, saving it to its designated stack offset.
  2. Load Insertion: The compiler inserts a load instruction immediately before every subsequent instruction that reads the spilled value, loading it into a temporary register just in time.
  3. Live Range Splitting: Spilling replaces a single, long live range with multiple tiny live ranges that exist only between memory loads and their immediate uses, drastically reducing register interference.

Spill Costs and Heuristics

Because memory reads and writes introduce latency and consume instruction cache space, compilers rely on cost models to decide which variable to spill:

  • Loop Nesting Depth: Variables used inside deeply nested loops are heavily penalized for spilling. The compiler prefers spilling variables accessed only outside loops.
  • Use Count: Variables with fewer read/write occurrences are prioritized for eviction.
  • Distance to Next Use: Under linear scan, the variable whose next use is farthest in the future is typically chosen to be spilled.

Special Considerations for C Compilers

Compilers targeting the C language face specific constraints during register allocation:

  • Calling Conventions (ABIs): Architectures partition registers into caller-saved (scratch) and callee-saved (preserved) registers. Allocators must weigh the cost of spilling against the overhead of saving and restoring callee-saved registers in the function prologue and epilogue.
  • Pointer Aliasing: In C, any variable whose address is taken with the & operator may be modified indirectly via a pointer. Compilers must track whether an address escapes to ensure an aliased variable is kept synchronized between registers and memory.
  • The volatile Qualifier: A variable marked volatile in C cannot reside purely in a register across sequence points. The compiler must emit explicit memory operations for each read and write, effectively forcing the variable to remain in memory rather than being permanently allocated to a register.