Register allocation

Register allocation maps temporary values or virtual registers in a compiler's representation to a limited supply of physical processor registers. A value's live range covers where it may still be needed. Overlapping live ranges constrain which values can share a processor register; register spilling moves some storage into computer memory when necessary.^[ref]

For example, in a=x+y; b=a*z, the processor register holding a can hold b after a's final use, if the target operation permits. If both values are needed later, overwriting a would lose required information. An interference graph represents simultaneous storage requirements, connecting register allocation to graph coloring. Real targets add constraints from register classes, reserved registers, calling conventions and particular machine instructions; minimizing the number of names alone does not solve the whole problem.

Register spilling is a compiler technique that keeps some values in computer memory when they cannot all remain in the available processor registers. Generated stores preserve a value before its register is reused; later loads recover it when needed. This is part of register allocation, whose choices affect the number of memory accesses.^[ref]

For example, suppose three independently computed values must survive to later instructions, but only two suitable processor registers are available. The allocator may store one value in a stack slot, use its register for another value, and reload it before its next use. The best choice depends on live ranges, use frequency and instruction constraints; recomputing a cheap value can sometimes avoid the store.

A live range is the portion of a program during which a computed value must remain available for a possible future use. It connects a definition with uses reached before that value is replaced. The concept concerns a particular value's lifetime, which need not occupy the whole textual scope of its source program variable.^[ref]

In a = read(); b = a + 1; return b;, the value assigned to a must survive until the addition reads it. After that read it can be discarded, while b must survive until the return. Register allocation can reuse storage for values whose live ranges do not overlap. Branches and loops can make a live range span several regions of a control-flow graph, rather than one uninterrupted interval of source lines.