Unification-based pointer analysis with directional assignments
Manuvir Das · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 2000
This paper describes a new algorithm for flow and context insensitive pointer analysis of C programs. Our studies show that the most common use of pointers in C programs is in passing the addresses of composite objects or updateable values as arguments to procedures. Therefore, we have designed a low-cost algorithm that handles this common case accurately. In terms of both precision and running time, this algorithm lies between Steensgaard's algorithm, which treats assignments bi-directionally using unification, and Andersen's algorithm, which treats assignments directionally using subtyping. Our “one level flow” algorithm uses a restricted form of subtyping to avoid unification of symbols at the top levels of pointer chains in the points-to graph, while using unification elsewhere in the graph. The method scales easily to large programs. For instance, we are able to analyze a 1.4 MLOC (million lines of code) program in two minutes, using less than 200MB of memory. At the same time, the precision of our algorithm is very close to that of Andersen's algorithm. On all of the integer benchmark programs from SPEC95, the one level flow algorithm and Andersen's algorithm produce either identical or essentially identical points-to information. Therefore, we claim that our algorithm provides a method for obtaining precise flow-insensitive points-to information for large C programs.
Cited by 304 works. doi:10.1145/349299.349309 Open-access PDF
Authors
References
- Points-to analysis in almost linear time
- Efficient context-sensitive pointer analysis for C programs
- Context-sensitive interprocedural points-to analysis in the presence of function pointers
- Efficient context-sensitive pointer analysis for C programs
- A safe approximate algorithm for interprocedural aliasing
- Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects
- A safe approximate algorithm for interprocedural pointer aliasing
- Parametric shape analysis via 3-valued logic
- Fast and accurate flow-insensitive points-to analysis
- Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C