William Landi
Barbara G. Ryder
Skip Abstract Section
Abstract
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.
- Ban79 J. Banning. An efficient way to find the side effects of procedure calls and the aliases of variables. In Confer. ence Record of the Sixth Ann~tal A CM Symposium on Principles of Programming Languages, pages 29-41, January 19 79. Google Scholar
Digital Library
- Bar78 J.M. Barth. A practical interprocedural data flow analysis algorithm. Communications of the A CM, 21(9):724-736, 1978. Google ScholarDigital Library
- Cal88 D. Callahan. The program summary graph and flowsensitive interprocedttral data flow analysis. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, pages 47-56, June 1988. Google ScholarDigital Library
- CK89 K. Cooper and K. Kennedy. Fast interprocedural alias analysis. In Conference Record of the $izteenth Annual A CM Symposium on Principles of Programming Languages, pages 49-59, January 1989. Google ScholarDigital Library
- Coo85 K. Cooper. Analyzing aliases of reference formal parameters. In Conference Record of the Twelfth Annual A CM Symposium on Principles of Programming Languages, pages 281-290, January 1985. Google ScholarDigital Library
- Coo89 B.G. Cooper. Ambitious data flow analysis of procedural programs. Master's thesis, University of Minnesota, May 1989.Google Scholar
- Cou86 D.S. Content. Retargetable high-level alias analysis. In Conference Record of the Thirteenth Annual A CM Symposium on Principles of Programming Languages, pages 110-118, January 1986. Google ScholarDigital Library
- CR82 A. Chow and A. Rudmik. The design of a data tlow analyzer. In Proceedings of the A CM SIGPLAN Sympo. slum on Compiler Construction, pages 106-113, June 1982. Google ScholarDigital Library
- CWZ90 D.R. Chase, M. Wegman, and F. K. Zadeck. Analysis of pointers and structures. In Proceedings of the SIC- PLAN '90 Conference on Programming Language De. sign and Implementation, pages 296-310, June 1990. SiGPLAN Notices, Vol 25, No 6. Google ScholarDigital Library
- Deu90 A. Deutsch. On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications. In Conference Record of the $e~en. teenth Annual A CM Symposium on Principles of Programming Languages, pages 157-168, January 1990. Google ScholarDigital Library
- Deu92 Alain Deutsch. A storeless mode of aliasing and its abstractions using finite representation of right-regular equivalence relations, in Proceedings of the IEEE 1992 Conference on Computer Languages, April 1992.Google ScholarCross Ref
- Gua88 C.A. Guarna. A technique for analyzing pointer and structure references in parallel restructuring compilers. In Proceedings of the International Conference on Parallel Processing, pages 212-220, 1988.Google Scholar
- HA90 W.L. Harrison III and Z. Ammarguellat. Parcel and miprac: Parallelizers for symbolic and numeric programs. In International Workshop on Compilers for Parallel Computers, December 1990.Google Scholar
- HN89 L.J. Hendren and A. Nicolau. Parallelizing programs with recursive data structures. In Proceedings of the 1989 International Conference on Parallel Processing, pages 49-56, August 1989.Google Scholar
- HPR89 S. Horwitz, P. Pfeiffer, and T. Reps. Dependence analysis for pointer variables. In Proceedings of the A CM SIGPLAN Symposium on Compiler Construe. tion, pages 28-40, June 1989. Google ScholarDigital Library
- JM79 N. Jones and S. Muchnlck. Flow analysis and op~imlzation of lisp-like structures. In S. Muchnick and N. Jones, editors, Program Flow Analysis: Theory and Applications, pages 102-131. Prentice Hall, 1979.Google Scholar
- JM82 N.D. Jones and S. S. Muchnick. A flexible approach to interprocedural data/low analysis and programs with recursive data structures. In Conference Record of the Ninth Annual A CM Symposium on Principles of Programming Languages, pages 66-74, January 1982. Google ScholarDigital Library
- KS86 H. Korth and A. Silberschatz. Database System Concepts. McGraw-Hill, New York, NY, 1986. Google ScholarDigital Library
- Lan92 W. Landi. Interprocedural Aliasing in the Presence of Pointers. PhD thesis, Rutgers University, January 1992. LCSR-TH-174. Google ScholarDigital Library
- LH88 J.R. Larus and P. N. Hilfinger. Detecting conflicts between structure accesses. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, pages 21-34, July 1988. SIGPLAN NOTICES, Vol. 23, No. 7. Google ScholarDigital Library
- LR91 W. Landl and B. G. Ryder. Pointer-induced aliaslng: A problem classlilcation. In Conference Record of the Eighteenth Annual A CM Symposium on Principles of Programming Languages, pages 93-103, January 1991. Google ScholarDigital Library
- Mye81 E.M. Myers. A precise interprocedural data flow al. gorithxqa. In Conference Record of the Eighth Annual A CM Symposium on Principles of Programming Languages, pages 219-230, January 1981. Google ScholarDigital Library
- NPD87 A. Neirynck, P. Panangaden, and A. Demers. Computation of aliases and support sets. In Conference Record of the Fourteenth Annual A CM Symposium on Principles of Programming Languages, pages 274-283, January 1987. Google ScholarDigital Library
- PRL91 H.D. Pande, B. G. Ryder, and W. Landi. }{nterprocedural def-use associations in c programs, in Proceedings of the Fifth Testing, Analysis, and Verification Symposium, October 1991. Google ScholarDigital Library
- RP88 B.G. Ryder and H. Pande. The interproeedural structure of c programs: An empirical study. Laboratory for Computer Science Research Technical Report LCSR-TR-99, Department of Computer Science, Rutgers University, February 1988.Google Scholar
- Ryd89 B. G. Ryder. Ismm: Incremental softwaxe maintenance manager. In Proceedings of the IEEE Computer Society Conference on Software Maintenance, pages 142-164~ October 1989.Google ScholarCross Ref
- Wei80 W.E. Weihl. Interprocedural data flow analysis in the presence of pointers, procedure variables and label variables. In Conference Record of the Seventh Annual A CM Symposium on Principles of Programming Languages, pages 83-94, January 1980. Google ScholarDigital Library
Index Terms
- A safe approximate algorithm for interprocedural aliasing
Recommendations
Interprocedural pointer alias analysis
We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
The undecidability of aliasing
Alias analysis is a prerequisite for performing most of the common program analyses such as reaching-definitions analysis or live-variables analysis. Landi [1992] recently established that it is impossible to compute statically precise alias information—...
A safe approximate algorithm for interprocedural pointer aliasing
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A SelectionDuring 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 ...
Comments