A safe approximate algorithm for interprocedural aliasing
William A. Landi, Barbara G. Ryder · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1992
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 ρ-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 336 works. doi:10.1145/143095.143137 Open-access PDF
Authors
References
- Database System Concepts
- 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
- A flexible approach to interprocedural data flow analysis and programs with recursive data structures
- Detecting conflicts between structure accesses
- Dependence analysis for pointer variables
- Parallelizing programs with recursive data structures