An incremental algorithm for software analysis

Abstract

In programming environments aimed at “industrial strength” software development, there is a need for software tools which facilitate both design and maintenance. These tools should encourage experimentation with different system configurations which enable designers to a priori estimate the associated system complexity and judge the ease of accommodating enhancements. Maintainers should be able to check straightforwardly the ramifications of system changes due to enhancements or “bug fixes”. With interprocedural data flow information about the definition and use of global variables and parameters in a software system, tools can be built to perform these tasks. For large, complex systems, efficient methods for interprocedural analysis are necessarily incremental, as a software system is a dynamically evolving entity. Incremental algorithms update current information about a system in response to a change rather than re-calculating the information by re-analyzing the entire system. This paper reports our development of a general purpose incremental data flow analysis algorithm, which is applicable to both intraprocedural and interprocedural domains. It is based on interval analysis, a technique whose observed performance is linear for most programs; under reasonable assumptions about program flow graphs this linearity can be verified [20].