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 aggressive.
|Original language||English (US)|
|Number of pages||11|
|Journal||Conference Record of the Annual ACM Symposium on Principles of Programming Languages|
|State||Published - 1996|
|Event||Proceedings of the 1996 ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages - St.Petersburg, FL, USA|
Duration: Jan 21 1996 → Jan 24 1996
All Science Journal Classification (ASJC) codes