Übersetzerbau 2 2021-10-11

Fach: Optimierungen in Übersetzern

Prüfer: Prof. Philippsen

Prüfung läuft ab wie bereits am 09.06.2017 beschrieben:

Wie üblich stellt der Beisitzer die Fragen, Prof. Philippsen selbst fragt nach, falls die Antwort nicht eindeutig oder tiefgehend genug war. Papier und Stift liegen bereit und dürfen (und sollen) bei Beantwortung der Fragen genutzt werden.

Welche Analysen haben wir denn in Ue2 so gemacht? Kontrollfluss, welche in einem KFG resultiert und verschiedene Datenflussanalysen.
Was ist ein KFG? Knoten sind Grunblöcke, Kanten sind mögliche Ausführungspfade.
Was sind GB? Ein maximaler Grundblock ist ein maximales Stück Code, welches auf jeden Fall ohne Unterbrechung ausgeführt wird. Ein GB endet somit bei einem Sprung oder bei einem Label.
Kann ein GB auch nur eine Zeile beinhalten? Man kann die GB beliebig klein machen, die Frage ist nur ob es sinnvoll ist.
Code vorgelegt:

jlt $i, 6, L1
jmp L2
L1:

Kann ich hier optimieren? Ja, man dreht die Bedingung beim ersten Sprung und streicht den zweiten.
Können Sie das verallgemeinern? Wenn ein bedingter Sprung direkt vor einem Unbedingten kommt.
Anderes Thema: Schleifen. Wie finde ich eine Schleife? Zuerst muss ich die Rückwärtskanten finden. Def. Rückwärtskanten erklärt.
Gibt es hier Rückwärtskanten?

                Entry
                   |
                   v
             ---  B1
             |      |
             |      v
             |     B2 <-
             |      |    |
             |      v    |
             ------>B3---|
                    |
                    |
                    v
                   Exit

Nein
Wenn die Kante von B1 nach B3 nicht wäre? Dann schon
Wie finde ich alle Knoten, die zur Schleife gehören? Algorithmus aus Vorlesung erklärt.
Was sind unmittelbare Dominatoren? siehe Definition
Welche Struktur haben diese? Dominatorbaum
Wie finde ich die ImmDoms? siehe Algo (Fixpunkt)
Wieso bilde ich bei diesem Algorithmus die Schnittmenge aus den Dominatoren der Vorgänger? (Hier hab ich etwas länger gebraucht) Wenn man nicht die Schnittmenge hätte, könnten auch Dominatoren in die Menge aufgenommen werden die keine sind. (Ich habe anhand einer Zeichnung erklärt, wieso Dominatoren der Vorgänger, welche sich nicht in der Schnittmenge befinden, u.U. keine Dominatoren den aktuellen Knoten sind
Welche Optimierungen kann bei Schleifen machen? Schleifeninvarianten Code rausziehen.
Was ist das, und wann kann ich das machen? Siehe Def.
Was gibt es noch? Parallelisierung
Wann kann ich das machen? Hier hab ich angefangen, die Abhängigkeitsarten zu erklären.
Es gibt noch andere Unterscheidungsarten von Abhängigkeiten außer RAW, WAR, WAW. Schleifengetragene Abhängigkeiten.
Was ist das? Siehe Def.
Code:

for (int i - 1; i = N; i++) {
  a[i] = a[i+1] + d[i];
  for (int j = 1; j <= N; ++j) {
    b[i,j] = b[i, j-1] * a[i];
  }
  c[i] = a[i-1] + b[i,N];
  d[i] = a[i+1] * 3;
}

Erklären sie mal Abhängigkeitsdistanzen Siehe Def.
Was ist die Abhängigkeitsdistanz in diesem Beispiel? Wir haben hier keine kanonische Schleife.
Was machen wir dann? Schleifenrumpfteilen, dazu brauchen wir einen Abhängigkeitsgraphen.
Machen sie mal

Fazit: Größtenteils keine schwierigen Fragen. Schwierig wird es wenn Prof. Philippsen fragt, wieso etwas funktioniert/terminiert. Es reicht nicht nur die Algorithmen auswendig zu können.