Compiler back end

A compiler back end translates an intermediate representation into operations suitable for a target machine. Typical tasks include instruction selection, register allocation, instruction scheduling and emission of assembly or object code. It uses facts about the target's instructions, registers, calling conventions and data layout.^[ref]

For example, a load from base + 4*i might use one indexed-addressing instruction when the target supports that addressing mode, or require separate address arithmetic otherwise. If more values are live than registers are available, Register allocation may spill some values to memory. Those choices change performance while having to preserve the source program's specified observable behavior. A target-independent intermediate form is therefore useful, but does not erase target-specific constraints.

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.