Aktuelle Forschung auf dem Gebiet der SSA-basierten Registerzuteilung ermöglichen eine Aufteilung des Problems in drei Phasen:

• Auslagern
• Färben
• Kopienminimierung

Der an der Universität Karlsruhe entwickelte Compiler libFirm ist der weltweit einzige, der diesen SSA-basierten Ansatz zur Registerzuteilung umsetzt. Während Auslagern und Färben in Linearzeit realisiert sind, können die bisherigen Heuristiken der Kopienminimierung diese Skalierbarkeit nicht bieten.

Ein vielversprechender Ansatz für eine lineare Heuristik ist die Modellierung als Partitioned Boolean Quadratic Problem (PBQP), das bereits erfolgreich für traditionelle Registerzuteilung erprobt wurde. Ziel der Studienarbeit ist es, dieses Verfahren auf das Kopienminimierungsproblem zu übertragen.

Aufgabe

• Entwicklung einer linearen Heuristik zur Kopienminimierung unter Benutzung des PBQP-Ansatzes
• Evaluierung des Verfahrens in Bezug auf die bereits vorhandenen Heuristiken

Literatur

• Hack: Register Allocation for Programs in SSA Form
• George, Apple: Iterated register coalescing
• Hack: Copy coalescing by graph recoloring

Voraussetzungen

• Spaß am Übersetzerbau
• Gute Programmierkenntnisse in C



Veröffentlichungen

Veröffentlichung

SSA-basierte Registerzuteilung mit integrierter Kopienminimierung

Betreuer

Ehemalige Mitarbeiter
Dipl.-Inform. Sebastian Buchwald

Studenten

Ehemalige Studenten
Thomas Bersch