Fusion-Based Register Allocation
G.Y. Lueh, T. Gross and A. Adl-Tabatabai
Abstract
The register allocation phase of a compiler maps live ranges of a
program to registers. If there are more candidates than
there are physical registers, the register allocator must spill a live
range (the home location is in memory) or split a live range (the live
range occupies multiple locations). One of the challenges for a register
allocator is to deal with spilling and splitting together. Fusion
based register allocation uses the structure of the program to
make splitting and spilling decisions, with the goal to move overhead
operations to infrequently executed parts of a program.
The basic idea of fusion based register allocation is to build up the
interference graph. Starting with some base region (e.g., a basic block,
a loop), the register allocator adds basic blocks to the region and
incrementally builds the interference graph. When there are more live
ranges than registers, the register allocator selects live ranges to
split; these live ranges are split along the edge that was most recently
added to the region.
This paper describes fusion based register allocation in detail and
compares it with other approaches to register allocation. For programs
from the SPEC92 suite, fusion based register allocation can improve the
execution time (of optimized programs, for the MIPS architecture) by up
to 8.4\% over Chaitin-style register allocation.