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 form. Strict SSA form guarantees that the definition of a variable always dominates all its uses. This property can be exploited in order to optimize the computation of liveness information. Our first contribution is the design of a fast data-flow algorithm, which, similar to traditional approaches, first traverses the control-flow graph in postorder propagating liveness information backwards. A second pass then traverses the loop-nesting forest, propagating liveness information within loops. Due to the properties of strict SSA form, the iterative calculation of a fixed-point can be~avoided. Another maybe more natural approach is to identify, one path at a time, all paths from a use of a variable to its unique definition. Such a 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 by the other algorithms, showing substantial speed-ups a factor of 2 on average. Depending on the underlying set implementation either the path-based approach or the loop-forest-based approach provides superior performance.
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 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 de calcul de type flot de données qui, de même que les approches traditionnelles, propage les informations de vivacité en remontant le flot d'un parcours en profondeur. Un deuxième parcours propage, cette fois-ci en descendant une hiérarchie de boucles (loop-nesting forest), l'information dans les boucles. Par ce procédé et du fait de la propriété de la forme SSA stricte, le calcul itératif traditionnel pour obtenir un point fixe est inutile. Une autre approche, peut-être plus naturelle, est d'identifier, un chemin à la fois, tous les chemins remontant de l'utilisation d'une variable jusqu'à sa définition. Une telle approche a été mentionné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.
Domaines
Langage de programmation [cs.PL]
Origine : Fichiers produits par l'(les) auteur(s)