Prüfung vom 12.09.2024

• Prüfer: Prof. Philippsen
• Beisitzer: Tobias Heineken
• Raum: Aquarium
• Note: 1.0

Saßen in der hinteren Reihe, vor mir Prof. Philippsen, links Tobias. Ablauf wie aus UE1 bekannt.

(F)rage, (A)ntwort

F: <Zettel> Wir haben hier ein e2-Programm, was haben wir denn in dieser Veranstaltung so gelernt?

func main(): int
    var a: int;
    var b: int;
    
    a := 4;
    b := 7;
    return 3 * a + b;
end

A: Optimierung damit unser Programm schneller läuft und weniger Speicher braucht. Hier kann man zB eine Konstantenweitergabe machen.

F: Wie würde das aussehen?

A: a nach unten ziehen, b auch, Ausdruck kann dann statisch zur Übersetzung berechnet werden.

F: Wir haben ja auch generell noch andere Analysen gelernt, die man anwenden möchte, was wären da so Beispiele?

A: Kontrollflussanalyse ist schonmal sehr wichtig, oder…

F: Wie macht man ne Kontrollflussanalyse?

A: Erstmal Grundblöcke bestimmen. <(Maximale) Grundblöcke erklärt> Um die zu bestimmen brauchen wir den Zwischencode.

F: <Zettel mit Zwischencode> Mach mal…

<trivialer e2-IR von Programm oben>

A: Hier ja sehr einfach, weder Labels noch Jumps, ganze Funktion ist ein Grundblock.

F: <Zettel> Und hier?

# Keine Ahnung wie der Code genau aussah, hier exemplarisch mal von nem Sort
.global a : int[10]

.func main : int
  .local i$0 dummy$0 : int
  .virt %v10 %v11 %v12 %v13 %v14 %v15 : int
  .code
      a[$0] = store $3
      a[$1] = store $5
      a[$2] = store $1
      a[$3] = store $9
      %v10 = call sort($4)
      dummy$0 = mov %v10
      i$0 = mov $0
      jge i$0, $10, L8
    L7:
      %v12 = load a[i$0]
      %v11 = call writeInt(%v12)
      dummy$0 = mov %v11
      %v13 = call writeChar($32)
      dummy$0 = mov %v13
      %v14 = add i$0, $1
      i$0 = mov %v14
      jlt i$0, $10, L7
    L8:
      %v15 = call writeChar($4)
      dummy$0 = mov %v15
      ret $0

A: <Angefangen Grundblöcke von oben nach unten zu bestimmen, hatte erst bei den calls einen Block aufhören lassen. Fragende Blicke und Gekritzel auf den Bewertungsbogen. Hab das dann erklärt, dass in der aufgerufenen Funktion ja ein exit passieren kann und man dann ggf über die globale Variable beobachtbare Veränderungen hat. Augenbraue gesenkt, Gekritzel durchgestrichen, gesagt ich soll ohne den Randfall weiter machen> Jetzt bauen wir daraus einen Kontrollflussgraphen. Knoten sind die Grundblöcke, gerichtete Kanten dazwischen, die zeigen an welcher Grundblock potentiell von anderem erreicht werden kann. Entry und Exit noch zusätzlich als Hilfestellung. <Fange an zu malen…>

F: <Zettel mit fertigem Kontrollflussgraphen, wurde aber glaub ich nicht weiter verwendet. Nochmal Zettel mit e2-Programm> Wie machen wir jetzt die Konstantenweitergabe hier?

func main(): int
    var a: int;
    var b: int;
    var t: int;

    a := 4;
    b := 7;

    while readChar() != 'Q' do
        t := a;
        a := readInt();
        writeInt(a + 13);
        a := t;
    end

    return 3 * a + b;
end

A: Hier wird a in der Schleife beschrieben, Konstantenweitergabe so erstmal nicht möglich.

F: Ein geübtes Auge sieht hier doch noch mehr!

A: Ah, a wird in t zwischengespeichert und am Ende wiederhergestellt. Dann geht das ganze natürlich doch.

F: Wie würde da ein Compiler vorgehen? <Gibt KFG noch dazu>

A: <Rede von Dominanzen, Datenfluss und Fixpunkt, werde dann in die Schranken gewiesen>

F: Hier konkret jetzt, da brauchen wir nicht voll auf die Glocke zu schlagen.

A: SSA kann man machen, dann sieht man dass es immer das selbe a ist. <SSA kurz erklärt>

F: Welche Verfahren gibts denn so um die SSA-Form zu bilden?

A: Dominanzgrenzenkriterium, bräuchte man Dominanzen. Oder Wertnummerierung, geht auch schon beim parsen vom Zwischencode.

F: <Zettel mit KFG> Dann machen wir mal letzteres.

