Register Allocation (in compilers)

Compiler has to decide which (limited) logical registers the generated instructions have to work on to carry out the program.

Algorithm #

• Compiler starts with infinite number of registers (virtual registers)

• The lifetime of each virtual register is determined

• A graph is constructed where each virtual register is a node

  • edges between nodes are created when their lifetimes overlap

• Assigning logical registers to virtual registers becomes a graph coloring problem: Neighboring nodes (share lifetime) can’t reside in the same logical register