Record Details

Bidirectional data flow analysis: Myths and reality

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Bidirectional data flow analysis: Myths and reality
 
Creator KHEDKER, UP
DHAMDHERE, DM
 
Subject strength reduction transformation
partial redundancy elimination
global program optimization
code motion
algorithm
frameworks
suppression
renvoise
morel
 
Description Research in bidirectional data flow analysis seems to have come to a halt due to an impression that the case for bidirectional data flow analysis has been considerably weakened by a plethora of investigations based on decomposability of known bidirectional placement algorithms into a sequence of purely unidirectional components. This paper shows that the approach of decomposability is not general enough in that it derives its power from the simplifying graph transformation of edge-splitting and the favourable nature of flows in partial redundancy elimination (PRE). This follows from the fact that in the absence of edge-splitting, PRE cannot be performed using a sequence of cascaded unidirectional flows. Further, edge-splitting inherently converts data flows involved in PRE into unidirectional flows. In our opinion, this obviates the need of an alternative formulation. We also show that edge-splitting cannot convert data flows involved in "truly" bidirectional data flow problems into unidirectional flows. Thus not every bidirectional data flow problem can be converted into unidirectional flows. Besides, we argue that the premise that bidirectional analysis is more complex than unidirectional analysis, is invalid. We also mention some issues in bidirectional data flow analysis which need to be investigated.
 
Publisher ASSOC COMPUTING MACHINERY
 
Date 2011-07-18T20:09:39Z
2011-12-26T12:50:48Z
2011-12-27T05:36:55Z
2011-07-18T20:09:39Z
2011-12-26T12:50:48Z
2011-12-27T05:36:55Z
1999
 
Type Article
 
Identifier ACM SIGPLAN NOTICES, 34(6), 47-57
0362-1340
http://dx.doi.org/10.1145/606666.606676
http://dspace.library.iitb.ac.in/xmlui/handle/10054/5050
http://hdl.handle.net/10054/5050
 
Language en