On the Complexity of Spill Everywhere under SSA Form

Abstract : Compilation for embedded processors can be either aggressive (time consuming cross-compilation) or just in time (embedded and usually dynamic). The heuristics used in dynamic compilation are highly constrained by limited resources, time and memory in particular. Recent results on the SSA form open promising directions for the design of new register allocation heuristics for embedded systems and especially for embedded compilation. In particular, heuristics based on tree scan with two separated phases --- one for spilling, then one for coloring/coalescing --- seem good candidates for designing memory-friendly, fast, and competitive register allocators. Still, also because of the side effect on power consumption, the minimization of loads and stores overhead (spilling problem) is an important issue. This paper provides an exhaustive study of the complexity of the ``spill everywhere'' problem in the context of the SSA form. Unfortunately, conversely to our initial hopes, many of the questions we raised lead to NP-completeness results. We identify some polynomial cases but that are impractical in JIT context. Nevertheless, they can give hints to simplify formulations for the design of aggressive allocators.
Type de document :
Article dans une revue
ACM SIGPLAN Notices, Association for Computing Machinery (ACM), 2007, Volume 42 (Issue 7), pp.103 - 112. 〈10.1145/1254766.1254782〉
Liste complète des métadonnées

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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00180322
Contributeur : Florent Bouchez <>
Soumis le : jeudi 18 octobre 2007 - 16:52:19
Dernière modification le : mardi 24 avril 2018 - 13:52:58
Document(s) archivé(s) le : dimanche 11 avril 2010 - 23:15:34

Fichiers

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

Identifiants

Collections

Citation

Florent Bouchez, Alain Darte, Fabrice Rastello. On the Complexity of Spill Everywhere under SSA Form. ACM SIGPLAN Notices, Association for Computing Machinery (ACM), 2007, Volume 42 (Issue 7), pp.103 - 112. 〈10.1145/1254766.1254782〉. 〈ensl-00180322〉

Partager

Métriques

Consultations de la notice

279

Téléchargements de fichiers

156