Split Register Allocation: Linear Complexity Without the Performance Penalty

Boubacar Diouf (1) , Albert Cohen (1) , Fabrice Rastello (2) , John Cavazos (3)

1 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
2 COMPSYS - Compilation and embedded computing systems
3 University of Delaware [Newark]

Just-in-time compilers are becoming ubiquitous, spurring the design of more efficient algorithms and more elaborate intermediate representations. They rely on continuous, feedback-directed (re-)compilation frameworks to adaptively select a limited set of hot functions for aggressive optimization. To date, (quasi-)linear complexity has remained a driving force in the design of just-in-time optimizers. This paper describes a \emph{split register allocator} showing that linear complexity does not imply reduced code quality. We present a \emph{split compiler} design, where more expensive ahead-of-time analyses guide lightweight just-in-time optimizations. A split register allocator can be very aggressive in its offline stage, producing a semantic summary through bytecode annotations that can be processed by a lightweight online stage. The challenges are fourfold: (sub-)linear-size annotation, linear-time online processing, minimal loss of code quality, and portability of the annotation. We propose a split register allocator meeting these challenges. A compact annotation derived from an optimal integer linear program (ILP) formulation of register allocation drives a linear-time algorithm near optimality. We study the robustness of this algorithm to variations in the number of physical registers. Our method is implemented in JikesRVM and evaluated on standard benchmarks.

Domaines: Langage de programmation [cs.PL]

Boubacar Diouf, Albert Cohen, Fabrice Rastello, John Cavazos. Split Register Allocation: Linear Complexity Without the Performance Penalty. International Conference on High Performance and Embedded Architectures and Compilers, Oct 2010, Pisa, Italy. 15 p. ⟨inria-00551513⟩