Parallel Copy Elimination on Data Dependence Graphs

Florian Brandner 1 Quentin Colombet 1
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Register allocation regained much interest in recent years due to the development of decoupled strategies that split the problem into separate phases: spilling, register assignment, and copy elimination. Traditional approaches to copy elimination during register allocation are based on interference graphs and register coalescing. Variables are represented as nodes in a graph, which are coalesced, if they can be assigned the same register. However, decoupled approaches strive to avoid interference graphs and thus often resort to local recoloring. A common assumption of existing coalescing and recoloring approaches is that the original ordering of the instructions in the program is not changed. This work presents an extension of a local recoloring technique called Parallel Copy Motion. We perform code motion on data dependence graphs in order to eliminate useless copies and reorder instructions, while at the same time a valid register assignment is preserved. Our results show that even after traditional register allocation with coalescing our technique is able to eliminate an additional 3% (up to 9%) of the remaining copies and reduce the weighted costs of register copies by up to 25% for the SPECINT 2000 benchmarks. In comparison to Parallel Copy Motion, our technique removes 11% (up to 20%) more copies and up to 39% more of the copy costs.
Type de document :
Rapport
[Research Report] RR-7735, INRIA. 2011, pp.29
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00625131
Contributeur : Florian Brandner <>
Soumis le : mercredi 21 septembre 2011 - 10:45:40
Dernière modification le : mardi 16 janvier 2018 - 15:42:50
Document(s) archivé(s) le : mardi 13 novembre 2012 - 14:06:12

Fichier

RR-7735.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00625131, version 1

Collections

Citation

Florian Brandner, Quentin Colombet. Parallel Copy Elimination on Data Dependence Graphs. [Research Report] RR-7735, INRIA. 2011, pp.29. 〈inria-00625131〉

Partager

Métriques

Consultations de la notice

298

Téléchargements de fichiers

192