Fast Liveness Checking for SSA-Form Programs

Abstract : Liveness analysis is an important analysis in optimizing compilers. Liveness information is used in several optimizations and is mandatory during the code-generation phase. Two drawbacks of conventional liveness analyses are that their computations are fairly expensive and their results are easily invalidated by program transformations. We present a method to check liveness of variables that overcomes both obstacles. The major advantage of the proposed method is that the analysis result survives all program transformations except for changes in the control-flow graph. For common program sizes our technique is faster and consumes less memory than conventional data-flow approaches. Thereby, we heavily make use of SSA-form properties, which allow us to completely circumvent data-flow equation solving. We evaluate the competitiveness of our approach in an industrial strength compiler. Our measurements use the integer part of the SPEC2000 benchmarks and investigate the liveness analysis used by the SSA destruction pass. We compare the net time spent in liveness computations of our implementation against the one provided by that compiler. The results show that in the vast majority of cases our algorithm, while providing the same quality of information, needs less time: an average speed-up of 16%.
Type de document :
[Research Report] 2007, pp.9
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Benoit Boissinot <>
Soumis le : mardi 27 novembre 2007 - 11:03:26
Dernière modification le : mardi 24 avril 2018 - 13:52:35
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 10:21:57


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00192219, version 1



Benoit Boissinot, Sebastian Hack, Daniel Grund, Benoît De Dinechin, Fabrice Rastello. Fast Liveness Checking for SSA-Form Programs. [Research Report] 2007, pp.9. 〈inria-00192219〉



Consultations de la notice


Téléchargements de fichiers