Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Optimierungen in Übersetzern (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

--- pruefungen:hauptstudium:ls2:ueb2-2015-08-19 [19.08.2015 11:49] – angelegt Rachus
+++ pruefungen:hauptstudium:ls2:ueb2-2015-08-19 [19.08.2015 19:11] (aktuell) – Rachus
@@ Zeile 3: / Zeile 3: @@
 **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 =====
@@ Zeile 14: / Zeile 18: @@
 ...
+OUTER:
 if ... goto END
@@ Zeile 23: / Zeile 28: @@
         e = b + c;
-        array[d] = e;
+        array_b[d] = e;
         d -= 1;
         goto INNER
@@ Zeile 30: / Zeile 35: @@
     ...
+goto OUTER;
 END:
@@ Zeile 39: / Zeile 46: @@
       * Kontrollflussgraph erstellen
       * Dominatoren bestimmen
-        * z.B.: Fixpunktalgorithmus
+		* Prüfung Variante 1:
-        * Warum funktioniert er?
+          * z.B.: Fixpunktalgorithmus
-        * 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?
+          * 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
-        * Und in schnell? (Nur Kopf einer wichtigen Region kann Schleifenkopf sein)
+        * Variante 1: Und in schnell? (Nur Kopf einer wichtigen Region kann Schleifenkopf sein)
-        * Worklistalgorithmus zum Schleifenknotensammeln
+        * 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
-      * Zugriff auf Array kann mögliche abhängige Induktionsvariable tmp (d, 4, 0), oder ähnlich erzeugen
+      * 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.
@@ Zeile 59: / Zeile 73: @@
     * 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
-  * Dominatorgrenzen
+    * 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