Computing Liveness Sets for SSA-Form Programs

Florian Brandner 1 Benoit Boissinot 1 Alain Darte 1 Benoît Dupont de Dinechin 2 Fabrice Rastello 1
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : Nous réexaminons le problème du calcul des ensembles de vivacité, c'est-à-dire des ensembles de variables en vie en entrée et sortie des blocs de base d'un programme en forme SSA (assignation unique statique) stricte. La forme SSA stricte est également appelée SSA avec propriété de dominance parce qu'elle garantit que la définition d'une variable domine toujours toutes ses utilisations. Nous exploitons cette propriété pour optimiser le calcul de vivacité. Notre première contribution est la conception d'un algorithme rapide de type flot de données qui, à la différence des approches traditionnelles, évite les itérations de calcul de point fixe. Grâce aux propriétés de la forme SSA stricte et à l'utilisation d'une hiérarchie de boucles (''loop-nesting forest''), nous montrons que deux passes sont suffisantes. Une première passe, similaire à la phase d'initialisation de la méthode de flot de données itérative, propage les informations de vivacité en remontant un parcours en profondeur du graphe de flot de contrôle. Une deuxième passe parcourt la hiérarchie de boucles pour mettre à jour l'information dans les boucles. Une autre approche consiste à propager depuis les utilisations jusqu'à la définition, une variable et un chemin à la fois, plutôt que d'effectuer des unions d'ensembles comme dans l'analyse de flot de données standard. Une telle stratégie d'exploration des chemins a été proposée par Appel dans son ''Tiger book'' et est également utilisée dans le compilateur LLVM. Notre seconde contribution est de montrer comment étendre et optimiser un algorithme basé sur cette idée pour calculer les ensembles de vivacité, une variable à la fois, et avec des structures de données adéquates. Finalement, nous évaluons et comparons les performances des algorithmes proposés avec les ''benchmarks'' de SPECINT 2000. L'approche traditionnelle de flot de données est clairement surpassée par les autres algorithmes, avec un facteur d'amélioration de 2 en moyenne. Selon l'implantation des ensembles de vivacité, la meilleure approche est soit celle par remontée de chemin, soit celle utilisant la hiérarchie de boucles. Les expérimentations montrent que notre algorithme flot de données offre de meilleures performances (amélioration de 43% par rapport à la meilleure alternative) quant les ensembles sont représentés par des ''bitsets'' et pour les programmes optimisés, programmes avec plus de variables, et des ensembles de vivacité et des intervalles de vie plus grands.
Type de document :
Rapport
[Research Report] RR-7503, INRIA. 2011, pp.25
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00558509
Contributeur : Florian Brandner <>
Soumis le : mardi 12 avril 2011 - 14:50:08
Dernière modification le : vendredi 20 avril 2018 - 15:44:23
Document(s) archivé(s) le : samedi 3 décembre 2016 - 13:42:59

Fichier

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

Identifiants

  • HAL Id : inria-00558509, version 2

Collections

Citation

Florian Brandner, Benoit Boissinot, Alain Darte, Benoît Dupont de Dinechin, Fabrice Rastello. Computing Liveness Sets for SSA-Form Programs. [Research Report] RR-7503, INRIA. 2011, pp.25. 〈inria-00558509v2〉

Partager

Métriques

Consultations de la notice

602

Téléchargements de fichiers

803