Eine der wichtigsten Optimierungen eines Compilers ist die Elimination partiellen Redundanzen (engl. partial redundancy elimination, PRE). Ein Ausdruck ist genau dann partiell redundant, wenn es einen Programmpfad gibt auf dem er mehrfach berechnet wird. Im folgenden Beispiel ist a+b partiell redundant, da a+b im auf dem linken Pfad zweimal berechnet wird.

Um diesen Umstand zu beheben, "verschiebt" man die zweite Berechnung von a+b auf den rechten Pfad. Dadurch wird a+b auf jedem Programmpfad nur einmal berechnet.

Obwohl praktisch alle moderne Zwischensprachen auf SSA-Form basieren, gibt es nur wenige PRE-Verfahren, die direkt auf SSA-Form arbeiten. Das wohl bekannteste SSA-basierte Verfahren ist GVN-PRE. Im Rahmen dieser Arbeit soll die GVN-PRE in den am Lehrstuhl entwickelten Compiler libFirm integriert werden, um die Möglichkeiten und Grenzen von SSA-basierter PRE zu evaluieren.

Aufgabe

• Erweiterung des libFirm Compilers um das GVN-PRE-Verfahren
• Evaluation der Möglichkeiten und Grenzen von SSA-basierter PRE

Literatur

• VanDrunen, Hosking: Value-Based Partial Redundancy Elimination

Voraussetzungen

• Spaß am Übersetzerbau
• Gute Programmierkenntnisse in C

Betreuer

Ehemalige Mitarbeiter
Dipl.-Inform. Sebastian Buchwald

Studenten

Ehemalige Studenten
Christian Helmer