Dynamic PointsTo Sets: A Comparison with Static Analyses and Potential Applications in Program Understanding and Optimization

In this paper, we compare the behavior of pointers in C programs, as approximated by static pointer analysis algorithms, with the actual behavior of pointers when these programs are run. In order to perform this comparison, we have implemented several well known pointer analysis algorithms, and we have built an instrumentation infrastructure for tracking pointer values during program execution. Our experiments show that for a number of programs from the Spec95 and Spec2000 benchmark suites, the pointer information produced by static pointer analyses is far worse than the actual behavior observed at run-time. These results have two implications: First, a tool like ours can be used to supplement static program understanding tools in situations where the static pointer information is too coarse to be usable. Second, a feedback-directed compiler can use profile data on pointer values to improve program performance, by ignoring aliases that do not arise at run time (and inserting appropriate run-time checks to ensure safety). For example, we were able to obtain a factor of 6 speedup on a frequently executed routine from m88ksim. 1