Interprocedural optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Interprocedural optimization: eliminating unnecessary recompilation

Full text

Pdf (2.46 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 15 , Issue 3 (July 1993) table of contents

Pages: 367 - 399

Year of Publication: 1993

ISSN:0164-0925

Authors

Michael Burke	IBM Research
Linda Torczon	Rice University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 31, Citation Count: 19

Additional Information:

references cited by index terms review 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/169683.169678 What is a DOI?

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	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	2	Frances Allen , Michael Burke , Philippe Charles , Ron Cytron , Jeanne Ferreant, An overview for the PTRAN analysis system for multiprocessing, Journal of Parallel and Distributed Computing, v.5 n.5, p.617-640, October 1988 [doi>10.1016/0743-7315(88)90015-9]
	3	ALLEN, F. E., CARTER, J. L., FABm, J., F~RRANTE, J., HARRISON, W. H., LOEW~ER, P. G., AND TREVlLLYAN, L. H. The experimental compiling system. IBM J. Res. Dev. 24, 6 (Nov. 1980), 695-715.
	4	ALLEN, F. E., AND COCKE, J. A catalogue of optimizing transformations In Desig, and Opt~mizat~on of Compilers, J. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J, 1972
	5	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]
	6	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 [doi>10.1145/78969.78963]
	7	Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
	8	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
	9	David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.21 n.7, p.152-161, July 1986
	10	Alan Carle , Keith D. Cooper , Robert T. Hood , Ken Kennedy , Linda Torczon, A practical environment for scientific programming, Computer, v.20 n.11, p.75-89, Nov. 1987 [doi>10.1109/MC.1987.1663418]
	11	Martin Donald Carroll , Barbara Ryder, Data flow update via dominator and attribute updates, 1988
	12	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
	13	F. C. Chow, Minimizing register usage penalty at procedure calls, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.85-94, June 20-24, 1988, Atlanta, Georgia, United States
	14	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]
	15	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
	16	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 [doi>10.1145/75277.75282]
	17	Keith D. Cooper , Ken Kennedy , Linda Lorczon, Interprocedural optimization: eliminating unnecessary recompilation, ACM SIGPLAN Notices, v.21 n.7, p.58-67, July 1986
	18	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 [doi>10.1145/6465.6489]
	19	DONGARRA, J. J., BUNC~t, J. R., MOLER, C. B., AND STEWART, G.W. LINPACK Users' Guide. SIAM, Philadelphia, Pa., 1979.
	20	FELDMAN, S. Make--a computer program for maintaining computer programs. Softw. Pract. Exper. 9, 4 (1979), 255-265.
	21	John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
	22	KAM, J., AND ULLMAN, J.D. Monotone data fiow analysis frameworks. Acta Inf. 7, 3 (1977), 305 317.
	23	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 [doi>10.1145/567532.567556]
	24	Stephen Richardson , Mahadevan Ganapathi, Code Optimization Across Procedures, Computer, v.22 n.2, p.42-50, February 1989 [doi>10.1109/2.19831]
	25	Stephen Richardson , Mahadevan Ganapathi, Interprocedural analysis vs. procedure integration, Information Processing Letters, v.32 n.3, p.137-142, August 24, 1989 [doi>10.1016/0020-0190(89)90014-8]
	26	ROSEN, B. K. Monoids for rapid data fiow analysis. SIAM J. Comput. 9, i (Feb. 1980), 159-196.
	27	Robert W. Schwanke , Gail E. Kaiser, Smarter recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.627-632, Oct. 1988 [doi>10.1145/48022.214505]
	28	SPILLMAN, T. C. Exposing side-effects in a PL/I optimizing compiler. In Proceedings of IFIP Congress 71 (Ljubljana, Yugoslavia, Aug. 1971), North-Holland, Amsterdam, 376 381.
	29	Robert Endre Tarjan, A Unified Approach to Path Problems, Journal of the ACM (JACM), v.28 n.3, p.577-593, July 1981 [doi>10.1145/322261.322272]
	30	Walter F. Tichy , Mark C. Baker, Smart recompilation, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.236-244, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318648]
	31	Walter F. Tichy, Smart recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.273-291, July 1986 [doi>10.1145/5956.5959]
	32	Linda Marie Torczon, Compilation dependences in an ambitious optimizing compiler (interprocedural, recompilation), 1985
	33	D. W. Wall, Register windows vs. register allocation, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.67-78, June 20-24, 1988, Atlanta, Georgia, United States
	34	Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]

