A generalized theory of bit vector data flow analysis

Reviewer: Gerald David Chandler

Dataflow problems are concerned with a set of flow equations that relate the flow of information concerning safe and profitable code transformations in programs. The larger part of this paper consists of systematizing known results. The major contributions are to make the results better understood and to provide a tighter bound on the complexity of dataflow analysis. This work represents a continuation of a program that has been carried on for more than a decade by Dhamdhere and his students and colleagues. It should prove valuable to workers in the field and a useful reference to newcomers. For the latter, it is likely to prove difficult, as it is heavy with definitions. The presentation seems to have suffered from what appears to be a reduction of a longer paper that included proofs. The language is clear, though, and there are no important typographical errors. The authors use as running examples the equations for five problems: reaching definitions, live variable, the Morel-Renvoise algorithm, the basic load store insertion algorithm, and the composite hoisting and strength reduction algorithm. Flow problems can be forward, backward, or bidirectional. In the last case, if a program is viewed as a directed graph, dataflow information flows up and down the graph. The authors observe that bidirectional problems are made clearer by distinguishing between flows through nodes and those along edges. They define sibling and spouse effects, in which information flows respectively from nodes that have the same parents or the same child, and show how these flows arise in bidirectional problems. After introducing their theoretical framework, the authors present an algorithm for solving the general flow problem based on wordwise analysis, in which a bit vector is used to represent the solution and is processed in word-units. This is plausibly said to save time “since all parts may not require processing of all nodes,” but they present no experimental confirmation, although they do refer to another paper with data. They point out that their methods are not restricted to bit-vector methods; rather, they apply to any dataflow framework that is monotonic and separable. One method of solution of flow problems is iterative, in which an initial solution is assumed and a fixed-point solution found by repeated substitution of the current answer in the equations. The authors point out that previous works were not rigorous in specifying how to choose initial values and fix this lacuna. The standard upper limit on the complexity of itera tive solutions is that it is proportional to the number of back edges not visited during a standard (reverse) postorder traversal. The authors improve on this by defining a graph width, which is the size of a subset of the back edges and thus a smaller limit.

Reviewer: Svetlana Segarceanu

Dataflow analysis is an important process used in program design, optimization, and debugging. The paper presents a generalized theory of bit vector dataflow analysis, which elucidates the known results in unidirectional and bidirectional dataflows and provides a deeper insight into the process of dataflow analysis. The theory presented in the paper handles both unidirectional (either forward or backward) and bidirectional dataflow problems. Though the presentation concerns bit vector problems, the theory is applicable to a larger class of dataflow problems. After an introductory section, the authors present the Morel Renvoise algorithm for partial redundancy elimination, which they use as a representative bidirectional problem throughout the paper. Section 3 presents an overview of the classical theory of dataflow analysis and compares the efficiency of several methods (such as meet over paths solution and maximum fixed point solution), and describes the two main approaches to dataflow analysis (the iterative method and the elimination method). The next section defines the bit vector frameworks, generalizes the classical concepts, and proposes generic dataflow equations. Section 5 presents a worklist-based generic algorithm, analyzes its performance, and proves that the complexity of the worklist-based iterative analysis is the same for unidirectional and bidirectional problems. Section 6 discusses several applications of the generalized theory. A new measure is defined, which is shown to bound the number of iterations of round-robin analysis for unidirectional and bidirectional problems. This section also establishes several results on the solution of bidirectional dataflows with regard to edge splitting and edge placement, and develops a feasibility criterion for decomposition of bi directional flows into a sequence of unidirectional flows. Section 7 draws conclusions on the significance and applicability of the results presented. Although not cited in the text, some of the figures clearly illustrate certain phenomena described. For instance, Figure 13 concerns Example 6.2.1.1, and Figure 14 is an illustration of the process of edge splitting. The main goal of the work—to unify the theoretical results concerning unidirectional and bidirectional dataflows—is thoroughly achieved. It extends previous results in dataflow analysis, most of which can be found in the references. Thus, it would be enlightening reading for people whose professional interests lie in this domain.