Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove? Or Revisiting Register Allocation: Why and How

2007/01/01 by Florent Bouchez, Alain Darte, Christophe Guillon +1 · 2 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Colored #Combinatorics #Completeness (order theory) #Computer science #Discrete mathematics #Graph #Graph coloring #Logic, programming, and type systems #Mathematics #Parallel Computing and Optimization Techniques #Programming language #Register (sociolinguistics) #Register allocation #Theoretical computer science #Time complexity

paper · doi:10.1007/978-3-540-72521-3_21

crossref issued 2007/01/01 · crossref published 2007/01/01 · crossref published-print 2007/01/01 · openalex publication_date 2007/01/01 · crossref created 2007/06/10 · crossref deposited 2019/05/19 · crossref indexed 2024/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Citations

• Efficiently computing static single assignment form and the control dependence graph
• Register allocation via coloring
• Improvements to graph coloring register allocation
• On the Complexity of Register Coalescing
• Iterated register coalescing
• Optimal spilling for CISC machines with few registers
• Register allocation & spilling via graph coloring

Cited by

• Split Register Allocation: Linear Complexity Without the Performance Penalty
• Register allocation [wikipedia]