Article

On the decidability of phase ordering problem in optimizing compilation

Authors:

Sid-Ahmed-Ali Touati,

Denis BarthouAuthors Info & Claims

CF '06: Proceedings of the 3rd conference on Computing frontiers

Pages 147 - 156

https://doi.org/10.1145/1128022.1128042

Published: 03 May 2006 Publication History

Abstract

We are interested in the computing frontier around an essential question about compiler construction: having a program P and a set M of non parametric compiler optimization modules (called also phases), is it possible to find a sequence s of these phases such that the performance (execution time for instance) of the final generated program P′ is "optimal" ? We prove in this article that this problem is undecidable in two general schemes of optimizing compilation: iterative compilation and library optimization/generation. Fortunately, we give some simplified cases when this problem be-comes decidable, and we provide some algorithms (not necessary efficient) that can answer our main question. Another essential question that we are interested in is parame-ters space exploration in optimizing compilation (tuning optimizing compilation parameters). In this case, we assume a fixed sequence of optimization, but each optimization phase is allowed to have a parameter. We try to figure out how to compute the best parameter values for all program transformations when the compilation sequence is given. We also prove that this general problem is undecidable and we provide some simplified decidable instances.

References

[1]

A. Cohen and S. Girbal and O. Temam. A Polyhedral Approach to Ease the Composition of Program Transformations. In Proceedings of Euro-Par'04, Aug. 2004.

[2]

B. Aarts and M. Barreteau and F. Bodin and P. Brinkhaus and Z. Chamski and H.-P. Charles and C. Eisenbeis and J. R. Gurd and J. Hoogerbrugge and P. Hu and W. Jalby and P. M. W. Knijnenburg and M. F. P. O'Boyle and E. Rohou and R. Sakellariou and H. Schepers and A. Seznec and E. A. Stohr and M. Verhoeven and H. A. G. Wijshoff. OCEANS: Optimizing Compilers for Embedded Applications. In Proceedings of EuroPar'97, Lecture Notes in Computer Science. Springer-Verlag, 1997.

Digital Library

[3]

C. Click and K. D. Cooper. Combining Analyses, Combining Optimizations. ACM Transactions on Programming Languages and Systems, 17(2):181--196, 1995.

Digital Library

[4]

D. Callahan, J. Cocke, and K. Kennedy. Estimating Interlock and Improving Balance for Pipelined Architectures. Journal of Parallel and Distributed Computing, 5(4):334--358, Aug. 1988.

Digital Library

[5]

K. D. Cooper, D. Subramanian, and L. Torczon. Adaptive Optimizing Compilers for the 21st Century. The Journal of Supercomputing, 23(1):7--22, 2002.

Digital Library

[6]

L. Eeckhout, H. Vandierendonck, and K. D. Bosschere. Quantifying the Impact of Input Data Sets on Program Behavior and its Applications. Journal of Instruction-Level Parallelism, 5, 2003. Electronic journal : www.jilp.org.

[7]

S. M. Freudenberger and J. C. Ruttenberg. Phase Ordering of Register Allocation and Instruction Scheduling. In Code Generation - Concepts, Tools, Techniques. Proceedings of the International Workshop on Code Generation, pages 146--172, London, 1992. Springer-Verlag.

[8]

M. Frigo. A Fast Fourier Transform Compiler. In Proc. of Programing Language Design and Implementation, 1999.

Digital Library

[9]

J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

Digital Library

[10]

J. P. Jones. Universal Diophantine Equation. Journal of Symbolic Logic, 47(3):403--410, 1982.

[11]

K. Kennedy, N. McIntosh, and K. McKinley. Static Performance Estimation in a Parallelizing Compiler. Technical Report CRPC-TR92204, Center for Research on Parallel Computation, Rice University, May 1992.

[12]

L. Almagor and K. D. Cooper and A. Grosul and T. J. Harvey and S. W. Reeves and D. Subramanian and L. Torczon and T. Waterman. Finding effective compilation sequences. In Proceeding of the Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'04), Washington, DC, June 2004. ACM.

