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, CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France
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.
Type de document :
Communication dans un congrès
International Conference on High Performance and Embedded Architectures and Compilers, Oct 2010, Pisa, Italy. 15 p, 2010
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00551513
Contributeur : Albert Cohen <>
Soumis le : mardi 4 janvier 2011 - 00:19:11
Dernière modification le : jeudi 9 février 2017 - 15:56:36
Document(s) archivé(s) le : lundi 5 novembre 2012 - 15:16:03

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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, 2010. 〈inria-00551513〉

Partager

Métriques

Consultations de la notice

430

Téléchargements de fichiers

280