Machine-Learning-Based Optimization Heuristics in Dynamic Compilers<

Raphael Mosaner

Abstract

Modern, optimizing compilers rely on hundreds of heuristics to decide whether and how to apply optimizations during compilation. These heuristics are typically hand-crafted and designed to achieve good performance on a set of benchmark programs which are based on real-world applications. This manual process has multiple shortcomings: It requires experienced compiler engineers as well as continuous re-evaluation and tweaking of heuristics if compiler internals change. In addition, maintaining multiple, domain-specific heuristics is often considered infeasible, which results in the deployment of one-size-fits-all heuristics.

Data-driven approaches, based on machine learning, have been shown to outperform hand-crafted compiler heuristics in that they can suggest optimization decisions which yield better performing programs after compilation. Nevertheless, only a single recent machine learning approach has made it into a production-level compiler. Existing research primarily focuses on using machine learning in static compilers, where the compilation process is stable and reproducible. In contrast, dynamic compilers run in parallel to the executed program where they compile frequently executed code. On top of that, the use of profiling-based speculative optimizations adds an additional level of non-determinism to dynamic compilation. This lack of consistency aggravates the use of data-driven approaches in such systems.

In this thesis, we make multiple contributions to the use of machine learning in dynamic compilers. We address the problems of data stability and consistency by proposing compilation forking, a technique for extracting performance data from method-local optimization decisions in arbitrary programs. Based on this data, we train several machine learning models to replace optimization heuristics for loop optimizations, such as peeling, unrolling or vectorization. Furthermore, we present self-optimizing compiler heuristics, based on machine learning models which are continuously refined with new data at the user site. This approach also enables the creation of domain-specific heuristics which we showed to outperform one-size-fits-all heuristics significantly. Apart from deploying machine learning in production systems, we also outline how models can assist compiler engineers during heuristics design and evaluation.

We implemented our approaches in the GraalVM compiler, which is among the most highly optimizing Java compilers on the market. Our learned models are either on par with the well-tuned heuristics in the GraalVM or outperform them significantly with only minor regressions. In addition to that, our assistive approach enabled improvements in existing heuristics without the actual deployment of machine learning models in production systems.

Kurzfassung

Moderne optimierende Compiler verwenden hunderte von Heuristiken um zu entscheiden, ob und wie Optimierungen während einer Compilation durchgeführt werden sollen. Diese Heuristiken werden typischerweise von Hand geschrieben und sind dahingehend optimiert, dass sie für gewisse Referenzprogramme, die auf realen Programmen basieren, gute Ergebnisse liefern. Dieser manuelle Prozess hat aber mehrere Nachteile: Das Erstellen von Heuristiken erfordert erfahrene Compiler-Ingenieure, die diese Heuristiken nach Änderungen im Compiler ständig neu bewerten und anpassen müssen. Außerdem ist es meist nicht praktikabel, mehrere Heuristiken für verschiedene Anwendungsdomänen zu warten, weshalb Heuristiken in der Regel allgemein gehalten sind.

In der Literatur wurde bereits gezeigt, dass datengetriebene Ansätze, die auf maschinellem Lernen basieren, zu besseren Optimierungsentscheidungen führen als händisch erzeugte Heuristiken, was die Performanz von übersetzten Programmen verbessert. Trotzdem hat es bisher nur ein einziger Ansatz mit maschinellem Lernen in einen bekannten, kommerziell genutzten Compiler geschafft. Existierende Forschungsarbeiten konzentrieren sich vor allem auf statische Compiler, bei denen der Übersetzungsprozess sehr stabil und reproduzierbar ist. Im Gegensatz dazu übersetzen dynamische Compiler Codeteile zu nicht vorhersehbaren Zeitpunkten während der Programmausführung. Zusätzlich führen spekulative Optimierungen, die auf Nutzungsprofilen basieren, zu einem gewissen Nicht-Determinismus im Compiler. Der Mangel an Reproduzierbarkeit erschwert den Einsatz datengetriebener Ansätze in solchen Systemen.

In dieser Dissertation tragen wir in mehrfacher Hinsicht zum Einsatz von maschinellem Lernen in dynamischen Compilern bei. Wir sorgen für die Stabilität und Konsistenz von dynamischer Übersetzung indem wir Compilation Forking vorstellen, das es uns erlaubt, die Effektivität von Optimierungsentscheidungen innerhalb von Methoden beliebiger Programme zu messen. Basierend auf diesen Messdaten, trainieren wir verschiedene Modelle mittels maschinellem Lernen und ersetzen damit manuelle Heuristiken für Schleifenoptimierungen, wie Peeling, Unrolling und Vektorisierung. Ferner präsentieren wir einen Ansatz, um Heuristiken fortlaufend zu optimieren, indem das dahinterstehende Modell wiederholt mit neuen Daten zur Laufzeit trainiert und verbessert wird. Dieser Ansatz erlaubt es auch, Heuristiken für spezielle Anwendungsdomänen zu erzeugen, die, wie wir zeigen konnten, bessere Ergebnisse liefern als allgemein gehaltene Heuristiken. Neben dem tatsächlichen Einsatz von maschinell trainierten Modellen zur Laufzeit, zeigen wir auch, wie diese Modelle Ingenieuren helfen können, die bestehenden Heuristiken zu verbessern und zu evaluieren.Alle unsere Ansätze wurden im GraalVM Compiler implementiert, einem der besten optimierenden Java Compiler am Markt. Unsere trainierten Modelle liefern zumindest ähnliche Ergebnisse wie die manuell optimierten Heuristiken im GraalVM Compiler; oft sind unsere Modelle signifikant besser und nur selten etwas schlechter. Zusätzlich unterstützt unser Ansatz Ingenieure bei der Verbesserungen der manuell erstellten Heuristi

PhD thesis, Johannes Kepler University Linz, April 2023