Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 341-364 |
Number of pages | 24 |
Journal | Computer Languages, Systems and Structures |
Volume | 35 |
Issue number | 4 |
DOIs | |
State | Published - Dec 2009 |
Keywords
- Common subexpression elimination
- Distributed data problem
- Higher-order strategies
- Program transformation
- Rewriting
- Strategic programming
ASJC Scopus subject areas
- Software
- Computer Networks and Communications