Article

Free access

An approach to ordering optimizing transformations

Authors:

D. Whitfield,

M. L. SoffaAuthors Info & Claims

PPOPP '90: Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming

Pages 137 - 146

https://doi.org/10.1145/99163.99179

Published: 01 February 1990 Publication History

PDF eReader

Abstract

As an approach to deriving an application order of optimizing transformations, a framework is developed for examining the interactions of the transformations. The framework is based on an axiomatic specification technique and includes both pre-conditions and post conditions that must exist before and after applying optimizations. For a selected set of optimizations, the framework is used to determine those interactions among the optimizations that can create conditions and those that can destroy conditions for applying other optimizations. From these interactions, an application order is derived to obtain the potential benefits of the optimizations that can be applied to a program. In some cases, the ordering of a pair of optimizations is unambiguous in that one optimization can either create or destroy the conditions for the other. In the few cases where there is a cyclic interaction, the ordering is resolved based on the perceived importance of the two optimizations.

References

[1]

Alfred Aho and Jeffrey Ullman, in Principles of Compiler Design, Addison-Wesley Publishing Co., Reading, MA, 1979.

Digital Library

Google Scholar

[2]

Alfred Aho, Ravi Sethi, and Jeffrey Ullman, in Compilers Principles, Techniques, and Tools, Addison-Wesley Publishing Co., Reading, MA, 1986.

Digital Library

Google Scholar

[3]

Alexender Aiken and Alexandru Nicolau, "A Development Environment for Horizontal Microcode," IEEE Transactions of Software Engineering, vol. 14, no. 5, pp. 584-594, May 1988.

Digital Library

Google Scholar

[4]

Frances Allen, "Program Optimization," in Annual Review in Automatic Programming 5, ed. L. Bolliet et al., pp. 239-307, Pergammon Press, New York, 1969.

Google Scholar

[5]

Frances Allen and John Cocke, "A Catalogue of Optimizing Transformations," in Design and Optimization of Compilers, ed. R. Rustin, pp. 1-30, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971.

Google Scholar

[6]

Randy Allen and Ken Kennedy, "Automatic Translation of FORTRAN Programs to Vector Form," A CM Transactions of Programming Languages and Systems, vol. 9, no. 4, pp. 491-542, October 1987.

Digital Library

Google Scholar

[7]

Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren, "The Program Dependence Graph and its Use in Optimization," ACM TOPLAS, vol. 9, no. 3, pp. 319-349, 1987.

Digital Library

Google Scholar

[8]

Mahadevan Ganapathi and Charles N. Fischer, "Integrating Code Generation and Peephole Optimization," Acta lnformatica, vol. 25, no. 1, pp. 85- 109, Jan., 1988.

Digital Library

Google Scholar

[9]

C.A.R. H oare, "An Axiomatic Basis for Computer Programming," CACM, vol. 12, no. 10, pp. 576- 583, October 1969.

Digital Library

Google Scholar

[10]

David B. Loveman, "Program Improvement by Source-to-Source Transformation," JACM, vol. 24, no. 1, pp. 121-145, Jan 1977.

Digital Library

Google Scholar

[11]

David A. Padua and Michael J. Wolfe, "Advanced Compiler Optimizations for Supercomputers," Communications of the ACM, vol. 29, no. 12, pp. 1184-1201, Dec 1986.

Digital Library

Google Scholar

[12]

Lori L. Pollock and Mary Lou Sofia, "Incremental Global Optimization for Faster Recompilation,'" Proceedings of IEEE International Conference on Computer Languages '90, March 1990.

Google Scholar

[13]

Michael Wolfe and Uptal Banerjee, "Data Dependence and Its Application to Parallel Processing," international Journal of Parallel Programming, vol. 16, no. 2, pp. 137-178, 1987.

Digital Library

Google Scholar

[14]

Michael Wolfe, in Optimizing Supercompilers for Supercomputers, The MIT Press, Cambridge, MA, 1989.

Digital Library

Google Scholar

Cited By

View all

Aragón-Jurado Jde la Torre JRuiz PGalindo PZomaya ADorronsoro B(2024)Automatic Software Tailoring for Optimal PerformanceIEEE Transactions on Sustainable Computing10.1109/TSUSC.2023.33306719:3(464-481)Online publication date: May-2024
https://doi.org/10.1109/TSUSC.2023.3330671
Pourmirza SPeters SDijkman RGrefen P(2019)BPMS-RAACM Transactions on Internet Technology10.1145/323267719:1(1-23)Online publication date: 18-Feb-2019
https://dl.acm.org/doi/10.1145/3232677
Billingsley WTorbay RFletcher PThomas RSteel JSüß J(2019)Taking a Studio Course in Distributed Software Engineering from a Large Local Cohort to a Small Global CohortACM Transactions on Computing Education10.1145/321828419:2(1-27)Online publication date: 9-Jan-2019
https://dl.acm.org/doi/10.1145/3218284
Show More Cited By

