article

Free access

Global optimization by suppression of partial redundancies

Authors:

E. Morel,

C. RenvoiseAuthors Info & Claims

Communications of the ACM, Volume 22, Issue 2

Pages 96 - 103

https://doi.org/10.1145/359060.359069

Published: 01 February 1979 Publication History

PDF eReader

Abstract

The elimination of redundant computations and the moving of invariant computations out of loops are often done separately, with invariants moved outward loop by loop. We propose to do both at once and to move each expression directly to the entrance of the outermost loop in which it is invariant. This is done by solving a more general problem, i.e. the elimination of computations performed twice on a given execution path. Such computations are termed partially redundant. Moreover, the algorithm does not require any graphical information or restrictions on the shape of the program graph. Testing this algorithm has shown that its execution cost is nearly linear with the size of the program, and that it leads to a smaller optimizer that requires less execution time.

References

[1]

Aho, A. V., and Ullman, J. D. The Theory of Parsing, Translation and Compiling, Vol. 2. Prentice-Hall, Englewood Cliffs, N.J., 1973.

Digital Library

Google Scholar

[2]

Allen, F. E. Control flow analysis. SIGPLAN Notices (ACM) 5, 7 (1970), 1-19.

Digital Library

Google Scholar

[3]

Allen, F. E. and Cocke, J. A catalogue of optimizing techniques. In Design and Optimization of Compilers, R. Rustin, Ed., Prentice- Hall, Englewood Cliffs, N.J., 1971, pp. 1-30.

Google Scholar

[4]

Cocke, J. Global common subexpression elimination. SIGPLAN Notices (ACM) 5, 7 (1970), 20-24.

Digital Library

Google Scholar

[5]

Goldtmrg, P. A comparison of certain optimization techniques. In Design and Optimization of Compilers, R. Rustin, Ed., Prentice-HaU, Englewood Cliffs, N.J., 1971, pp. 31-50.

Google Scholar

[6]

Hecht, M. S., and UUman, J. D. A simple algorithm for global data flow analysis problems. SIAM J. Comptng. 4 (1975), 519-532.

Crossref

Google Scholar

[7]

Ichbiah, J. D., Rissen, J. P., Heliard, J. C., and Cousot, P. The system implementation language LIS. Ref. Manual 4549 E/EN, CII-HB, Louveciennes, France, Dec. 1974.

Google Scholar

[8]

Kennedy, K. A comparison of two algorithms for global data flow analysis. SIAM J. Comptng. 5 (1976), 158-180.

Crossref

Google Scholar

[9]

KildaU, G. A. A unified approach to global program optimization. Conf. Rec. of ACM Symp. on Principles of Programming Languages, Boston, Oct. 1973, pp. 194-206.

Digital Library

Google Scholar

[10]

Knuth, D. E. An empirical study of FORTRAN programs. Software-Practice and Experience (April 1971), pp. 105-134.

Crossref

Google Scholar

[11]

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

Digital Library

Google Scholar

[12]

Morel, E., and Renvoise, C. Etude et r6alisation d'un optimiseur global. Ph.D. Th., Universit6 de Paris VI, Juin 1974 (English version available).

Google Scholar

[13]

Morel, E., and Renvoise, C. A global algorithm for the elimination of partial redundancies. 2nd Int. Symp. on Programming, Paris, April 13-15, 1976, pp. 147-159 (edited by Dunod, Paris).

Google Scholar

[14]

Schaefer, M. A Mathematical Theory of Global Program Optimization. Prentice-Hall, Englewood Cliffs, N.J., 1973.

Digital Library

Google Scholar

Cited By

View all

Yanase YSumikawa Y(2023)Lazy Demand-driven Partial Redundancy EliminationJournal of Information Processing10.2197/ipsjjip.31.45931(459-468)Online publication date: 2023
https://doi.org/10.2197/ipsjjip.31.459
Gourdin LJul ERacordon D(2023)Lazy Code Transformations in a Formally Verified CompilerProceedings of the 18th ACM International Workshop on Implementation, Compilation, Optimization of OO Languages, Programs and Systems10.1145/3605158.3605848(3-14)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.1145/3605158.3605848
Roy RPaleri V(2023)Lexical-based partial redundancy elimination: An optimal algorithm with improved efficiencyJournal of Computer Languages10.1016/j.cola.2023.10120475(101204)Online publication date: Jun-2023
https://doi.org/10.1016/j.cola.2023.101204
Show More Cited By

