Efficient Field-Sensitive Pointer Analysis for C

Author(s). David J. Pearce, Paul H.J. Kelly and Chris Hankin.

Venue. In ACM Transactions on Programming Languages and Systems (TOPLAS), 30 (1), 2007. ©ACM Press

Abstract. The subject of this paper is flow- and context-insensitive pointer analysis. We present a novel approach for precisely modelling struct variables and indirect function calls. Our method em- phasises efficiency and simplicity and is based on a simple language of set constraints. We obtain an O(v^4) bound on the time needed to solve a set of constraints from this language, where v is the number of constraint variables. This gives, for the first time, some insight into the hardness of performing field-sensitive pointer analysis of C. Furthermore, we experimentally evaluate the time versus precision trade-off for our method by comparing against the field-insensitive equivalent. Our benchmark suite consists of 11 common C programs ranging in size from 15,000 to 200,000 lines of code. Our results indicate the field-sensitive analysis is more expensive to compute, but yields significantly better precision. In addition, our technique has been integrated into the latest release (version 4.1) of the GNU Compiler GCC. Finally, we identify several previously unknown issues with an alternative and less precise approach to modelling struct variables, known as field-based analysis.

Notes. This algorithm is currently used in the GNU C Compiler (GCC) and in the godoc tool for Go. An implementation of the algorithm in C++ is availale here. You can also find discussion of the GCC implementation in this paper: Structure Aliasing in GCC by Dan Berlin, in Proceedings of the GCC Developers Summit, 2005 PDF.