Digital Library

[13]

M. E. Wolf and D. E. Maydan and D.-K. Chen. Combining Loop Transformations Considering Caches and Scheduling. International Journal of Parallel Programming, 26(4):479--503, 1998.

Digital Library

[14]

M. Pschel and J. M. F. Moura and J. Johnson and D. Padua and M. Veloso and B. Singer and J. Xiong and F. Franchetti and A. Gacic and Y. Voronenko and K. Chen and R. W. Johnson and N. Rizzolo. SPIRAL: Code Generation for DSP Transforms. Proceedings of the IEEE special issue on Program Generation, Optimization and Adaptation, (2):232--275, 2005.

[15]

M. Zhao and B. R. Childers and M. L. Soffa. A Model-Based Framework: An Approach for Profit-driven Optimization. In ACM SIGMICRO Int. Conference on Code Generation and Optimization (CGO'05), San Jose, California, Mar. 2005.

Digital Library

[16]

W. Mangione-Smith, T.-P. Shih, S. Abraham, and E. Davidson. Approaching a Machine-Application Bound in Delivered Performance on Scientifique Code. In Proceedings of the IEEE, volume 81, pages 1166--1178, Aug. 1993.

[17]

Y. Matiyasevich. Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets. Math. Comput. Simul., 67(1-2):125--133, 2004.

Digital Library

[18]

R. Jain. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. John Wiley and Sons, Inc., New York, 1991.

[19]

R. Whaley and A. Petitet and J. Dongarra. Automated Empirical Optimizations of Software and the ATLAS Project. Parallel Computing, 27(1-2):3--25, 2001. ISSN 0167--8191.

Digital Library

[20]

U. Schwiegelshohn, F. Gasperoni, and K. Ebcioglu. On Optimal Parallelization of Arbitrary Loops. Journal of Parallel and Distributed Computing, 11:130--134, 1991.

Digital Library

[21]

T. Alexander. Performance Prediction for Loop Restructuring Optimization. Master thesis, University of Carnegie Mellon. Physics/Computer Science Department, July 1993.

[22]

T. L. Veldhuizen and A. Lumsdaine. Guaranteed Optimization: Proving Nullspace Properties of Compilers. In 9th International Symposium on Static Analysis (SAS 2002). Lecture Notes in Computer Science., volume 2477, pages 263--277. springer, 2002.

Digital Library

[23]

K. B. Theobald, G. R. Gao, and L. J. Hendren. On the Limits of Program Parallelism and its Smoothability. In Wen-mei Hwu, editor, Proceedings of the 25th Annual International Symposium on Microarchitecture, pages 10--19, Portland, OR, Dec. 1992. IEEE.

Digital Library

[24]

S. Triantafyllis, M. Vachharajani, and D. I. August. Compiler Optimization-Space Exploration. Journal of Instruction-Level Parallelism, 7, Jan. 2005. Electronic journal: www.jilp.org.

[25]

K.-Y. Wang. Precise Compile-Time Performance Prediction for Superscalar-Based Computers. ACM SIGPLAN Notices, 29(6):73--84, June 1994.

Digital Library

[26]

D. Whitfield and M. L. Soffa. An Approach for Exploring Code-Improving Transformations. ACM Transactions on Programming Languages and Systems, 19(6):1053--1084, 1997.

Digital Library

Cited By

Theodoridis TSu Z(2024)Refined Input, Degraded Output: The Counterintuitive World of Compiler BehaviorProceedings of the ACM on Programming Languages10.1145/36564048:PLDI(671-691)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656404
Kœhler TGoens ABhat SGrosser TTrinder PSteuwer M(2024)Guided Equality SaturationProceedings of the ACM on Programming Languages10.1145/36329008:POPL(1727-1758)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632900
Zhang YChandra SBlincoe KTonella P(2023)Detection of Optimizations Missed by the CompilerProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3617846(2192-2194)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3617846
Show More Cited By

Index Terms

On the decidability of phase ordering problem in optimizing compilation
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Practical exhaustive optimization phase order exploration and evaluation

Choosing the most appropriate optimization phase ordering has been a long-standing problem in compiler optimizations. Exhaustive evaluation of all possible orderings of optimization phases for each function is generally dismissed as infeasible for ...
Optimizing compilation of constraint handling rules in HAL

In this paper we discuss the optimizing compilation of Constraint Handling Rules (CHRs). CHRs are a multi-headed committed choice constraint language, commonly applied for writing incremental constraint solvers. CHRs are usually implemented as a ...
Compiling with continuations, continued
Proceedings of the ICFP '07 conference

We present a series of CPS-based intermediate languages suitable for functional language compilation, arguing that they have practical benefits over direct-style languages based on A-normal form (ANF) or monads. Inlining of functions demonstrates the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CF '06: Proceedings of the 3rd conference on Computing frontiers

May 2006

430 pages

ISBN:1595933026

DOI:10.1145/1128022

General Chairs:
Monica Alderighi
IASF - INAF
,
Valentina Salapura
IBM
,
Program Chair:
Sally A. McKee
Cornell University

Copyright © 2006 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: 03 May 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CF06

Sponsor:

CF06: Computing Frontiers Conference

May 3 - 5, 2006

Ischia, Italy

Acceptance Rates

Overall Acceptance Rate 273 of 785 submissions, 35%

Upcoming Conference

CF '25

Sponsor:
sigmicro

22nd ACM International Conference on Computing Frontiers

May 28 - 30, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
441
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)3

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Theodoridis TSu Z(2024)Refined Input, Degraded Output: The Counterintuitive World of Compiler BehaviorProceedings of the ACM on Programming Languages10.1145/36564048:PLDI(671-691)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656404
Kœhler TGoens ABhat SGrosser TTrinder PSteuwer M(2024)Guided Equality SaturationProceedings of the ACM on Programming Languages10.1145/36329008:POPL(1727-1758)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632900
Zhang YChandra SBlincoe KTonella P(2023)Detection of Optimizations Missed by the CompilerProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3617846(2192-2194)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3617846
Theodoridis TRigger MSu ZFalsafi BFerdman MLu SWenisch T(2022)Finding missed optimizations through the lens of dead code eliminationProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507764(697-709)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3503222.3507764
Jain SAndaluri YVenkataKeerthy SUpadrasta R(2022)POSET-RL: Phase ordering for Optimizing Size and Execution Time using Reinforcement Learning2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)10.1109/ISPASS55109.2022.00012(121-131)Online publication date: May-2022
https://doi.org/10.1109/ISPASS55109.2022.00012
Nandi CWillsey MAnderson AWilcox JDarulova EGrossman DTatlock ZDonaldson ATorlak E(2020)Synthesizing structured CAD models with equality saturation and inverse transformationsProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3386012(31-44)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3386012
Ahmadvand MFischer DBanescu SBalenson D(2019)SIP shakerProceedings of the 35th Annual Computer Security Applications Conference10.1145/3359789.3359848(203-214)Online publication date: 9-Dec-2019
https://dl.acm.org/doi/10.1145/3359789.3359848
Leopoldseder DStadler LRigger MWürthinger TMössenböck HKell SMarr S(2018)A cost model for a graph-based intermediate-representation in a dynamic compilerProceedings of the 10th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3281287.3281290(26-35)Online publication date: 4-Nov-2018
https://dl.acm.org/doi/10.1145/3281287.3281290
Rigger MGrimmer MMössenböck H(2016)Sulong - execution of LLVM-based languages on the JVMProceedings of the 11th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems10.1145/3012408.3012416(1-4)Online publication date: 17-Jul-2016
https://dl.acm.org/doi/10.1145/3012408.3012416
Shaikhha AKlonatos YParreaux LBrown LDashti MKoch CÖzcan FKoutrika GMadden S(2016)How to Architect a Query CompilerProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2915244(1907-1922)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2915244
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents