Die Befehlsauswahl ist die Phase eines Compilers, die seine maschinenunabhängige Zwischensprache in die Maschinensprache der Zielarchitektur übersetzt. In einem graphbasierten Compilerframework wie libFirm entspricht dabei jeder Zielbefehl einigen kleinen Mustern von Knoten. Taucht eines dieser Muster im Programm auf, kann dafür der Zielbefehl eingesetzt werden.

Der Befehlsauswahlalgorithmus muss nun die kleinste Mustermenge finden, die das gesamte Programm abdeckt. Dieses Problem ist als NP-vollständig bekannt, und es gibt gute Heuristiken dafür. In der Praxis wird oft auch ein greedy Ansatz verwendet, der gute Ergebnisse liefert.

In dieser Arbeit soll ein weiteres Teilproblem der Befehlsauswahl betrachtet werden: Das Graph-Pattern-Matching, das heißt das Finden aller möglichen Vorkommen der Muster im Programm zu bestimmen. Mit wachsender Mustermenge wird es zunehmend ineffizient, an einem Punkt des Programms alle Muster durchzuprobieren. In dieser Arbeit soll ein Algorithmus entworfen und implementiert werden, der stattdessen die Struktur der vorher bekannten Mustermenge nutzt, um ein effizientes Matching zu ermöglichen.

Aufgabe:

• Erarbeiten eines effizienten Matching-Algorithmus
• Integration in libFirm

Voraussetzungen

• Gute Kenntnisse in Datenstrukturen und Graphenalgorithmen
• Erste Erfahrungen im Compilerbau vorteilhaft

Schlüsselworte

Compiler, Befehlsauswahl, Graphen 

Veröffentlichungen

Veröffentlichung

Generating Instruction Selectors For Large Pattern Sets

Betreuer

Ehemalige Mitarbeiter
Dipl.-Inform. Sebastian Buchwald
M.Sc. Andreas Fried

Studenten

Ehemalige Studenten
Markus Schlegel