article

ACME: adaptive compilation made efficient

Authors:

Keith D. Cooper,

Alexander Grosul,

Timothy J. Harvey,

Devika Subramanian,

Todd WatermanAuthors Info & Claims

ACM SIGPLAN Notices, Volume 40, Issue 7

Pages 69 - 77

https://doi.org/10.1145/1070891.1065921

Published: 15 June 2005 Publication History

Abstract

Research over the past five years has shown significant performance improvements using a technique called adaptive compilation. An adaptive compiler uses a compile-execute-analyze feedback loop to find the combination of optimizations and parameters that minimizes some performance goal, such as code size or execution time.Despite its ability to improve performance, adaptive compilation has not seen widespread use because of two obstacles: the large amounts of time that such systems have used to perform the many compilations and executions prohibits most users from adopting these systems, and the complexity inherent in a feedback-driven adaptive system has made it difficult to build and hard to use.A significant portion of the adaptive compilation process is devoted to multiple executions of the code being compiled. We have developed a technique called virtual execution to address this problem. Virtual execution runs the program a single time and preserves information that allows us to accurately predict the performance of different optimization sequences without running the code again. Our prototype implementation of this technique significantly reduces the time required by our adaptive compiler.In conjunction with this performance boost, we have developed a graphical-user interface (GUI) that provides a controlled view of the compilation process. By providing appropriate defaults, the interface limits the amount of information that the user must provide to get started. At the same time, it lets the experienced user exert fine-grained control over the parameters that control the system.

References

[1]

L. Almagor, Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steven W. Reeves, Devika Subramanian, Linda Torczon, and Todd Waterman. Finding effective compilation sequences. In Proceedings of LCTES 2004, pages 231--239, June 2004.

Digital Library

[2]

Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting equality of variables in programs. In Conference Record of th 15th POPL, pages 1--11, San Diego, CA, USA, January 1988.

Digital Library

[3]

Thomas Ball and James R. Larus. Optimally profiling and tracing programs. In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Programming Languages, pages 59--70, January 1992.

Digital Library

[4]

Preston Briggs. The Massively Scalar Compiler Project. Appendix B of a nuweb document that forms part of the Mscp infrastructure. Available online as www.cs.rice.edu/~keith/EAC/iloc.pdf., July 1994.

[5]

Preston Briggs and Keith D. Cooper. Effective partial redundancy elimination. In Proceedings of ACM SIGPLAN 94 PLDI, pages 159--170, June 1994.

Digital Library

[6]

Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. Register allocation via graph coloring. Computer Languages, 6(1):47--57, January 1981.

Digital Library

[7]

Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steve Reeves, Devika Subramanian, Linda Torczon, and Todd Waterman. Searching for compilation sequences. 2005. Submitted for publication.

[8]

Keith D. Cooper, Philip J. Schielke, and Devika Subramanian. Optimizing for reduced code space using genetic algorithms. In Proceedings of LCTES 1999, pages 1--9, May 1999.

Digital Library

[9]

Keith D. Cooper, Devika Subramanian, and Linda Torczon. Adaptive optimizing compilers for the 21st century. In Proceedings of the 2001 LACSI Symposium. Los Alamos Computer Science Institute, Santa Fe, NM, October 2001.

[10]

Keith D. Cooper and Linda Torczon. Engineering a Compiler. Morgan-Kaufmann Publishers, 2003.

[11]

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM TOPLAS, 13(4):451--490, October 1991.

Digital Library

[12]

Jack W. Davidson and Christopher W. Fraser. The design and application of a retargetable peephole optimizer. ACM TOPLAS, 2(2):191--202, April 1980.

Digital Library

[13]

Susan L. Graham, Peter B. Kessler, and Marshall K. McKusick. gprof: a call graph execution profiler. In Proceedings of the 1982 SIGPLAN Symposium on Compiler Constrion, pages 120--126, June 1982.

Digital Library

[14]

