Trace Register Allocation

Josef Eisl

Abstract

Register allocation, i.e., mapping the variables of a programming language to the physical registers of a processor, is a mandatory task for almost every compiler and consumes a significant portion of the compile time. In a just-in-time compiler, compile time is a particular issue because compilation happens during program execution and contributes to the overall application run time. Compilers often use global register allocation approaches, such as graph coloring or linear scan, which only have limited potential for improving compile time since they process a whole method at once. With growing methods sizes, these approaches are reaching their scalability boundary due to their limited flexibility.

We developed a novel trace register allocation framework, which competes with global approaches in both, compile time and code quality. Instead of processing a whole method at once, our allocator processes linear code segments (traces) independently and is therefore able to (1) select different allocation strategies based on the characteristics of a trace in order to control the tradeoff between compile time and peak performance, and (2) to allocate traces in parallel in order to reduce compilation latency, i.e., the time until the result of a compilation is available.

We implemented our approach in GraalVM, a production-quality Java Virtual Machine developed by Oracle. Our experiments verify that, although our allocator works on a non-global scope, it performs equally well (or even better) than a state-of-the-art global allocator. This result is already remarkable, since it refutes the common believe that global register allocation is a necessity for good allocation quality. Furthermore, to demonstrate the flexibility of trace register allocation, we seamlessly reduce register allocation time in a range from 0 to 40%, depending on how much peak performance penalty we are willing to sacrifice (from 0-12% on average). As an extra benefit, we present parallel trace register allocation, a mode where traces are allocated concurrently by multiple threads. In our experiments, this reduces the register allocation latency by up to 30% when using 4 threads compared to a single allocation thread.

Our work adds a new class of register allocators to the list of state-of-the-art approaches. Its flexibility opens manifold opportunities for future research and optimization, and enriches the landscape of compiler construction.

Kurzfassung

Eine der wesentlichen Aufgaben eines Compilers ist es die potentiell unbegrenzte Anzahl von Variablen eines Programms auf die physisch vorhandenen Maschinenregister eines Prozessors abzubilden. Dieser Vorgang - die sogenannte Registerallokation - trägt erheblich zur Übersetzungszeit eines Programms bei. Die Optimierung solcher Registerallokatoren spielt besonders für dynamische Übersetzer (Just-In-Time Compiler), in denen die Übersetzung erst zur Laufzeit stattfindet, eine wichtige Rolle, da die Allokationszeit hier maßgeblich zur Gesamtlaufzeit des Programms beiträgt. Viele Übersetzer verwenden globale Registerallokatoren, zum Beispiel nach dem Graph Coloring oder Linear Scan Verfahren, in denen das Optimierungspotential aufgrund des methoden-basierten Ansatzes eingeschränkt ist. Mit zunehmender Methodengröße erreichen diese bestehenden Ansätze die Grenzen ihrer Skalierbarkeit.

Um dieses Problem zu lösen, haben wir im Zuge dieser Arbeit einen neuartigen Trace-basierten Registerallokator entwickelt, der eine Methode nicht als Ganzes verarbeitet, sondern sie in lineare Codesegmente (Traces) zerlegt, die dann unabhängig voneinander bearbeitet werden. Zum einen können so abhängig von den Eigenschaften der Codesegmente unterschiedliche Strategien angewendet werden, die uns beispielsweise erlauben, für kritische Teile mehr Zeit aufzuwenden als für weniger kritische Teile. Zum anderen können die einzelnen Segmente parallel verarbeitet werden, was die Latenzzeit einer Übersetzung verringert.

Die Implementierung unseres Registerallokators erfolgte in GraalVM, einer von Oracle entwickelten hochoptimierenden virtuellen Maschine für Java. Unsere Experimente haben gezeigt, dass unser lokaler Ansatz mindestens gleich gut - und in einigen Fällen sogar besser - als globale State-of-the-Art-Allokatoren arbeitet. Diese Erkenntnis widerlegt somit die weit verbreitete Annahme, dass für gute Ergebnisse globale Allokationsverfahren benötigt werden. Aufgrund der Flexibilität unseres Ansatzes konnte, abhängig von den tolerierten Performance-Einbußen (durchschnittlich zwischen 0-12%), die Registerallokationszeit um bis zu 40% reduziert werden. Zusätzlich erlaubt unser Allokator eine parallele Abarbeitung, die beispielsweise bei der Verwendung von vier Threads anstelle von einem, die Allokationslatenz um bis zu 30% verringert.

Unser hier vorgestellter Registerallokator fügt sich nahtlos in die Liste der State-of-the-Art- Ansätze ein. Die zusätzliche Flexibilität eröffnet eine Vielzahl an zukünftigen Forschungsmöglichkeiten und bereichert die bestehende Übersetzerbau-Landschaft.

PhD thesis, Johannes Kepler University Linz, July 2021