Incremental analysis of constraint logic programs

Global analyzers traditionally read and analyze the entire program at once, in a nonincremental way. However, there are many situations which are not well suited to this simple model and which instead require reanalysis of ce rtain parts of a program which has already been analyzed. In these cases, i t appears inefficient to perform the analysis of the program again from scr atch, as needs to be done with current systems. We describe how the fixed-p oint algorithms used in current generic analysis engines for (constraint) l ogic programming languages can be extended to support incremental analysis. The possible changes to a program are classified into three types: additio n, deletion, and arbitrary change. For each one of these, we provide one or more algorithms for identifying the parts of the analysis that must be rec omputed and for performing the actual recomputation. The potential benefits and drawbacks of these algorithms are discussed. Finally, we present some experimental results obtained with an implementation of the algorithms in t he PLAI generic abstract interpretation framework. The results show signifi cant benefits when using the proposed incremental analysis algorithms.