Linear scan register allocation on SSA form

2010/04/24 by Christian Wimmer, Michael Franz · 4 citations
Computer Science · #Parallel Computing and Optimization Techniques #Logic, programming, and type systems #Embedded Systems Design Techniques #Register allocation #Computer science #Compiler #Register (sociolinguistics) #Overhead (engineering) #Parallel computing #Processor register #Shift register #Algorithm #Programming language #Computer hardware #Memory address

paper · doi:10.1145/1772954.1772979

openalex publication_date 2010/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

The linear scan algorithm for register allocation provides a good register assignment with a low compilation overhead and is thus frequently used for just-in-time compilers. Although most of these compilers use static single assignment (SSA) form, the algorithm has not yet been applied on SSA form, i.e., SSA form is usually deconstructed before register allocation. However, the structural properties of SSA form can be used to simplify the algorithm.

Citations

• Efficiently computing static single assignment form and the control dependence graph
• The DaCapo benchmarks

Cited by

• Trace Register Allocation Policies
• Trace-based Register Allocation in a JIT Compiler
• Parallel trace register allocation
• Register allocation [wikipedia]

Related

• Efficient global register allocation
• Trace Register Allocation Policies
• Studying optimal spilling in the light of SSA
• Trace-based Register Allocation in a JIT Compiler
• Register Allocation By Model Transformer Semantics