A Tiling Perspective for Register Optimization

Abstract : Register allocation is a much studied problem. A particularly important context for optimizing register allocation is within loops, since a significant fraction of the execution time of programs is often inside loop code. A variety of algorithms have been proposed in the past for register allocation, but the complexity of the problem has resulted in a decoupling of several important aspects, including loop unrolling, register promotion, and instruction reordering. In this paper, we develop an approach to register allocation and promotion in a unified optimization framework that simultaneously considers the impact of loop unrolling and instruction scheduling. This is done via a novel instruction tiling approach where instructions within a loop are represented along one dimension and innermost loop iterations along the other dimension. By exploiting the regularity along the loop dimension, and imposing essential dependence based constraints on intra-tile execution order, the problem of optimizing register pressure is cast in a constraint programming formalism. Experimental results are provided from thousands of innermost loops extracted from the SPEC benchmarks, demonstrating improvements over the current state-of-the-art.
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-00998915
Contributor : Gcg Equipe <>
Submitted on : Tuesday, June 3, 2014 - 4:20:47 AM
Last modification on : Saturday, September 17, 2016 - 1:36:48 AM
Long-term archiving on : Wednesday, September 3, 2014 - 10:58:04 AM

Files

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

Identifiers

  • HAL Id : hal-00998915, version 1
  • ARXIV : 1406.0582

Collections

Citation

Fabrice Rastello, Sadayappan Ponnuswany, Duco van Amstel. A Tiling Perspective for Register Optimization. [Research Report] RR-8541, Inria. 2014, pp.24. ⟨hal-00998915⟩

Share

Metrics

Record views

526

Files downloads

500