Efficient field-sensitive pointer analysis of C
Open Access
- 1 November 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 30 (1) , 4
Abstract
The subject of this article is flow- and context-insensitive pointer analysis. We present a novel approach for precisely modelling struct variables and indirect function calls. Our method emphasises 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.Keywords
This publication has 78 references indexed in Scilit:
- A dynamic topological sort algorithm for directed acyclic graphsACM Journal of Experimental Algorithmics, 2007
- Which pointer analysis should I use?ACM SIGSOFT Software Engineering Notes, 2000
- Interprocedural pointer alias analysisACM Transactions on Programming Languages and Systems, 1999
- Propagating differences: An efficient new fixpoint algorithm for distributive constraint systems1998
- The model checker SPINIEEE Transactions on Software Engineering, 1997
- The undecidability of aliasingACM Transactions on Programming Languages and Systems, 1994
- On finding the strongly connected components in a directed graphInformation Processing Letters, 1994
- An interval-based approach to exhaustive and incremental interprocedural data-flow analysisACM Transactions on Programming Languages and Systems, 1990
- Advanced compiler optimizations for supercomputersCommunications of the ACM, 1986
- Dynamic cycle detectionInformation Processing Letters, 1983