Register allocation via coloring

1981/01/01 by Gregory J. Chaitin, Marc A. Auslander, Marc Auslander +6 · 19 citations
Computer Science · Mathematics · #Arithmetic #Compiler #Computer science #Constraint Satisfaction and Optimization #Graph #Graph coloring #Mathematics #Operating system #Optimizing compiler #Parallel Computing and Optimization Techniques #Parallel computing #Point (geometry) #Processor register #Programming language #Register (sociolinguistics) #Register allocation #Teaching and Learning Programming #Theoretical computer science

paper · doi:10.1016/0096-0551(81)90048-5

crossref issued 1981/01/01 · crossref published 1981/01/01 · crossref published-print 1981/01/01 · openalex publication_date 1981/01/01 · crossref created 2003/08/07 · crossref deposited 2019/03/15 · openalex created_date 2025/10/10 · crossref indexed 2026/07/10 · openalex updated_date 2026/07/28

Cited by

• All Structured Programs Have Small Tree Width and Good Register Allocation
• Iterated register coalescing
• Improvements to graph coloring register allocation
• Spill code minimization via interference region spilling
• Retargetable Graph-Coloring Register Allocation for Irregular Architectures
• 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
• 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
• Parallel trace register allocation
• The 801 minicomputer
• Register allocation [wikipedia]