Linear scan register allocation
Massimiliano Poletto, Vivek Sarkar · ACM Transactions on Programming Languages and Systems · 1999
We describe a new algorithm for fast global register allocation called linear scan . This algorithm is not based on graph coloring, but allocates registers to variables in a single linear-time scan of the variables' live ranges. The linear scan algorithm is considerably faster than algorithms based on graph coloring, is simple to implement, and results in code that is almost as efficient as that obtained using more complex and time-consuming register allocators based on graph coloring. The algorithm is of interest in applications where compile time is a concern, such as dynamic compilation systems, “just-in-time” compilers, and interactive development environments.
Cited by 357 works. doi:10.1145/330249.330250 Open-access PDF
Authors
References
- Introduction to Algorithms
- Compilers: Principles, Techniques, and Tools
- A study of replacement algorithms for a virtual-storage computer
- Register allocation via coloring
- Advanced Compiler Design and Implementation
- An efficient method of computing static single assignment form
- An overview of the PL.8 compiler
- A retargetable C compiler : design and implementation
- Improvements to graph coloring register allocation
- Register allocation via usage counts