A higher-order strategy for eliminating common subexpressions

Optimizing compilers often perform an operation known as common subexpression elimination to improve code efficiency. 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-flow 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.