1999/09/01 by Massimiliano Poletto, Vivek Sarkar · 5 citations
Computer Science · #Parallel Computing and Optimization Techniques #Software Testing and Debugging Techniques #Logic, programming, and type systems #Register allocation #Computer science #Allocator #Graph coloring #Compiler #Parallel computing #Compile time #Graph #Algorithm #Time complexity #Theoretical computer science #Programming language
paper · pdf · doi:10.1145/330249.330250
openalex publication_date 1999/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
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.