Liveness analysis is an important analysis in optimizing compilers.
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%.

We also present a generalization based on the loop forest theory, for
maximal reuse of existing data-structures.

References:
http://hal.archives-ouvertes.fr/docs/00/19/22/19/PDF/fast_liveness.pdf