Article

Free access

A unified approach to global program optimization

Author:

Gary A. KildallAuthors Info & Claims

POPL '73: Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages

Pages 194 - 206

https://doi.org/10.1145/512927.512945

Published: 01 October 1973 Publication History

Abstract

A technique is presented for global analysis of program structure in order to perform compile time optimization of object code generated for expressions. The global expression optimization presented includes constant propagation, common subexpression elimination, elimination of redundant register load operations, and live expression analysis. A general purpose program flow analysis algorithm is developed which depends upon the existence of an "optimizing function." The algorithm is defined formally using a directed graph model of program flow structure, and is shown to be correct. Several optimizing functions are defined which, when used in conjunction with the flow analysis algorithm, provide the various forms of code optimization. The flow analysis algorithm is sufficiently general that additional functions can easily be defined for other forms of global code optimization.

References

[1]

Aho, A., Sethi, R., and Ullman, J. A formal approach to code optimization. Proceedings of a Symposium on Compiler Optimization. University of Illinois at Urbana-Champaign, July, 1970.

Digital Library

[2]

Allen, F. Program optimization. In Annual Review in Automatic Programming, Pergamon Press, 5(1969), 239-307.

[3]

____ A basis for program optimization. IFIP Congress 71, Ljubljana, August, 1971, 64-68.

[4]

____ Control flow analysis. Proceedings of a Symposium on Compiler Optimization, University of Illinois at Urbana-Champaign, July, 1970.

Digital Library

[5]

Anderson, J. A note on some compiling algorithms. Comm. ACM 7, 3 (March 1964), 149-150.

Digital Library

[6]

Arden, B. Galler, B., and Graham, R. An algorithm for translating boolean expressions. Jour. ACM 9, 2(April 1962), 222-239.

Digital Library

[7]

Bachmann, P. A contribution to the problem of the optimization of programs. IFIP Congress 71, Ljubljana, August, 1971, 74-78.

[8]

Ballard, A., and Tsichritzis, D. Transformations of programs. IFIP Congress 71, Ljubljana, August, 1971, 89-93.

[9]

Breuer, M. Generation of optimal code for expressions via factorization. Comm. ACM 12, 6(June 1970), 333-340.

Digital Library

[10]

Busam, V., and Englund, D. Optimization of expressions in FORTRAN. Comm. ACM 12, 12(Dec. 1969), 666-674.

Digital Library

[11]

Cocke, J. Global common subexpression elimination. Proceedings of a Sybposium on Compiler Optimization. University of Illinois at Urbana-Champaign, July, 1970.

Digital Library

[12]

____, and Miller, R. Some analysis techniques for optimizing computer programs. Proc. Second International Conference of System Sciences, Hawaii, January, 1969, 143-146.

[13]

____, and Schwartz, J. Programming Languages and Their Compilers: Preliminary Notes. Courant Institute of Mathematical Sciences, New York University, 1970.

Digital Library

[14]

Day, W. Compiler assignment of data items to registers. IBM Systems Journal, 8, 4(1970), 281-317.

[15]

Earnest, C., Balke, K., and Anderson, J. Analysis of graphs by ordering nodes. Jour. ACM 19, 1(Jan. 1972), 23-42.

Digital Library

[16]

Elson, M., and Rake, S. Code generation technique for large language compilers. IBM Systems Journal 3(1970), 166-188.

Digital Library

[17]

Fateman, R. Optimal code for serial and parallel computation. Comm. ACM 12, 12(Dec. 1969), 694-695.

Digital Library

[18]

Finkelstein, M. A compiler optimization technique. The Computer Review (Feb. 1968), 22-25.

[19]

Floyd, R. An algorithm for coding efficient arithmetic operations. Comm. ACM 4, 1(Jan. 1961), 42-51.

Digital Library

[20]

Frailey, D. Expression Optimization using unary complement operators. Proceedings of a Symposium on Compiler Optimization, University of Illinois at Urbana-Champaign, July, 1970.

Digital Library

[21]

____, A study of optimization using a general purpose optimizer. (PhD Thesis) Purdue University, Lafayette, Ind., January 1971.

Digital Library

[22]

Freiburghouse, R. The MULTICS PL/I compiler. AFIPS Conf. Proc. FJCC (1969), 187-199.

[23]

Gear, C. High speed compilation of efficient object code. Comm. ACM 8, 8(Aug. 1965), 483-488.

