Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Übersetzerbau 2 2016-10-10   (Übersicht)

Übersetzerbau 2 2016-10-10

Fach: Optimierungen in Übersetzern

Prüfer: Prof. Philippsen

Beisitzer: Marius Kamp

Der Beisitzer stellt wie üblich die Fragen. Philippsen wirft manchmal Fragen ein, oder sagt „passt schon machen wir weiter“ etc.

Codebeispiel

Der folgende Code war gegeben: (Es waren noch ein paar mehr unwichtige Statements drin)

static int c;
static int g;

int *get_ptr() {
        return &c;
}

int main() {
        int *p = get_ptr();
        int d;

        /* Teil 1 */
        for (int i = 0; i < 4000; i++) {
                d = *p + 4711;
                A[i, i] = d;
        }
        
        /* Teil 2 */

        for (int i = 0; i < 4000; i++) {
                for (int j = 0; j < 4000; j++) {
                        A[i][j] = A[i+1][j-2];
                }
        }
}

Fragen

Was muss der Compiler erst mal machen um diesen Code zu analysieren? → Kontrollfluss berechnen

Was ist Kontrollfluss/Kontrollflussgraph? → Grundblock erwähnen etc.

Was berechnet man auf Basis des Kontrollfluss? → Dominanz (mit Definition)

Wie würdest du das machen? → Tarjan/Iterativer Fixpunkt

Wie funktioniert Tarjan? → Hab groben Ablauf erklärt.

Mach doch mal! (Es wurde ein Zettel gegeben auf dem der spannende Tiefenbaum schon gegeben war) → SemDom erklärt und von zwei Knoten berechnet + Immdom erklärt und berechnet.

Und für was braucht man die Dominanz nun eigentlich? → Schleifen finden. (wichtige) Regionen erklärt.

Was ist eine „Schleife“? → Natürliche Schleife erklärt

Mal eine unnatürliche Schleife hin! → Standardbeispiel hingemalt

Was ist das Problem an so einer Schleife? → Erstmal erklärt, dass man vorallem invarianten Code aus der Schleife rausziehen will. Das wird bei einer unnatürlichen Schleife kompliziert etc.

Okay, zurück zum code Beispiel. Was gibt es an invarianten Code hier? → Ich habe die Zuweisung d = … markiert und erklärt warum. Philippsen sagte „Okay, nehmen wir mal an dass es wirklich schleifen invariant ist“ als Anspielung auf Alias was danach noch kam. Hier wie immer nicht aus der Ruhe bringen lassen nur weil Philippsen impliziert das etwas falsch wäre.

Was macht man jetzt damit? → Rausziehen. Definition von herausziehbar. Ich hab etwas gebraucht um zu merken, dass man die Schleife erstmal in do-while Form umbauen muss…

Ist das jetzt auch sicher Schleifeninvariant? → Nein, man muss erstmal Aliasanalyse betreiben.

Was ist das? Wie macht man das? Was für Geschmacksarten gibt es? → Erklärt was es ist. Fluss-sensitiv vs. Fluss-insensitiv. May vs. must. Intra vs. interprozedural.

Wann benutzt man welches Verfahren → …

Machen Sie doch mal Steensgaard! → Steensgaard ausgeführt. (Bei der Durchführung musste man nie etwas verschmelzen)

(Zwischendrinn war die Frage, welche Knoten der Graph hat und wie der Graph heißt) → Speichergraph und ein Knoten pro _Speicherstelle_

Was sagt der Graph nun? → *p und c sind Aliase, aber das ändert nichts an der Schleifen Invarianz.

Warum muss man Kanten verschmelzen → Dadurch gibts quasi-lineare Laufzeit.

Nun zu Teil 2. Was ist denn hier los? → Schleifengetragene Abhängigkeit. Erstmal die drei Arten erklärt. Abhängigkeitsdistanz hingeschrieben. (1, -2)

Kann man das jetzt paralellisieren? → Die j Schleife ja, die i Schleife aber nicht, weil sie die Abhängigkeit trägt.

Ich will aber die i Schleife paralellisieren! → Dafür muss aus der -2 eine 0 werden und dann kann man die Schleifen vertauschen. Dafür kann man die Schleife zuerst neigen.

Was ist neigen? → Man addiert die eine Laufvariable auf die andere mit konstantem Faktor f.

Wie ist der Faktor bzw. wie schaut der neue Distanzvektor aus? → (1, -2 + f * 1) Also ist der Faktor 2

Mach mal! → Hier wollten sie hauptsächlich sehen, dass man die Grenzen richtig anpasst.

So und jetzt können wir einfach tauschen? → Nein, weil die innere Grenze von der äuseren Variable abhängt. Also muss man das mit Motzkin oder so anpassen. (Mehr als eine Erwähnung war nicht verlangt)

Hat ein Blatt mit Grundblöcken und schon berechneten Dominanzgrenzen rausgezogen. Ich hab gleich begonnen SSA und SSA Transformation etc zu erklären. Professor Phillippsen hat mich gestoppt nachdem ich PHI Funktionen erklärt hatte und gefragt wie die Rücktransformation denn richtig funktioniert. Habe die richtige Rücktransformation hingeschrieben.

Warum soll das jetzt richtig sein? → Ähm keine Ahnung… Sie wollten eigentlich die Erklärung zu überschneidenden Lebensspannen hören. (Ich erinnere mich nicht mehr an den genauen Wortlaut der Frage, aber er hat quasi gesagt, dass es so falsch wäre. Mal wieder nicht aus der Ruhe bringen lassen)

Bewertung

Obwohl ich ein paar Sachen nicht ganz genau wusste wars eine 1,0. Phillippsen hat mir zu Gute gelegt, dass wir sehr viele Fragen durch geschafft haben. Also passt auf, dass ihr Fragen zügig beantwortet. Rumlabern hilft euch hier nicht. Alles in allem sehr angenehme Prüfungsatmosphäre und auch faire Fragen.