HOME | ENGLISH | IMPRESSUM | KIT

Bachelor-/Masterarbeit (offen): Verbessertes Loop-Unrolling für FIRM

Loop-Unrolling ist eine Transformation, die den Schleifenkörper vervielfacht und den schleifensteuernden Code entsprechend anpasst.


for (int i = 0; i < 100; ++i) {
  stuff(i);
}

wird transformiert zu

for (int i = 0; i < 100; i += 4) {
  stuff(i);
  stuff(i + 1);
  stuff(i + 2);
  stuff(i + 3);
}

Das Ausrollen der Schleife verringert den Overhead für das Überprüfen der Schleifenbedingung, was wichtig ist, wenn die Operation stuff() einfach ist. Weiterhin ermöglicht Loop-Unrolling vielen anderen Optimierungen das Arbeiten mit Werten aus mehreren Schleifeniterationen.

Das Beispiel zeigt die einfachste Situation: die Iterationszahl der Schleife ist statisch bekannt und ohne Rest durch den Ausrollfaktor (im Beispiel 4) teilbar. Im allgemeinen Fall ist die Iterationszahl zur Compile-Zeit unbekannt. Trotzdem können solche Schleifen ausgerollt werden, z.B. mit einer Technik ähnlich Duff's Device.

FIRM besitzt bereits eine Transformation zum Ausrollen von Schleifen, allerdings schlägt diese zu selten an, da sie zu strenge Anforderungen an die Form der Schleife stellt.

Im Rahmen dieser Bachelor-/Masterarbeit soll eine verbesserte Loop-Unrolling-Optimierung in den am Lehrstuhl entwickelten Compiler libFirm integriert werden. Dabei soll eine vorgeschaltete Transformation die Schleife zunächst in Loop-Closed-SSA-Form transformieren. Abschließend soll die Qualität der Optimierung evaluiert werden.

Aufgabe:

  • Analyse der Schwachstellen der bisherigen Implementierung
  • Implementierung einer Transformation in LCSSA-Form
  • Implementierung der Loop-Unrolling-Optimierung
  • Evaluation der Optimierung

Voraussetzungen

  • Programmierkenntnisse in C
  • Interesse am Compilerbau und Optimierungen

Schlüsselworte

Compiler, libFirm, Optimierung 

Betreuer

Wissenschaftliche Mitarbeiter
Sebastian Buchwald
Manuel Mohr