Prüfungsprotokoll Übersetzerbau 2

Prüfer (P): Michael Philippsen
Beisitzer (B): Stefan Kempf

Disclaimer: Wie üblich bei Prüfungen von Prof. Philippsen waren die Rollen in der Prüfung selbst meist vertauscht. Die meisten Prüfungsfragen kamen also vom Beisitzer. Prof. Philippsen hat mit notiert und gelegentlich nach gefragt bzw. Hinweise gegeben. Insgesamt war die Atmosphäre sehr locker. Die Prüfer wirkten freundlich und haben auch hin und wieder den ein oder anderen Witz gemacht.

B: Wir haben hier mal nicht ganz so schönen Code

int A[65]
int B[]
int C[]

int f = random() * 2 + 1;
int e = random(); // nicht ganz sicher, aber auch nicht weiter wichtig

switch( f )
{
case default: 
	for( int i = 1; i < 2048; ++i )
	{
		for( int j = 0; j < 2048; ++j )
		{
case 0:		e++;
case 2:		e++;
case 4:		e++;
			
			// Es waren mehr Zugriffe und ich erinnere mich nicht mehr genau an die einzelnen Indizes. Ich habe lediglich die Abhängigkeiten nachgebildet, die gegeben waren.
			A[i,j+1] = A[i+1, j]
			C[i-1,j] = e*f;
			D[i,j] = C[i,j]
		}	
	}
}
// ...

B: Warum ist der Code jetzt ziemlich hässlich?
S: Das Switch baut im Default-Case eine doppelte Schleife auf, die sich über alle andere Cases erstreckt. Wir springen also ggf. mitten in die Schleife. Damit haben wir eine unnatürliche Schleife mit mehreren Eingängen.

B: Was ist eine unnatürliche Schleife, wie erkennen wir diese?
S: Keinen klaren Schleifenkopf, Bedingung Rumpf, sondern Sprünge mitten in die Schleife. Erkennbar durch Reduktion im KFG.

B: Kannst du den KFG für dieses Konstrukt mal ungefähr skizzieren
S: Ganz grobe Skizze (nur eine Schleife notwendig). Erst Schleife mit Bedingung, Rumpf. Dann Switch-Knoten mit Kanten zu den einzelnen Rumpf-Knoten.

B: Ist es denn jetzt wirklich so schlimm wie es aussieht?
S: Naja switch hat nur gerade Fälle. Man könnte also prüfen, ob f gerade ist und die Additionen vereinfachen.

B: Ja aber muss man das unbedingt?
S: Nein, weil e auf jeden Fall ungerade ist. Somit sind diese Sprünge in die Schleife überhaupt nicht möglich und man hat nur noch zwei normale Schleifen.

B: Wir kann ein Kompiler das erkennen?
S: Er könnte eine Ablaufanalyse machen und sich für diese Variable speichern „undefiniert, aber ungerade“ und diese Information im Switch verwenden.

B: Gut wir haben jetzt keine unnatürlichen Schleifen mehr, wie erkennen wir jetzt die natürlichen
S: Rückwärts-Kanten finden. Dazu muss gelten: (n,d) d >= >= n. Also ist eine Dominanzberechnung notwendig.

B: Wie können wir Dominanzen Berechnen?
S: Zum Beispiel mit Lengauer-Tarjan

B: Okay, wie funktioniert dieser Algorithmus. Erkläre die einzelnen Schritte man ungefähr
S: Tiefensuche, Knoten nummerieren, übrige Kanten (Rückwärts, Vorwärts, Links-Rechts), SemDom-Bestimmung Bottom-Up, ImmDom aus SemDoms bestimmbar

P: Bestimmt man die ImmDoms dann auch Bottom-Up?
S: Kann man machen, muss sich dann evtl. merken, dass der ImmDom eines SemDoms noch nicht bestimmt wurde und diesen später ersetzen. Top Down ist auch möglich, dann sollte man alle Informationen haben.
P: Und man muss sich weniger merken.

B: Jetzt haben wir Rückwärtskanten, wie bekommen wir jetzt die Schleife?
S: d und n sind Schleifenknoten. Wir starten bei n und laufen rückwärts über die Vorgänger (wenn Pfad von p →* n ohne d, dann ist p Schleifenknoten).
B: Und wenn wir bei d ankommen, sind wir fertig und hören auf?
S: Nein. Wir haben eine Worklist und fügen keine Vorgänger von Knoten, die bereits in der Schleife sind, mehr in die Worklist ein. D.h. der Algorithmus hört an d auf, berechnet aber ggf. noch andere Pfade fertig.

