Enhancing Bayesian Optimization for Compiler Auto-tuning

Modern compilers offer a wide range of passes for code optimisation. Selecting the right combination and order of these passes, known as phase ordering, can improve the performance of compiled binaries. Autotuning, which refers to automatically searching the space of possible pass combinations, is a powerful technique for compiler phase ordering. However, its practical adoption remains challenging due to the vast search space of compiler optimisations and the high cost of evaluating candidate configurations.

This thesis enhances compiler autotuning by leveraging Bayesian optimisation (BO) to efficiently explore the complex space of compiler phase ordering. BO builds an online surrogate model to approximate the objective function to reduce evaluation overhead. It uses an acquisition function (AF) to guide sampling, improving search efficiency. While promising, applying BO to compiler autotuning requires addressing multiple open challenges.

First, standard BO struggles with high-dimensional search spaces like compiler phase ordering. To address this, this thesis introduces a simple yet effective AF initialisation strategy to enhance BO's ability to navigate high-dimensional optimisation spaces.

Second, the complex interactions between compiler passes make it difficult to model the relationship between pass sequences and performance to build an effective surrogate model. To tackle this, a new compiler autotuning strategy is proposed to incorporate compilation statistics to model these interactions. This method improves BO's search efficiency, requiring only one-third of the search budget compared to previous approaches while delivering higher-performance binaries.

Finally, a real-world program often contains multiple source files and complex compilation workflows. Applying compiler autotuning to such settings requires efficiently allocating the search budget across the compilation targets. To address this, this thesis presents an adaptive BO scheme that dynamically allocates search budgets across source files and develops a framework to automate compiler autotuning setup.

Together, these contributions improve the efficiency, scalability, and usability of BO-based compiler autotuning, making it a more practical tool for autotuning compiler phase ordering.