Record Details

E-path_PRE - Partial redundancy elimination made. easy

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title E-path_PRE - Partial redundancy elimination made. easy
 
Creator DHAMDHERE, DM
 
Subject data-flow-analysis
strength reduction transformation
global program optimization
edge placement
code motion
algorithm
reality
partial redundancy elimination
eliminatability of expressions
code optimization
data flow analysis
redundant code movement
 
Description Partial redundancy elimination (PRE) subsumes the classical optimizations of loop invariant movement and common subexpression elimination. The original formulation of PRE involved complex bi-directional data flows and had two major deficiencies-missed optimization opportunities and redundant code movement. To eliminate redundant code movement, most current PRE approaches use a hoisting-followed-by-sinking approach. Unfortunately, this approach has a high conceptual complexity and requires complicated correctness proofs. We show that optimization by partial redundancy elimination is simpler than it has been made out to be. Its essence is the concept of eliminatability of an expression. We show that E-path_PRE, a formulation of PRE based on the concept of eliminatability paths (E-paths), is easy to understand and simple to prove correct. It uses only well-known data flow concepts of available expressions and anticipatable (i.e. very-busy) expressions to directly identify code insertion points which avoid redundant code movement. These features reduce the conceptual complexity of PRE considerably. Interestingly, performance studies show that E-path_PRE is also less expensive to perform than the closest equivalent approach to PRE. This is a sheer bonus.
 
Publisher ASSOC COMPUTING MACHINERY
 
Date 2011-07-18T20:30:44Z
2011-12-26T12:50:49Z
2011-12-27T05:36:56Z
2011-07-18T20:30:44Z
2011-12-26T12:50:49Z
2011-12-27T05:36:56Z
2002
 
Type Article
 
Identifier ACM SIGPLAN NOTICES, 37(8), 53-65
0362-1340
http://dx.doi.org/10.1145/596992.597004
http://dspace.library.iitb.ac.in/xmlui/handle/10054/5056
http://hdl.handle.net/10054/5056
 
Language en