Generalized Trace Compilation for Java

Christian Häubl

Abstract

Traditional method-based just-in-time (JIT) compilation translates methods to optimized machine code. Trace-based compilation only generates machine code for frequently executed paths, so-called traces, that may span multiple methods. This results in faster compilation, less generated machine code, and often better optimized machine code.

We present our implementation of trace recording and a trace-based JIT compiler in a modification of the Java HotSpot VM. Our tracing implementation records traces for Java applications during execution and supports traces that either start at loop headers or at method entries. After several times of trace recording, our trace-based JIT compiler merges the recorded traces into a structure suitable for compilation, a so-called trace graph. During compilation, traditional and trace-specific optimizations are applied and guarded with run-time checks if necessary. The generated machine code is then invoked by the interpreter or by other compiled traces. When a run-time guard fails or a method part must be executed that was not covered by traces and was therefore not compiled, execution falls back to the interpreter.

Our most profitable optimization is trace inlining, which is similar to method inlining in method-based JIT compilers. It widens the compilation scope and allows optimizing code parts of multiple methods as a whole, which increases the performance. The major advantage of trace inlining over method inlining is that the trace information is contextsensitive and therefore more accurate as it depends on the specific call site. This allows inlining different method parts for each specific call site which increases performance while reducing code size and compilation time.

In terms of peak performance, our trace-based JIT compiler outperforms the Java Hot- Spot client compiler by up to 59%. On some of the benchmarks, we also outperform the HotSpot server compiler in spite of the fact that our compiler performs significantly fewer optimizations and is therefore substantially faster.

Kurzfassung

Herkömmliche methodenbasierte just-in-time (JIT) Kompilierung übersetzt Methoden in optimierten Maschinencode. Pfadbasierte Kompilierung erzeugt nur Maschinencode für häufig ausgeführte Pfade, sogenannte Traces, die auch über mehrere Methoden hinweggehen können. Dies führt zu einer schnelleren Kompilierung sowie zu weniger generiertem und oft besser optimiertem Maschinencode.

Wir implementierten ein Verfahren, um Traces während der Ausführung von Java Programmen aufzuzeichnen, sowie einen pfadbasierten JIT Compiler, indem wir die Java HotSpot VM modifizierten. Traces können bei einem Schleifenkopf oder am Anfang einer Methode beginnen. Aufgezeichnete Traces werden an den JIT Compiler übergeben, welcher diese in einen Trace-Graphen zusammenführt. Beim Übersetzen des Trace-Graphen nach Maschinencode werden traditionelle, optimistische und pfadspezifische Optimierungen angewandt. Der erzeugte Maschinencode wird dann vom Interpreter oder von bereits kompiliertem Code aufgerufen. Wenn ein Methodenteil ausgeführt werden muss, der nicht durch Traces abgedeckt ist und somit nicht kompiliert wurde, dann wird der Maschinencode deoptimiert und die Ausführung im Interpreter fortgesetzt.

Unsere lohnendste Optimierung ist das Inlinen von Traces, welches ähnlich funktioniert, wie das Inlinen von Methoden in einem methodenbasierten JIT Compiler. Inlining erhöht die Optimierungsmöglichkeiten des Compilers und ermöglicht es, mehrere Methoden gemeinsam zu optimieren. Dies wiederum erhöht die Ausführungsgeschwindigkeit des generierten Maschinencodes. Der große Vorteil von Trace Inlining gegenüber dem Inlining von Methoden ist, dass die Trace-Information kontextabhängig ist. Wird an mehreren Programmstellen die gleiche Methode aufgerufen, so kann jeder Methodenaufruf gezielt durch die nötigen Teile der gerufenen Methode ersetzt werden. Dies führt zu besser optimiertem und weniger generiertem Maschinencode sowie zu einer schnelleren Kompilierung.

Programmen die mit unserem tracebasierten Compiler übersetzt wurden, werden um bis zu 59% schneller ausgeführt als bei einer Übersetzung mit dem HotSpot Client Compiler. Bei einigen Benchmarks übertrifft unser tracebasierter Compiler sogar den HotSpot Server Compiler, obwohl unser Compiler deutlich weniger Optimierungen durchführt.

PhD thesis, Johannes Kepler University Linz, Jänner 2015