Optimization framework for the CACAO VM

Abstract

Eine Virtuelle Maschine (VM) ist eine Software, die verwendet wird, um andere Programme auszuführen. Das geschieht entweder durch Interpretieren der einzelnen Instruktionen oder durch Übersetzen von Programmteilen in Maschinencode. Da beim zweiten Ansatz die Übersetzung erst stattfindet, wenn das Programm benötigt wird, spricht man auch von just-in-time (JIT) Übersetzung. Die Cacao VM ist eine virtuelle Maschine für Java Bytecode. Cacao ist eine reine JIT VM. Das bedeutet, alle Methoden werden übersetzt, bevor sie ausgeführt werden. Dazu bedarf es eines schnellen Übersetzers um eine zeitnahe Programmausführung zu gewährleisten. Dazu verwendet der sogenannte Baseline Compiler einfache Datenstrukturen und die einzelnen Übersetzungsschritte sind stark an einander gekoppelt. Für die meisten Programmteile reicht das Ergebnis des Baseline Compilers aus. Für häufig verwendete Methoden würde es sich allerdings auszahlen, mehr Zeit in eine bessere Übersetzung zu investieren. Da man im Vorhinein nicht feststellen kann, welche Programmteile oft verwendet werden, untersucht die virtuelle Maschine das Laufzeitverhalten der Applikation und wählt darauf aufbauend Methoden für erneute Übersetzung aus. Dieses Verfahren wird adaptive Optimierung genannt. Bisweilen verwendet Cacao den Baseline Compiler für die Optimierung häufig genutzter Teile. Das hat mehrere Nachteile. Zum Einen wird der Baseline Compiler dadurch immer komplizierter und die Wartung aufwendiger. Das größere Problem liegt allerdings darin, dass der Baseline Compiler durch die einfache, aber effiziente Form unflexibel ist und sich das Entwickeln neuen Optimierungen schwierig gestaltet. Diese Arbeit beschreibt ein neues Übersetzer-Framework, das den Baseline Compiler als optimierenden Übersetzer ablösen soll. Das Framework verwendet zwei neue Zwischendarstellungen. Die graph-basierte high-level Darstellung eignet sich besonders für Programmanalysen und Transformationen. Ihr Ziel ist es den Entwicklungsprozess für Optimierungen einfach und schnell zu gestalten. Die low-level Darstellung ist speziell an die Bedürfnisse von maschinennahen Aufgaben, wie zum Beispiel Register Allokation oder der Generierung von Maschinencode, angepasst. Der Übersetzer verfügt über einen Pass Manager, der sich um die Ausführung und den Datenaustausch der Pässe kümmert. Zur Zeit beinhaltet die Übersetzer-Pipeline die IR-Graphen Erstellung, strukturelle Analysen, verschiedene Scheduler, Befehlsauswahl, einen Register Allokator sowie einen Maschinencode Emitter. Der empirische Vergleich mit dem Baseline Compiler zeigt das Potential des neuen Systems und gibt zukünftige Aufgaben vor.

A virtual machine is a software that takes charge of executing another program. This either can be done by interpreting the instructions of the program, or by compiling parts of it when needed. The second approach is also called just-in-time (JIT) compilation. The Cacao VM is a virtual machine for Java bytecode. It follows a JIT-only approach meaning that all methods are compiled into native machine code prior execution. This requires a fast compiler to minimize the latency for program execution. Consequently, the compiler, called baseline compiler, uses simple data representation and the passes are highly integrated. While the generated machine code is adequate for most parts of a program, the over-all performance can be improved, if more time for better optimization is invested for frequently executed methods. It can not be decided a priori which methods will be called regularly. To gain this knowledge the virtual machine profiles the run-time behavior of the program and selects methods for recompilation with more efforts. This approach is known as adaptive optimization. So far the Cacao VM uses the baseline compiler with a higher optimization level for recompilation. This approach has two problems. On the one hand, the additional optimizations complicate the baseline compiler and maintenance is more difficult. On the other hand and more important, due to the simple but efficient construction the baseline compiler is inflexible and new optimizations are hard to implement. This work presents a new compilation framework for Cacao, which replaces the baseline compiler as the optimizing compiler. It features two intermediate representations. The graph-based high-level representation is intended for program analysis and transformation. It is designed to make optimization development fast and easy. The low-level representation is focused on tasks close to the machine level, like register allocation and code emission. The compiler contains a pass manager to administer the execution and data exchange of passes. Currently, the transformation pipeline includes IR construction, structural analysis, scheduling, instruction selection, register allocation and code emission. An empirical comparison between the baseline compiler and the new framework discloses the potential of the new framework and sets the agenda for future directions of the project.