Go to page
 

Bibliographic Metadata

Title
Implementation of a Register Allocation Verifier for the Graal Compiler / submitted by Gabriel Schörghuber, BSc.
AuthorSchörghuber, Gabriel
CensorMössenböck, Hanspeter
PublishedLinz, 2019
DescriptionIII, 42 Blätter : Illustrationen
Institutional NoteUniversität Linz, Masterarbeit, 2019
LanguageEnglish
Document typeMaster Thesis
URNurn:nbn:at:at-ubl:1-26022 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Implementation of a Register Allocation Verifier for the Graal Compiler [0.53 mb]
Links
Reference
Classification
Abstract (German)

Die Aufgabe eines Register Allokators ist es Variablen zu Register zuweisen. Die Fehlersuche bei Reg- ister Allokatoren gestaltet sich häufig als mühsam. Die Fehler können in einem Teil des Programmes liegen, der nicht ausgeführt wird für alle Parameter. Die Fehler bleiben unentdeckt, da sie keinen Ab- sturz des Programmes verursachen und das Ergebnis der Ausführung korrekt ist. Auch wenn sich der Fehler bemerkbar macht, dann ist es schwierig von der Ausführung zurück auf den fehlerbehafteten Teil der Register Allokation zu schließen. Unser Tool führt eine statische Analyse des allokierten Programmes durch um Fehler zu identifizieren und gibt zusätzliche Informationen über diese, um sie zu lokalisiern. SARAVerify betrachtet bei der Analyse den Register Allokator als Blackbox. Das er- möglicht uns die meisten Register Allokatoren mit unserem Tool zu überprüfen, ohne sie abändern zu müssen. Wir verifizierten die zwei Register Allokatoren des Graal Compilers mit unserem Tool. Um uns zu versichern, dass unser Tool korrekt funktioniert, haben wir Fehler in die allozierten Programme eingebaut. SARAVerify hat 99% der eingebauten Fehler gefunden. Wir untersuchten die Fälle, in de- nen die eingebauten Fehler nicht gefunden wurden. Es stellte sich heraus, dass die Modifikationen keine Fehler auslösten und damit auf Stellen im Programm hinweisen, an der die Register Allokation möglicherweise optimiert werden kann. Unser Tool unterstützt Entwicklerinnen und Entwickler von Register Allokatoren bei der Fehlersuche und ermöglicht somit eine schnelle Verbesserung von Register Allokatoren.

Abstract (English)

A register allocator maps variables to registers. Finding bugs in register allocation can be a tedious task. The bugs may be located in a part of the program that is not executed for every input and therefore do not cause any errors or a wrong result. Even if a bug causes problems during the execution, it is hard to find, because tracking the executed code back to the regiser allocation decisions is difficult. To address these issues, we implemented SARAVerify, a verifier that detects errors caused by a wrong register allocation. Instead of relying on execution of the generated code it uses static analysis to uncover problems and to provide meaningful error information to locate the issue. Our tool treats the register allocator as a black box. Therefore, it supports most of the register allocation algorithms without requiring any modification. We verified the two register allocators of the Graal compiler with our tool. To further ensure that the tool works correct, we injected errors into the allocated code. The tool was able to detect 99% of all injected errors. Those that were not detected turned out to be no errors, but are indications of possible optimizations of the register allocation. Our tool supports the developers of register allocators and enables rapid improvements of register allocation algorithms.

Stats
The PDF-Document has been downloaded 4 times.