Übersetzerbau 2 2015-07-27

Fach: Optimierungen in Übersetzern

Prüfer: Prof. Philippsen

Beisitzer: Jakob Krainz

In dieser Konstellation stellt v.a. der Beisitzer die Fragen (hab ich bei Philippsen auch schon anders erlebt), der Prüfer selbst mischt sich nur an einigen Stellen ein. Papier und Stift liegen bereit und werden im Rahmen der Prüfung auch benutzt.

B[eisitzer]: Was haben wir in Übersetzerbau 2 gemacht?

S[tudent]: Optimierungen in Übersetzern.

B: Auf welcher Ebene wendet man diese Optimierungen üblicherweise an?

S: Dem Zwischencode.

B: Was haben wir nicht behandelt?

S: Echte Optimierungen – alle behandelten optimieren nicht wirklich, sondern verbessern nur. [Konsequente Antwort wäre an dieser Stelle: Den Rest des Universums außer Optimierungen in Übersetzern.]

B: Hmmja, was noch nicht?

S: Optimierungen auf anderen Ebenen als dem Zwischencode.

B: Ja. Was macht man als erstes, wenn man optimieren möchte?

S: Kontrollflussgraph aufstellen.

B: Woraus besteht ein Kontrollflussgraph?

S: Grundblöcke und Kanten.

B: Was ist denn ein Grundblock?

S: Folge von Instruktionen, beginnt an möglichen Einsprungpunkten, endet bei Sprüngen. Hier gehen Grundblöcke über Funktionsaufrufe hinweg, kann man auch anders definieren.

B: Was kann man da anders machen, wenn du mal an Exceptions denkst?

S: Vielleicht minimale Grundblöcke? Das grade beschriebene waren maximale.

B: Ja, auch. Aber da geht noch was anderes… kommt das in der Vorlesung vor?

S: Kann ich mir nicht denken.

P[rüfer]: Wir können es ja jetzt erarbeiten.

S: Hmm, also mann müsste ja nach jeder Instruktion einen bedingten Sprung einfügen. Das wäre eigtl. das Ende des Grundblocks, dann wären es wieder minimale. Also fasst man diese Sprünge wohl nicht als echte Sprünge auf oder so.

B: Ja, man lässt das Verlassen des Grundblocks einfach an mehreren Stellen zu. Was stellt man denn dann mit dem Kontrollflussgraphen an?

S: Man braucht ihn für einige Optimierungen.

B: Hast du da mal Beispiele?

S: Garbage removal (das geht aber ansich auch ohne Kontrollflussgraph), Kopienfortschreibung, Konstantenpropagation.

B: Was kann man noch tun?

S: Dominatoren finden.

B: Was ist denn ein Dominator?

S: Dominator für Knoten n ist ein Knoten, durch den alle Pfade von der Wurzel zu n führen.

B: Wie findet man Dominatoren?

S: Iterativer Fixpunkt-Algorithmus oder Lengauer-Tarjan.

B: Hier ist ein Beispiel für einen Kontrollflussgraphen. (Relativ einfachen Graphen mit sechs Knoten, einer großen Schleife und einer Selbstschleife vorgelegt.) Du sagtest iterativer Fixpunkt-Algorithmus… wie findet man hier Dominatoren?

