Incremental analysis for flow- and context-sensitive data-flow problems

Data-flow analysis is widely used in extracting from source programs useful information for program optimization, program under- standing, program restructuring, and testing. When a quality solution is demanded, the consideration of the control flow information and calling contexts in the data-flow analysis is inevitable, but it usually involves extensive computation. When the data-flow information is used in an application in which users may interactively change the source program and check program properties involving the data-flow informa- tion, then keeping the information consistent with the current state of the program and performing the update efficiently will become very important. Incremental data-flow analysis seeks to update data-flow information after source code changes without recomputation from scratch, based on the knowledge of the former solution and the changes. The data-flow problem we are targeting is the interprocedural modification side effect (MOD) problem for C. Landi and Ryder proposed a decomposition for the problem, which consists of two major sub- problems: the pointer aliasing problem computes the set of aliases at each program point, and the PMOD problem computes the interprocedural side effect of a procedure. Based on the problem decomposition, we proposed incremental algorithms for these two sub-problems respectively to handle some atomic changes. Then, for the PMOD problem, we conducted a feasibility study of our incremental algorithms, which revealed, on average, a small source change, such as deletion of a single-line statement, causes a change of a small scale (about 3.5%) to the program representation, and affects only 4% of the old PMOD solution. This indicates a great opportunity for the incremental analysis. As for the pointer aliasing problem, we empirically studied the effectiveness of our prototyped incremental algorithms in terms of performance and precision. In handling a small source change, our incremental algorithm outperforms the exhaustive algorithm by a 6-fold speedup. In addition, our incremental algorithms compute the same solution as the exhaustive algorithm in 74% of the tests, while simply restarting iteration without reinitialization does so in less than 10% of the tests. Generalization of the approach to handle other flow- and context-sensitive data-flow problems as well as processing multiple changes together is also discussed.Technical report DCS-TR-393Ph.D