Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » ueb2-2014-07-17   (Übersicht)

  • Optimierungen in Übersetzern (7.5 ECTS)
  • Prüfer: Prof. Philippsen
  • Beisitzer: Stefan Kempf
int A[65536];
 
int main(){
    int e = random();
    int f = random();
    int ret = 0;
 
    if ( e > 0 ){
        const void *labels = { &&out1, &&out2 };
        goto labels[e % 2];
    }
 
    for(int i = 4; i < 65536; i++){
        if ( e * f == 0 ){
            A[i] = A[i - 4] + e * f;
        }else{
            printf("A[i] = %d\n", A[i]);
        }
    }
 
out1:
    ret++;
out2:
    ret++;
out3:
    ret++;
 
    if (A[0] == 1){
        printf("A[0] == 1\n");
        ret += e/f + 1;
    }else{
        printf("A[0] != 1\n");
        ret += e/f + 2;
    }
 
    return ret;
}

(P) = Prüfer, (S) = Student

(P) Auf welcher Ebene des Codes optimiert man überhaupt?

(S) Zwischencode

(P) Mit was fängt man an?

(S) RemoveGarbage, z.B. unnötige Labels entfernen

(P) Wie ist das hier?

(S) Nur out3 entfernbar, Rest kann angesprungen werden. Code wird nicht entfernt, nur das Label selbst.

(P) Wäre in dem if ( e > 0 ) ein Funktionsaufruf, der labels[] übergeben bekommt, dürfte man dann out3 auch entfernen?

(S) Potentiell könnte eine Funktion natürlich das Array verändern, hier jedoch als _const_ deklariert → out3 sicher nicht angesprungen.

(P) Was kann man dann machen?

(S) KFG aufbauen (musste ich hier nicht machen, nur erläutern, dass von dem goto labels[e % 2] mehrere Kanten zu den Blöcken gehen, wo eben die Labels sind), Dominanzanalyse

(P) Wozu Dominanzanalyse?

(S) SSA, Kontrollflussabhängigkeiten, Schleifenfindung

(P) Was habt ihr zur Analyse implementiert?

(S) Lengauer-Tarjan

(P) Skizzier mal grob, was da passiert.

(S) Bottom-Up auf spannendem Tiefensuchbaum, Semidominatoren (Kandidaten für ImmDoms) bestimmen aus den Vorgängern, danach nochmal Top-Down drüber, um Pfade zu finden, die sich „drum rum mogeln“; musste ich wirklich nur grob machen, habe noch als kleine Skizze (ca. wie in der Vorlesung) erklärt, warum man den Top-Down-Pass braucht.

(P) Wie berechnet sich die Dominanzgrenze?

(S) Formeln für DG, DG_local und DG_up hingeschrieben und erläutert.

(P) SSA? Was ist das?

(S) Nur noch eine starke Definition, Durchnummerieren von Variablen, Phi-Fkt. an Dominanzgrenzen.

(P) Hat Intel dann ne Instruktion „Phi-Funktion“?

(S) Nein, muss aufgelöst werden, naiv hat aber Probleme, deshalb tmp-Variablen.

(P) Dann schauen wir uns mal die Schleife an, was kann man da machen?

(S) (Wollte loslegen mit Schleifenoptimierung, wurde gebremst). e*f ist schleifeninvariant, kann vorgezogen werden. Durch Invarianz der if-Bedingung geht auch Loop Unswitching, d.h. Schleife „nach innen“ ziehen. (mit mehr Hilfe: durch Konstantenfortschreibung aus der Bedingung heraus [CBE e*f, 0 ] kann man in den positiven Branch e*f = 0 propagieren, d.h. der Array-Ausdruck vereinfacht ich zu A[i] = A[i - 4];)

(P) Kann man das parallelisieren, wie findet man das raus?

(S) Abhängigkeitsdistanzen bestimmen, ist hier Fluss mit Distanz 4, RV = (<), naiv nicht parallelisierbar. Aber: Wenn man Streifenschneiden macht, also parallel A[0] bis A[3] bearbeitet, dann A[4] bis A[7] etc., kann man in diesen Streifen parallel rechnen.

(P) Noch zum if unten, wir hatten ja auch Vorhersehbare Ausdrücke…

(S) Erst mal naiv drauf los, Definition gesagt und gesehen, dass e/f an sich vorhersehbar ist. Mit leichtem Draufhelfen dann aber festgestellt, dass ja f == 0 sein kann, und das Rausziehen vor die Schleife die Division by Zero vor dem printf statt danach stattfinden lässt → ändert die Semantik → geht nicht!