Prüfung vom 23.07.2026

• Prüfer: Prof. Philippsen
• Beisitzer: Tobias Heineken

(F)rage, (A)ntwort

F: Was macht ein Compiler denn als erstes mit Programm-Code, wenn er optimieren will und warum?

A: KFG (für Analysen, um Legalität der Optimierungen zu garantieren)

F: Was ist ein KFG und bauen Sie mal einen.

F: Was ist SSA und machen Sie mal Wertnummerierungsverfahren (Da wollten Sie bei mir genau wissen, wann eine vorläufige Phi-Funktion bearbeitet wird).

F: Was ist ein Alias und warum müssen wir das wissen?

A: Alias = selbe Speicherstelle über zwei unterschiedliche Identifier erreichbar. Brauchen das für Legalitäts-Check bei z.B. Konstantenfortschreibung.

F: machen Sie mal Steensgard (Der Code war einfach 35 Zeilen lang ) hier mal eine stark gekürzte und vereinfachte Version:

int r;
void foo(int a) {
    int c = 5;
    int *ptr = &c;
    ptr = &a;
    
    
    r = a + 13 + c;
}

raus kommt: ptr → {c, a}

F: Was sind denn hier jetzt Aliase?

A: Alias sind {ptr, a}, {prt,c} und {a,c} (v.A. auf letzteres wollten sie als spannendes Resultat hinaus, weil man mit Steensgard alleine hier keine Konstantenfortschreibung machen kann)

F: Hier Blatt mit Code, was kann man hier machen?

int A[10, 20];
void foo(int p) {
    for (int i = 0; i < p; i++) {
        A[1, i] = A[0,p];
        A[1,i] = p + 13;
    }
}

A: Schleifeninvarianten Code rausziehen

int A[10, 20];
void foo(int p) {
    int t1 = A[0,p];
    int t2 = p + 13;
    for (int i = 0; i < p; i++) {
        A[1, i] = t1;
        A[1,2*i] = t2;
    }
}

F: und jetzt will ich die Schleife parallelisieren…

A: erst Abhängigkeitsvektoren aufstellen: output-Abhängigkeit einmal d(≤) und d( = ), deswegen kann ich die Schleife nicht direkt parallel ausführen.

ab hier war ich bissi lost und hab Hilfe bekommen

Erst Loop-Peeling, damit die Abhängigkeit in der ersten Iteration weg ist:

int A[10, 20];
void foo(int p) {
    int t1 = A[0,p];
    int t2 = p + 13;
    
    if (p >= 0) {
        A[1, 0] = t1;
        A[1, 0] = t2;
    } 
    
    for (int i = 1; i < p; i++) {
        A[1, i] = t1;
        A[1, 2*i] = t2;
    }
}

Jetzt ist nur noch die eine output-Abhängigkeit vorhanden → jetzt ist Schleifenrumpfteilen möglich

Dann sind beide resultierenden Schleifen parallel ausführbar.