Index Terms

Global optimization by suppression of partial redundancies
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Index terms have been assigned to the content through auto-classification.

Recommendations

Partial redundancy elimination in SSA form

The SSAPRE algorithm for performing partial redundancy elimination based entirely on SSA form is presented. The algorithm is formulated based on a new conceptual framework, the factored redundancy graph, for analyzing redundancy, and representes the ...
Compiler transformations for effectively exploiting a zero overhead loop buffer

A Zero Overhead Loop Buffer (ZOLB) is an architectural feature that is commonly found in DSP processors. This buffer can be viewed as a compiler managed cache that contains a sequence of instructions that will be executed a specified number of times ...
Redundancy Elimination in Distributed Matrix Computation
SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data

As matrix computation becomes increasingly prevalent in large-scale data analysis, distributed matrix computation solutions have emerged. These solutions support query interfaces of linear algebra expressions, which often contain redundant ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 22, Issue 2

Feb. 1979

61 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359060

Editor:
Robert L. Ashenhurst
The Univ. of Chicago, IL

Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1979

Published in CACM Volume 22, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

381
Total Citations
View Citations
1,581
Total Downloads

Downloads (Last 12 months)132
Downloads (Last 6 weeks)19

Reflects downloads up to 12 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yanase YSumikawa Y(2023)Lazy Demand-driven Partial Redundancy EliminationJournal of Information Processing10.2197/ipsjjip.31.45931(459-468)Online publication date: 2023
https://doi.org/10.2197/ipsjjip.31.459
Gourdin LJul ERacordon D(2023)Lazy Code Transformations in a Formally Verified CompilerProceedings of the 18th ACM International Workshop on Implementation, Compilation, Optimization of OO Languages, Programs and Systems10.1145/3605158.3605848(3-14)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.1145/3605158.3605848
Roy RPaleri V(2023)Lexical-based partial redundancy elimination: An optimal algorithm with improved efficiencyJournal of Computer Languages10.1016/j.cola.2023.10120475(101204)Online publication date: Jun-2023
https://doi.org/10.1016/j.cola.2023.101204
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Scalar OptimizationEngineering a Compiler10.1016/B978-0-12-815412-0.00016-4(517-573)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00016-4
Fukuhara JTakimoto M(2022)Scalar Replacement Considering Branch DivergenceJournal of Information Processing10.2197/ipsjjip.30.16430(164-178)Online publication date: 2022
https://doi.org/10.2197/ipsjjip.30.164
Krause P(2021)lospre in linear timeProceedings of the 24th International Workshop on Software and Compilers for Embedded Systems10.1145/3493229.3493304(35-41)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1145/3493229.3493304
Howar FJasper MMues MSchmidt DSteffen B(2021)The RERS challenge: towards controllable and scalable benchmark synthesisInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-021-00617-z23:6(917-930)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s10009-021-00617-z
Damani SSarkar V(2021)Common Subexpression Convergence: A New Code Optimization for SIMT ProcessorsLanguages and Compilers for Parallel Computing10.1007/978-3-030-72789-5_5(64-73)Online publication date: 26-Mar-2021
https://doi.org/10.1007/978-3-030-72789-5_5
Steffen BMurtovi A(2021)Generative Program Analysis and Beyond: The Power of Domain-Specific Languages (Invited Paper)Verification, Model Checking, and Abstract Interpretation10.1007/978-3-030-67067-2_3(29-51)Online publication date: 17-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-67067-2_3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Partial redundancy elimination in SSA form

Compiler transformations for effectively exploiting a zero overhead loop buffer

Redundancy Elimination in Distributed Matrix Computation

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations