A high-level graph approach to incremental data flow analysis
F.-J. Wang · 1988
Incremental data flow analysis updates global flow information according to program changes during optimization or editing in language-based editors. The techniques of intermediate-level analysis presume a set of primitive program changes and develop an independent modification process according to each primitive change. However, the complicated editing operations such as a tree substitution cause many redundant computations although these operations can be treated as a sequence of basic modifications. High-level analysis, which is based on the parsing tree, is easier at handling these editing operations. The existing high-level analysis techniques are either less powerful or less efficient for the integrated analysis of these operations. In this dissertation, a high-level graph approach to data flow analysis in structure-goto programs based upon hierarchical recursive graph (HRG) is presented. A structure-goto program is a program in which a goto-statement cannot jump into a structure statement. This approach divides an incremental process into three phases to integrate the data flow analysis for all types of program changes in language-based editors, where the first phase deals with the affected HRG's, the second phase updates local data flow information by tracing the affected HRG's, and the third phase propagates the affected global flow information. This approach uses live variables to show the processing of flow analysis in both batch and incremental modes. It provides three solutions for different requirements: robust, demand, and screen-oriented analyses, where robust analysis keeps global flow information always correct, demand analysis updates local flow information and calculates the information of a location under demand, and screen-oriented analysis maintains only the global flow information shown on the screen. The characteristics of HRG's are discussed and used to simplify this approach. Furthermore, the solutions for reaching definition problems, data flow anomaly detection and location listing in our approach are also presented.