A practical interprocedural data flow analysis algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A practical interprocedural data flow analysis algorithm

Full text

Pdf (1.31 MB)

Source

Communications of the ACM archive
Volume 21 , Issue 9 (September 1978) table of contents

Pages: 724 - 736

Year of Publication: 1978

ISSN:0001-0782

Author

Jeffrey M. Barth

Stanford Univ., Stanford, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 72, Citation Count: 61

Additional Information:

abstract references cited by index terms

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/359588.359596 What is a DOI?

ABSTRACT

A new interprocedural data flow analysis algorithm is presented and analyzed. The algorithm associates with each procedure in a program information about which variables may be modified, which may be used, and which are possibly preserved by a call on the procedure, and all of its subcalls. The algorithm is sufficiently powerful to be used on recursive programs and to deal with the sharing of variables which arises through reference parameters. The algorithm is unique in that it can compute all of this information in a single pass, not requiring a prepass to compute calling relationships or sharing patterns. The algorithm is asymptotically optimal in time complexity. It has been implemented and is practical even on programs which are quite large.

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.

	1	Allen, F.E. Interprocedural data flow analysis. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 398--402.
	2	Allen, F.E., and Schwartz, J.T. Determining the data relationships in a collection of procedures (unpublished detailed summary).
	3	Ammann, U. Compiler for PASCAL 6000--3.4. ETH, Institut fiir Informatik, Zurich, Switzerland, 1974.
	4	Jeffrey M. Barth, An interprocedural data flow analysis algorithm, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.119-131, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512962]
	5	Jeffrey Michael Barth, A practical interprocedural data flow analysis algorithm and its applications., 1977
	6	Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
	7	Hecht, M.S., and Shaffer, J.B. Ideas on the design of a "quad improver" for SIMPL-T, Pt. I: Overview and intersegment analysis. Comptr. Sci. Tech, Rcp. TR-405, U. of Maryland, CoUege Park, Md., Aug. 1975. This report is superceded by {8}, but contains some information not in the latter paper.
	8	Hecht, M.S., and Shaffer, J.B. A modest quad improver for SIMPL-T, Dept. Comptr. Sci., U. of Maryland, CoUegc Park, Md., April 1977.
	9	Hecht, M.S., and UUman, J.D. A simple algorithm for global flow problems. SIAM J. Comptng. 4, 4 (Dec. 1975), 519-532.
	10	Kathleen Jensen , Niklaus Wirth, Pascal-User Manual and Report, Springer-Verlag New York, Inc., Secaucus, NJ, 1975
	11	Lomet, D.B. Data flow analysis in the presence of procedure calls. Res. Rep. RC5728 IBM T.J. Watson Res. Ctr., Yorktown Heights, N.Y., Nov. 1975.
	12	J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
	13	Rosen, B.K. Data flow analysis for recursive PL/I programs. Res, Rep. RC5211, IBM T.J. Watson Res. Ctr., Yorktown Heights, N.Y., Jan. 1975. This report is superceded by {16}.
	14	Rosen, B.K. High level data flow analysis, Pt. 1 (classical structured programming). Res. Rep. RC5598, IBM, T.J. Watson Res. Ctr., Yorktown Heights, N.Y., Aug. 1975.
	15	Rosen, B.K. High level data flow analysis, Pt. 2 (escapes and jumps). Res. Rep. RC5744, IBM T.J. Watson Res. Ctr., Yorktown Heights, N.Y. Dec. 1975.
	16	Rosen, B.K. Data flow analysis for procedural languages. T.J. Watson Res. Ctr., Yorktown Heights, N.Y., 1976.
	17	Spillman, T.C. Exposing side effects in a PL/I optimizing compiler. Proceedings IFIP Conference 1971, North Holland Publishing Company, Amsterdam (1971), 376-381.
	18	Robert E Tarjan, Solving path problems on directed graphs., Stanford University, Stanford, CA, 1975

