Improvements to graph coloring register allocation

1994/05/01 by Preston Briggs, Keith D. Cooper, Linda Torczon · 18 citations
Computer Science · #Parallel Computing and Optimization Techniques #Formal Methods in Verification #Software Testing and Debugging Techniques #Allocator #Computer science #Graph coloring #Register allocation #Suite #Parallel computing #Graph #Thread (computing) #Code (set theory) #Programming language #Theoretical computer science

paper · pdf · doi:10.1145/177492.177575

openalex publication_date 1994/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26

Abstract

We describe two improvements to Chaitin-style graph coloring register allocators. The first, optimistic coloring , uses a stronger heuristic to find a k -coloring for the interference graph. The second extends Chaitin's treatment of rematerialization to handle a larger class of values. These techniques are complementary. Optimistic coloring decreases the number of procedures that require spill code and reduces the amount of spill code when spilling is unavoidable. Rematerialization lowers the cost of spilling some values. This paper describes both of the techniques and our experience building and using register allocators that incorporate them. It provides a detailed description of optimistic coloring and rematerialization. It presents experimental data to show the performance of several versions of the register allocator on a suite of FORTRAN programs. It discusses several insights that we discovered only after repeated implementation of these allocators.

Citations

• Efficiently computing static single assignment form and the control dependence graph
• Register allocation via coloring
• Singular value decomposition and least squares solutions
• Register allocation & spilling via graph coloring
• Register allocation & spilling via graph coloring

Cited by

• Iterated register coalescing
• Linear scan register allocation
• Hybrid Optimizations: Which Optimization Algorithm to Use?
• Register allocation for Intel processor graphics
• Quality and speed in linear-scan register allocation
• Split Register Allocation: Linear Complexity Without the Performance Penalty
• Optimal spilling for CISC machines with few registers
• On the Complexity of Register Coalescing
• Optimal Bitwise Register Allocation Using Integer Linear Programming
• Linear Scan Register Allocation in a High-Performance Erlang Compiler
• Optimized interval splitting in a linear scan register allocator
• Optimistic register coalescing
• Register Spilling and Live-Range Splitting for SSA-Form Programs
• Trace-based Register Allocation in a JIT Compiler
• A generalized algorithm for graph-coloring register allocation
• Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove? Or Revisiting Register Allocation: Why and How
• Linear Scan Register Allocation in the Context of SSA Form and Register Constraints
• Register allocation [wikipedia]