AbstractData-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.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).