Digital Library

[24]

Gries, D. Compiler Construction for Digital Computers. John Wiley and Sons, Inc., New York, 1971.

Digital Library

[25]

Hill, V., Langmaack, H., Schwartz, H., and Seegumuller, G. Efficient handling of subscripted variables in ALGOL-60 compilers. Proc. Symbolic Languages in Data Processing, Gordon and Breach, New York, 1962, 331-340.

[26]

Hopkins, M. An optimizing compiler design. IFIP Congress 71, Ljubljana, August, 1971, 69-73.

[27]

Horowitz, L., Karp, R., Miller, R., and Winograd, S. Index register allocation. Jour. ACM 13, 1(Jan. 1966), 43-61.

Digital Library

[28]

Huskey, H., and Wattenberg, W. Compiling techniques for boolean expressions and conditional statements in ALGOL-60. Comm. ACM 4, 1(Jan. 1961), 70-75.

Digital Library

[29]

Huskey, H. Compiling techniques for algebraic expressions. Computer Journal 4, 4(April 1961), 10-19.

[30]

Huxtable, D. On writing an optimizing translator for ALGOL-60. In Introduction to System Programming, Academic Press, Inc., New York, 1964.

[31]

IBM System/360 Operating System, FORTRAN IV (G and H) Programmer's Guide. c28-6817-1, International Business Machines, 1967, 174-179.

[32]

Kennedy, K. A global flow analysis algorithm. Intern. J. of Computer Mathematics, Section A, Vol. 3, 1971, 5-15.

[33]

Kildall, G. Global expression optimization during compilation. Technical Report No. TR# 72-06-02, University of Washington Computer Science Group, University of Washington, Seattle, Washington, June, 1972.

[34]

____ A code synthesis filter for basic block optimization. Technical Report No. TR# 72-01-01, University of Washington Computer Science Group, University of Washington, Seattle, Washington, January, 1972.

[35]

Lowry, E., and Medlock, C. Object code optimization. Comm. ACM 12, 1(Jan. 1969), 13-22.

Digital Library

[36]

Luccio, F. A comment on index register allocation. Comm. ACM 10,9 (Sept. 1967), 572-572-574.

Digital Library

[37]

Maurer, W. Programming-An Introduction to Computer Language Technique. Holden-Day, San Francisco, 1968, 202-203.

Digital Library

[38]

McKeeman, W. Peephole optimization. Comm. ACM 8, 7(July 1965), 443-444.

Digital Library

[39]

Nakata, I. On compiling algorithms for arithmetic expressions. Comm. ACM 19, 8(Aug. 1967), 492-494.

Digital Library

[40]

Nievergelt, J. On the automatic simplification of computer programs. Comm. ACM 8, 6(June 1965), 366-370.

Digital Library

[41]

Painter, J. Compiler effectiveness. Proceedings of a Symposium on Compiler Optimization, University of Illinois at Urbana-Champaign, July, 1970.

[42]

Randell, B., and Russell, L. ALGOL 60 Implementation. Academic Press, Inc., New York, 1964.

Digital Library

[43]

Redziejowski, R. On arithmetic expressions and trees. Comm. ACM 12, 2(Feb. 1969), 81-84.

Digital Library

[44]

Ryan, J. A direction-independent algorithm for determining the forward and backward compute points for a term or subscript during compilation. Computer Journal 9, 2(Aug. 1966), 157-160.

[45]

Schnieder, V. On the number of registers needed to evaluate arithmetic expressions. BIT 11(1971), 84-93.

[46]

Sethi, R., and Ullman, J. The generation of optimal code for arithmetic expressions. Jour. ACM 17, 4(Oct. 1970), 715-728.

Digital Library

[47]

Wagner, R. Some techniques for algebraic optimization with application to matrix arithmetic expressions. Thesis, Carnegie-Mellon University, June, 1968.

Digital Library

[48]

Yershov, A. On programming of arithmetic operations. Comm. ACM 1, 8(Aug. 1958), 3-6.

Digital Library

[49]

____ ALPHA-an automatic programming system of high efficiency. Jour. ACM 13, 1(Jan. 1966), 17-24.

Digital Library

Cited By