CITED BY 61

	C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States
	P. P. Chang , W.-W. Hwu, Inline function expansion for compiling C programs, ACM SIGPLAN Notices, v.24 n.7, p.246-257, July 1989
	K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, ACM SIGPLAN Notices, v.23 n.7, p.57-66, July 1988
	B. Maher , D. H. Sleeman, Automatic Program Improvement: Variable Usage Transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.236-264, April 1983
	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
	K. D. Cooper , K. Kennedy, Fast interprocedual alias analysis, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-59, January 11-13, 1989, Austin, Texas, 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
	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
	Gail C. Murphy , David Notkin , Erica S.-C. Lan, An empirical study of static call graph extractors, Proceedings of the 18th international conference on Software engineering, p.90-99, March 25-29, 1996, Berlin, Germany
	J. M. Lucassen , D. K. Gifford, Polymorphic effect systems, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.47-57, January 10-13, 1988, San Diego, California, United States
	Douglas Long , Lori A. Clarke, Data flow analysis of concurrent systems that use the rendezvous model of synchronization, Proceedings of the symposium on Testing, analysis, and verification, p.21-35, October 08-10, 1991, Victoria, British Columbia, Canada
	David Cann, Retire Fortran?: a debate rekindled, Communications of the ACM, v.35 n.8, p.81-89, Aug. 1992
	Barton P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, ACM SIGPLAN Notices, v.24 n.1, p.141-150, Jan. 1989
	A. Neirynck , A. J. Demers, Computation of aliases and support sets, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.274-283, January 21-23, 1987, Munich, West Germany
	Mary Jean Harrold , Mary Lou Soffa, Efficient computation of interprocedural definition-use chains, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.2, p.175-204, March 1994
	Luke Hornof , Jacques Noyé, Accurate binding-time analysis for imperative languages: flow, context, and return sensitivity, ACM SIGPLAN Notices, v.32 n.12, p.63-73, Dec. 1997
	M. Harrold , M. Soffa, Interprocedual data flow testing, ACM SIGSOFT Software Engineering Notes, v.14 n.8, p.158-167, Dec. 1989
	Mariam Kamkar , Nahid Shahmehri , Peter Fritzson, Affect-chaining and dependency oriented flow analysis applied to queries of programs, Proceedings of the 1988 ACM SIGSMALL/PC symposium on ACTES, p.36-44, May 04-06, 1988, Cannes, France
	David Binkley, Precise executable interprocedural slices, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.31-45, March–Dec. 1993
	Robert J. Sheraga , John L. Gieser, Automatic microcode generation for horizontally microprogrammed processors, ACM SIGMICRO Newsletter, v.12 n.4, p.154-168, Dec. 1981
	Ira R. Forman, Global data flow analysis by decomposition into primes, Proceedings of the 6th international conference on Software engineering, p.386-392, September 13-16, 1982, Tokyo, Japan
	Gail C. Murphy , David Notkin , William G. Griswold , Erica S. Lan, An empirical study of static call graph extractors, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.2, p.158-191, April 1998
	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
	Tor E. Jeremiassen , Susan J. Eggers, Reducing false sharing on shared memory multiprocessors through compile time data transformations, ACM SIGPLAN Notices, v.30 n.8, p.179-188, Aug. 1995
	Zhiyuan Li , Pen-Chung Yew, Efficient interprocedural analysis for program parallelization and restructuring, ACM SIGPLAN Notices, v.23 n.9, p.85-99, Sept. 1988
	John Hennessy, Program optimization and exception handling, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.200-206, January 26-28, 1981, Williamsburg, Virginia
	Barbara G. Ryder , William A. Landi , Philip A. Stocks , Sean Zhang , Rita Altucher, A schema for interprocedural modification side-effect analysis with pointer aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.2, p.105-186, March 2001
	David Cann, Retire Fortran? A debate rekindled, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.264-272, November 18-22, 1991, Albuquerque, New Mexico, United States
	Robert Muth , Saumya Debray, On the complexity of flow-sensitive dataflow analyses, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.67-80, January 19-21, 2000, Boston, MA, USA
	Jong-Deok Choi , Barton P. Miller , Robert H. B. Netzer, Techniques for debugging parallel programs with flowback analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.491-530, Oct. 1991
	Laurie J. Hendren , Alexandru Nicolau, Intererence analysis tools for parallelizing programs with recursive data structures, Proceedings of the 3rd international conference on Supercomputing, p.205-214, June 05-09, 1989, Crete, Greece
	William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, ACM SIGPLAN Notices, v.28 n.6, p.56-67, June 1993
	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
	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
	L. J. Hendren , A. Nicolau, Parallelizing Programs with Recursive Data Structures, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.35-47, January 1990
	Keith D. Cooper , Ken Kennedy , Linda Torczon, The impact of interprocedural analysis and optimization in the Rⁿ programming environment, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.491-523, Oct. 1986
	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
	Jack Dongarra , Ian Foster , Geoffrey Fox , William Gropp , Ken Kennedy , Linda Torczon , Andy White, References, Sourcebook of parallel computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
	Neil D. Jones , Alan Mycroft, Data flow analysis of applicative programs using minimal function graphs, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.296-306, January 01, 1986, St. Petersburg Beach, Florida
	B. P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, ACM SIGPLAN Notices, v.23 n.7, p.135-144, July 1988
	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
	Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States
	Daniel R. Perkins , Richard L. Sites, Machine-independent PASCAL code optimization, ACM SIGPLAN Notices, v.14 n.8, p.201-207, August 1979
	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
	Gerardo Canfora , Aniello Cimitile , Ugo de Carlini, A Logic-Based Approach to Reverse Engineering Tools Production, IEEE Transactions on Software Engineering, v.18 n.12, p.1053-1064, December 1992
	Keith D. Cooper , Ken Kennedy, Interprocedural side-effect analysis in linear time, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Yao-Wen Huang , Fang Yu , Christian Hang , Chung-Hung Tsai , Der-Tsai Lee , Sy-Yen Kuo, Securing web application code by static analysis and runtime protection, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA
	William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural pointer aliasing, 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
	David C. Cann , Paraskevas Evripidou, Advanced Array Optimizations for High Performance Functional Languages, IEEE Transactions on Parallel and Distributed Systems, v.6 n.3, p.229-239, March 1995
	David Callahan , Alan Carle , Mary Wolcott Hall , Ken Kennedy, Constructing the Procedure Call Multigraph, IEEE Transactions on Software Engineering, v.16 n.4, p.483-487, April 1990
	Keith Brian Gallagher , James R. Lyle, Using Program Slicing in Software Maintenance, IEEE Transactions on Software Engineering, v.17 n.8, p.751-761, August 1991
	Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Complexity of Points-To Analysis of Java in the Presence of Exceptions, IEEE Transactions on Software Engineering, v.27 n.6, p.481-512, June 2001
	Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico
	Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia
	Barbara G. Ryder , Marvin C. Paull, Elimination algorithms for data flow analysis, ACM Computing Surveys (CSUR), v.18 n.3, p.277-316, Sept. 1986
	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
	Shibin Hu, Comment on Cooper and Kennedy's flow-insensitive interprocedural summary information computation algorithm, ACM SIGPLAN Notices, v.28 n.5, p.3-8, May 1993
	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