A Polynomial Spilling Heuristic: Layered Allocation

Boubacar Diouf 1 Albert Cohen 1 Fabrice Rastello 2
1 Parkas - Parallélisme de Kahn Synchrone
CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria Paris-Rocquencourt, DI-ENS - Département d'informatique de l'École normale supérieure
2 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Register allocation is one of the most important, and one of the oldest compiler optimizations. Its purpose is to map temporary variables to either machine registers or main memory locations and explicit load/store instructions. The latter option is referred to as spilling. This paper addresses the minimization of the spill code overhead, one of the di fficult problems in register allocation. We devised a heuristic approach called layered. It is rooted in the recent advances in SSA-based register allocation. As opposed to the conventional incremental spilling approaches, our method incrementally allocates clusters of variables. We describe a new polynomial method, the layered-optimal allocator, and demonstrate its quasi-optimiality on standard benchmarks and on two architectures.
Document type :
Reports
Liste complète des métadonnées

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00713693
Contributor : Boubacar Diouf <>
Submitted on : Monday, July 2, 2012 - 3:07:03 PM
Last modification on : Thursday, February 7, 2019 - 2:42:36 PM
Document(s) archivé(s) le : Thursday, December 15, 2016 - 7:56:33 PM

File

RR-8007.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00713693, version 2

Citation

Boubacar Diouf, Albert Cohen, Fabrice Rastello. A Polynomial Spilling Heuristic: Layered Allocation. [Research Report] RR-8007, INRIA. 2012, pp.23. ⟨hal-00713693v2⟩

Share

Metrics

Record views

378

Files downloads

451