Linear Scan Register Allocation for the Java HotSpot™ Client Compiler

Christian Wimmer
Institute for System Software
wimmer@ssw.jku.at

Abstract

Register allocation is the task of assigning local variables and temporary values to physical registers of a processor. It is crucial for the efficiency of compiled code. The most commonly used algorithm treats the task of register allocation as a graph coloring problem. It generates code of good quality, but is too slow for just-in-time compilers because of its quadratic runtime complexity. For such compilers, the linear scan algorithm is an efficient alternative: It generates code of nearly the same quality, but is much faster than the graph coloring algorithm because it needs only a single pass over the lifetime intervals.

The Java HotSpot™ Virtual Machine by Sun Microsystems uses a just-in-time compiler to generate native code for frequently executed methods. To achieve a high compilation speed and a low startup time, the HotSpot client compiler avoids time-consuming optimizations. The current product version assigns registers using a local heuristic. In the context of this master thesis, a research version of the compiler was extended with the linear scan algorithm for register allocation. The implemented variant improves the basic algorithm with more advanced optimizations: It makes use of lifetime holes, splits intervals if necessary and models register constraints of the target architecture with fixed intervals.

Benchmark results prove that the linear scan algorithm is a good tradeoff if both compilation time and runtime of a program matter: The compilation time is only slightly higher in comparison with the old local heuristic for register allocation, but the resulting code executes about 30% faster. The benchmarks also indicate the high impact of the Intel SSE2 extensions on the speed of numeric Java applications.

Kurzfassung

Eine der wichtigsten Compileroptimierungen ist die Registerallokation, die lokale Variablen und temporäre Werte auf die Register des Prozessors abbildet. Das am häufigsten verwendete Verfahren basiert auf Graphfärbung. Es erzeugt hochqualitativen Code, ist aber wegen seiner quadratischen Laufzeitkomplexität zu langsam für Just-in-Time-Compiler. Für solche Anwendungen ist das Linear-Scan-Verfahren eine effiziente Alternative. Es erzeugt zwar nicht ganz so guten Code, ist aber in der Laufzeit im Wesentlichen linear.

Die Java HotSpot™ Virtual Machine von Sun Microsystems verwendet einen Just-in-Time-Compiler, um Maschinencode für häufig ausgeführte Methoden zu erzeugen. Um eine hohe Übersetzungsgeschwindigkeit zu erreichen, führt der HotSpot Client Compiler dabei keine zeitaufwendigen Optimierungen durch. Die aktuelle Produkt-Version verwendet derzeit eine einfache Heuristik für die Registerallokation. Diese Diplomarbeit beschreibt die Registerallokation nach dem Linear-Scan-Verfahren für eine Forschungs-Version des Compilers. Optimierungen wie die Ausnutzung von Löchern in Live-Intervallen, die Möglichkeit zur Teilung von Intervallen und die Verwendung von vorgefärbten Intervallen führen zu einer Verbesserung der Code-Qualität.

Benchmarks zeigen, dass das Linear-Scan-Verfahren einen guten Kompromiss zwischen Übersetzungszeit und Laufzeit eines Programms darstellt: Die Übersetzungszeit steigt im Vergleich mit dem alten, heuristischen Registerallokations-Verfahren nicht wesentlich an, die Geschwindigkeit des erzeugen Codes ist jedoch um etwa 30% höher. Zusätzlich zeigen die Benchmarks den großen Einfluss der Intel SSE2-Erweiterungen auf die Geschwindigkeit von numerischen Java-Anwendungen.

Master's thesis, Johannes Kepler University Linz, August 2004

Download as PDF