Übersetzerbau 2 2017-06-09

Fach: Optimierungen in Übersetzern

Prüfer: Prof. Philippsen

Beisitzer: Patrick Kreutzer

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.

In Übersetzerbau 2 haben wir diverse Analysen gemacht. Wozu brauchen wir Analysen überhaupt, warum sind die so wichtig? (Datenfluss- und Kontrollflussanalyse kurz erklärt und warum man sie braucht.)

Ich bekommen Code, der etwa folgende Struktur hatte:

   int b = 0;
   
   for(int b = 1; i < p; i++){
     if(p == 2){   
         if(b == 1234){
           a = 3;
         } else {
           b++;
         }
     } else {
         a = 5;
     }
     a = a * 91;
   }
   
   return a; 
 

Wir möchten nun Variablennutzung, die potentiell einen undefinierten Wert haben, erkennen. Wie machen wir das? (Brauchen Kontrollflussgraph, was ist das, was ist Grundblock etc)

Bekomme den KFG fertig aufgebaut mit den jeweiligen Instruktionen auf einem Zettel. Und wie sieht die Datenflussanalyse für das Problem aus?

Datenflussanalyseverfahren beschreiben, (Vorwärts/Rückwärts, wie werden die Bits kodiert, was bedeutet ein einzelnes Bit, wann setzt man es, wann setzt man es zurück, Schnittmenge oder Vereinigungsmenge, was macht der Basisblock…) [Wichtig: Nicht versuchen, es auf ein Verfahren aus der Vorlesung runterzubrechen, sondern ein 'eigenes' entwickeln!]

Wir haben ja auch noch SSA gemacht, was ist SSA? (SSA erklären, nur eine Starke, keine schwache Definition, einmal statisch im Code, Phi-Funktionen erwähnen, wichtig!)

Warum ist das toll? (Erleichtert Datenflussanalyse, mit Beispiel erklärt)

Lass uns das mal machen, wir funktioniert das? (Zwei Verfahren, Dominanzgrenzverfahren und Wertnummerierung)

Was ist eine Dominanzgrenze, wie berechnet man die? (Erklären mit den jeweiligen Mengen aus der Vorlesung)

Bekomme Dominanzgrenzen fertig auf einem Papier zum KFG. Mach mal Dominanzgrenzverfahren! (Dominanzgrenzverfahren am Beispiel gemacht, mit jeweiligen Phi-Funktionen und jeweiligen Werten)

Können wir damit herausfinden, ob eine Variablennutzung undefiniert ist? (Knifflige Frage, Antwort dazu: Ja, wenn man in den Phi-Funktionen Werte aus Blöcken hat, bei denen die jeweilige Variable nicht beschrieben wird (wie oben beim ersten Block b=0, bei denen a zuvor nicht definiert wird) kann bei der Phi-Funktion eine Variable ausgewählt werden, die nicht definiert wird. Diese propagiert sich zu den anderen Phi-Funktionen durch)

Wir haben uns auch mit Alias-Analyse beschäftigt. Hier ist etwas Code:

  int *p, a, b, c;
  
  // Code der nicht bekannt ist, aber was mit a, b, c macht
  
  if(x == 1) { p = &a; } else {p = &b; }
  
  *p = 5;
  // Hier wird a gelesen

  if(x == 2) {p = &c; } else {p = &c}
  
  *p = 3;
   // Hier wird a gelesen

   return c;

Wir möchten nun herausfinden, dass p zum Schluss auf c zeigt, zwischendurch aber auf a oder b. Welche Eigenschaften muss unser Analyseverfahren besitzen, um auf diesen Code anwendbar zu sein? [Wichtig: Hier nicht verunsichern lassen, eins der Vorlesungs-Verfahren zu nutzen oder diese explizit darauf hinzuoptimieren. Die passen hier alle nicht wirklich weil wir sicheres Wissen wollen, frei davon und sinnvoll antworten.] (Lösung: Must-Analyse (sicheres wissen von c), Flusssensitiv (ansonsten würde am Ende a, b, c alias von *p sein, intraprozedural (gibt keine Funktionen, deswegen reicht das))

Wir haben hier noch eine Schleife, warum sind Optimierungen an Schleifen so wichtig oder interessant für uns (Code wird mehrfach ausgeführt, Optimierung bringt hier am meisten)

Hier ist Code:

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

Diese Schleife ist anders als die, die wir in Compilerbau 2 sonst angeschaut haben, warum? (In Vorlesung und Übung waren es (fast) immer kanonische Schleifen, also perfekt geschachtelt, Instruktionen immer ganz innen)

Genau, das ist blöd. Was machen wir nun? (Schleifenrumpfteilen, Abhängigkeitsdistanzen aufstellen)

Wie funktioniert das? (Abhängigkeitsgraph aufstellen, gleiche starke Zusammenhangskomponente muss bleiben, bei Pfaden zwischen Instruktionen die Schleife jeweils davor. Sollte ich dann auch mal am Beispiel machen)

Danach noch Frage nach Parallelisierbarkeit und wie man das an den Abhängigkeitsdistanzen erkennt.