Eliminating dead code on recursive data

This paper describes a powerful method for dead-code analysis and elimination in the presence of recursive data constructions. We describe 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 constraints constructed from the program and programming language semantics. The analysis yields the most precise program-based grammars that satisfy the constraints. 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 framework for representing and analyzing properties of recursive data structures using general regular tree grammars applies to other analyses as well.