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 

Veröffentlichungen

Veröffentlichung

Ausrollen von Schleifen für Zwischensprachen in LCSSA-Form

Betreuer

Ehemalige Mitarbeiter
Dipl.-Inform. Sebastian Buchwald

Studenten

Studenten
Elias Aebi