Elana Granston and Anne Holler. Automatic recommendation of compiler options. In Proceedings of the 4th Feedback Directed Optimization Workshop, December 2001.

[15]

Alexander Grosul. Adaptive Ordering of Code Transformations in an Optimizing Compiler. PhD thesis, Rice University, 2005.

Digital Library

[16]

Jin-Kao Hao, Frédéric Lardeux, and Frédéric Saubion. A hybrid genetic algorithm for the satisfiability problem. In Proceedings of the First International Workshop on Heuristics, Beijing, China, July 2002.

[17]

Toru Kisuki, Peter M.W. Knijnenburg, and Michael F.P. O'Boyle. Combined selection of tile sizes and unroll factors using iterative compilation. In Proceedings of PACT '00, pages 237--248, October 2000.

Digital Library

[18]

Jens Knoop, Oliver Rüthing, and Bernhard Steffen. Lazy code motion. In Proceedings of the ACM SIGPLAN 92 PLDI, pages 224--234, July 1992.

Digital Library

[19]

Prasad Kulkarni, Stephen Hines, Jason Hiser, David Whalley, Jack Davidson, and Douglas Jones. Searches for effective optimization phase sequences. In Proceedings of ACM SIGPLAN 2004 PLDI, pages 171--182, May 2004.

Digital Library

[20]

Prasad Kulkarni, Wankang Zhao, Hwashin Moon, Kyunghwan Cho, David Whaley, Jack Davidson, Mark Bailey, Yunheung Paek, and Kyle Gallivan. Finding effective optimization phase sequences. In Proceedings of the 2003 ACM SIGPLAN Conference on Languages, Tools, and Compilers for Embedded Systems, pages 12--23, June 2003.

Digital Library

[21]

Kathryn S. McKinley, Steve Carr, and Chau-Wen Tseng. Improving data locality with loop transformations. ACM Transactions on Programming Languages and Systems (TOPLAS), 18(4):424--453, July 1996.

Digital Library

[22]

Etienne Morel and Claude Renvoise. Global optimization by suppression of partial redundancies. Communications of the ACM, 22(2):96--103, February 1979.

Digital Library

[23]

L. Taylor Simpson. Value-Driven Redundancy Elimination. PhD thesis, Rice University, 1996.

Digital Library

[24]

Mark Stephenson, Saman Amarasinghe, Martin Martin, and Una-May O'Reilly. Meta optimization: improving compiler heuristics with machine learning. In Proceedings of the ACM SIGPLAN 2003 PLDI, pages 77--90, May 2003.

Digital Library

[25]

Spyridon Triantifyllis, Manish Vachharajani, Neil Vachharajani, and David I. August. Compiler optimization-space exploration. In Proceedings of the 1st CGO, March 2003.

Digital Library

[26]

Mark Wegman and F. Kenneth Zadeck. Constant propagation with conditional branches. ACM TOPLAS, 13(2):181--210, April 1991.

Digital Library

[27]

Deborah L. Whitfield and Mary Lou Soffa. An approach for exploring code improving transformations. ACM TOPLAS, 19(6):1053--1084, November 1997.

Digital Library

[28]

M. Zhao, B. Childers, and M.L. Soffa. Predicting the impact of optimizations for embedded systems. In Proceedings of LCTES 2003, pages 1--11, June 2003.

Digital Library

Cited By

Zhuang YLin THuang Y(2023)The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combineConnection Science10.1080/09540091.2023.227321935:1Online publication date: 30-Oct-2023
https://doi.org/10.1080/09540091.2023.2273219
Da Silva JLeão LPetrucci VGamatié APereira F(2021)Mapping Computations in Heterogeneous Multicore Systems with Statistical Regression on Program InputsACM Transactions on Embedded Computing Systems10.1145/347828820:6(1-35)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3478288
Sebastio SBaranov EBiondi FDecourbe OGiven-Wilson TLegay APuodzius CQuilbeuf J(2020)Optimizing Symbolic Execution for Malware Behavior ClassificationComputers & Security10.1016/j.cose.2020.101775(101775)Online publication date: Feb-2020
https://doi.org/10.1016/j.cose.2020.101775
Show More Cited By

