Modular Pointer Analysis

Experiments with algorithms for flow-insensitive, context-insensitive pointer analysis developed by Lars Andersen and Bjarne Steensgaard indicate that neither is likely to scale up well enough to be applied to large programs (hundreds of thousands of lines). Steensgaard's algorithm produces results that are too conservative (i.e., the points-to sets tend to be quite large, which in turn leads to overly conservative results in subsequent analyses that make use of the points-to information). While Andersen's algorithm produces much better results, it seems to be limited by its space requirements.

In this talk, we explore techniques for modular pointer analysis: analyzing small pieces of the program (e.g., individual functions or files), then combining the results of the individual analyses. We expect a modular approach to have two important benefits:

1. It will permit algorithms like Andersen's to be applied to much larger programs than would otherwise be possible.
2. It will provide a way to summarize the effects (on pointers) of auxiliary files such as libraries. This means that programs that use libraries can be analyzed in the context of this summary information, rather than requiring source code for the library functions.