Index Terms

An approach to ordering optimizing transformations
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
        Concurrent programming structures

Recommendations

An approach to ordering optimizing transformations

As an approach to deriving an application order of optimizing transformations, a framework is developed for examining the interactions of the transformations. The framework is based on an axiomatic specification technique and includes both pre-...
A unifying framework for optimizing transformations
Structuring Optimizing Transformations and Proving Them Sound

A compiler optimization is sound if the optimized program that it produces is semantically equivalent to the input program. The proofs of semantic equivalence are usually tedious. To reduce the efforts required, we identify a set of common ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PPOPP '90: Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming

February 1990

206 pages

ISBN:0897913507

DOI:10.1145/99163

Chairman:
David Padua
Univ. of Illinois at Urbana/Champaign, Urbana

ACM SIGPLAN Notices Volume 25, Issue 3
Mar. 1990
216 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/99164
Editor:
David Padua
Univ. of Illinois at Urbana/Champaign, Urbana
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 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PPOPP90

Sponsor:

SIGPLAN

PPOPP90: Principals & Practice of Parallel Processing

March 14 - 16, 1990

Washington, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

71
Total Citations
View Citations
647
Total Downloads

Downloads (Last 12 months)100
Downloads (Last 6 weeks)23

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Aragón-Jurado Jde la Torre JRuiz PGalindo PZomaya ADorronsoro B(2024)Automatic Software Tailoring for Optimal PerformanceIEEE Transactions on Sustainable Computing10.1109/TSUSC.2023.33306719:3(464-481)Online publication date: May-2024
https://doi.org/10.1109/TSUSC.2023.3330671
Pourmirza SPeters SDijkman RGrefen P(2019)BPMS-RAACM Transactions on Internet Technology10.1145/323267719:1(1-23)Online publication date: 18-Feb-2019
https://dl.acm.org/doi/10.1145/3232677
Billingsley WTorbay RFletcher PThomas RSteel JSüß J(2019)Taking a Studio Course in Distributed Software Engineering from a Large Local Cohort to a Small Global CohortACM Transactions on Computing Education10.1145/321828419:2(1-27)Online publication date: 9-Jan-2019
https://dl.acm.org/doi/10.1145/3218284
Eshuis RHull RYi M(2019)Reasoning About Property Preservation in Adaptive Case ManagementACM Transactions on Internet Technology10.1145/317777819:1(1-21)Online publication date: 25-Jan-2019
https://dl.acm.org/doi/10.1145/3177778
Ouni AWang HKessentini MBouktif SInoue K(2018)A Hybrid Approach for Improving the Design Quality of Web Service InterfacesACM Transactions on Internet Technology10.1145/322659319:1(1-24)Online publication date: 22-Dec-2018
https://dl.acm.org/doi/10.1145/3226593
Andersson BKim HNiz DKlein MRajkumar RLehoczky J(2018)Schedulability Analysis of Tasks with Corunner-Dependent Execution TimesACM Transactions on Embedded Computing Systems10.1145/320340717:3(1-29)Online publication date: 22-May-2018
https://dl.acm.org/doi/10.1145/3203407
Vasilios KGeorgios KNikolaos V(2018)Combining Software Cache Partitioning and Loop Tiling for Effective Shared Cache ManagementACM Transactions on Embedded Computing Systems10.1145/320266317:3(1-25)Online publication date: 22-May-2018
https://dl.acm.org/doi/10.1145/3202663
Ashouri AKillian WCavazos JPalermo GSilvano C(2018)A Survey on Compiler Autotuning using Machine LearningACM Computing Surveys10.1145/319797851:5(1-42)Online publication date: 18-Sep-2018
https://dl.acm.org/doi/10.1145/3197978
Mahmud RRamamohanarao KBuyya R(2018)Latency-Aware Application Module Management for Fog Computing EnvironmentsACM Transactions on Internet Technology10.1145/318659219:1(1-21)Online publication date: 30-Nov-2018
https://dl.acm.org/doi/10.1145/3186592
RASTGOO MNakisa BRakotonirainy AChandran VTjondronegoro D(2018)A Critical Review of Proactive Detection of Driver Stress Levels Based on Multimodal MeasurementsACM Computing Surveys10.1145/318658551:5(1-35)Online publication date: 4-Sep-2018
https://dl.acm.org/doi/10.1145/3186585
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

An approach to ordering optimizing transformations

A unifying framework for optimizing transformations

Structuring Optimizing Transformations and Proving Them Sound