Code-Generierung und -Optimierung

Compiler-Phasen

• Front-End (abhängig von Quellsprache):
  • Eingabe ist (Menge von) Quelltexten
  • lexikalische Analyse (Scanner)

    erzeugt Liste von Tokens

  • syntaktische Analyse (Parser)

    erzeugt Syntaxbaum

  • semantische Analyse (Typprüfung, Kontrollfluß, Registerwahl) erzeugt Zwischencode
• Back-End (Abhängig von Zielsprache/Maschine):
  • Zwischencode-Optimierer
  • Code-Generator

    erzeugt Programm der Zielsprache

  • (Assembler, Linker, Lader)

Informationen im Syntaxbaum

Parser benutzt kontextfreie Grammatik

jedes Programm besitzt auch kontextabhängige Eigenschaften

$\to$ müssen durch Durchlaufen des gesamten Syntaxbaumes berechnet werden.

Beispiele für solche Informationen:

• Sichtbarkeiten (public, private, usw.)
• Typen
• Datenfluß-Eigenschaften von Variablen

Daten-Fluß-Analyse

bestimmt für jeden Code-Block:

• gelesene Variablen
• geschriebene Variablen

ermöglicht Beantwortung der Fragen:

• ist Variable $x$ hier initialisiert?
• wann wird Variable $y$ zum letzten mal benutzt?
• ändert sich Wert des Ausdrucks $A$?

Problem: zur exakten Beantwortung müßte man Code ausführen. (Bsp: Verzweigungen, Schleifen)

Ausweg: Approximation durch abstrakte Interpretation

Zwischencode-Generierung

$$Id: zwigen.tex,v 1.1 2004/01/19 14:23:29 joe Exp $$

Aufgabe:

• Eingabe: annotierter Syntaxbaum
• Ausgabe: Zwischencode-Programm ($=$ Liste von Befehlen)

Arbeitsschritte (für Registermaschinen):

• common subexpression elimination (CSE)
• Behandlung von Konstanten
• Register-Zuweisungen
• Linearisieren

Common Subexpression Elimination -- CSE

Idee: gleichwertige (Teil)ausdrücke (auch aus verschiedenen Ausdrücken) nur einmal auswerten.

Implementierung: Sharing von Knoten im Syntaxbaum

Vorsicht: Ausdrücke müssen wirklich völlig gleichwertig sein, einschließlich aller Nebenwirkungen.

Auch Pointer/Arrays gesondert behandeln.

Beispiele: $f(x) + f(x)$; $f(x) + g(y)$ und $g(y) + f(x)$; $a * (b * c)$ und $(a * b) * c$; .. a [4] .. a [4] ..

Aufgabe: untersuchen, wie weit gcc CSE durchführt. Bis zum Seminar Testprogramme ausdenken!

Constant Propagation

$$Id: cp.tex,v 1.1 2004/01/19 14:23:29 joe Exp $$

• konstante Teil-Ausdrücke kennzeichnen

• und so früh wie möglich auswerten

  z. B. vor der Schleife statt in der Schleife)

• aber nicht zu früh!

  z. B. A nicht vor einer Verzweigung if ( .. ) { x = A; }

Constant Folding, Strength Reduction

$$Id: cf.tex,v 1.1 2004/01/19 14:23:29 joe Exp $$

strength reduction:

``starke'' Operationen ersetzen,

z. B. x * 17 durch x << 4 + x

constant folding:

Operationen ganz vermeiden:

konstante Ausdrücke zur Compile-Zeit bestimmen

z. B. c + ('A' - 'a')

Aufgabe: wieweit macht gcc das? Tests ausdenken!

evtl. autotool zu strength reduction (Additionsketten)

Linearisieren

$$Id: linear.tex,v 1.1 2004/01/19 14:23:29 joe Exp $$

zusammengesetzte Ausdrücke übersetzen

in einzelne Anweisungen mit neuen Variablen:

$x = a * a + 4 * b * c$ $\to$

h1 = a*a; h2 = 4*b; h3 = h2 * c; x = h1 + h3

Registervergabe

$$Id: reg.tex,v 1.2 2004/01/19 19:16:00 joe Exp $$

benötigen Speicher für

• lokale Variablen und
• Werte von Teilausdrücken (wg. Linearisierung)

am liebsten in Registern (ist schneller als Hauptspeicher)

es gibt aber nur begrenzt viele Register.

Zwischencode-Generierung für ``unendlich'' viele symbolische Register, dann Abbildung auf Maschinenregister und Hauptspeicher (register spilling).

Register-Interferenz-Graph

(für einen basic block)

Knoten: die symbolischen Register $r_1, r_2, \ldots$

Kanten: $r_i \leftrightarrow r_k$, falls $r_i$ und $r_k$ gleichzeitig lebendig sind.

(lebendig: wurde geschrieben, und wird noch gebraucht)

finde Knotenfärbung (d. i. Zuordnung $c$: symbolisches Register $\to$ Maschinenregister) mit möglichst wenig Farben (Maschinenregistern), für die

$\forall (x,y) \in E(G): c(x) \neq c(y)$.

Ist algorithmisch lösbares, aber schweres Problem (NP-vollständig)

Register-Graphen-Färbung (Heuristik)

Heuristik für Färbung von $G$:

• wenn $\vert G\vert=1$, dann nimm erste Farbe
• wenn $\vert G\vert>1$, dann
  • wähle $x =$ Knoten mit minimalem Grad,
  • färbe $G\setminus\{x\}$
  • gib $x$ die kleinste Farbe, die nicht in Nachbarn $G(x)$ vorkommt.

Aufgabe: finde Graphen $G$, für die man nach dieser Heuristik keine optimale Färbung erhält.

Falls dabei mehr Farben als Maschinenregister, dann lege die seltensten Registerfarben in Hauptspeicher.

(Es gibt bessere, aber kompliziertere Methoden.)

Peephole-Optimierung, Instruction Selection

$$Id: is.tex,v 1.1 2004/01/19 14:23:29 joe Exp $$

Zwischencode-Liste übersetzen in Zielcode-Liste.

kurze Blöcke von aufeinanderfolgenden Anweisungen optimieren (peephole) und dann passenden Maschinenbefehl auswählen.

durch Mustervergleich (pattern matching), dabei Kosten berechnen und optimieren

gcc: Zwischencode ist maschinenunabhängige RTL (Register Transfer Language),

damit ist nur Instruction Selection maschinenabhängig

$\to$ leichter portierbar.

$$Id: semi.tex,v 1.1 2004/01/21 09:58:39 joe Exp $$