HOME | ENGLISH | IMPRESSUM | KIT

Diplomarbeit (abgeschlossen): SSA-basierte Eliminierung partieller Redundanzen

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.

Programm mit partiellen Redundanzen

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.

Optimiertes Programm ohne partielle Redundanzen

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

Voraussetzungen

  • Spaß am Übersetzerbau
  • Gute Programmierkenntnisse in C

Betreuer

Wissenschaftliche Mitarbeiter
Sebastian Buchwald

Studenten

Ehemalige Studenten
Christian Helmer