Efficient Liveness Computation Using Merge Sets and DJ-Graphs

Dibyendu Das 1 Ramakrishna Upadrasta 2 Benoît Dupont de Dinechin 3
2 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : In this work we devise an efficient algorithm that computes the liveness information of program variables. The algorithm employs SSA form and DJ-graphs as representation to build M erge sets. The Merge set of node n, M (n) is based on the structure of the Control Flow Graph (CFG) and consists of all nodes where a φ-function needs to be placed, if a definition of a variable appears in n. The merge sets of a CFG can be computed using DJ-graphs without prior knowledge of how the variables are used and defined. Later, we can answer the liveness query (as a part of other optimization or analysis phase) by utilizing the knowledge of the use/def of variables, the dominator tree and the pre-computed merge sets. On average, merge sets have been shown to be of size comparable to the Dominance Frontier (DF) set of a CFG and can be computed efficiently for all kinds of applications consisting of both reducible and irreducible loops. This is an advantage over existing algorithms which require additional complexities while handling applications using irreducible loops. For cases where the merge sets have already been created during the SSA construction step, the cost of our algorithm reduces even further when we use these merge sets for liveness computation. We have compared our new algorithm with a recent algorithm for computing liveness based on SSA form, and show how it performs better in practice, though being simpler to understand and implement.
Type de document :
Article dans une revue
ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2012, ACM TACO Special Issue on "High-Performance and Embedded Architectures and Compilers", 8 (4), 〈10.1145/2086696.2086706〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00647369
Contributeur : Albert Cohen <>
Soumis le : jeudi 1 décembre 2011 - 21:37:04
Dernière modification le : jeudi 29 septembre 2016 - 01:22:37
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 14:05:52

Fichier

ramakrishna_taco.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Dibyendu Das, Ramakrishna Upadrasta, Benoît Dupont de Dinechin. Efficient Liveness Computation Using Merge Sets and DJ-Graphs. ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2012, ACM TACO Special Issue on "High-Performance and Embedded Architectures and Compilers", 8 (4), 〈10.1145/2086696.2086706〉. 〈hal-00647369〉

Partager

Métriques

Consultations de
la notice

292

Téléchargements du document

360