title: An SSA-based Register Allocator for the Glasgow Haskell Compiler
Creators: name: Maurer, Benjamin
Publisher: name: TU Wien
Year: 2022
Subjects: subject: register allocation
subject: SSA
subject: Haskell
subject: spilling
subject: register assignment
subject: chordal graphs

description: Registerallokation ist einer der letzten Schritte beim Übersetzen eines Programms. Dessen Aufgabe ist es Programmwerte den Prozessorregistern zuzuweisen und sie in den Arbeitsspeicher auszulagern, sollten davon nicht genügend verfügbar sein. Dieses leistungskritische Problem optimal zu lösen ist, im Allgemeinen, NP-schwer. Die meisten, für die Praxis geeigneten Algorithmen, lassen sich als Graphenfärbe- oder Linear-Scan-Verfahren kategorisieren. Mehrere Forschungsgruppen haben 2005 entdeckt, dass die Konfliktgraphen von Programmen in Static Single Assignment (SSA) Form chordal sind. Die wichtigste Implikation dessen ist, dass dadurch eine klare Trennung der Allokationsphasen ermöglicht wird. Der Glasgow Haskell Compiler (GHC) ist ein leistungsfähiger Übersetzer für die rein funktionale Programmiersprache Haskell. Sein "Native Code Generator" enthält sowohl einen Linear-Scan-, als auch Graphenfärbe-Allokator, wobei ersterer bessere Ergebnisse erzielt. Diese Arbeit beschreibt Algorithmen zur SSA-basierten Registerallokation, insbesonders jenes Design, welches zur Umsetzung in GHC ausgewählt wurde. Eine detaillierte Evaluierung des neuen Allokators und ein Vergleich zu den Bestehenden wurde mithilfe GHCs nofib Benchmarksammlung durchgeführt. Während sich der neue, SSA-basierte Allokator dem Graphenfärbe-Allokator überlegen zeigt, kann er den Linear-Scan-Allokator nicht übertreffen. Ladebefehle wurden leicht verringert, wie auch Kopierbefehle, aber die Anzahl an Speicherbefehlen erhöht. Der SSA-basierte Allokator produziert Code, welcher im Durchschnitt 0.47% langsamer als jener des Linear-Scan-Allokators ist. Mögliche Ursachen und Verbesserungsmöglichkeiten werden besprochen.
description: Register allocation is one of the last steps in the compilation pipeline. It is responsible for assigning program values to CPU registers and store them in memory when no free registers are available. Solving this performance critical task optimally is, in general, NP-hard. Most practical algorithms fall in the categories of linear scan and graph coloring approaches. In 2005, several research groups discovered, that the interference graphs of programs in Static Single Assignment (SSA) form are chordal. The most important implication being, that this allows for a separation of the spill, assign and coalesce phases. The Glasgow Haskell Compiler (GHC) is an industrial strength compiler for the purely functional programming language Haskell. Its Native Code Generator features both a linear scan and graph coloring register allocator, with the former delivering better performance. This work discusses SSA-based register allocation algorithms, especially the design chosen for implementation in GHC. A detailed evaluation of the new allocator and comparison to the pre-existing ones is performed, using GHC’s nofib benchmark suite. While the new SSA-based allocator proves superior over the graph coloring allocator, it does not surpass the linear scan allocator. Reloads are slightly decreased, as well as copies, but spills are higher. The SSA-allocator produced code is on average 0.47% slower than linear scan. Possible reasons for this, as well as opportunities for improvement are discussed.