Jump Threading ist eine Compiler-Optimierung, die bedingte in unbedingte Sprünge verwandelt und dabei (meistens) Code dupliziert.

In der obigen Abbildung ist ein Steuerflussgraph (CFG) abgebildet. Ausgehend vom cyan-gefärbten Grundblock sieht man einen Vorgänger mit einem bedingten Sprung, der wiederum einen Vorgänger besitzt, welcher das Sprung festlegt. Der bedingte Sprung kann nicht im allgemeinen entfernt werden, da die Festlegung den Vergleich nicht dominiert; Es existiert ein zweiter Vorgänger.

Jump Threading dupliziert nun den Block mit dem bedingten Sprung und lässt den festlegenden Block in die Kopie (grün) springen. Insbesondere werden Operationen wie der Aufruf von foo kopiert. Dadurch kann der Vergleich in der Kopie in einen unbedingten Sprung umgewandelt werden. Man beachte, dass kein Pfad mehr vom Vergleich zur Festlegung führt. So ist Termination bei wiederholter Anwendung leicht zu zeigen.

Die Kante vom bedingten Sprung zum cyan-gefärbten Grundblock ist durch diese Transformation kritisch geworden. Dies wird (wie üblich) durch einen Split gelöst; Ein zusätzlicher leere Grundblock wird eingefügt. Das ist im folgenden Beispiel illustriert, was eine koplexere Situation darstellt.

Auch hier ein cyan-gefärbter Grundblock als Ausgangspunkt, ein bedingter Sprung im Vorgänger und weiter oben eine Festlegung der Bedingung. Wenn die Festlegung wie hier weiter entfernt liegt, müssen mehrere Blöcke kopiert werden. Rechts sieht man in grün zwei kopierte Blöcke und außerdem den Block der die kritische Kante entfernt mit rotem Rand.

Problematisch bei diesem Beispiel ist, dass der neue Block mit roten Rand wieder optimiert werden kann. Der Vorgänger ist ein bedingter Sprung und der besitzt wiederum die Festlegung als Vor-Vor-Vor-Vor-Vorgänger. Die Jump Threading Implementierung die aktuell in libFirm ist, terminiert in diesem Randfall nicht.

Aufgabe dieser Arbeit ist eine Neuimplementierung des Jump Threading Phase in libFirm, wobei insbesondere Analyse und Transformation getrennt werden sollen. Interessant (falls möglich) ist eine Formulierung als Datenflussanalyse.

Voraussetzungen

• Kenntnisse im Compilerbau (zB Compilervorlesung)
• Erfahrung mit libFirm (zB Compilerpraktikum)

Schlüsselworte

compiler, optimization, jump threading, control flow, termination 

Veröffentlichungen

Veröffentlichung

Generalized Jump Threading in libFIRM

Betreuer

Ehemalige Mitarbeiter
Dr.-Ing. Andreas Zwinkau

Studenten

Ehemalige Studenten
Joachim Priesner