Computing Liveness Sets for SSA-Form Programs
Résumé
We revisit the problem of computing liveness sets, i.e., the set of variables live-in and live-out of basic blocks, for programs in strict SSA (static single assignment). Strict SSA is also known as SSA with dominance property because it ensures that the definition of a variable always dominates all its uses. This property can be exploited to optimize the computation of liveness sets. Our first contribution is the design of a fast data-flow algorithm, which, unlike traditional approaches, avoids the iterative calculation of a fixed point. Thanks to the properties of strict SSA form and the use of a loop-nesting forest, we show that two passes are sufficient. A first pass, similar to the initialization of iterative data-flow analysis, traverses the control-flow graph in postorder propagating liveness information backwards. A second pass then traverses the loop-nesting forest, updating liveness information within loops. Another approach is to propagate from uses to definition, one variable and one path at a time, instead of unioning sets as in standard data-flow analysis. Such a path-exploration strategy was proposed by Appel in his ''Tiger book'' and is also used in the LLVM compiler. Our second contribution is to show how to extend and optimize algorithms based on this idea to compute liveness sets one variable at a time using adequate data~structures. Finally, we evaluate and compare the efficiency of the proposed algorithms using the SPECINT 2000 benchmark suite. The standard data-flow approach is clearly outperformed, all algorithms show substantial speed-ups of a factor of 2 on average. Depending on the underlying set implementation either the path-exploration approach or the loop-forest-based approach provides superior performance. Experiments show that our loop-forest-based algorithm provides superior performances (average speed-up of 43% on the fastest alternative) when sets are represented as bitsets and for optimized programs, i.e., when there are more variables and larger live-sets and live-ranges.
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.
Domaines
Langage de programmation [cs.PL]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...