Iterated Register Coalescing
An important function of any register allocator is to target registers
so as to eliminate copy instructions. Graph-coloring register
allocation is an elegant approach to this problem. If the source and
destination of a move instruction do not interfere, then their nodes
can be coalesced in the interference graph. Chaitin's coalescing
heuristic could make a graph uncolorable (i.e., introduce spills);
Briggs et al. demonstrated a conservative coalescing heuristic that
preserves colorability. But Briggs's algorithm is too
conservative, and leaves too many move instructions in our programs.
We show how to interleave coloring reductions with Briggs's coalescing
heuristic, leading to an algorithm that is safe but much more
- This technical report has been publish as
Iterated Register Coalescing, Lal George and Andrew W. Appel,
ACM Transactions on Programming Languages and Systems
18(3) 300-324, May 1996. Shorter version appeared in 23rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January 1996.