Übersetzerbau 2 2015-07-29

Fach: Optimierungen in Übersetzern

Prüfer: Prof. Philippsen

Beisitzer: Marius Kamp

Beisitzer stellt Fragen, Philippsen schreibt auf und hakt nur hin und wieder nach. Ich hab selbst fast nix aufgeschrieben (finde ich angenehm), nur bisschen gemalt. Der Beisitzer ist top - denkt schnell mit, weiß was er hören will, gibt sinnvolle Hinweise.

B[eisitzer]: Wir haben jetzt erstmal keinen konkreten Code ausgedruckt vorbereitet. Ganz allgemein, wenn du den tollsten optimierenden Compiler bauen willst, was brauchst du so/machst du so?

S[tudent]: Erstmal garbage wegwerfen, doppelte labels, sinnlose Sprünge, etc. Dann Kontrollflussgraph aufbauen.

B: Was ist das?

S: Besteht aus Grundblöcken, Grundblöcke fangen bei Instruktionen an, zu denen hingesprungen wird oder eine Instruktion nach dem Ende eines Grundblocks, sie hören da auf wo ein Branch ist oder eine instruktion vor dem Beginn eines Grundblocks. Der KFG gibt dann die möglichen Ausführungsreihenfolgen der Grundblöcke bei Programmausführung an.

P: Was ist mit Exceptions? Jeder Grundblock nur eine Instruktion lang?

S: Nö. Man mach einfach ne Pseudokante zum exception-handler, und ignoriert exceptions erstmal. Optimieren macht da wahrscheinlich eh erstmal nicht soviel Sinn.

B: Jetzt haben wir hier mal nen KFG (zeigt Beispiel). Was kann man da jetzt mit machen?

S: Dominanz ausrechnen. Habe zwei Verfahren erklärt (Fixpunkt aus VL und anderes sehr simples N^2-Verfahren). Beim Fixpunkt hab ich kurz gehangen, weil ich vergessen hatte zu sagen dass man die Dominatoren der Vorgänger schneidet und mit dem aktuellen Knoten vereinigt (ich hatte nur vereinigt gesagt). Mir wurde aber schnell geholfen und ich kam dann auch drauf.

B: Ja, was will man denn am meisten optimieren?

S: Schleifen, weil die oft ausgeführt werden. Es gibt zwei Arten, natürliche und unnatürliche. Hier ist eine unnatürliche, das sieht man per draufgucken oder T1/T2-Algo (erklärt).

B: stimmt. und natürliche Schleifen?

S: Rückwärtskante suchen, Ziel davon ist Schleifenkopf. Ziel: Finde Blöcke, die Teil der Schleife sind, angefangen Algo zu erklären, wurde sehr schnell mit „stimmt schon“ unterbrochen.

B: Legt mir Code vor mit einer Schleife. ca so:

int arrA[2048][2048];
int arrB[2048][2048];

int *getA() { return arrA; }
int *getB() { return arrB; }

main() {
  int c = 0;
  A = getA();
  B = getB();

  for (int i = 1024; i < 2048; i++) {
    B[c][c] = 0;
    for (int j = 1; j < 2048; j++) {
      A[i][j] = A[i - 512][j] + A[i-512][j - 1];
    }
    c = c * c;
  }
  ...
  // mehr Dinge die ich nicht mehr brauchte iirc
}

S: Ja, also c ist immer 0. Die Zuweisung kann also weg, und die zweite Zeile ist B[0][0] = 0; Das kann ich rausziehen unter der Voraussetzung, dass A und B keine Aliase sind. Kurz nachgeschaut - sind keine Aliase.

B: Generell so Aliasanalyse, sag mal was.

S: Gibt zwei Formen, inter- und intraprozedural. Schnell und grob vs langsam und genauer, beim genaueren dafür Probleme beim Funktionsaufruf.

B: Und was nehmen wir hier?

S: Interprozedural, sonst müssen wir davon ausgehen dass A und B Aliase sind. Also Steensgard.

P[rüfer]: Ja äh, das musste jetzt schon erklären wie das geht. Vom Draufgucken sieht jeder, dass A und B keine Aliase sind.

S: *Malt Steensgard auf, mit Verschmelzung falls es ein Alias ist*

B: Und was ist wenn man da jetzt so bedingte Zuweisungen hat?

S: Wir gucken unabhängig vom kontrollfluss (habe keyword fluss-insensitiv nicht gebracht, war aber nicht schlimm), daher ist uns das egal. Alles andere zu teuer.

B: Ok, sind also keine Aliase. Was muss man beachten beim Rausziehen?

S: Erklärt Bedingungen, vergisst, die Schleife in do-while-Form zu transformieren.

P: Wo ist denn der Schleifenausgang?

S: Zeigt auf die schließende }

P: Mal mal KFG hin wo man das sieht.

S: ähja, „ohhh“.

P: Genau, reicht schon. Rest passt.

B: So, was machen wir jetzt mit der Schleife? Sag mal Abhängigkeitsvektoren!

S: *liest ab* (512, 0) und (512, 1)

B: Kann man die innere Schleife parallelisieren?

S: Klar, alle Abhängigkeiten werden getragen.

P: Und wenn ich die äußere Schleife vektorisieren will?

S: Macht keinen Sinn??? Hier hab ich ein bisschen gehakt. Es ging darum, dass wir ganz allgemein die äußere Schleife parallelisieren wollen. Ich hab dann angefangen und gesagt ich würde ne Produktschleife machen, da dann 64er-Streifen schneiden und alles ist gut. Damit waren sie zufrieden, aber:

P: oder man vertauscht einfach die Reihenfolge der Schleifen.

S: Achso, ja, das geht auch.

B: Was ist denn, wenn da jetzt nicht j - 1 sondern j + 1 stünde?

S: Ja dann kann man die Laufrichtung der inneren Schleife invertieren, und alles bleibt beim alten. Mit ein bisschen hin und her dann noch die Matrix erklärt inklusive Transformationsmatrizen.

B: So, jetzt haben wir noch SSA. Warum will man das?

S: Konstanten/Kopienpropagation ist toll

B: Was macht man da?

S: *Erklärt phi-Funktion*

B: Wo muss die phi-Funktion hin?

S: Dominanzgrenze, auch rekursiv (mit Erklärung).

B: Wie geht das andere Verfahren? Wie heißt es?

S: Wertnummerierungsverfahren komplett erklärt, inklusive bisschen Implementierungsdetails vom Übungscompiler.

B: Und wenn man das jetzt rückgängig machen will?

S: Gegenmaßnahmen von $Typ erklärt (war egal, dass ich den Namen nicht wusste), erklärt, dass es eigentlich nur auf die Lebensspanne ankommt, konventionelle SSA-Form erklärt (war gefühlt wichtig nicht *nur* konventionelle SSA-Form zu wissen)

P: Ja dann ziehen wir hier mal nen Schlussstrich, gehen Sie bitte kurz raus?

Typisches „was würden Sie sich geben“-Spiel, allerdings mit dem Kommentar „wir haben nicht lang gebraucht“ → 1,0 geraten und bekommen

Ich hab bestimmt diverse Dinge vergessen, die ich auch noch gefragt wurde. Mein Kopf ist etwas leer…