Incremental Resource Usage Analysis

The aim of incremental global analysis is, given a program, its anal-ysis results and a series of changes to the program, to obtain the new analysis results as efficiently as possible and, ideally, without having to (re-)analyze fragments of code which are not affected by the changes. Incremental analysis can significantly reduce both the time and the memory requirements of analysis. This paper presents an incremental resource usage analysis for a sequential Java-like language. Our main contributions are (1) a multi-domain incre-mental fixed-point algorithm which can be used by all global pre-analyses required to infer the cost (including class, sharing, cyclic-ity, constancy, and size analyses), and which takes care of propagat-ing dependencies among such domains, and (2) a novel form of cost summaries which allows us to incrementally reconstruct only those components of cost functions affected by the change. Experimen-tal results in the COSTA system show that the proposed incremental analysis performs very efficiently in practice