S: (Einen Schritt des Algorithmus' am ersten Knoten durchgeführt und laut kommentiert, dabei eine eingehende Kante übersehen.))

B: Da ist aber noch ein Vorgänger.

S: Ohh stimmt, hab ich übersehen. Ändert aber nichts am Ergebnis.

B: Warum nicht?

S: Weil der Vorgänger der Startknoten ist und eine Schnittmenge mit {S} nur wieder {S} ergeben kann.

B: Was zeichnet einen Fixpunkt-Algorithmus aus?

S: Dass es irgendwann keine Änderung mehr zur vorherigen Runde gibt.

B: Warum passiert das hier?

S: Weil die Schnittmengen immer nur kleiner werden oder gleich bleiben können.

B: Wozu kann man die Dominatoren gebrauchen?

S: Kontrollflussbahängigkeit erkennen.

B: Das ist zu allgemein. Was geht da genau?

S: Knoten ist kontrollflussbhängig, wenn er im inversen Kontrollflussgraphen in der Dominanzgrenze liegt.

B: Was ist denn eine Dominanzgrenze?

S: Menge von Knoten, bei denen der Vorgänger dominiert wird, der Knoten selbst aber nicht mehr.

B: Wozu kann man Dominanz sonst noch verwenden?

S: … [Hier musste ich länger nachdenken, „so herum“ hatte ich noch nie drüber nachgedacht.] Bestimmte Optimierungen brauchen die Dominanz auch.

P: Aha, welche?

S: …

P: Denken Sie mal eher ans Stichwort SSA-Form.

S: Ahh ja, zur Herstellung der SSA-Form ist eine Möglichkeit, an den Dominanzgrenzen Phi-Funktionen einzufügen.

B: Wonach müssen wir suchen, um Schleifen zu finden?

S: Rückwärtskanten.

B: Wo sind hier welche?

S: Hier, (gezeigt) und dann ist da noch eine Selbstkante (auch gezeigt).

B: Was gehört zu einer Schleife?

S: Schleifenkopf und Knoten im Schleifenrumpf.

B: Was ist der Zusammenhang zwischen Schleifen und Dominanz?

S: Neben den Knoten der Rückwärtskante gehören zur Schleife die Knoten, die vom Schleifenkopf dominiert werden und von denen es einen Pfad zum Schleifenausgang gibt.

B: Das gilt nicht für alle Schleifen, sondern bloß für welche?

S: Natürliche Schleifen.

B: Was sind denn unnatürliche Schleifen?

S: Haben keinen eindeutigen Kopf.

B: Skizzier mal eine.

S: (Beispiel aus den Vorlesungsfolien gezeichnet.)

B: Wie findet man schleifen?

S: Worklist-Algorithmus.

B: Wie funktioniert der?

S: (Algorithmus erklärt.)

B: Wo für ist denn die SSA-Form gut?

S: Sie erleichtert Optimierungen.

B: Konkreter?

S: Pro Nutzung gibt es nur eine erreichende Definition, das erleichtert bspw. die Konstantenpropagation, da man nicht alle Definitionen aus verschiedenen Pfaden überprüfen muss.

B: Wie kommt man in die SSA-Form?

S: Wie gesagt, iteratives Verfahren mit Einfügen von Phi-Funktionen an den Dominanzgrenzen, rekursiv an deren Dominanzgrenzen usw. Alternativ Verfahren mit Wertnummerierung.

B: Wir haben hier einen Kontrollflussgraphen mit Code, der dem anderen entspricht. (Vorgelegt.) Bring den Code man mit einem Verfahren deiner Wahl in SSA-Form.

S: OK, dann mach ich jetzt Wertnummerierung. Was soll ich annehmen für Variablen, die vorher nicht definiert sind?

B: Das sind Funktionsparameter.

S: (Angefangen, das Verfahren durchzuführen.)

P: OK, ich glaub das kann er. Machen wir weiter.

B: Was gibt es für ein Problem beim Rückweg aus der SSA-Form?

S: Die Phi-Funktionen existieren nur virtuell, müssen aufgelöst werden.

B: Wie funktioniert das?

S: Naiv fügt man am Ende jedes Vorgängers eine Zuweisung ein. Funktioniert leider nicht immer.

B: Warum nicht?

S: Zwei Probleme – verlorener Tausch und verlorene Kopie.

B: Was ist das Grundproblem dahinter?

S: Lebensspanne eines Arguments der Phi-Funktions über den Grundblock hinaus.

B: Was tut man dagegen?

S: Sreedhars Gegenmaßnahmen.

B: Wie sehen die aus?

S: Man fügt Temporärvariablen ein.

B: (Schreibt ein kleines Beispiel mit zwei Variablen aufs Blatt.) Wenn das hier deine Argumente für die Phi-Funktion sind, was tust du?

S: (Temporärvariablen eingefügt.)

B: Was kann man statt diesen Gegenmaßnahmen tun?

S: Weiß nicht, worauf du hinauswillst.

B: Warst du in der Übung zur SSA-Form?

S: War in den meisten Übungen, also wrsl. ja.

B: Sagt dir conventional SSA was?

S: Ja, mal gehört.

B: Was ist das?

S: Also, ich hab den Begriff mal gehört.

B: OK, lassen wir das. Was kann man sonst noch für Optimierungen machen?

S: Schleifentransformationen oder -restrukturierungen.

B: Und sonst mit Schleifen?

S: Z.B. Ausrollen, aber das ist eigtl. schon wieder eine Transformation.

B: Aha, Ausrollen. Aber was haben wir denn zuerst gemacht, viel einfachere Optimierungen?

S: …

B: Was ist denn schleifeninvarianter Code?

S: Operation, deren Operanden nicht von der Iteration abhängig sind.

B: Was heißt das? Wie sind die genauen Bedingungen?

S: Alle Opernaden konstant, außerhalb der Schleife definiert oder selbst schleifeninvariant.

B: Wann kann man den Code dann herausziehen?

S: Muss in allen Pfaden vorkommen.

P: (Schmerzverzerrtes Gesicht) Nö.

B: Schauen wir's uns mal an dem Beispiel an. Diese Instruktion hier ist schleifeninvariant, darf ich sie herausziehen?

S: Ja.

B: Wann dürfte ich das nicht?

S: Wenn es eine Möglichkeit gäbe, dass sie nicht ausgeführt wird.

B: Was muss sie also?

S: Alle Schleifenausgänge dominieren.

P: Kann man Teilausdrücke immer vorziehen?

S: Im Prinzip schon. Lohnt sich aber nicht immer, wenn sie nur in bestimmten Fällen überhaupt ausgewertet werden.

P: Wirklich immer?

S: Wenn Sie so fragen, wrsl. nicht. Aber ich bin mir relativ sicher, dass das so auf einer Folie stand.

P: Was kann denn schiefgehen? Wenn ich a * b vorziehe, nichts. Aber bei a / b, wenn b null ist… darf ich das?

S: Kommt drauf an, welche Bedingungen an Äquivalenz der Programme gestellt werden. Der Fehler tritt dann halt an einer anderen Stelle auf. Obwohl, wenn der jeweilige Pfad eigtl. gar nicht ausgeführt worden wäre, hätte das auch gut gehen können. Also hat man ein anderen Verhalten und darf das nicht.

B: Was sind denn Induktionsvariablen?

S: Einfache und abhängige: Bei einfachen wird pro Iteration ein konstanter Faktor addiert oder subtrahiert; abhängige lassen sich durch Multiplikation mit und Addition von einem konstantem Faktor aus den einfachen berechnen.

Nachdem man wieder herein gebeten wird, fragt einen Philippsen immer, was man sich selbst geben würde. Merke: Nur laut nachdenken gilt nicht. Es reicht auch nicht aus, auf den Einwurf „Auf die Frage kann man sich vorbereiten“ mit „1,0“ zu antworten – eine konkrete, ernst gemeinte Zahl muss auf den Tisch.

Letztenendes war die Note im erwarteten Bereich, relativ gut und für das Modul sowie den Verlauf der Prüfung absolut zufriedenstellend.