Index Terms

ACME: adaptive compilation made efficient
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

ACME: adaptive compilation made efficient
LCTES '05: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

Research over the past five years has shown significant performance improvements using a technique called adaptive compilation. An adaptive compiler uses a compile-execute-analyze feedback loop to find the combination of optimizations and parameters ...
Investigating Adaptive Compilation Using the Mipspro Compiler

Despite the astonishing increases in processor performance over the last 40 years, delivered application performance remains a critical issue for many important problems. Compilers play a critical role in determining that performance. A modern ...
Reducing virtual call overheads in a Java VM just-in-time compiler
Special issue on interaction between compilers and computer architectures

Java, an object-oriented language, uses virtual methods to support the extension and reuse of classes. Unfortunately, virtual method calls affect performance and thus require an efficient implementation, especially when just-in-time (JIT) compilation is ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 40, Issue 7

Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

July 2005

238 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1070891

Issue’s Table of Contents

LCTES '05: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems
June 2005
248 pages
ISBN:1595930183
DOI:10.1145/1065910
General Chair:
Yunheung Paek
Seoul National University, Seoul, Korea
,
Program Chair:
Rajiv Gupta
University of Arizona, Tucson, USA

Copyright © 2005 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2005

Published in SIGPLAN Volume 40, Issue 7

Check for updates

Author Tag

adaptive compilation

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

80
Total Citations
View Citations
750
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)4

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhuang YLin THuang Y(2023)The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combineConnection Science10.1080/09540091.2023.227321935:1Online publication date: 30-Oct-2023
https://doi.org/10.1080/09540091.2023.2273219
Da Silva JLeão LPetrucci VGamatié APereira F(2021)Mapping Computations in Heterogeneous Multicore Systems with Statistical Regression on Program InputsACM Transactions on Embedded Computing Systems10.1145/347828820:6(1-35)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3478288
Sebastio SBaranov EBiondi FDecourbe OGiven-Wilson TLegay APuodzius CQuilbeuf J(2020)Optimizing Symbolic Execution for Malware Behavior ClassificationComputers & Security10.1016/j.cose.2020.101775(101775)Online publication date: Feb-2020
https://doi.org/10.1016/j.cose.2020.101775
Memeti SPllana SBinotto AKołodziej JBrandic I(2019)Using meta-heuristics and machine learning for software optimization of parallel computing systemsComputing10.1007/s00607-018-0614-9101:8(893-936)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s00607-018-0614-9
Memeti SPllana SBinotto AKołodziej JBrandic I(2018)A Review of Machine Learning and Meta-heuristic Methods for Scheduling Parallel Computing SystemsProceedings of the International Conference on Learning and Optimization Algorithms: Theory and Applications10.1145/3230905.3230906(1-6)Online publication date: 2-May-2018
https://dl.acm.org/doi/10.1145/3230905.3230906
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
Ashouri ABignoli APalermo GSilvano CKulkarni SCavazos J(2017)MiCOMPACM Transactions on Architecture and Code Optimization10.1145/312445214:3(1-28)Online publication date: 6-Sep-2017
https://dl.acm.org/doi/10.1145/3124452
Kelefouras V(2017)A methodology pruning the search space of six compiler transformations by addressing them together as one problem and by exploiting the hardware architecture detailsComputing10.1007/s00607-016-0535-499:9(865-888)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s00607-016-0535-4
Roy ABalaprakash PHovland PWild S(2016)Exploiting Performance Portability in Search Algorithms for Autotuning2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW.2016.85(1535-1544)Online publication date: May-2016
https://doi.org/10.1109/IPDPSW.2016.85
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.

Figures

Tables

Media

View Issue’s Table of Contents