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.