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
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
2 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00551513
Contributor : Albert Cohen <>
Submitted on : Tuesday, January 4, 2011 - 12:19:11 AM
Last modification on : Friday, April 20, 2018 - 3:44:23 PM
Long-term archiving on : Monday, November 5, 2012 - 3:16:03 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00551513, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

545

Files downloads

373