Abstract
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 optimisation 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 dissertation I present meta optimization, a
methodology for automatically constructing high quality
compiler heuristics using machine learning techniques.
This thesis describes machine-learned heuristics for
three important compiler optimisations: hyperblock
formation, register allocation, and loop unrolling. The
machine-learned heuristics outperform (by as much as 3x
in some cases) their state-of-the-art hand-crafted
counterparts. By automatically collecting data and
systematically analysing them, my techniques discover
subtle interactions that even experienced engineers
would likely overlook. In addition to improving
performance, my techniques can significantly reduce the
human effort involved in compiler design. Machine
learning algorithms can design critical portions of
compiler heuristics, thereby freeing the human designer
to focus on compiler correctness.
The progression of experiments I conduct in this thesis
leads to collaborative compilation, an approach which
enables ordinary users to transparently train compiler
heuristics by running their applications as they
normally would. The collaborative system automatically
adapts itself to the applications in which a community
of users is interested.
Users
Please
log in to take part in the discussion (add own reviews or comments).