Dynamic Points-To Sets: A Comparison with Static Analyses and Potential Applications in Program Understanding and Optimization

M. Mock, M. Das, C. Chambers, and S. Eggers

Department of Computer Science and Engineering
University of Washington
and Microsoft Research (M. Das)

In the proceedings of the ACM SIGPLAN SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01), June 2001, pp. 66 - 72.  

ACM's Copyright Policy.

`
  • PostScript (428kB)
  • Compressed PostScript (compress, 92kB)
  • Compressed PostScript (gzip, 66kB)
  • PDF (85kB)
    		•  To save the paper to a file using Netscape Navigator, right click on one of the links at the left and select "Save Link As..."

    Abstract

    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.


    Last updated January 16, 2002.
    Markus Mock (mock@cs.washington.edu)