Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Allgemein   (Übersicht)

Allgemein

Philippsen konnte nicht selber prüfen deshalb wurde ich nur von den Tutoren geprüft.

Eigentlich werden die 3 Phasen vom Compiler durchgegangen und zu den jeweiligen Stationen detailfragen gestellt. Diese sind allerdings vorbereitet also muss man vermutlich alle Verfahren in allen Stufen erklären und anwenden können. Habe relativ viel selbst geredet und erzählt bis mir nichts mehr einfiel. War trotzdem viel zu schnell und bin am Ende in die Detailfragen reingeschlittert.

Prüfungsathmosphäre war entspannt und man kann sich Dinge auch erarbeiten wenn man dabei sagt was man gerade denkt.

Prüfung

Analyse

Was ist denn ein Compiler?

  • Lexer/Parser erklären usw wie in den anderen Protokollen.
  • Lexer: Zeichenstrom zu Tokenstrom
  • Parser: Tokenstrom mit Grammatik zu KONKRETEM STRUKTURBAUM
  • Danach Typrechnung und Symbolanalyse ergeben AST

Warum teilt man diese?

  • Lexer kann schön mit REGEX gemacht werden
  • Parser ist kompilizerter und kann daher auch Typ2 Grammatiken parsen
  • Parser wird durch Lexer schneller
  • Lexer kann auch Verschiedene Encodings abfackeln usw.

Variable wird „int“ genannt, wo schlägt das fehl (also statt „int a“ „int int“)?

  • Hier habe ich mich etwas verplappert. Es wurde dann im Detail nachgefragt wieso genau es wo Fehlschlägt, konnte es mir dann erarbeiten.
  • Im Parser da der Lexer nur token macht (Lexer produziert TK_INT TK_INT was kein Wort der Grammatik ist)

Abbildung

Habe dann ein Codeschnipsel bekommen mit geschachtelten funktionen. Sah oBdA so aus:

int outersum(int[] arr) {
    ...
    int innersum(int a, int b) {  // [1]
        ...
        if(...) {
            return innersum(3,4)  // [2]
        } else {
            return innersum(arr[0], 5)  // [3]
        }
    }
    return innersum(1,2)  // [4]
}

