INCREMENTAL DATA FLOW ANALYSIS IN A STRUCTURED PROGRAM EDITOR

Recent work in the area of software engineering has centered on the creation of sophisticated environments to enhance the development and maintenance of computer programs. One goal of this effort is to provide the programmer with information about the program early in the development cycle. With this information, the programmer can then correct design deficiencies and catch small programming errors. One type of analysis that can be provided in these environments is data flow analysis. Data flow analysis can find many common programming errors such as uninitialized variables and calculated values that are never used. Additionally, this analysis can be used to maintain a data base that can aid the programmer in determining the effect that seemingly small changes may have on the entire program. In an interactive programming environment, small changes are made to the program. Ideally, the data flow information for the problem should be updated as each small change is made. Traditionally, data flow techniques analyze the entire program for all variables at once, though the analysis can be performed for each variable separately. Updating the solution for each variable separately is a reasonable technique in an interactive environment since many source changes are small and local. By performing the analysis for each variable separately, the program flow graph can be modified in a manner that is unique for each variable. This transformation leads to the development of an analysis technique that is both linear in the size of the program and immune to the adverse effects that arise from flow graph irreducibility or deep loop nesting. The class of problems amenable to this technique is restrictive but does include problems as complex as the Live Analysis and Reaching Definitions problems. The output of the latter problem can then be used to build Use-Def chains. In the incremental form of this algorithm, the solution can be updated for most changes by visiting only the part of the program flow graph in which the solution actually changes. For other types of changes, a larger area of the program flow graph must be visited, but this area is typically smaller than the entire program flow graph