CITED BY 19

	Andrew Ayers , Stuart de Jong , John Peyton , Richard Schooler, Scalable cross-module optimization, ACM SIGPLAN Notices, v.33 n.5, p.301-312, May 1998
	Gagan Agrawal , Joel Saltz , Raja Das, Interprocedural partial redundancy elimination and its application to distributed memory compilation, ACM SIGPLAN Notices, v.30 n.6, p.258-269, June 1995
	Craig Chambers , Jeffrey Dean , David Grove, A framework for selective recompilation in the presence of complex intermodule dependencies, Proceedings of the 17th international conference on Software engineering, p.221-230, April 24-28, 1995, Seattle, Washington, United States
	M. W. Hall , S. Hiranandani , K. Kennedy , C.-W. Tseng, Interprocedural compilation of Fortran D for MIMD distributed-memory machines, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.522-534, November 16-20, 1992, Minneapolis, Minnesota, United States
	John Mellor-Crummey, Compile-time support for efficient data race detection in shared-memory parallel programs, ACM SIGPLAN Notices, v.28 n.12, p.129-139, Dec. 1993
	Ali-Reza Adl-Tabatabai , Geoff Langdale , Steven Lucco , Robert Wahbe, Efficient and language-independent mobile programs, ACM SIGPLAN Notices, v.31 n.5, p.127-136, May 1996
	Mauricio Serrano , Rajesh Bordawekar , Sam Midkiff , Manish Gupta, Quicksilver: a quasi-static compiler for Java, ACM SIGPLAN Notices, v.35 n.10, p.66-82, Oct. 2000
	Rolf Adams , Walter Tichy , Annette Weinert, The cost of selective recompilation and environment processing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.3 n.1, p.3-28, Jan. 1994
	Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States
	G. Ramalingam , Thomas Reps, A categorized bibliography on incremental computation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.502-510, March 1993, Charleston, South Carolina, United States
	David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Chris Lattner , Vikram Adve, Automatic pool allocation for disjoint data structures, ACM SIGPLAN Notices, v.38 n.2 supplement, p.13-24, February 2003
	Gagan Agrawal, Interprocedural Partial Redundancy Elimination With Application to Distributed Memory Compilation, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.609-625, July 1998
	Vugranam C. Sreedhar , Michael Burke , Jong-Deok Choi, A framework for interprocedural optimization in the presence of dynamic class loading, ACM SIGPLAN Notices, v.35 n.5, p.196-207, May 2000
	Keith D. Cooper , Ken Kennedy, Interprocedural side-effect analysis in linear time, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Sungdo Moon , Xinliang D. Li , Robert Hundt , Dhruva R. Chakrabarti , Luis A. Lozano , Uma Srinivasan , Shin-Ming Liu, SYZYGY - A Framework for Scalable Cross-Module IPO, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.65, March 20-24, 2004, Palo Alto, California
	Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
	Martin Hirzel , Daniel Von Dincklage , Amer Diwan , Michael Hind, Fast online pointer analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.2, p.11-es, April 2007
	Xiaoxia Ren , Ophelia C. Chesley , Barbara G. Ryder, Identifying Failure Causes in Java Programs: An Application of Change Impact Analysis, IEEE Transactions on Software Engineering, v.32 n.9, p.718-732, September 2006

INDEX TERMS

Primary Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.4 Processors
Subjects: Optimization

General Terms:
Algorithms, Languages

Keywords:
data-flow analysis, interprocedural analysis and optimization, recompilation analysis

REVIEW

"Noah S. Prywes : Reviewer"

The authors discuss the use of interprocedural dataflow information in analysis that leads to reducing the recompilation needed when a procedure in a large program is changed. The paper is oriented specifically to FORTRAN and to a more...

Collaborative Colleagues:

Michael Burke: colleagues

Linda Torczon: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player