ABSTRACT
This chapter presents a generic version of round-robin method and define a tight complexity bound for general monotone data flow frameworks. It discusses work list based iterative algorithm which computes data flow information in a demand driven fashion. This algorithm forms the basis of formalizing the exact amount of work that a data flow analysis algorithm needs to perform. For a long time, the complexity measures in most of the classical literature were restricted to unidirectional data flow problems. Complexity of bidirectional problems like partial redundancy elimination (PRE) was first explained by U. P. Khedker and D. M. Dhamdhere which also introduced the notion of information flow path in context of bit vector frameworks. The original bidirectional formulation of PRE contains three types of flow functions: Forward edge flow functions, backward edge flow functions and backward node flow functions. The preferred order of traversal depends on the flow functions in the data flow problem.
