Next: Introduction

Efficient Context-Sensitive Pointer Analysis for C Programs

Robert P. Wilson and Monica S. Lam
Computer Systems Laboratory
Stanford University, CA 94305

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.


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

Bob Wilson