Compiler optimisation is the process of making a compiler produce better code, i.e. code that,
for example, runs faster on a target architecture. Although numerous program transformations
for optimisation have been proposed in the literature, these transformations are not always beneficial and they can interact in very complex ways. Traditional approaches adopted by compiler
writers fix the order of the transformations and decide when and how these transformations
should be applied to a program by using hard-coded heuristics. However, these heuristics require a lot of time and effort to construct and may sacrifice performance on programs they have
not been tuned for.
This thesis proposes a probabilistic machine learning solution to the compiler optimisation problem that automatically determines "good" optimisation strategies for programs. This
approach uses predictive modelling in order to search the space of compiler transformations.
Unlike most previous work that learns when/how to apply a single transformation in isolation or
a fixed-order set of transformations, the techniques proposed in this thesis are capable of tackling the general problem of predicting "good" sequences of compiler transformations. This is
achieved by exploiting transference across programs with two different techniques: Predictive
Search Distributions (PSD) and multi-task Gaussian process prediction (multi-task GP). While
the former directly addresses the problem of predicting "good" transformation sequences, the
latter learns regression models (or proxies) of the performance of the programs in order to
rapidly scan the space of transformation sequences.
Both methods, PSD and multi-task GP, are formulated as general machine learning techniques. In particular, the PSD method is proposed in order to speed up search in combinatorial
optimisation problems by learning a distribution over good solutions on a set of problem in¬
stances and using that distribution to search the optimisation space of a problem that has not
been seen before. Likewise, multi-task GP is proposed as a general method for multi-task learning that directly models the correlation between several machine learning tasks, exploiting the
shared information across the tasks.
Additionally, this thesis presents an extension to the well-known analysis of variance
(ANOVA) methodology in order to deal with sequence data. This extension is used to address the problem of optimisation space characterisation by identifying and quantifying the
main effects of program transformations and their interactions.
Finally, the machine learning methods proposed are successfully applied to a data set that
has been generated as a result of the application of source-to-source transformations to 12 C
programs from the UTDSP benchmark suite.