Improvements to Conservative and Optimistic Register Coalescing

Abstract : Register coalescing is used, as part of register allocation, to reduce the number of register copies. Developing efficient register coalescing heuristics is particularly important to get rid of the numerous move instructions introduced by code transformations such as static single assignment, among others. The challenge is to find a good trade-off between a too aggressive strategy that could make the interference graph uncolorable, possibly increasing the spill (transfer to memory), and a too conservative strategy that preserves colorability but leaves too many moves. The two main approaches are ``iterated register coalescing'' by George and Appel and ``optimistic coalescing'' by Park and Moon. The first one coalesces moves, one by one, in a conservative way. In the second one, moves are first coalesced regardless of the colorability, then some coalescings are undone to reduce spilling. Previous experiments show that optimistic coalescing outperforms conservative coalescing. We show that, with a more involved conservative strategy, incremental conservative coalescing can be as efficient as optimistic coalescing. We also develop a more aggressive optimistic approach with a different de-coalescing phase. The combination of the two approaches leads to about 10% improvements compared to traditional optimistic coalescing.
Type de document :
Article dans une revue
Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems, 2008, pp.147-156. 〈10.1145/1450095.1450119〉
Liste complète des métadonnées

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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00179685
Contributeur : Florent Bouchez <>
Soumis le : mardi 16 octobre 2007 - 12:58:02
Dernière modification le : mardi 24 avril 2018 - 13:52:54
Document(s) archivé(s) le : lundi 27 juin 2011 - 17:17:27

Fichiers

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

Identifiants

Collections

Citation

Florent Bouchez, Alain Darte, Fabrice Rastello. Improvements to Conservative and Optimistic Register Coalescing. Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems, 2008, pp.147-156. 〈10.1145/1450095.1450119〉. 〈ensl-00179685〉

Partager

Métriques

Consultations de la notice

369

Téléchargements de fichiers

213