Dynamic Points-To Sets: A Comparison
with Static Analyses and Potential Applications in Program
Understanding and Optimization
In the proceedings of the
Workshop on Program Analysis for Software Tools and Engineering
(PASTE'01), June 2001, pp. 66 - 72.
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 infrastruc ture 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 feedbackdirected
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.