Register Allocation in Compilers

Question

What is meant by spilling of registers or spill code which appears in Register allocation phase of Code generation where compiler backend must allocate variables to memory or registers?.

Answer 1

Hardware registers are expensive (both in terms of die area and the number of instruction bits required to address them), and therefore generally quite few in number. Spilling occurs when the number of live variables (or, more accurately, the number of live ranges) at a given program point exceeds the number of available registers.

Consider the following example program executing in an imaginary machine that has two hardware registers. Assume the compiler performs no optimization aside from register allocation.

a := 1   ; liveout: {a}
b := 2   ; liveout: {a,b}
c := 3   ; liveout: {a,b,c}
d := a + b + c

Since a and b are used in the definition of d, their live ranges cross the definition of c. But since the machine only has two registers, it's impossible for a, b and c to all be held in a register when d is defined. At least one of them must be spilled.

In the simplest form of spilling, all definitions of the spilled variable are replaced with stores to a stack slot, and all uses are replaced with loads. Some compilers also have the option of performing register-to-register spilling, meaning that the value is stored to and loaded from a register of a different class. For instance, on x86-64 the compiler could spill a value from a general-purpose register like rax into a SIMD register like xmm0. This has the benefit of reducing memory traffic.

As an alternative to spilling, a compiler may instead perform live range splitting. This involves breaking live ranges into smaller pieces - inserting loads and stores only at the split points - to enable coloring of an otherwise uncolorable interference graph.

As you can probably imagine, the choice of which variable to spill has a significant impact on the performance of the resulting code. Arbitrarily spilling a variable used or defined in a tight loop may have disastrous consequences. As such, a good compiler likely applies some form of heuristics to esimate the cost of spilling each variable before making its choice.