U.P. Khedker, D.M. Dhamdhere

A generalized theory of bit vector data flow analysis,

*ACM Transactions on
Programming Languages & Systems*, vol.16, 5 (Sept.
1994), 1472-1511.

**abstract**

The classical theory of data flow analysis, which has its roots in unidirectional flows, is inadequate to characterize bidirectional data flow problems. We present a generalized theory of bit vector data flow analysis which explains the known results in unidirectional and bidirectional data flows and provides a deeper insight into the process of data flow analysis. Based on the theory, we develop a worklist-based generic algorithm which is uniformly applicable to unidirectional and bidirectional data flow problems. It is simple, versatile and easy to adapt for a specific problem. We show that the theory and the algorithm are applicable to all bounded monotone data flow problems which possess the property of the separability of solution.

The theory yields valuable information about the complexity of data
flow analysis. We show that the complexity of worklist-based iterative
analysis is same for unidirectional and bidirectional problems. We also
define a measure of the complexity of round-robin iterative analysis.
This measure, called * width*, is uniformly applicable to
unidirectional and bidirectional problems and provides a tighter bound
for unidirectional problems than the traditional measure of * depth*.
Other applications include explanation of isolated results in efficient
solution techniques and motivation of new techniques for bidirectional
flows. In particular, we discuss edge-splitting, edge placement and develop
a feasibility criterion for decomposition of a bidirectional flow into a
sequence of unidirectional flows.