Incremental data flow analysis based on a unified model of elimination algorithms
Barbara G. Ryder · 1982
In this thesis we present our work on the development of incremental update algorithms for global data flow analysis, algorithms which modify a known data flow solution to reflect changes in the problem. We have shown that given a data flow problem defined on a digraph, the effects of a set of localized program changes can be determined without full re-analysis by some global data flow algorithm. Our major research contributions fall into three categories. First, we have modelled three elimination methods for global data flow analysis: Allen/Cocke interval analysis, Hecht/Ullman T1-T2 analysis, and Tarjan interval analysis. Our models allow comparison among the methods and highlight the sources of worst case complexity improvement. Second, we have designed two incremental update data flow algorithms based on the Allen/Cocke algorithm (ACINCF, ACINCB) and the Hecht/Ullman algorithm (HUINC). The complexity and correctness of these algorithms is demonstrated. Third, we have studied our incremental algorithm performance on a robust, Algol-like structured programming language L. We have identified program structures which affect the complexity of incremental updating and established their effects singly and in concert. Specifically, for reducible digraphs we have shown that the elimination phase of ACINCF (and/or ACINCB) updates on each linear system in the derived sequence, a set of interval head equations and at most the equations in one interval. Further, we have considered program changes within one interval in a nested loop in a program in L and have characterized the set of all variables whose equations may be affected, in terms of each variable's corresponding program structure and its relation to the original change site. Thus, we have ascertained all the data flow solutions affected by the changes. Our result enables us to analyze a digraph in L with a set of possible changes identifying a priori, nodes whose equations will be affected by these changes.