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.