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.
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:
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:
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