Lund NHüttel H(2024)A Type System for Data Flow and Alias Analysis in ReScriptElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.410.8410(116-132)Online publication date: 31-Oct-2024
https://doi.org/10.4204/EPTCS.410.8
Susan S(2024)Leveraging Slither and Interval Analysis to build a Static Analysis ToolElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.410.10410(150-166)Online publication date: 31-Oct-2024
https://doi.org/10.4204/EPTCS.410.10
Ge XFang CLi XSun WWu DZhai JLin SZhao ZLiu YChen Z(2024)Machine Learning for Actionable Warning Identification: A Comprehensive SurveyACM Computing Surveys10.1145/369635257:2(1-35)Online publication date: 19-Sep-2024
https://dl.acm.org/doi/10.1145/3696352
Show More Cited By

A unified approach to global program optimization
1. Software and its engineering
  1. Software notations and tools

Recommendations

An enhanced particle swarm optimization with levy flight for global optimization

Enhanced PSO with levy flight.Random walk of the particles.High convergence rate.Provides solution accuracy and robust. Hüseyin Haklı and Harun Uguz (2014) proposed a novel approach for global function optimization using particle swarm optimization with ...
Gravity-based particle swarm optimization with hybrid cooperative swarm approach for global optimization

Premature convergence has been recognized as one of the major drawbacks of particle swarm optimization PSO algorithms. In particular, the lack of diversity in PSO performance is an essential cause that commonly results in high susceptibility to ...
Non-parametric particle swarm optimization for global optimization

Proposing an improved PSO scheme called non-parametric particle swarm optimization (NP-PSO).Combining local and global topologies with two quadratic interpolation operations to increase the search ability in NP-PSO.Removing PSO parameters in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '73: Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages

October 1973

242 pages

ISBN:9781450373494

DOI:10.1145/512927

Conference Chair:
Patrick C. Fischer
University of Waterloo, Waterloo, Ontario, Canada
,
Program Chair:
Jeffrey D. Ullman
Princeton University, Princeton, NJ 08540

Copyright © 1973 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1973

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

POPL '73 Paper Acceptance Rate 22 of 100 submissions, 22%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

659
Total Citations
View Citations
6,175
Total Downloads

Downloads (Last 12 months)578
Downloads (Last 6 weeks)90

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lund NHüttel H(2024)A Type System for Data Flow and Alias Analysis in ReScriptElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.410.8410(116-132)Online publication date: 31-Oct-2024
https://doi.org/10.4204/EPTCS.410.8
Susan S(2024)Leveraging Slither and Interval Analysis to build a Static Analysis ToolElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.410.10410(150-166)Online publication date: 31-Oct-2024
https://doi.org/10.4204/EPTCS.410.10
Ge XFang CLi XSun WWu DZhai JLin SZhao ZLiu YChen Z(2024)Machine Learning for Actionable Warning Identification: A Comprehensive SurveyACM Computing Surveys10.1145/369635257:2(1-35)Online publication date: 19-Sep-2024
https://dl.acm.org/doi/10.1145/3696352
Chen HZhang NXiang SZeng ZDai MZhang Z(2024)Allo: A Programming Model for Composable Accelerator DesignProceedings of the ACM on Programming Languages10.1145/36564018:PLDI(593-620)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656401
Lesbre DLemerre M(2024)Compiling with Abstract InterpretationProceedings of the ACM on Programming Languages10.1145/36563928:PLDI(368-393)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656392
Niu WAgrawal GRen BTsafrir DMUSUVATHI MGupta RAbu-Ghazaleh N(2024)SoD2: Statically Optimizing Dynamic Deep Neural Network ExecutionProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624869(386-400)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3617232.3624869
Schlichtkrull ARydhof Hansen RNielson FHong JPark J(2024)Isabelle-verified correctness of Datalog programs for program analysisProceedings of the 39th ACM/SIGAPP Symposium on Applied Computing10.1145/3605098.3636091(1731-1734)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3605098.3636091
Karakaya KBodden ERoychoudhury APaiva AAbreu RStorey M(2024)Symbol-Specific Sparsification of Interprocedural Distributive Environment ProblemsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639092(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639092
Steenhoek BGao HLe WRoychoudhury APaiva AAbreu RStorey M(2024)Dataflow Analysis-Inspired Deep Learning for Efficient Vulnerability DetectionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3623345(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3623345
McMichen TGreiner NZhong PSossai FPatel ACampanoni SGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Representing Data Collections in an SSA FormProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444817(308-321)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444817
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents