Post-Pass Periodic Register Allocation to Minimise Loop Unrolling Degree

Mounira Bachir 1 Sid Touati 2 Albert Cohen 1
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
Abstract : This paper solves an open problem regarding loop unrolling after periodic register allocation. Although software pipelining is a powerful technique to extract fine-grain parallelism, it generates reuse circuits spanning multiple loop iterations. These circuits require periodic register allocation, which in turn yield a code generation challenge, generally addressed through: (1) hardware support -- rotating register files -- deemed too expensive for embedded processors, (2) insertion of register moves with a high risk of reducing the computation throughput -- initiation interval (II) -- of software pipelining, and (3) post-pass loop unrolling that does not compromise throughput but often leads to unpractical code growth. The latter approach relies on the proof that MAXLIVE registers are sufficient for periodic register allocation [2, 3, 5]; yet the only heuristic to control the amount of post-pass loop unrolling does not achieve this bound and leads to undesired register spills [4, 7]. We propose a periodic register allocation technique allowing a software-only code generation that does not trade the optimality of the II for compactness of the generated code. Our idea is based on using the remaining registers: calling Rarch the number of architectural registers of the target processor, then the number of remaining registers that can be used for minimising the unrolling degree is equal to Rarch − MAXLIVE. We provide a complete formalisation of the problem and algorithm, followed by extensive experiments. We achieve practical loop unrolling degrees in most cases -- with no increase of the II -- while state-of-the-art techniques would either induce register spilling, degrade the II or lead to unacceptable code growth.
Type de document :
Communication dans un congrès
LCTES '08, Jun 2008, Tucson, United States. ACM, pp.141-149, 2008, Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems. 〈http://dl.acm.org/citation.cfm?id=1375677〉. 〈10.1145/1375657.1375677〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00637218
Contributeur : Sid Touati <>
Soumis le : lundi 31 octobre 2011 - 12:30:36
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mercredi 1 février 2012 - 02:21:26

Fichier

Post-Pass_Periodic_Register.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Mounira Bachir, Sid Touati, Albert Cohen. Post-Pass Periodic Register Allocation to Minimise Loop Unrolling Degree. LCTES '08, Jun 2008, Tucson, United States. ACM, pp.141-149, 2008, Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems. 〈http://dl.acm.org/citation.cfm?id=1375677〉. 〈10.1145/1375657.1375677〉. 〈inria-00637218〉

Partager

Métriques

Consultations de la notice

408

Téléchargements de fichiers

159