ITERATED REGISTER COALESCING

An important function of any register allocator is to target registers so as to eliminate copy instructions. Graph-coloring register allocat ion is an elegant approach to this problem. If the source and destinat ion of a move instruction do not interfere, then their nodes can be co alesced in the interference graph. Chaitin's coalescing heuristic coul d make a graph uncolorable (i.e., introduce spills); Briggs et al. dem onstrated a, conservative coalescing heuristic that preserves colorabi lity. But Briggs's algorithm is too conservative and leaves too many m ove instructions in our programs. We show how to interleave coloring r eductions with Briggs's coalescing heuristic, leading to an algorithm that is safe but much more aggressive.