Automating the Construction of Compiler Heuristics using Machine Learning

Designing optimizing compilers is a black art. Compiler writers are expected to create effective and inexpensive solutions to NP-hard problems such as instruction scheduling and register allocation. To make matters worse, separate optimization phases have strong interactions and competing resource constraints. Compiler writers deal with system complexity by dividing the problem into multiple phases and devising approximate heuristics for each phase. However, to achieve satisfactory performance, developers are forced to manually tweak their heuristics with trial-and-error experimentation.

In this talk I will discuss how to construct effective compiler heuristics with machine learning. In particular I will show how to automatically learn powerful heuristics for several important compiler problems: region formation, register allocation, loop unrolling, and adaptive recompilation. In most cases, the machine-learned heuristics perform much better than their state-of-the-art hand-crafted counterparts. By automatically collecting data and systematically analyzing them, my techniques discover non-obvious and non-trivial interactions that even experienced engineers would likely overlook. In addition to improving performance, my techniques have a significant impact on design complexity. Machine learning algorithms can design significant portions of a compiler heuristic, thereby freeing the human designer to focus on compiler correctness.

This work serves as a foundation for a general framework to custom tailor compilation technology to increasingly large applications and complex architectures. As industry shifts toward ever more complex systems, automated design techniques will be necessary to efficiently construct effective compilers.