Fast interprocedual alias analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast interprocedual alias analysis

Full text

Pdf (1.01 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Austin, Texas, United States

Pages: 49 - 59

Year of Publication: 1989

ISBN:0-89791-294-2

Authors

K. D. Cooper	Department of Computer Science, Rice University, Houston, Texas
K. Kennedy	Department of Computer Science, Rice University, Houston, Texas

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 36, Citation Count: 38

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/75277.75282 What is a DOI?

ABSTRACT

We present a new algorithm for computing interprocedural aliases due to passing parameters by reference. This algorithm runs in O(N2+NE) time and, when combined with algorithms for alias-free, flow-insensitive data-flow problems, yields algorithms for solution of the general flow-insensitive problems that also run in O(N2+NE) time.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Alle 74	F.E. Allen, "Interprocedural data flow analysis", Proc. of the 197~ IFIPS Congress, 1974.
	Bann 79	John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
	Bart 78	Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
	Burk 84	M. Burke, "An interval analysis approach toward interprocedural data flow", Report RC 10640, IBM T.J. Watson Research Center, Yorktown Heights, N.Y., July, 1984.
	BuCy 86	Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
	Call 88	D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
	CCKT 86	David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.21 n.7, p.152-161, July 1986
	CaKe 87	D. Callahan , K. Kennedy, Analysis of interprocedural side effects in a parallel programming environment, Proceedings of the 1st International Conference on Supercomputing, p.138-171, March 1988, Athens, Greece
	CaRy 86	Martin Carroll , Barbara G Ryder, An incremental algorithm for software analysis, Proceedings of the second ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.171-179, December 09-11, 1986, Palo Alto, California, United States
	Coop 85	Keith D. Cooper, Analyzing aliases of reference formal parameters, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.281-290, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318658]
	CoKe 84	Keith D. Cooper , Ken Kennedy, Efficient computation of flow insensitive interprocedural summary information, ACM SIGPLAN Notices, v.19 n.6, p.247-258, June 1984
	CoKe 87	Keith D. Cooper , Ken Kennedy, Efficient computation of flow-insensitive interprocedural summary information—a correction, ACM SIGPLAN Notices, v.23 n.4, p.35-42, April, 1988 [doi>10.1145/44326.44329]
	CoKe 88	K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.57-66, June 20-24, 1988, Atlanta, Georgia, United States
	HoRB 88	S. Horwitz, T. Reps and D Binkley, "Interprocedural slicing using dependence graphs", Proc. SIGPLAN 88 Conference on Programming Language Design and Implementation, SIGPLAN Notices 23(7), July 1988.
	Myer 80	E. Myers, "A precise a~d efficient ulgorithm for determining existential summary data flow information", Technical Report CU-CS-175-80, Department of Computer Science, University of Colorado, Masch, 1980.
	Rose 79	Barry K. Rosen, Data Flow Analysis for Procedural Languages, Journal of the ACM (JACM), v.26 n.2, p.322-344, April 1979 [doi>10.1145/322123.322135]
	Spil 71	T.C. Spillma~, "Exposing side-effects in a PL/I optimizing compiler", Proc. of the 1971 IFIPS Gongrees, 1971.
	Torc 85	Linda Marie Torczon, Compilation dependences in an ambitious optimizing compiler (interprocedural, recompilation), 1985

