logo of the SSW institute ;)
Computer Science
System Software

Home

General
Staff
Contact
Partners
Alumni

Research
Areas
Projects
Papers
Books
Reports
Awards

Teaching
Lectures
Exams
B.Projects
M.Theses
PhD Theses
Go Abroad

Misc
Talks
Library
Gallery
Links
Search

Webmaster


Linear Scan Register Allocation in the Context of SSA Form and Register Constraints

Hanspeter Mössenböck and Michael Pfeiffer
Johannes Kepler University Linz
Institute for Practical Computer Science
Altenbergerstraße 69, A-4040 Linz
{moessenboeck,pfeiffer}@ssw.uni-linz.ac.at


Abstract

Linear scan register allocation is an efficient alternative to the widely used graph coloring approach. We show how this algorithm can be applied to register-constrained architectures like the Intel x86. Our allocator relies on static single assignment form, which simplifies data flow analysis and tends to produce short live intervals. It makes use of lifetime holes and instruction weights to improve the quality of the allocation. Our measurements confirm that linear scan is several times faster than graph coloring for medium-sized to large programs.


Paper at the International Conference on Compiler Construction (CC'02), Grenoble, April 2002
Lecture Notes in Computer Science 2304, pp.229 ff, Springer-Verlag, 2002
You can download the paper in PDF.