Übersetzerbau 2 2015-07-27

Fach: Optimierungen in Übersetzern (7,5 ECTS)

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 removel (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: Zum Schleifen finden.

B: Wozu sonst noch?

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 ist SSA-Form ist eine Möglichkeit, an den Dominanzgrenzen Phi-Funktionen einzufügen.