Register allocation by graph coloring under full live-range splitting

Abstract : Register allocation is often a two-phase approach: spilling of registers to memory, followed by coalescing of registers. Extreme liverange splitting (i.e. live-range splitting after each statement) enables optimal solutions based on ILP, for both spilling and coalescing. However, while the solutions are easily found for spilling, for coalescing they are more elusive. This difficulty stems from the huge size of interference graphs resulting from live-range splitting. This paper focuses on coalescing in the context of extreme liverange splitting. It presents some theoretical properties that give rise to an algorithm for reducing interference graphs. This reduction consists mainly in finding and removing useless splitting points. It is followed by a graph decomposition based on clique separators. The reduction and decomposition are general enough, so that any coalescing algorithm can be applied afterwards. Our strategy for reducing and decomposing interference graphs preserves the optimality of coalescing. When used together with an optimal coalescing algorithm (e.g. ILP), optimal solutions are much more easily found. The strategy has been tested on a standard benchmark, the optimal coalescing challenge. For this benchmark, the cutting-plane algorithm for optimal coalescing (the only optimal algorithm for coalescing) runs 300 times faster when combined with our strategy. Moreover, we provide all the optimal solutions of the optimal coalescing challenge, including the three instances that were previously unsolved.
Type de document :
Communication dans un congrès
ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded systems (LCTES'2009), Jun 2009, Dublin, Ireland. 2009


https://hal.inria.fr/inria-00387749
Contributeur : Sandrine Blazy <>
Soumis le : mardi 2 juin 2009 - 10:11:22
Dernière modification le : lundi 5 octobre 2015 - 16:57:41
Document(s) archivé(s) le : lundi 15 octobre 2012 - 11:00:26

Fichier

LCTES09.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00387749, version 1

Collections

Citation

Sandrine Blazy, Benoît Robillard. Register allocation by graph coloring under full live-range splitting. ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded systems (LCTES'2009), Jun 2009, Dublin, Ireland. 2009. <inria-00387749>

Partager

Métriques

Consultations de
la notice

233

Téléchargements du document

113