Registerallokation (englisch Register Allocation) ist die Compiler-Phase, die entscheidet, welche Werte zu einem Zeitpunkt in den schnellen CPU-Registern liegen dürfen und welche stattdessen im Hauptspeicher (Stack) verwaltet werden müssen. Sie ist einer der wichtigsten Performance-Hebel: Wer Register gut vergibt, spart teure Lade- und Speicherbefehle.
Warum Register so wertvoll sind
Register sind der schnellste Speicher, den ein Prozessor kennt. Fast jede Rechenoperation arbeitet direkt auf Registern - ein add braucht zwei Register-Quellen und ein Register-Ziel. Werte, die nicht in Registern liegen, müssen vor der Benutzung aus dem RAM geladen (Load) und nach der Änderung zurückgeschrieben (Store) werden. Jeder Load ist ein Speicherzugriff mit Cache-Kosten. Die Registerallokation versucht deshalb, möglichst viele lebende Werte gleichzeitig in Registern zu halten.
Liveness-Analyse: Wer lebt noch?
Vor der eigentlichen Vergabe bestimmt die Lebendigkeitsanalyse (Liveness Analysis), an welchen Programmstellen ein Wert noch benötigt wird. Ein Wert ist an einem Punkt live, wenn er auf einem späteren Pfad noch gelesen wird, bevor er überschrieben wird. Tote Werte (dead values) können ihr Register sofort freigeben - typisch nach der letzten Benutzung einer Variablen.
Der Interferenzgraph
Aus der Liveness-Analyse baut der Compiler den Interferenzgraphen: Jeder Knoten ist eine Variable oder ein Zwischenergebnis (Temporary), jede Kante verbindet zwei Werte, die zur selben Zeit leben. Solche Werte interferieren - sie dürfen niemals dasselbe Register bekommen, weil sie sich sonst gegenseitig überschreiben würden.
Registerallokation als Färbungsproblem
Damit wird die Allokation zu einem Knotenfärbungsproblem (Graph Coloring): Jede Farbe entspricht einem Register, und benachbarte Knoten müssen verschiedene Farben erhalten. Stehen k Register zur Verfügung, sucht der Compiler eine Färbung mit k Farben des Interferenzgraphen. Das ist eng verwandt mit der Kantenfärbung - dort sind Kanten die zu färbenden Objekte, hier sind es Knoten. Beide Färbungsprobleme stammen aus der Graphentheorie. Optimales Färben allgemeiner Graphen ist NP-vollständig - praktische Allokatoren arbeiten deshalb mit Heuristiken, die in der Praxis fast immer eine gute Färbung finden.
Chaitins Algorithmus
Der klassische Ansatz stammt von Gregory Chaitin (1981) und läuft in mehreren Schritten:
- Bauen: Liveness-Analyse und Interferenzgraph erzeugen.
- Vereinfachen: Knoten mit weniger als k Nachbarn auf einen Stack legen (sie sind garantiert färbbar, sobald die anderen gefärbt sind).
- Spill-Entscheidung: Bleibt ein Knoten mit k oder mehr Nachbarn übrig, wird ein Kandidat zum Spill erklärt - sein Wert wandert in den Hauptspeicher. Ein Kostenmodell wählt den Kandidaten, der am wenigsten Zusatzcode verursacht.
- Färben: Knoten in umgekehrter Stack-Reihenfolge eine freie Farbe geben; schlägt das fehl, wird zusätzlich gespillt.
- Wiederholen: Nach dem Einfügen der Spill-Code-Stellen (Store/Load) wird der Graph neu aufgebaut und erneut gefärbt.
John Cocke und später Preston Briggs verfeinerten das Verfahren: Coalescing verschmilzt Knoten, die durch eine reine Kopier-Instruktion verbunden sind (Move), und optimistisches Färben erlaubt, eigentlich gespillte Knoten doch noch zu färben, wenn beim Zuweisen eine Farbe frei ist.
Linear Scan und moderne Allokatoren
Für Compiler mit kurzen Übersetzungszeiten - besonders Just-in-Time-Compiler - ist Chaitins Verfahren teuer. Massimiliano Poletto schlug 1999 Linear Scan vor: Die Allokation läuft in einem Durchlauf über die sortierten Lebensintervalle der Werte und ist deutlich schneller, bei nur leicht schlechterem Code. Die LLVM-Projektfamilie nutzt einen greedy-Allokator, der Lineare-Scan-Ideen mit Live-Range-Splitting kombiniert; GCC setzt auf eine Chaitin-Briggs-artige Allokation mit IRA (Integrated Register Allocator).
Spills: Die Kosten der Knappheit
Übersteigt die Zahl gleichzeitig lebender Werte die Zahl der Register, muss der Compiler Werte auf den Stack auslagern. Zusätzlicher Spill-Code (Store nach Definition, Load vor jeder Benutzung) kostet Ausführungszeit und Platz. Besonders ausgeprägt ist das Problem auf Architekturen mit wenigen Registern - etwa älteren x86-Varianten ohne viele Allzweckregister oder günstigen Eingebetteten-Systemen. Die Registerallokation zählt deshalb zu den wichtigsten Optimierungen überhaupt: Jeder vermiedene Spill spart in inneren Schleifen oft mehrere Prozent Laufzeit.
Verwandte Grundlagen: Kantenfärbung, Graph-Datenstruktur, Compiler, Knoten, Kante, NP-Vollständigkeit.