Abstract

Optimizing compilers often perform an operation known as common subexpression elimination to improve code effciency. Typically this is accomplished either by pruning a directed acyclic graph to replace eliminated subexpressions by memory fetches of stored values or by using partial redundancy elimination, a data- ow analysis method. In this paper a higher-order strategic method is presented that rewrites expression trees to eliminate common subexpressions using equivalences in the lambda calculus. This approach offers several advantages--it is intuitive, transformations can be defined and applied within a high-level rewrite system, and it uses transformations for which correctness preservation can be proven.

Key words: program transformation, higher-order strategies, strategic programming, rewriting, common subexpression elimination, distributed data problem