Incremental analysis means making efficient use of the results of analyzing an original program when a modified program is analyzed. This is likely to be of interest to anyone concerned with modifying software while preserving or improving its efficiency.

Three key contributions are presented in this paper: an algorithm that identifies precisely those previous results that have become invalid following program modification, leaving as many prior results as possible available for a new analysis; an incremental resource usage analysis that, given some cost metrics and an incremental analysis, computes the resource usage of a new program; and a new form of cost summary that reconstructs only the elements of cost functions affected by changes to the software.

The analysis algorithm acts on programs that are represented using a rule-based intermediate language. Java and other Java-like programming languages can be compiled into this intermediate representation. The rule-based intermediate language is amenable to abstract interpretation, which forms the basis for program analysis.

Analysis delivers calling and answer patterns, called the method summary, for each method of interest and each domain of interest. Given a change to a program and analysis results for the original, unmodified program, method summaries provide the basis for constructing new analysis results for all domains. Method summaries also provide the basis for incremental cost (resource usage) analysis.

Experimental investigation shows that incremental analysis is significantly faster than analysis performed without reference to previous results. A search for a situation where incremental analysis might be expected to perform worse found that incremental analysis performed as well as, or marginally better than, analysis from scratch.

Overall, the paper provides an interesting approach to program analysis that is likely to be applicable to software testing as well as to cost estimation.