Object code optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Object code optimization

Full text

Pdf (1.30 MB)

Source

Communications of the ACM archive
Volume 12 , Issue 1 (January 1969) table of contents

Pages: 13 - 22

Year of Publication: 1969

ISSN:0001-0782

Authors

Edward S. Lowry	International Business Machines Corp., Poughkeepsie, NY
C. W. Medlock	International Business Machines Corp., Poughkeepsie, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 53, Citation Count: 66

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

ABSTRACT

Methods of analyzing the control flow and data flow of programs during compilation are applied to transforming the program to improve object time efficiency. Dominance relationships, indicating which statements are necessarily executed before others, are used to do global common expression elimination and loop identification. Implementation of these and other optimizations in OS/360 FORTRAN H are described.

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	H. D. Huskey , W. H. Wattenburg, Compiling techniques for Boolean expressions and conditional statements in ALGOL 60, Communications of the ACM, v.4 n.1, p.70-75, Jan. 1961 [doi>10.1145/366062.366098]
	2	PROSSER, R.T. Applications of Boolean matrices to the analysis of flow diagrams. Proc. Eastern Joint Comput. Conf., Dec. 1959, Spartan Books, New York, pp. 133-138.
	3	A. P. Yershov, ALPHA—An Automatic Programming System of High Efficiency, Journal of the ACM (JACM), v.13 n.1, p.17-24, Jan. 1966 [doi>10.1145/321312.321314]
	4	J. Nievergelt, On the automatic simplification of computer programs, Communications of the ACM, v.8 n.6, p.366-370, June 1965 [doi>10.1145/364955.364963]
	5	C. W. Gear, High speed compilation of efficient object code, Communications of the ACM, v.8 n.8, p.483-488, Aug. 1965 [doi>10.1145/365474.365489]
	6	R. W. Allard , K. A. Wolf , R. A. Zemlin, Some effects of the 6600 computer on language structures, Communications of the ACM, v.7 n.2, p.112-119, Feb. 1964 [doi>10.1145/363921.363940]
	7	ALLEN, F. E. Program optimization. In Annual Review in Automatic Programming, Vol. 5, Pergamon, New York (in press).

