Title
A higher-order strategy for eliminating common subexpressions
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.
Year
DOI
Venue
2009
10.1016/j.cl.2008.06.004
Computer Languages, Systems & Structures
Keywords
Field
DocType
higher-order strategy,lambda calculus,acyclic graph,higher-order strategic method,common subexpressions,common subexpression elimination,code efficiency,partial-redundancy elimination,data-flow analysis method,optimizing compiler,rewrites expression tree,rewriting,directed acyclic graph,higher order,data flow analysis,partial redundancy elimination
Lambda calculus,Common subexpression elimination,Programming language,Program transformation,Computer science,Correctness,Compiler,Theoretical computer science,Directed acyclic graph,Rewriting,Binary expression tree
Journal
Volume
Issue
ISSN
35
4
Computer Languages, Systems & Structures
Citations 
PageRank 
References 
0
0.34
28
Authors
2
Name
Order
Citations
PageRank
R. Daniel Resler1223.48
Victor Winter292.32