Wie würde ein Compiler das denn transformieren?
Wie sieht die neue Funktion aus? (vorne oder hinten FP argument einzeichnen)
Wo werden Zugriffe transformiert?

  • Framepointer und Stacks erklärt
  • Innere Funktion ins global Scope
  • Signatur Anpassen mit Statischen Vorgängerverweis SV
  • Zugriffe auf äußere Variable über SV
  • Habe an konkreten Punkten erklärt:
    • [1] innere funktion muss nach aussen als globale funktion (Nameskollisionen erwähnen)
    • [2] rekursiver aufruf → SV hinzufügen (dh funktion hat dann signatur „int kollissionenvermeiden$innersum(fp *SV, int a, int b)
    • [3] Zugriff auf arr MUSS auch transformiert werden (zugriff über SV), auf Symbolanalyse eingehen
    • [2,3] aufruf innersum muss SV durchschleifen
    • [4] aufruf von innersum muss SV (FP von outersum, das ist der aktuelle) als argument mitgeben

Zwischensprachen, warum braucht man die?

  • Mehr Zielarchitekturen leichter zu unterstützen
  • evtl bessere und vor allem leichtere optimierungen möglich

Codierung

Baumtransformationsregeln mit Baum bekommen

        *
   +        +
a    b    c    d

gab alle normalen regeln und eine große:

          *
R -> R     +
           R   R

Nach was sieht das denn aus?

  • Baumtransformationen
  • Habe dann von selbst erklärt dass man von oben die Regeln matcht und dann von unten Code erzeugt
    • Kollision kleine und größe regel erklären und mit maximum munch auflösen (maximum munch)

Worauf muss man dabei achten?

  • Keine registervergabe
  • Blätter müssen einzeln regeln haben, generatorproblem
  • Hier wollten sie glaube ich auf was anderes raus, kann mich aber nicht mehr genau erinnern

Habe dann bereits generierten Zwischencode bekommen. Weiss nicht mehr genau wie er aussah das Verfahren funktioniert aber immer gleich, es gab eine MOV instruktion auf die man eingehen hätte können.

Wie macht man danach dann hier die Registervergabe?

  • Reduktion auf Graphfärbung
  • Lebensspannen definieren, quasi: „Zuweisung bis letzter möglicher Lesezugriff vor nächster Zuweisung“
  • Von unten durchgehen, alle Variablen sind Tot
  • Jede Zeile bei Zuweisung „v0 = add v1, v2“ beginnt linke seite (v0) und auf der rechte seite (v1, v2) enden falls sie nicht schon leben.
  • Kollissionen sind dann gleichzeitig existierende Lebensspannen
  • Start und Ende von zwei Lebensspannen kollidieren nur bei gewissen Architekturen (nicht bei 3 Registeraddressierung)

Mir wurde dann gesagt dass ich das Blatt umdregen solle. Blatt umgedreht, Graph war bereits angegeben, sah ungefähr so aus:

    --- (v4) --- (v0)======= <- MOVE Kante
   |       |    /    |                |
   |    (v3) --- (v1)--------(v5)
   |   /              |
(v2)-------------

(+ Registerclique, r0, r1, r2)

Für was stehen hier Knoten und Kanten?

  • Knoten: Lebenspannen (müssen nicht den Variablen entsprechen → können geteilt werden)
  • Kanten: Kollisionen von Lebensspannen (Gleichzeitige Existenz), da diese nicht in das gleiche Register können

Wie wenden sie das Verfahren nun an?

  • v0 mit v5 verschmelzen da bereits alle nachbarn von v5 kante mit v0 haben, erfüllt somit eine der drei Coalescing Regeln:
    • Grad Summenknoten < R
    • Weniger als R Nachbarn mit Grad >= R
    • Jeder Nachbar von einem Knoten:
      • Interferiert bereits mit dem anderen
      • ODER hat Grad < R
  • Grad<R nacheinander auf den Stack, (gab noch paar einzelne mit Grad < R)
  • Optimistische erweiterung erklären weil alle knoten Grad >= R, dh. Spill Knoten markieren und Trotzdem weitermachen, also Spill (v3) auf den stack und dann nacheinander (v2),(v4),(v1),(v05)
  • Stack rückwärts auslesen und farben vergeben die nicht mit den bereits vergebenen Kollidieren (habe die Farben an die Knoten im Graph geschrieben)
  • beim spill knoten angekommen, keine farbe möglich, also gesagt dass nun spillcode erzeugt werden muss

Un wie machen sie jetzt weiter?

  • VON NEU ohne spillknoten beginnen da keine färbung möglich (war mir nicht sicher aber nach ein paar nachfragen konnte ich es mir denken)

[Hier hat er schon auf die Uhr geschaut hatte aber noch massig zeit]
Was kann man denn danach machen?

  • wollte auf Pipelines und ILP hinaus, also das erklärt
  • DAG generieren, latenz und execution time von unten annotieren

Wie genau siehr hier ein Schleifenzähler aus?

  • loops unmöglich da DAG, wusste aber auch nicht wie die verhindert wird (wurde im ende als detailfrage gewertet und war wohl nicht so wichtig)

[Wieder ein Blick auf die Uhr]
Debugger, was ist das?

  • Über debugger geredet, war ne generelle frage
  • Betriebssystem ermöglich Prozessen sich al Debuggee anzumelden
  • Danach kann ein anderer Prozess mit z.B. PTRACE debugging beginnen (ist somit Debugger)
  • Debugger hat über Betriebssystem Zugriff auf Register und Speicher des Debuggees

Wie implementiert man Breakpoints?

  • ersetzten im Maschinencode mit Trap instruktion (unschön, kann unterschiedliche länge haben in x86)
  • oder nutzen der Hardwareregister die trap bei Instruktionszähler XY auslösen

Was sind Watchpoints?

  • Zum Speicherüberwachen, adressenzugriffe werden abgefangen und lösen auch trap aus
  • habe gesagt dass man watchpoints über speicherschutz implementieren könnte auch wenn das unschön wäre weil viele false positives

Wie würde man Watchpoints implementieren ohne Speicherschutz (Flat Memory)?

  • Fiel mir nicht ein, Zeit war aber auch um
  • Man könnte Single Step execution machen und jede instruktion schauen ob ein zugriff passieren würde