Eliminating Dead Code on Recursive Data
Yanhong A. Liu and Scott D. Stoller
This paper describes a general and powerful method for dead code analysis
and elimination in the presence of recursive data constructions. We
represent partially dead recursive data using liveness patterns based on
general regular tree grammars extended with the notion of live and dead,
and we formulate the analysis as computing liveness patterns at all
program points based on program semantics. This analysis yields a most
precise liveness pattern for the data at each program point, which is
significantly more precise than results from previous methods. The
analysis algorithm takes cubic time in terms of the size of the program in
the worst case but is very efficient in practice, as shown by our
prototype implementation. The analysis results are used to identify and
eliminate dead code. The general framework for representing and analyzing
properties of recursive data structures using general regular tree
grammars applies to other analyses as well.
BiBTeX
PDF
Scott Stoller's Home Page