CITED BY 38

	Hemant D. Pande , William Landi, Interprocedural Def-Use associations in C programs, Proceedings of the symposium on Testing, analysis, and verification, p.139-153, October 08-10, 1991, Victoria, British Columbia, Canada
	Pedro V. Artigas , Manish Gupta , Samuel P. Midkiff , José E. Moreira, Automatic loop transformations and parallelization for Java, Proceedings of the 14th international conference on Supercomputing, p.1-10, May 08-11, 2000, Santa Fe, New Mexico, United States
	Thomas J. Marlowe , Barbara G. Ryder, An efficient hybrid algorithm for incremental data flow analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-196, December 1989, San Francisco, California, United States
	Yong-Fong Lee , Barbara G. Ryder, A comprehensive approach to parallel data flow analysis, Proceedings of the 6th international conference on Supercomputing, p.236-247, July 19-24, 1992, Washington, D. C., United States
	Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, ACM SIGPLAN Notices, v.29 n.6, p.242-256, June 1994
	Keith D. Cooper , Mary W. Hall , Linda Torczon, Unexpected side effects of inline substitution: a case study, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.22-32, March 1992
	Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States
	Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Type-based alias analysis, ACM SIGPLAN Notices, v.33 n.5, p.106-117, May 1998
	Mary W. Hall , Ken Kennedy, Efficient call graph analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.227-242, Sept. 1992
	Ben Heggy , Mary Lou Soffa, Architectural support for register allocation in the presence of aliasing, Proceedings of the 1990 conference on Supercomputing, p.730-739, October 1990, New York, New York, United States
	William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, ACM SIGPLAN Notices, v.27 n.7, p.235-248, July 1992
	Michael Burke , Linda Torczon, Interprocedural optimization: eliminating unnecessary recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.3, p.367-399, July 1993
	David Bernstein , Doron Cohen , Dror E. Maydan, Dynamic memory disambiguation for array references, Proceedings of the 27th annual international symposium on Microarchitecture, p.105-111, November 30-December 02, 1994, San Jose, California, United States
	G. A. Venkatesh, Experimental results from dynamic slicing of C programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.197-216, March 1995
	Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990
	Susan Horwitz , Thomas Reps , Mooly Sagiv, Demand interprocedural dataflow analysis, ACM SIGSOFT Software Engineering Notes, v.20 n.4, p.104-115, Oct. 1995
	David Melski , Thomas Reps, Interconvertbility of set constraints and context-free language reachability, ACM SIGPLAN Notices, v.32 n.12, p.74-89, Dec. 1997
	Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States
	Michael Burke , Jong-Deok Choi, Precise and efficient integration of interprocedural alias information into data-flow analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.14-21, March 1992
	David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.25 n.6, p.296-310, Jun. 1990
	David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994
	István Forgács, Double iterative framework for flow-sensitive interprocedural data flow analysis, ACM Transactions on Software Engineering and Methodology (TOSEM), v.3 n.1, p.29-55, Jan. 1994
	H. D. Pande , W. A. Landi , B. G. Ryder, Interprocedural Def-Use Associations for C Systems with Single Level Pointers, IEEE Transactions on Software Engineering, v.20 n.5, p.385-403, May 1994
	Chi-Keung Luk, Memory disambiguation for general-purpose applications, Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p.43, November 07-09, 1995, Toronto, Ontario, Canada
	Saumya Debray , Robert Muth , Matthew Weippert, Alias analysis of executable code, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-24, January 19-21, 1998, San Diego, California, United States
	Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Using types to analyze and optimize object-oriented programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.30-72, Jan. 2001
	William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States
	Mary Jean Harrold , Brian Malloy, A Unified Interprocedural Program Representation for a Maintenance Environment, IEEE Transactions on Software Engineering, v.19 n.6, p.584-593, June 1993
	David Chase , Mark Wegman , F. Ken Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Keith D. Cooper , Ken Kennedy, Interprocedural side-effect analysis in linear time, ACM SIGPLAN Notices, v.39 n.4, April 2004
	William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural pointer aliasing, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Ramakrishnan Venkitaraman , Gopal Gupta, Static program analysis of embedded executable assembly code, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA
	Jongwook Woo , Jean-Luc Gaudiot , Andrew L. Wendelborn, Alias analysis in Java with reference-set representation for high-performance computing, International Journal of Parallel Programming, v.32 n.1, p.39-76, February 2004
	Thomas Reps, Undecidability of context-sensitive data-independence analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.1, p.162-186, Jan. 2000
	Hemant D. Pande , Barbara G. Ryder, Static type determination for C++, Proceedings of the 6th conference on USENIX Sixth C++ Technical Conference, p.5-5, April 11-14, 1994, Cambridge, MA
	James Giles, Aliasing, syntax, and string handling in Fortran and in C, ACM SIGPLAN Fortran Forum, v.15 n.2, p.12-13, Aug. 1996
	Thomas J. Marlowe , William G. Landi , Barbara G. Ryder , Jong-Deok Choi , Michael G. Burke , Paul Carini, Pointer-induced aliasing: a clarification, ACM SIGPLAN Notices, v.28 n.9, p.67-70, Sept. 1993
	Zoran Budimlić , Mackale Joyner , Ken Kennedy, Improving Compilation of Java Scientific Applications, International Journal of High Performance Computing Applications, v.21 n.3, p.251-265, August 2007