A: <10 Minuten Click/Braun exerziert, Tücken waren hier, dass man zum einen die Selbstkante richtig behandeln muss (zweiter Parameter der φ'-Funktion noch nicht eintragen) und die φ'-Funktionen erst ganz am Ende aufzulösen, siehe Vorlesung und Übung> Jetzt können wir noch prunen, dann sehen wir auch, dass hier am Ende die Konstante durchkommt!

F: <Zettel> Auf was muss man bei dieser Version achten?

var a: int;
var b: int;

func main(): int
    var t: int;

    a := 4;
    b := 7;

    while readChar() != 'Q' do
        t := a;
        a := readInt();
        magic(a);
        writeInt(a + 13);
        a := t;
    end

    return 3 * a + b;
end

func magic(p: int): void
    a := p;
end

A: a und b global, magic-Aufruf dazwischen, der potentiell globale Variablen ändert und im Falle hier mit a auch tut. Als Mensch sieht man zwar immer noch, dass der Aufruf effektiv gar nichts tut, wenn der Compiler aber rein intraprozedural vorgeht kann er das nicht beweisen. Globale Variablen auch nicht in der SSA, also geht das auch nicht.

F: Wie siehts mit b aus?

A: Auch global, muss bei nem Aufruf pessimistisch davon ausgehen, dass sich potentiell alle globalen Variablen geändert haben.

F: Wenn man sich jetzt magic mal genauer anschaut?

A: Eigentlich ziemlich trivial, könnte man inlinen, dann siehts der Compiler auch.

F: <Zettel> Einmal beschreiben:

// irgend sowas... (in Farbe gedruckte) Ausgeburt der Hölle auf jeden Fall...
for (int i = 3; i < 70; i++)
    for (int j = 101; j > 12; j--)
        for (int k = 2; k < 40; k += i)
            A[i, j, k] = A[i - 1, k, j] + A[2 * i - 1, k + 1, j] * B[k - 1, j, j]

A: Also erstmal sehen wir hier drei kanonische Schleifen <kurz erklärt was das ist>, die nicht grade schön ausschauen…

F: Ja das war natürlich Absicht :) Wie geht ein Compiler damit um?

A: Man will Abhängigkeiten feststellen, zB mit Distanz-/Richtungsvektoren. Die kann ich mir hier glaube ich mit Draufgucken sparen, Iterationstabelle wird auch nix.

F: Sowas macht ein Compiler ja nicht, wie würde der das lösen?

A: Ungleichungssystem, dann mit Fourier-Motzkin lösen…

F: Dann stellen wir das mal auf.

A: Schleifengrenzen erstmal noch trivial… <Dann grober Patzer, hab erst die Indizes als Gleichung hingeschrieben, ist natürlich Käse, weil das ne Abhängigkeit in der selben Iteration bedeuten würde, wurde allerdings früh drauf aufmerksam gemacht. Dann noch die Umbenennung der Laufvariablen vergessen ¯\(ツ)/¯ Bin allerdings zum Glück noch auf die Einbeziehung der Laufrichtung (∠) gekommen>

F: <Erleichterung bei Tobias, weil er seine Frage jetzt doch noch stellen kann> Wie löst man das ∠ jetzt auf?

A: Logische Operatoren, ∨ und ∧ Verküpfungen.

F: Aber so ein Fourier-Motzkin kann ja schlecht logische Operatoren verwenden.

A: Da macht man ne Fallunterscheidung. Bei ∨ wird gesplittet, alle „normalen“ Ungleichungen kommen bei beiden Fällen mit. ∧ kann man normal in zwei einzelne Ungleichungen aufteilen,

F: Und was ist dann das Ergebnis?

A: Hier konkret O.o oder allgemein?

F: Allgemein…

A: Wenn da ne ganzzahlige Lösung rauskommt, dann existieren Abhängigkeiten.

F: Und wie sieht das mit dem += i aus? Das muss man ja auch noch irgendwie behandeln.

A: Hm ja, da müsste man noch testen, ob eine Lösung davon in k nen Teiler von i hat.

F: „Eine“ Lösung?

A: Achso ja, bei Fourier-Motzkin kommt ne Lösungsmenge raus. Wenn die am Ende nicht leer ist dann haben wir Abhängigkeiten.

F: <Zum Glück neuer, einfacherer Code> Wir haben ja noch ein bisschen Zeit, wie sieht's hiermit aus?

for (int i = 0; i < 10; i++) {
    for (int j = 1; j < 20; j++ {
        t = B[i, j] + A[i, j + 1];
        A[i, j] = t;
    }
}

. . . t . . .

A: Generell will man ja parallelisieren, hier aber erstmal das t im Weg. Man kann Skalarvervielfachung anwenden und aus dem t ein Array bauen. Muss man aber aufpassen, weil am Ende noch lebendig, also Rekonstruktion aus T-Array am Ende der Schleifen. <Distanzvektor aufgestellt> Dann kann man schonmal die äußere Schleife parallel ausführen.

F: Und wenn wir das noch zusätzlich mit der inneren machen wollen?

A: Schleifenneuausrichtung, sieht dann so aus: <gezeigt, eine Iteration mehr, Index j + 1 angepasst> Jetzt ist die getragene Abhängigkeit weg, man muss aber noch wegen den Iterationsgrenzen aufpassen, deswegen hier nochmal if drum rum <kritzel>, weil if in Schleife aber blöd ist schälen wir die Iteration ab…

Zeit um

Grundblock und call wurde nur kurz angesprochen und auf UE3 verwiesen, hat sich nicht negativ ausgewirkt.

Die Ungleichungen/Fourier-Motzkin allerdings schon, weil in der Schleifenanalyse danach aber die Abhängigkeit mit dem t sofort erkannt und auch die zweite flott aufgelöst wurde, hat man sich noch auf die Kurve zur 1.0 einigen können.

Genaue Begriffe waren nicht unbedingt relevant (die ich auch hin und wieder vergessen hatte), solange man die Algorithmen schnell und korrekt anwenden kann.