Instruction selection for the CACAO VM

Abstract

Befehlsauswahl (Instruction Selection) ist eine wichtige Aufgabe eines Übersetzers. Sie ist für die Auswahl von Maschinenbefehlen verantwortlich, die die Aktionen eines Programmes - oder genauer gesagt dessen Zwischendarstellung - ausführen. Maschinenbefehle sind spezifisch für die jeweilige Zielarchitektur, z.B. unterscheiden sich Maschinenbefehle für x86 und ARM. Daher benötigt diese Aufgabe Wissen über die Zielarchitektur und den verfügbaren Befehlssatz. Im Gegensatz zu gewöhnlichen Compilern, die Sourcecode zu Maschinencode übersetzen, und Interpretern, die Sourcecode innerhalb eines Aufrufs ausführen, verwenden virtuelle Maschinen einen gemischten Ansatz. Code, der in der Programmiersprache Java verfasst ist wird zu Java Bytecode übersetzt, der von einer virtuellen Maschine ausgeführt werden kann. Diese Darstellung ist vergleichsweise maschinennahe, jedoch nicht spezifisch für eine Zielarchitektur. Eine virtuelle Maschine führt den Bytecode aus, indem sie ihn entweder interpretiert oder über einen JIT-Compiler in Maschinencode übersetzt und diesen ausführt. Die CACAO VM ist eine virtuelle Maschine für Java, die über keinen Interpreter verfügt. Sie verwendet einen schnellen, nicht optimierenden Compiler zur Generierung von Maschinencode für die Programmausführung. Häufig verwendete Teile des Programms können mit einem optimierenden Compiler erneut übersetzt werden um die Ausführung zu beschleunigen. Diese Arbeit hat das Ziel die Befehlsauswahl des optimierenden Compilers zu verbessern. Sie verwendet Pattern Matching um Maschinenbefehle auszuwählen, deren Ausführung - verglichen mit dem derzeit verwendeten konservativen Ansatz - schneller ist. lburg - ein Code-Generator Generator - wird verwendet um den Code der Mustererkennung zu erzeugen der im optimierenden Compiler verwendet wird. Dieser Generator verwendet Spezifikationen in einem Baum-Grammatik Format, die architekturspezifische Muster für die Befehlsauswahl bereitstellen. Die Implementierung des Algorithmus - teilweise generiert - enthält keine Spezifika von Zielplattformen. Der Code, der von der optimierten Version erzeugt wird, ist bis zu 76% schneller. Die Übersetzungszeit erhöht sich durch das Pattern Matching um etwa 5%, jedoch werden weniger Maschinenbefehle und Operanden emittiert, wodurch sich die Zeit und der Speicherbedarf für die Analyse der Aktivitätsbereiche und die Registerbelegung verringern.

Instruction selection is an important task of a compiler. It is responsible for selecting machine instructions that can perform the actions specified in a program - or to be more precise - a higher level representation of it. Machine instructions are specific to the target architecture, e.g. the machine instructions for x86 and ARM differ. Therefore, this task depends on knowledge about the target architecture and the available instruction set. In contrast to traditional compilers that translate source code to machine code, and interpreters that execute source code within one invocation, virtual machines take a mixed approach. Code written in the programming language Java is compiled to Java bytecode that can be executed in a virtual machine. This representation is comparatively low level, but not target specific. A virtual machine executes it by either interpreting it, or compiling it just-in-time (JIT) and executing the compiled version. The CACAO VM is a Java Virtual Machine that does not feature an interpreter. It uses a fast baseline compiler to generate machine code for program execution. Frequently used program parts can be recompiled by an optimizing compiler to speed up execution. This work aims to improve the instruction selection of the optimizing compiler. It applies pattern matching to find machine instructions that execute faster than the ones selected by the currently applied conservative approach. It adapts lburg - a code-generator generator - to produce the pattern matching code that is used in the optimizing compiler. This generator uses specifications in tree grammar format that contain target specific patterns for instruction selection. The algorithm implementation - partly generated - is kept platform agnostic. The code generated by the optimized version runs up to 76% faster. Compile time is increased by about 5% due to pattern matching, but due to less machine instructions and operands emitted lifetime analysis and register allocation are performed faster and require less memory.