Register Allocation on the Intel® Itanium® Architecture

Gerolf Hoflehner

Abstract

Register allocators based on graph-coloring have been implemented in commercial and research compilers since Gregory Chaitin’s and colleagues pioneering work in the early 1980’s. A coloring allocator decides which live range (a program or compiler generated variable) is allocated a machine register (“allocation problem”). The Itanium processor architecture supports predicated code, control- and data speculation and a dynamic register stack. These features make the allocation problem more challenging. This thesis analyses and describes efficient extensions in a coloring allocator for the Itanium processor.

• Predicated code: The thesis describes compile time efficient coloring methods in the presence of predicated instructions, without compromising run-time performance of a more elaborate allocator based on the predicate query system, PQS. In particular it classifies predicated live ranges and shows that classical register allocation techniques can be used effectively to engineer efficient coloring allocators for predicated code. When predicated code is generated from compiler control flow more expensive predicate analysis frameworks like PQS don’t have to be employed.
• Speculated code: The thesis describes a new method of efficiently allocating speculated live ranges avoiding spill code generated by a more conservative method. In particular the NaT propagation problem is solved efficiently.
• Dynamic register stack: The thesis reviews methods to use the dynamic register stack effectively in particular regions with function calls and/or pipelined loops.
• Scalable allocation: A generic problem of coloring allocators is that they can be slow for large candidate sets. This thesis proposes the scalable allocator as a generic coloring method capable of allocating effectively programs with large register candidates sets. The methods can also be used for parallel allocation e.g. on multi-core machines.

The experimental results on the CPU2006 benchmark suite illustrate the effectiveness of new methods. Finally, the thesis reviews the development of coloring allocators since Chaitin.

Kurzfassung

Gregory Chaitin und seine Kollegen haben um 1980 die Pionierarbeit für Registerallokation basierend auf Graphfärbung („Farballokator“) geleistet. Diese Allokatoren entscheiden, welchen „Lebensspannen“ (d.h. deklarierte oder vom Compiler erzeugte Variablen, engl. live ranges) Maschinenregister („Farben“) zugeteilt werden (Allokationsproblem). Der Itanium-Prozessor unterstützt Instruktionen mit Prädikaten (bedingt ausführbare Instruktionen), Kontroll- und Datenspekulation sowie einen dynamischen Register Stack. Diese Eigenschaften erschweren die Lösung des Allokationsproblems. Die vorliegende Dissertation untersucht und beschreibt effiziente Erweiterungen in einem Farballokator für den Itanium-Prozessor.

• Prädikate: Es werden effiziente Methoden (zur Übersetzerzeit) für Farballokatoren vorgestellt, die Lebenspannen in Code mit bedingt ausführbaren Instruktionen allokieren. Insbesondere werden „prädikatierte“ Lebensspannen klassifiziert und es wird gezeigt, das klassische Methoden zu einem effizienten Farballokator für diese Lebensspannen erweitert werden können. In einem Compiler kann die Allokation mit diesen Methoden genau so effizienten Code generieren wie aufwendigere Verfahren, insbesondere Verfahren, die das „predicate query system“ (PQS) benutzen.
• Spekulation: Es wird eine neue Methode erläutert, die – im Vergleich zu konservativen Verfahren – Spill Code für spekulative Lebensspannen vermeiden kann. Inbesondere wird eine effiziente Lösung für das NaT Propagation Problem vorgestellt.
• Dynamischer Register Stack: Es wird beschrieben, wie der dynamische Register Stack in Code mit Funktionsaufrufen oder „pipelined“ Schleifen (engl. „software-pipeline loops“) effizient verwendet werden kann.
• Skalierbare Allokation: Es wird der skalierbare Allokator vorgeschlagen für die Lösung Allokationsprobleme beliebiger Grösse. Skalierbare Allokation erlaubt insbesondere die Parallelisierung des Allokationsproblems und ist unabhängig von der Prozessor-Architektur.

Die experimentellen Resultate für die CPU2006 Benchmark Suite zeigt die Effizienz der vorgestellen Verfahren. Schließlich enthält diese Dissertation einen ausführlichen Überblick über die Forschungsergebnisse für Farballokatoren seit Chaitin.

PhD thesis, Johannes Kepler University Linz, März 2010