D.M. Dhamdhere, U.P. Khedker

Complexity of bidirectional data flows,

*Proceedings of Twentieth annual symposium on the
Principles of Programming Languages*,

Charleston, South Carolina,
January 1993, 397-408.

**abstract**

The concept of an *information flow path* arising from the
generalized theory of data flow analysis [21] is used to analyze the
complexity of data flow analysis. The *width* (*w*) of a
program flow graph with respect to a class of data flow problems is
introduced as a measure of the complexity of round-robin iterative analysis.
This provides the first known complexity result for round robin iterative
analysis of bidirectional data flows commonly used in algorithms based
on the suppression of partial redundancies [6,7,8,9,17,18,25].
We also show that width provides a better bound on the complexity of
unidirectional data flows than the classical notion of * depth*.

The paper presents ways to reduce the width, and thereby the complexity of
flow analysis, for several interesting problems. Complexity analysis
using the notion of width is also shown to motivate efficient solution
methods for various bidirectional problems, viz. the *alternating
iterations* method for the partial redundancy elimination problems.
The paper also presents a condition for the decomposability of a
bidirectional problem into a sequence of unidirectional problems.