Optimierungen in Übersetzern

Prüfer: Michael Philippsen
Beisitzer: Thorsten Blaß

Bleistift und Papier gegeben. Desweiteren werden im Laufe der Prüfung Zettel präsentiert: Mit Code, mit dem Kontrollflussgraph (wenn man ihn mal selbst angefangen hat zu malen und sie glauben, dass man das kann) und mit dem Dominatorbaum. Teilweise hatte ich das Problem, dass ich nicht wusste, ob ich jetzt direkt das „Ergebnis“ sagen soll, oder wie der Compiler dahin kommt. Gewünscht schien aber immer zu sein, wie der Compiler dahin kommt. Insgesamt wirkte die Prüfung auf mich eher wie eine leichte, dafür aber auch strenger bewertet.

Es war Code vorgegeben, der ganz grob so aussah (Labels waren eigentlich Zahlen, etc.)

...

if ... goto END 

    ... 

    INNER:

    if d <= 0 goto END_INNER
    
        e = b + c;
        array[d] = e;
        d -= 1;
        goto INNER

    END_INNER:

    ... 

END:

• Welche Induktionsvariablen gibt es?
  • Hier ist damit anzufangen, wie der Compiler analysiert:
    • Einteilung in Grundblöcke
    • Kontrollflussgraph erstellen
    • Dominatoren bestimmen
      • z.B.: Fixpunktalgorithmus
      • Warum funktioniert er?
      • Warum kann ein Knoten in der Menge eines Vorgängerknotens nicht Dominator des momentanen Knotens sein, wenn der andere Vorgängerknoten diesen nicht auch als Dominator hat?
  • Schleifen bestimmen
    • Rückwärtskante finden: Kante von dominiertem zu dominierenden Knoten
    • Und in schnell? (Nur Kopf einer wichtigen Region kann Schleifenkopf sein)
    • Worklistalgorithmus zum Schleifenknotensammeln
  • Einfache Induktionsvariable ist Variable, die bei jedem Schleifendurchlauf nur konstant inkrementiert wird.
    • Einschub: Schleifeninvarianz.
    • d ist einfache Induktionsvariable
    • Zugriff auf Array kann mögliche abhängige Induktionsvariable tmp (d, 4, 0), oder ähnlich erzeugen
• Eliminiere d
  • tmp durch tmp', startend mit d, um 4 am Ende der Schleife inkrementiert ersetzen.
  • In Bedingung d durch tmp' ersetzen.
  • d aus innerer Schleife entfernen.
• Schleifeninvarianter Code? Herauszuziehen
  • Fixpunktalgorithmus zum Finden erklärt
  • e = b + c
  • Kann vorgeschoben werden
  • Bedingung: Dominierung aller Schleifenausgänge
  • while {} → if() { do {} while (); } am Beispiel gemacht
• Dominatorgrenzen
  • Was ist das?
  • Wofür kann man diese verwenden? (Kontrollflussabhängigkeit, SSA nach Cytron)
  • Wie berechnet man diese (erklären und an einem Beispiel vormachen)
  • Bitte formal DGup angeben.