The Effects of the Precision of Pointer Analysis

Marc Shapiro and Susan Horwitz
University of Wisconsin

In order to analyze programs that manipulate pointers, it is necessary to have safe information about what each pointer might point to. There are many algorithms that can be used to determine this information, with varying degrees of accuracy. However, there has been very little previous work that addresses how much the relative accuracies of different pointer-analysis algorithms affect ``transitive'' results: the results of a subsequent analysis.

We have carried out a number of experiments with flow-insensitive, context-insensitive pointer analyses to address the following questions:

We found that using a more precise pointer analysis does in general lead to more precise transitive results. However, the magnitude of the payoff in precision depends on the particular use of the points-to information. We also found that direct effects are good predictors of transitive effects, and that increased precision in points-to information not only causes a subsequent analysis to produce more precise results, it also causes the subsequent analysis to run faster.

(Click here to access the paper.)