Bidirectional data flow analysis: Myths and reality
DSpace at IIT Bombay
View Archive InfoField | 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
|
|