E-path_PRE - Partial redundancy elimination made. easy
DSpace at IIT Bombay
View Archive InfoField | 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
|
|