2021

MLGO: a Machine Learning Guided Compiler Optimizations Framework

Trofin, Mircea, Qian, Yundi, Brevdo, Eugene et al.

Understand

Leveraging machine-learning (ML) techniques for compiler optimizations has been widely studied and explored in academia.

However, the adoption of ML in general-purpose, industry strength compilers has yet to happen.
We propose MLGO, a framework for integrating ML techniques systematically in an industrial compiler -- LLVM.
As a case study, we present the details and results of replacing the heuristics-based inlining-for-size optimization in LLVM with machine learned models.

Built on

Simple statistical gradient-following algorithms for connectionist reinforcement learning
Ronald J Williams. 1992 · 1992
Earlier work this paper cites.
Training Compilers for Better Inlining Decisions
Jeffrey Dean, Jeffrey Dean, Craig Chambers, and Craig Chambers. 1993 · 1993
Earlier work this paper cites.
A Framework for Behavioural Cloning.. In Machine Intelligence 15 . 103–129
Michael Bain and Claude Sammut. 1995 · 1995
Earlier work this paper cites.
Learning to Schedule Straight-Line Code (NIPS 1997) . 029– 935
Eliot Moss, Paul Utgoff, John Cavazos, Bordley Carla, and David Scheeff. [n.d.] · 1997
Earlier work this paper cites.
Learning to Schedule Straight-Line Code
J. Eliot B. Moss, Paul E. Utgoff, John Cavazos, Doina Precup, Darko Stefanovic, Carla E. Brodley, and David Scheeff. 1998 · 1998
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation. In Advances in neural information processing systems . 1057–1063
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. 2000 · 2000
Earlier work this paper cites.
Building a Basic Block Instruction Scheduler with Reinforcement Learning and Rollouts
Amy McGovern, Eliot Moss, and Andrew G. Barto. 2002 · 2002
Earlier work this paper cites.
Automatic tuning of inlining heuristics. In SC’05: Proceedings of the 2005 ACM/IEEE Conference on Supercomputing . IEEE, 14–14
John Cavazos and Michael FP O’Boyle. 2005 · 2005
Earlier work this paper cites.
Predicting Unroll Factors Using Supervised Classification. In Proceedings of the International Symposium on Code Generation and Optimization (CGO ’05) . IEEE Computer Society, Washington, DC, USA, 123–134
Mark Stephenson and Saman Amarasinghe. 2005 · 2005
Earlier work this paper cites.
Automating the Construction of Compiler Heuristics Using Machine Learning
Mark W. Stephenson. 2006 · 2006
Earlier work this paper cites.
An Adaptive Strategy for Inline Substitution
Waterman T. Cooper K.D., Harvey T.J. 2008 · 2008
Earlier work this paper cites.

Similar

Milepost GCC: Machine Learning Enabled Self-tuning Compiler
Grigori Fursin, Yuriy Kashnikov, Abdul Wahid Memon, Zbigniew Chamski, Olivier Temam, Mircea Namolaru, Elad Yom-Tov, Bilha Mendelson, Ayal Zaks, Eric Courtois, François Bodin, Phil Barnard, Elton Ashton, Edwin V. Bonilla, John Thomson, Christopher K. I. Williams, and Michael F. P. O’Boyle. 2011 · 2011
Cited alongside, same era.
Reinforcement learning in robotics: A survey
Jens Kober, J Andrew Bagnell, and Jan Peters. 2013 · 2013
Cited alongside, same era.
Playing atari with deep reinforcement learning
Original
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. 2013 · 2013
Cited alongside, same era.
Automatic Construction of Inlining Heuristics Using Machine Learning. In Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO) (CGO ’13) . IEEE Computer Society, Washington, DC, USA, 1–12
Douglas Simon, John Cavazos, Christian Wimmer, and Sameer Kulkarni. 2013 · 2013
Cited alongside, same era.
Semantic locality and context-based prefetching using reinforcement learning. In 2015 ACM/IEEE 42nd Annual International Symposium on Computer Architecture (ISCA) . 285–297
L. Peled, S. Mannor, U. Weiser, and Y. Etsion. 2015 · 2015
Cited alongside, same era.
Tensorflow: A system for large-scale machine learning. In 12th { \{ USENIX } \} symposium on operating systems design and implementation ( { \{ OSDI } \} 16) . 265–283
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al · 2016
Cited alongside, same era.
Learning to superoptimize programs
Original
Rudy Bunel, Alban Desmaison, M Pawan Kumar, Philip HS Torr, and Pushmeet Kohli. 2016 · 2016
Cited alongside, same era.
Mastering the game of Go with deep neural networks and tree search
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al · 2016
Cited alongside, same era.
End-to-end Deep Learning of Optimization Heuristics
Chris Cummins, Pavlos Petoumenos, Zheng Wang, and Hugh Leather. 2017 · 2017
Cited alongside, same era.
Inductive representation learning on large graphs. In Advances in neural information processing systems . 1024–1034
Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017 · 2017
Cited alongside, same era.
Tensorflow Agents
unspecified. 2020a
Cited in the paper.
Tensorflow tf.train.SequenceExample
unspecified. 2020b
Cited in the paper.

Then

Evolution strategies as a scalable alternative to reinforcement learning
Original
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. 2017 · 2017
Later among the works it cites.
Proximal policy optimization algorithms
Original
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017 · 2017
Later among the works it cites.
XLA — Tensorflow, Compiled
unspecified. 2020d · 2017
Later among the works it cites.
Learning to Optimize Tensor Programs
Original
Tianqi Chen, Lianmin Zheng, Eddie Q. Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018 · 2018
Later among the works it cites.
Structured evolution with compact architectures for scalable policy optimization
Original
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard E Turner, and Adrian Weller. 2018 · 2018
Later among the works it cites.
Learning Memory Access Patterns (ICML, 2018)
M. Hashemi, K. Swersky, G. Ayers A. Smith, J. Chang H. Litz, C. Kozyrakis, and P. Ranganathan. 2018 · 2018
Later among the works it cites.
Machine Learning in Compiler Optimization
Zheng Wang and Michael O’Boyle. 2018 · 2018
Later among the works it cites.
Learning to optimize Halide with tree search and random programs (ACM Transactions on Graphics) . 2–12
Andrew Adams, Karima Ma, Luke Anderson, Riyadh Baghdadi, Tzumao Li, Michael Charbi, Benoit Steiner, Steven Johnson, Kayvon Fatahlian, Fredo Durand, and Jonathan Regan-kelley. 2019 · 2019
Later among the works it cites.
code2vec: Learning distributed representations of code
Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav. 2019 · 2019
Later among the works it cites.
NeuroVectorizer: End-to-End Vectorization with Deep Reinforcement Learning. In Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization (CGO 2020) . Association for Computing Machinery, New York, NY, USA, 242–255
Ameer Haj-Ali, Nesreen K. Ahmed, Ted Willke, Yakun Sophia Shao, Krste Asanovic, and Ion Stoica. 2020 · 2020
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…