Dynamic points-to sets

摘要

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 existing scalable 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). As an example, we were able to obtain a factor of 6 speedup on a frequently executed routine from m88ksim.