1998/05/01 by Omri Traub, Glenn Holloway, Michael D. Smith · 1 citation
Computer Science · #Parallel Computing and Optimization Techniques #Software Testing and Debugging Techniques #Logic, programming, and type systems #Register allocation #Computer science #Allocator #Compiler #Graph coloring #Parallel computing #Register (sociolinguistics) #Graph #Processor register #Shift register #Algorithm #Dynamic compilation #Programming language #Theoretical computer science #Computer hardware
paper · pdf · doi:10.1145/277652.277714
openalex publication_date 1998/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
A linear-scan algorithm directs the global allocation of register candidates to registers based on a simple linear sweep over the program being compiled. This approach to register allocation makes sense for systems, such as those for dynamic compilation, where compilation speed is important. In contrast, most commercial and research optimizing compilers rely on a graph-coloring approach to global register allocation. In this paper, we compare the performance of a linear-scan method against a modern graph-coloring method. We implement both register allocators within the Machine SUIF extension of the Stanford SUIF compiler system. Experimental results show that linear scan is much faster than coloring on benchmarks with large numbers of register candidates. We also describe improvements to the linear-scan approach that do not change its linear character, but allow it to produce code of a quality near to that produced by graph coloring.