Eliminating Dead Computations on Recursive Data

This paper describes a general and e ective method for backward dependence analysis in the presence of recursive data constructions. The goal is to identify partially dead recursive data and eliminate dead computations on them. The method uses projections based on general regular tree grammars extended with the notion of live and dead, and de nes the analysis as mutually recursive grammar transformers. To guarantee that the analysis terminates, we describe how to use nite grammar abstract domains or carefully designed approximation operations. For methods based on nite domains, we describe a new application in caching intermediate results for program improvement. For methods based on approximation operations, we describe algorithms for three such operations that together produce more precise analysis results than previous methods. Finally, the analysis results are used to identify and eliminate dead computations.