Linear Scan Register Allocation in the Context of SSA Form and Register Constraints
Hanspeter Mössenböck and Michael Pfeiffer
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