WHY INCREMENTAL ANALYSIS?

Throughout its life cycle, an application changes frequently - components are added, removed, and modified - and its call graph changes concurrently. The call graph is central to interprocedural analysis, the cornerstone of many software development tools for object-oriented languages. When an application's call graph is modified, vital interprocedurally gathered information can become invalid and obsolete. The construction of contextual def-use associations (cdus) relies on a precise call graph; to update cdus following a program edit, the underlying call graph must also be updated. Starting from scratch is a highly undesirable approach; there is a susbstantial cost in exhaustively generating a call graph with the appropriate level of precision. Incremental algorithms aim to reduce this cost and can also easily indicate potentially affected program regions in which to begin incremental reanalysis of data flow information.

The goal of incremental algorithms is to reuse results from previous analyses to update the desired information, performing only an amount of work proportional to the impact of the original change and avoiding redundant reanalysis. Incremental reanalysis is especially effective in situations in which small-impact changes are applied to a large system of applications; in these cases, exhaustive recomputation would involve significant redundant analysis. In other words, complete reanalysis of a target program in response to a minor change - like deleting a call site - is simply a waste of effort. In this case and in many others, the incremental approach employs a more efficient and effective strategy.

INCREMENTAL CALL GRAPH REANALYSIS
AND DELETING A CALL SITE

As with many other incremental algorithms, the incremental call graph reconstruction algorithm requires that an initial exhuastive analysis be performed prior to reanalysis. Another precondition is that the information be as precise and correct as desired before changes are made to the program. Thus, before invoking Delete_Call_Site, we assume that a precise call graph has been exhaustively computed for the program in question.

Call graphs for object-oriented programs are affected by any edit that directly changes the caller-callee relationships between methods or modifies the type information at call sites. Deleting a call site is one example of an edit that directly changes calling relationships. Professor Souter's Delete_Call_Site algorithm incrementally handles the call graph updates required in response to the deletion of a call site. Existing type information stored in the network of templates is modified only when necessary and left unchanged otherwise.

The procedure involves an incremental version of Agesen's Cartesian product algorithm that exploits a key property of the template call graph to maintain precision after program edits. At any given template node of the template call graph - a directed graph - every incoming edge carries exactly the same type information. When an edge representing a deleted call site is removed, either the sink node (the "destination" of the edge) becomes unreachable, or the remaining incoming edges carry the same type information into the node as they did before the edit. The template itself is not modified or deleted, even if it becomes unreachable, as it may be needed when updates are propagated throughout the call graph. In any case, no update is necessary for the subgraph of the sink node to maintain precision in the context of the modified call graph.