Next: Introduction
Efficient Context-Sensitive Pointer Analysis for C Programs
Robert P. Wilson and Monica S. Lam
Computer Systems Laboratory
Stanford University, CA 94305
http://suif.stanford.edu
{bwilson,lam}@cs.stanford.edu
This research was supported in part by ARPA contract DABT63-94-C-0054,
an NSF Young Investigator award, and an Intel Foundation graduate
fellowship.
In Proceedings of the ACM SIGPLAN'95 Conference on
Programming Language Design and Implementation, La Jolla, CA, June
18-21, 1995, pp. 1-12.
Copyright (C) 1995 by ACM, Inc.
Abstract:
This paper proposes an efficient technique for context-sensitive
pointer analysis that is applicable to real C programs. For
efficiency, we summarize the effects of procedures using partial
transfer functions. A partial transfer function (PTF) describes the
behavior of a procedure assuming that certain alias relationships hold
when it is called. We can reuse a PTF in many calling contexts as
long as the aliases among the inputs to the procedure are the same.
Our empirical results demonstrate that this technique is
successful-a single PTF per procedure is usually sufficient to
obtain completely context-sensitive results. Because many C programs
use features such as type casts and pointer arithmetic to circumvent
the high-level type system, our algorithm is based on a low-level
representation of memory locations that safely handles all the
features of C. We have implemented our algorithm in the SUIF
compiler system and we show that it runs efficiently for a set of
C benchmarks.
Next: Introduction