Quality and speed in linear-scan register allocation

DSpace/Manakin Repository

Quality and speed in linear-scan register allocation

Citable link to this page


Title: Quality and speed in linear-scan register allocation
Author: Traub, Omri; Holloway, Glenn H.; Smith, Michael D.

Note: Order does not necessarily reflect citation order of authors.

Citation: Traub, Omri, Glenn Holloway, and Michael D. Smith. 1998. Quality and Speed in Linear-scan Register Allocation. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, Montreal, QC, June 17-19, 1998: 142-151. doi:10.1145/277650.277714
Full Text & Related Files:
Abstract: 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.
Published Version: doi:10.1145/277650.277714
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:34325454
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search