CITED BY 66

	Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.279-288, May 24-26, 1998, Dallas, Texas, United States
	Dennis J. Frailey, An intermediate language for source and target independent code optimization, ACM SIGPLAN Notices, v.14 n.8, p.188-200, August 1979
	Barry K. Rosen, High-level data flow analysis, Communications of the ACM, v.20 n.10, p.712-724, Oct. 1977
	Jean E. Sammet, Brief survey of languages used for systems implementation, ACM SIGPLAN Notices, v.6 n.9, p.1-19, October 1971
	D Harel, A linear algorithm for finding dominators in flow graphs and related problems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.185-194, May 06-08, 1985, Providence, Rhode Island, United States
	C. A. Papachristou , V. R. Immaneni , D. B. Sarma, An automatic migration scheme based on modular microcode and structured firmware sequencing, ACM SIGMICRO Newsletter, v.15 n.4, p.155-164, Dec. 1984
	Andrew S. Tanenbaum , Hans van Staveren , E. G. Keizer , Johan W. Stevenson, A practical tool kit for making portable compilers, Communications of the ACM, v.26 n.9, p.654-660, Sept. 1983
	Thomas C. Lowe, Automatic segmentation of cyclic program structures based on connectivity and processor timing, Communications of the ACM, v.13 n.1, p.3-6, Jan. 1970
	John T. Bagwell, Jr., Local optimizations, ACM SIGPLAN Notices, v.5 n.7, p.52-66, July 1970
	Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, A new, simpler linear-time dominators algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1265-1296, Nov. 1998
	Jack W. Davidson , Christopher W. Fraser, The Design and Application of a Retargetable Peephole Optimizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.191-202, April 1980
	Keith D. Cooper , Devika Subramanian , Linda Torczon, Adaptive Optimizing Compilers for the 21st Century, The Journal of Supercomputing, v.23 n.1, p.7-22, August 2002
	Christopher W. Fraser, A knowledge-based code generator generator, ACM SIGPLAN Notices, v.12 n.8, p.126-129, August 1977
	John H. Crawford , Mehdi Jazayeri, Engineering A Program Optimizer, Proceedings of the 1978 annual conference, p.247-253, December 04-06, 1978, Washington, D.C., United States
	Francois Robert Broca , Richard E. Merwin, Direct microprogrammed execution of the intermediate text from a high-level language compiler, Proceedings of the annual conference, p.57-63, August 27-29, 1973, Atlanta, Georgia, United States
	Marvin V. Zelkowitz, Perspectives in Software Engineering, ACM Computing Surveys (CSUR), v.10 n.2, p.197-216, June 1978
	A. V. Aho , J. D. Ullman, Transformations on straight line programs - (Preliminary Version), Proceedings of the second annual ACM symposium on Theory of computing, p.136-148, May 04-06, 1970, Northampton, Massachusetts, United States
	Paul W. Purdom, Jr. , Edward F. Moore, Immediate predominators in a directed graph [H], Communications of the ACM, v.15 n.8, p.777-778, Aug. 1972
	Francois Robert Broca , Richard E. Merwin, Direct microprogrammed execution of the intermediate text from a high-level language compiler, ACM SIGPLAN Notices, v.9 n.8, p.145-153, August 1974
	Paul B. Schneck, A survey of compiler optimization techniques, Proceedings of the annual conference, p.106-113, August 27-29, 1973, Atlanta, Georgia, United States
	B. P. Buckles , G. C. Hintze, Levels of abstraction and compilers, Proceedings of the annual conference, p.419-423, October 20-22, 1976, Houston, Texas, United States
	R. A. Freiburghouse, Register allocation via usage counts, Communications of the ACM, v.17 n.11, p.638-642, Nov. 1974
	Roy F. Touzeau, A Fortran compiler for the FPS-164 scientific computer, ACM SIGPLAN Notices, v.19 n.6, p.48-57, June 1984
	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
	Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979
	Richard L. Sites, The Compilation of Loop Induction Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.50-57, July 1979
	Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
	Barry K. Rosen, Data Flow Analysis for Procedural Languages, Journal of the ACM (JACM), v.26 n.2, p.322-344, April 1979
	Barron C. Housel , Maurice H. Halstead, A methodology for machine language decompilation, Proceedings of the 1974 annual conference, p.254-260, January 1974
	Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts
	William A. Wulf, A case against the GOTO, Proceedings of the ACM annual conference, p.791-797, August 01-01, 1972, Boston, Massachusetts, United States
	Christopher W. Fraser, A compact, machine-independent peephole optimizer, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-6, January 29-31, 1979, San Antonio, Texas
	Dorothy E. Denning , Peter J. Denning, Certification of programs for secure information flow, Communications of the ACM, v.20 n.7, p.504-513, July 1977
	R. C. Holt, Data descriptors: a compile-time model of data and addressing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.367-389, July 1987
	Ron Cytron , Andy Lowry , F. Kenneth Zadeck, Code motion of control structures in high-level languages, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.70-85, January 01, 1986, St. Petersburg Beach, Florida
	Brendon Cahoon , Kathryn S. McKinley, Simple and effective array prefetching in Java, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.86-95, November 03-05, 2002, Seattle, Washington, USA
	Vincent A. Busam , Donald E. Englund, Optimization of expressions in Fortran, Communications of the ACM, v.12 n.12, p.666-674, Dec. 1969
	Ravi Sethi, Complete register allocation problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.182-195, April 30-May 02, 1973, Austin, Texas, United States
	W. M. Waite, The mobile programming system: STAGE2, Communications of the ACM, v.13 n.7, p.415-421, July 1970
	William C. Nylin, Jr., Flow graph analysis using linear connected regions, Proceedings of the annual conference, p.7-11, October 20-22, 1976, Houston, Texas, United States
	E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979
	B. Press, Meta-optimizer development, ACM SIGPLAN Notices, v.8 n.6, June 1973
	Changqing Fu , Kent Wilken, A faster optimal register allocator, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
	Guy L. Steele, Arithmetic shifting considered harmful, ACM SIGPLAN Notices, v.12 n.11, p.61-69, November 1977
	Nobuyoshi Terashima, SYSL: system description language, ACM SIGPLAN Notices, v.9 n.12, p.35-44, December 1974
	A. V. Aho , J. E. Hopcroft , J. D. Ullman, On finding lowest common ancestors in trees, Proceedings of the fifth annual ACM symposium on Theory of computing, p.253-265, April 30-May 02, 1973, Austin, Texas, United States
	B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States
	Robert E. Noonan, Dynamic algebra, Proceedings of the 1974 annual conference, p.326-334, January 1974
	C. A. Papachristou , V. R. Immaneni, Vertical Migration of Software Functions and Algorithms Using Enhanced Microsequencing, IEEE Transactions on Computers, v.42 n.1, p.45-61, January 1993
	René Krenz , Elena Dubrova, A fast algorithm for finding common multiple-vertex dominators in circuit graphs, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Daniel R. Perkins , Richard L. Sites, Machine-independent PASCAL code optimization, ACM SIGPLAN Notices, v.14 n.8, p.201-207, August 1979
	Karl J. Ottenstein, Intermediate program representations in compiler construction: a supplemental bibliography, ACM SIGPLAN Notices, v.19 n.7, July 1984
	William A. Wulf, A case against the GOTO, ACM SIGPLAN Notices, v.7 n.11, November 1972
	Barry K. Rosen, Stickiness and liveness, ACM SIGPLAN Notices, v.14 n.2, p.44-45, February 1979
	Tetsuo Saitou , Mitsugu Suzuki , Tan Watanabe, Dominance analysis of irreducible CFGs by reduction, ACM SIGPLAN Notices, v.40 n.4, April 2005
	J. J. Duby, Extensible languages: A potential user's point of view, ACM SIGPLAN Notices, v.6 n.12, p.137-140, December 1971
	René Krenz , Elena Dubrova, Improved Boolean function hashing based on multiple-vertex dominators, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Barry K. Rosen, How practical is POPL?, ACM SIGPLAN Notices, v.15 n.1, p.115-116, January 1980
	Matthew S. Hecht , Jeffrey D. Ullman, Analysis of a simple algorithm global data flow problems, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.207-217, October 01-03, 1973, Boston, Massachusetts
	Alfred V. Aho , Ravi Sethi , J. D. Ullman, A formal approach to code optimization, ACM SIGPLAN Notices, v.5 n.7, p.86-100, July 1970
	Robert R. Kessler, Peep: an architectural description driven peephole optimizer, ACM SIGPLAN Notices, v.19 n.6, p.106-110, June 1984
	W. A. Wulf, A case against the GOTO, Classics in software engineering, Yourdon Press, Upper Saddle River, NJ, 1979
	Bjorn De Sutter , Ludo Van Put , Koen De Bosschere, A practical interprocedural dominance algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.4, p.19-es, August 2007
	Maxim Teslenko , Elena Dubrova, An Efficient Algorithm for Finding Double-Vertex Dominators in Circuit Graphs, Proceedings of the conference on Design, Automation and Test in Europe, p.406-411, March 07-11, 2005
	Elena Dubrova, Structural Testing Based on Minimum Kernels, Proceedings of the conference on Design, Automation and Test in Europe, p.1168-1173, March 07-11, 2005
	M. H. Halstead, Language selection for applications, Proceedings of the June 4-8, 1973, national computer conference and exposition, June 04-08, 1973, New York, New York