TU Wien:Codegeneratoren VO (Krall)/Prüfungsstoff WS10

... ohne Anspruch auf Vollstaendigkeit :-)

Ein Index zum Skriptum WS10 ist hier zu finden.

Stoff für die schriftliche Prüfung

Mit 3-4 Beispielen ist laut Aussagen des Professors zu rechnen. Alle Unterlagen sind erlaubt. Siehe Diskussion

Registerallokation

Angabe: Interferenzgraphen, Liveranges und def&uses

• man soll den Graphen faerben
  • Chaitin (Seite 128)
  • Briggs (Seite 118)
  • Chow (Priority-Based) (Seite 147)

Interprozedurale Registerallokation

Angabe: Liste von Prozeduren + L_REF (Local Reference Set) und Callgraph

• Parentset & Childset berechnen (aka. P_REF & C_REF, siehe Web Algorithmus)
• Web Algorithmus anwenden (ab Seite 220. Auf Seite 222 ist ein Beispiel zu finden)

Instruction Scheduling

• Listscheduling, Heuristiken anwenden
  • IBM Artikel (Seite 235)
  • HP Lab Paper (Seite 240)

• Software Pipelining
  • Modulo Variable Renaming (Seite 287)
  • loop, kernel, prolog, epilog
  • vermutlich: Initation Interval bestimmen

Bemerkung: Der genau gleiche Stoff ist auch im WS2011 und WS2012 gekommen.

Stoff für die mündliche Prüfung

Jeder bekommt drei Fragen. Kann eine Frage nicht beantwortet werden, so geht sie laut Aussagen des Prof. in der Runde weiter. Unterlagen sind -- nona -- nicht erlaubt. Pro Termin ist fix mit einer Frage aus dem SSA und/oder SIMD Paper zu rechnen (und das sollte dann wohl auch sitzen, wenn man sich die Autoren anschaut, heh).

Hier ein Versuch den Stoff ansatzweise zu erarbeiten:

Computerarchitekturen

Folgende Begriffe sollte man erklaeren koennen:

• CISC vs. RISC
• Mikroarchitektur
• ... nur weil die ISA RISC beschreibt, bedeutet das nicht dass eine konkrete Implementierung RISC sein muss
• Adressierungsarten
• Pipelining
• Superskalar
• Epic
• VLIW
• In-Order Execution & Out-of-Order Execution
• Bypass
• Branch Prediction

Zitat: "Man soll die Ueberschriften des PowerPC 604 Artikels erklaeren koennen"

Optimierungen

... sind auch im WUB Skriptum zu finden.

• Zwischendarstellung
• was kann man vom Front End erwarten?
• was fuer Arten von Dependencies gibt es bei
  • azyklische Graphen
  • zyklische Graphen
• Skalare Optimierungen
• Loop Optimierungen
• Common Subexpression
• und viele mehr \o/

Befehlsauswahl

• wie funktioniert iburg? (Blattknoten auswerten)
• Unterschied zwischen burg und iburg
  • burg: dynamische Programmierung (compile-compile time)
  • iburg macht das erst spaeter, daher koennen Kosten auch dynamische sein (TODO: bessere Erklaerung)
• Optimale Befehlsausahl auf SSA Graphen
  • PBQP (Partitioned Boolean Quadratic Problem)
    • AW: Problem ist NP-Complete. Es gibt zwei Mengen:
      • $X=\lbrace x_{1},\dots {},x_{n}\rbrace$
      • und fuer jedes $x_{i}$ gibt es einen Defintionsbereich $\lbrace \mathbb {D} _{1},\dots ,\mathbb {D} _{n}\rbrace$

Nun gibt es zwei Arten von Kosten:

• lokale Kosten: fuer $x_{i}$ wird ein $d_{i}\in \mathbb {D} _{i}$ gewaehlt. Die Kosten ergeben sich dann aus: $c(x_{i},d_{i})$
• benachbarte Kosten: $C(x_{i},x_{j},d_{i},d_{j})$

Die Gesamtkosten sind dann die Summe aller lokalen Kosten und aller benachbarten Kosten. Das Ziel ist es eine Zuordnung fuer jedes $x_{i}$ zu finden, die minimale Kosten ergibt.

Um das Instruction Selection Problem nun auf PBQP zu reduzieren, wird fuer jeden Knoten aus dem SSA Graphen ein $x_{u}$ eingefuehrt. Der Definitionsbereich fuer $x_{u}$ sind sogenannte "Base Rules" (i.e. Produktionen der Form $nt_{0}\leftarrow op(nt_{1},\dots ,nt_{k})$). Die Kosten der Funktion $c(.)$ ergeben sich dann z.B. aus der Anzahl der Zyklen oder Speicheranforderungen der Produktion. (TODO: $C(.)$?)

• was ist bei div das Problem? (Zyklen!)

Registerbelegung

• Unterschiede zwischen Chaitin und Briggs:
  • Live Ranges
  • Konfliktgraph
  • Knotengrad
  • wie wird der Graph reduziert?
  • Faerben

• Wie implementiert man den Konfliktgraphen (matrix vs. liste)?
  • AW: beides!

• Priority Based Coloring (TODO, erklaerungen)
  • Unterschiede zu Briggs? (Seite 154 (zumindest fuer Chaitin))
  • Basic Bloecke
  • Zitat: "Das teuerste kriegt ein Register"

• Coalescing?
  • aggressives Coalescing
    • hat Chaitin verwendet
  • konservatives Coalescing
    • hat Briggs verwendet
  • imperatives (?) / optimistic Coalescing
    • aggressiv bis Konflikt, dann Liverange Splitting
  • postive/negative Punkte der oben genannten Verfahren?

• ORA
  • Warum "Faktor 1000" besser?
    • AW: 10x CPU, 10x Besserer Solver und 10x Algorithmus => 1000x besser.
  • wie funktioniert der Algorithmus?
  • was heisst hier optimal?
    • macht er Umordung? Coalescing?
  • Was ist Rematerialization?
    • AW: wenn man einen Wert aus einen anderen errechnen kann.

Interprozedurale Registerallokation

• Walls: Remove Load & Store
  • Linker schmeisst es raus
• Artikel "Register Allocation Across Procedure and Modul Boundaries"
  • Spill Code Motion erklaeren?

Instruction Scheduling

• List Scheduling
  • IBM Artikel: Critical Pfad, Superskalar
  • HP Artikel: ???
• Komplexitaets Diskussion!
• Was macht man zu erst? Instruction Scheduling oder Register Allokation? (Phase Ordering)
  • IPS
  • DAG
  • RASE
• Trace
  • was ist das?
    • AW: aehnlich wie Basicblock, man darf aber rein- und rausspringen (aber keine Loop!)
  • VAM (Value Allocation Mapping)
  • Delayed Bindings

Software Pipelining

• was ist das?
• Modulo Variable Renaming
• IF Conversion
• Epilog, Prolog
• Modulo Scheduling
  • wie funktionierts?
  • Resourceconstraints, etc.
• wo ist das Problem bei dem schenialen (sic) Algorithmus?
  • AW: keine Heuristik fuers Zusammenfassen von Instruktionen angegeben.

Codeerzeugung fuer SIMD Instruktionen

• Algorithmus der Loop Unrolling macht
• wie schauts mit dem Alignment bei LOAD bzw. STORE aus?
  • Constant Expansion
  • Scalar Expansion
  • Acculumator Splitting