Optimierungen in Übersetzern

Prüfer: Michael Philippsen
Beisitzer: Thorsten Blaß

Das Prüfungsprotokoll beinhaltet zwei Prüfungen.

Allgemein

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.

Diese Prüfung wurde an diesem Tag mindestens zweimal in ähnlicher Weise gehalten. Am Ende wurd wie bei Prüfungen von Herrn Philippsen üblich die Frage nach der eigenen Einschätzung der Note gestellt.

Prüfungsverlauf

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

...

OUTER:
if ... goto END 

    ... 

    INNER:

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

    END_INNER:

    ... 

goto OUTER;

END:

Welche Induktionsvariablen gibt es?
- Hier ist damit anzufangen, wie der Compiler analysiert:
  - Einteilung in Grundblöcke
  - Kontrollflussgraph erstellen
  - Dominatoren bestimmen
- Prüfung Variante 1:
  - 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?
- Prüfung Variante 2:
  - Lengauer Tarjan: Wie funktioniert er. Nach vier Basisblöcken wurde dann der gesamte Domtree vorgegeben.
- Schleifen bestimmen
  - Rückwärtskante finden: Kante von dominiertem zu dominierenden Knoten
  - Variante 1: Und in schnell? (Nur Kopf einer wichtigen Region kann Schleifenkopf sein)
  - Variante 2:
    - Und sie haben jetzt erwähnt, dass es schneller geht, wenn man Regionen hat. Was sind wichtige Regionen? Siehe Folien
    - Warum beschleunigt dies das Schleifenfinden? Nur zum „ausgezeichneten Knoten“ der Region eingehende Kanten müssen betrachtet werden
  - Worklistalgorithmus zum Schleifenknotensammeln (inkl.: Warum kommen wir nicht drüber hinaus)
- Einfache Induktionsvariable ist Variable, die bei jedem Schleifendurchlauf nur konstant inkrementiert wird.
  - Einschub: Schleifeninvarianz.
  - d ist einfache Induktionsvariable
  - Variante 1: Zugriff auf Array kann mögliche abhängige Induktionsvariable tmp (d, 4, 0), oder ähnlich erzeugen
  - Variante 2: Zugriff auf Array kann mögliche abhängige Induktionsvariable tmp (d, 4, array_b) erzeugen, wobei array_b Anfangsadresse des array ist
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
- Variante 2: Reicht aber doch nicht aus. Welche Bedingungen noch? (Einzige Zuweisung, alle Verwendungen strikt dominiert)
- while {} → if() { do {} while (); } am Beispiel gemacht
- Variante 2: Schleifeninvariante Teilausdrücke:
  - Kann ich doch immer rausziehen? Nein. z.B. temp = a/b, b könnte 0 sein,…
  - Ist umgebende Bedingung auch bei Teilausdrücken nötig? Nein, nicht zwingend, aber meist zieht man Teilausdrücke raus, die teuer sind → spart also im Mittel Laufzeit.
- Wo wird dann der herausgezogene Code genau platziert?
Variante 1: 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.
Variante 2: Kontrollflussanalyse/abhängigkeit
- Was ist das?
- Wie kann ich die Kontrollflussabhängigkeit berechnen? (Graph invertieren, Dominanzgrenzen, siehe Folien…)
- Dominanzgrenzen: Wie werden diese berechnet? DG_{local}, DG_{up} am Beispiel erklärt