Iterative Data-flow Analysis, Revisited
Keith D. Cooper, Timothy J. Harvey, Ken Kennedy · 2004
ABSTRACT The iterative algorithm is widely used to solve instances of data-flow analysis problems. The algorithm is attractive because it is easy to implement and robust in its behavior. The theory behind the algorithm shows that, for a broad class of problems, it terminates and produces correct results. The theory also establishes a set of conditions where the algorithm runs in at most d(G) + 3 passes over the graph-- a round-robin algorithm, running a "rapid " framework, on a reducible graph [22]. Fortunately, these restrictions encompass many practical analyses used in code optimization. In practice, compilers encounter situations that lie outside this carefully described region. Compilers encounter irreducible graphs-- probably more often than the early studies suggest. They use variations of the algorithm other than the round-robin form. They run on problems that are not rapid.