Iterated register coalescing

1996/05/01 by Lal George, Andrew W. Appel · 3 citations
Computer Science · Mathematics · #Parallel Computing and Optimization Techniques #Software Testing and Debugging Techniques #Logic, programming, and type systems #Computer science #Register allocation #Allocator #Graph coloring #Iterated function #Heuristic #Graph #Call graph #Parallel computing #Register (sociolinguistics) #Algorithm #Theoretical computer science #Programming language #Artificial intelligence #Mathematics #Compiler

paper · pdf · doi:10.1145/229542.229546

openalex publication_date 1996/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

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.

Citations

• Efficiently computing static single assignment form and the control dependence graph
• Register allocation via coloring
• Improvements to graph coloring register allocation
• Register allocation & spilling via graph coloring
• On the Geographical Problem of the Four Colours
• Register allocation & spilling via graph coloring

Cited by

• Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove? Or Revisiting Register Allocation: Why and How
• Register coalescing techniques for heterogeneous register architecture with copy sifting
• Register allocation [wikipedia]