An approach to incremental and modular context-sensitive analysis

Abstract

The flexibility of dynamic languages often comes at the cost of having to perform at run time a number of additional tasks when compared to static languages. This includes for example detecting property violations in calls to built-ins and libraries (as well as in user code) or performing dynamic specialization and other optimizations. Analyzing programs statically can help reduce the amount and cost of these dynamic tasks. However, performing global analysis can in turn be costly at compile time for large code bases, and this can be a special burden if it is performed at each development iteration. On the other hand, changes between development iterations are often isolated within a few components, and analysis cost can be reduced by reusing the results of previous analyses. This has been achieved to date through modular analysis, which reduces memory consumption and often localizes the computation during reanalysis mainly to the modules affected by changes, and through global incremental fixpoint analysis techniques, that achieve cost reductions at finer levels of granularity, such as changes in program lines, but which are not directly applicable to modular programs. This paper describes, implements, and evaluates a context- sensitive fixpoint analysis algorithm aimed at achieving both inter-modular (coarse-grain) and intra-modular (fine-grain) incrementality, solving the problems related to propagation of the fine-grain change information and effects across module boundaries, for additions and deletions in multiple modules. The implementation and evaluation of our algorithm shows encouraging results: the expected advantages of fine- grain incremental analysis carry over to the modular analysis context. Furthermore, the fine-grained propagation of analysis information of our algorithm improves performance with respect to traditional modular analysis even when analyzing from scratch.