A safe approximate algorithm for interprocedural pointer aliasing
William A. Landi, Barbara G. Ryder · ACM SIGPLAN Notices · 2004
During execution, when two or more names exist for the same location at some program point, we call them aliases. In a language which allows arbitrary pointers, the problem of determining aliases at a program point is P -space-hard [Lan92]. We present an algorithm for the Conditional May Alias problem, which can be used to safely approximate Interprocedural May Alias in the presence of pointers. This algorithm is as precise as possible in the worst case and has been implemented in a prototype analysis tool for C programs. Preliminary speed and precision results are presented.
Cited by 279 works. doi:10.1145/989393.989440
Authors
References
- Abstract interpretation
- A unified approach to global program optimization
- Database System Concepts
- Points-to analysis in almost linear time
- A practical interprocedural data flow analysis algorithm
- An efficient way to find the side effects of procedure calls and the aliases of variables
- A precise inter-procedural data flow algorithm
- Analysis of pointers and structures
- Flow analysis and optimization of LISP-like structures
- Efficient context-sensitive pointer analysis for C programs