Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » ueb1-2014-02-10-1

  • Grundlagen des Übersetzerbaus (7.5 ECTS)
  • Prüfer: Prof. Philippsen
  • Beisitzer: Stefan Kempf

Papier und Stift waren da, sowie ein Blatt mit Code.

shared int g;
shared int h;
int[10][20] A;
 
int foo(){
    int i;
    int j;
    ....
    while ( j < 10 ) {    (1)
        A[i][j] := 2;       (3)
    ...
    atomic {                (2)
        g := g + 2;
        h := g + 1;
        return h;
    }
    ...
}
 
int bar(){
    g := g + 2;
}
 
int main(){
    int dummy;
    dummy := foo();
    return 0;
}

(P) Einstiegsfrage: Was macht denn der Compiler bei (1)

(S) Lexer erkennt while, {, j, <, … als Token, und gibt die dann aus. Der Parser bekommt dann die Token, erkennt, dass das ein while mit ner Bedingung ist und baut mithilfe von Regeln den AST zusammen.

(P) Erkennt der Parser bei dem j schon, welches j das ist?

(S) Nein, kommt erst später in der Analyse des AST

(P) Wir wollen jetzt atomic-Blöcke erlauben. Als shared deklarierte Variablen dürfen nur in atomic-Blöcken verwendet werden. Was müssen wir jetzt ändern? (Grammatik des Übungscompilers lag vor)

(S) Lexer muss atomic und shared als Token kennen, außerdem muss die Regel für VarDecl angepasst werden, um shared als modifier zu erlauben. atomic hätte ich als statement mit angehängtem Block modelliert

(P) Wie könnte man denn jetzt erkennen, ob shared-Variablen nur in atomic-Blocks verwendet werden?

(S) (da hing ich bissl) Wollte es als Bottom-Up verkaufen, dass man von der Verwendung einer Variable nach oben gehen kann, um zu sehen, ob man sich in einem atomic-Block befindet. Das geht aber nicht so einfach, Top-Down die Information mitzugeben ist einfacher.

(P) Wenn man jetzt eine neue Funktion hat, z.B.

int baz(){
     return (g + 2);
}

ist das dann automatisch ungültig?

(S) mit bissl draufhelfen: Nein, es kann ja sein, dass in einer anderen Funktion ein Block a la

atomic{
    dummy := baz();
}

steht, dann ist das gültig. Was wir also brauchen, ist außerdem Information über den möglichen Kontrollfluss, also welche Funktionen welche aufrufen (können).

(P) Okay, dann übersetzen wir Stelle (2) mal in Zwischencode, das atomic soll über Pseudo-Statements „LOCK var“ implementiert werden.

(S) Da muss man jetzt bissl aufpassen, weil ein return im Atomic-Block steht. Was man da machen könnte, ist z.B. die Semantik von returns unter x86 zu nutzen, dass der Return-Wert noch im Lock ins Register gelegt wird.

LOCK h
LOCK g
t1 := g + 2
g := t1
t2 := g + 1
h := t2
eax := h
UNLOCK g
UNLOCK h
return

(P) Jetzt kucken wir uns mal den Array-Zugriff in (3) an, wie würde denn da der AST ausschauen, und wie könnte man dann Code erzeugen?

(S) Erst mal linearisierten Code gebaut (A + (20*i + j)*4), und dann den Baum gezeichnet.

+
| \
A  *
   | \
   +  4
   | \
   *  j
   | \
  20  i

Code kann man dann entweder per DP, G&G oder Baumtransformation erzeugen.

(P) Sagen wir mal, wir machen Baumtransformation, die Maschine rechnet nur auf Registern und unsere Maschine kann (Basis+Index*Scale)-Adressierung. Wie sähe das dann aus, und welcher Code kommt raus?

(S) Wir brauchen Patterns für den Baum, also z.B. {Wert, Variable} → Register, (r_i + r_j) → r_k, (r_i * r_j) → r_k. Bei Anwendung der Regeln wird immer Code ausgespuckt. Pattern für Basis+Index*Scale wäre:

    +
    | \
Basis  *
       | \
  Offset  Scale

Dann die Variablen erst mal alle in Register, das „+“ noch rausreduziert und zum Schluss die Basis+Index*Scale-Adressierung angewendet. Code:

MOV A, r1
MOV 20, r2
MOV i, r3
MOV j, r4
MOV 4, r5
MUL r2, r3, r6
ADD r6, r4, r7
//x86-Syntax: (Basis, Index, Scale)
MOV irgendwas, (r1, r7, r5)

(P) Wir haben da ja jetzt viele Register verwendet, wie bildet man das auf echte Register ab?

(S) Graph-Färben, Kollisionsgraph, erklärt, wie sich der hier aufbaut, was eine Kante bedeutet. Grad<n-Regel erläutert und kurz umrissen, wie das hier funktionieren würde.

(P) Wenn wir das haben, ist das dann komplett fertig?

(S) Nein, wir können noch Instruktions-Scheduling machen. Erklärt, dass man da Top-Sort macht mit Kosten für die Ausführung und mögliche Wartezeiten (z.B. das MUL im generierten Code), dann Top-Down immer die Instruktion zuerst nehmen, die die höchste Wartezeit nach sich zieht.

Ergebnis: sehr zufrieden :-D Das leichte Hängen beim atomic wurde mir nicht groß angekreidet, sonst scheint es sich wirklich auszuzahlen, schnell zu antworten und nicht lange überlegen zu müssen, auch wenn's dann erst mal nur eine Rückfrage zur Klärung ist. Zeit war am Ende recht knapp, Graph-Färben und Instruktions-Scheduling war innerhalb von <5 Minuten noch dran.