Elimination of parallel copies using code motion on data dependence graphs

Florian Brandner 1 Quentin Colombet 2
2 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.
keyword : Copy elimination
Type de document :
Article dans une revue
Computer Languages, Systems and Structures, Elsevier, 2013, 39 (1), pp.25 - 47. 〈10.1016/j.cl.2012.09.001〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00768781
Contributeur : Alain Darte <>
Soumis le : dimanche 23 décembre 2012 - 22:51:30
Dernière modification le : vendredi 20 avril 2018 - 15:44:23

Lien texte intégral

Identifiants

Collections

Citation

Florian Brandner, Quentin Colombet. Elimination of parallel copies using code motion on data dependence graphs. Computer Languages, Systems and Structures, Elsevier, 2013, 39 (1), pp.25 - 47. 〈10.1016/j.cl.2012.09.001〉. 〈hal-00768781〉

Partager

Métriques

Consultations de la notice

177