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
CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria Paris-Rocquencourt, DI-ENS - Département d'informatique de l'École normale supérieure
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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [19 references]  Display  Hide  Download

Contributor : Albert Cohen <>
Submitted on : Thursday, December 1, 2011 - 9:37:04 PM
Last modification on : Thursday, March 14, 2019 - 9:44:05 AM
Document(s) archivé(s) le : Friday, November 16, 2012 - 2:05:52 PM


Files produced by the author(s)




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⟩



Record views


Files downloads