B: Sagen sie mal was zur SSA-Form
S: Kurz beschrieben, was man erreichen will. Vorteile von SSA-Form. Man erstellt für jede Zuweisung neue Variablen.
P: Jetzt fehlt aber noch eine ganz entscheidende Sache bei SSA.
S: Phi-Funktionen. Prinzip erklärt und warum man sie braucht.
B: Jetzt tun diese Phi-Funktionen irgendwie Magie. Was mache ich damit am Ende, wenn ich ausführbaren Code möchte.
P: Ganz einfach: Ich rufe die rchtige Assembler-Funktion auf.
S: Naives Auflösen der Phi-Funktionen (Einfügen von Zuweisungen in übergeordneten Kontrollfluss-Knoten); Probleme mit verlorenen Tausch-, Kopieroperationen; Gegenmaßnahmen von Sreedhar erklärt.

B: Okay, dann haben wir jetzt die Schleifen. Können wir diese jetzt noch optmieren?
S: <Überlegt> Ich suche gerade nach schleifeninvariantem Code, aber auf den ersten Blick ist das alles abhängig.
B: Nicht alles. Es ist nur etwas versteckt.
S: Ah ja bei der Berechnung der Arrays haben wir tendenziell die konstante Array-Dimension. Da könnte man dann Teilausdrücke vor die Schleife ziehen.
B: Was ist denn eigentlich schleifen-invarianter Code
S: Nur Definitionen von außerhalb der Schleife. Eine einzige Definition innerhalb der Schleife, die Schleifeninvariant. Konstanten.
B: Okay und können wir jeden invarianten Code einfach vor die Schleife ziehen?
S: Wenn wir (Teil)Ausdrücke vorziehen wollen, können wir das machen, wenn er invariant ist. Wollen wir ganze Zuweisungen vorziehen, wird es komplizierter. Dann muss die Zuweisung die einzige Zuweisung in der Schleife sein. Außerdem muss der Zuweisungsblock alle Schleifenausgänge dominieren und alle Variablennutzungen dieser zugewiesenen Variable strikt dominieren.

B: Gut und können wir jetzt noch irgendwas optimieren?
S: Wir können Induktionsvariablen finden (in den ganzen Array-Zugriffen gibt es einige) und vereinfachen und ggf. eliminieren. <grobe Erklärung von Induktionsvariablen>
B: Okay, wenn wir jetzt irgendwo im Code ein temp = i*4 haben, was können wir dann machen?
S: Dann können wir in jedem Durchlauf temp = temp + 4 schreiben und müssen vor der Schleife temp = i * 4, also mit 4 initialisieren. Wenn das die einzige Verwendung von i wäre, könnten wir jetzt die Variable i eliminieren und müssten die Abbruchbedingung entsprechend anpassen (*4).

B: Können wir diese Schleife jetzt noch durch Parallelisierung optimieren?
S: Ja dazu müssen wir die Abhängigkeitsdistanzen berechnen.
B: Machen Sie mal.
S: <zeichnet Tabelle>
B: Macht sich der Compiler eigentlich auch eine Tabelle?
S: Vermutlich nicht, aber spontan habe ich jetzt auch keine andere Möglichkeit
B: Dann zeichnen Sie erst mal weiter.
P: <Wärend Student zeichnet> Interessante Frage. Dabei kann man das ja egtl. einfach ablesen (sollte wohl ein Hinweis sein) ;)
S: C: (1,0) <Durch Beisitzer vorgeben, um Zeit zu sparen> A:(1,-1)

S: Wir können die innere Schleife parallelisieren, weil die Abhängigkeiten alle von der äußeren Schleife getragen werden.
B: Wenn wir jetzt aber die äußere Schleife parallelisieren wollen?
S: Ja dann…
B: Dann müssen wir ein bisschen tricksen.
S: <Zuerst war A:(1,1) vorgegeben, was ein bisschen verwirrt hatte. Vorschlag Schleifen-Neigen, Tauschen - noch nicht zielführend>
B: Tipp: Wir wollen C: (0,0) erreichen
S: Wir können Loop-Alignment machen. Dann ändert sich C[i,j] = e*f und baut entsprechende if-Anweisungen ein (um die anderen Zuweisungen). Damit hat man die Abhängigkeit eliminiert.
B: Und jetzt?
S: Schleifen-Neigen, sodass sich für A:(1,-1) A:(1,0) ergibt. Dann können wir die Schleifen tauschen und haben (0,0) (0,1) und die äußere Schleife lässt sich parallelisieren.

Insgesamt eine echt faire Prüfung. Als ich am Anfang den Code gesehen habe, musste ich schon etwas schlucken, weil das echt nicht schön aussah und man darauf die ganzen Algorithmen nicht praktisch ausführen möchte. Dadurch dass der Code aber so komplex war, musste ich die Algorithmen auch nicht direkt vorführen, sondern viele nur in der Theorie und an kleineren Beispielen erklären - was meiner Meinung nach einfacher ist, als diese an komplexen Beispielen durchzuführen. Kleinere Hilfestellungen seitens der Prüfer werden einem nicht als negativ ausgelegt, wenn man mit den gegebenen Hilfen das eigentliche Ziel der Frage schnell erfüllen kann.