Compilerbau/Kapitel 5: Codeerzeugung

Aus Halloserv Wiki

Übersicht

Vorbereitung: Transformation des Codes

Konstantenpropagierung

Zuerst werden triviale Ausdrücke symbolisch ausgewertet.

Bei einer Variablenbindung der Form

let x = c in e

werden die Terme der Form

reduziert.

let x = Vector() in e
let  = x in e'

Danach wird der nutzlose (weil z.B. nicht ausgeführte) Code entfernt. Beispielsweise ist let x = h in e nutzlos, falls h ein trivialer Ausdruck oder ein Vektor $\langle \ldots \rangle$ mit $x \notin free(e)$ ist.

Instruktionsauswahl

Abbildung trivialer Ausdrücke, Header und wichtiger Ausdrücke (Serious) auf Assembler-Befehle.

Serious: Jeder Term entspricht einer Folge von Assembler-Befehlen
trivialer Ausdruck: zwei verschiedene Verfahren (greedy und optimal)
$\infty$ -viele Register
wir ignorieren vorerst das Retten von Registern über Funktionsaufrufe

Einschub: Retten von Registern (?)

m rt reg-arg0: erzeugt Spielraum bei der Registerallokation, falls in der Funktion arg0 gebraucht wird. framepointer sind eigentlich unnötig, da sp-fp konstant ist.

Konkret für MIPS-Assembler:

RISE, LOAD/STORE
32 GPRs (General Purpose Registers)
Sonderregister: PC, ..., HI, LO
Koprozesor: FPU

siehe Instruktionsauswahl durch Patternmatching

Lebendigkeitsanalyse

siehe Lebendigkeitsanalyse

Registerzuteilung

siehe Registerallokation

Instruktionsauswahl durch Patternmatching

Idee:

beschreibe Instruktionen durch Fragmente von trivialen Ausdrücken
jede Instruktion / jedes Fragment ist mit Kosten assoziiert, beispielsweise die Anzahl der Maschinenzyklen für die Ausführung
bestimme dann die Abdeckung eines trivialen Ausdrucks aus Fragmenten mit minimalen Kosten.

2 grundliegende Algorithmen:

greedy
- top-down-Patternmatching der Fragmente auf den Eingabeausdruck
- Pattern dürfen überlappen
- Pattern aufsteigend nach Kosten geordnet
  $\rightarrow$ einfach (durch Ocaml-Patternmatching, findet aber nicht die Abdeckung mit minimalen Kosten
- Appell: "optimal cover" (2 aufeinandertreffende Fragmente können nicht durch ein Fragment mit geringeren Kosten ersetzt werden

dynamische Programmierung
- verwende Baumgrammatik mit Attributen ( Verallgemeinerung von kontextfreien Grammatiken)
  - Menge von nichtterminalen Symbolen können Attribute mit sich führen
  - Produktionen der Form $A \rightarrow Baum \ (=Ausdruck)$ , wobei Blätter auch Nichtterminale sein können.

Beispiel: Baumgrammatik

<div> ::= VAR(id)
        | ADD (<div>,<div>)
        | CONST(id)

ADD(VAR "x", CONST "1")

Auf der rechten Seite der Grammatikregel ist auch ADD( $τ$ , CONST(1))ADD(VAR(id),CONST(1)) erlaubt, mit $τ$ als Nichtterminal und VAR(id)

Jede Regel hat außerdem Kosten mit sich assoziiert.

Nichtterminale können folgende Attribute besitzen:

Liste der Instruktionen
simulierte Kosten
Wert von Konstanten
Registernamen

Aufgabenstellung Vorliegender Term/Ausdruck/Baum soll auf sein Startsymbol reduziert werden $\rightarrow$ Parsen des Terms !

Verfahren:

Bottom-Up Durchlauf durch den Baum
lege an jedem Knoten die Liste der matchenden Nichtterminale ab
für jedes Nichtterminal ist nur das mit minimalen Kosten interessant Autoren-Anmerkung(Firefox): Vielleicht sollte das eigentlich "für jede Liste ist nur das NT mit den geringsten Kosten..." bedeuten. In beiden Quellen allerdings identisch so formuliert
Matchen (am Knoten)
- Knotennamen müssen gleich sein
- falls rechte Seite $T(A_1, \ldots , A_n)$ suche $A_1, \ldots , A_n$ in den Kinderknoten
- falls erfolgreich:
  - berechne Kosten
  - verkette Codesequenzen
  - hänge attribuiertes Nichtterminal an den Knoten des Subjektterms an. Autoren-Anmerkung(Firefox): Was ist ein Subjektterm ?

Lebendigkeitsanalyse

siehe Appel: Modern Compiler Implementation in ML, Kapitel 10

Zustand des übersetzten Programs

Folge von Instruktionen über Pseudoregister
Annahme: Maschine mit unendlich vielen Registern
Reale Maschine: endlich viele Register

Gesucht: Abbildung Pseudoregister $\rightarrow$ reale Register, sodass 2 unterschiedliche Pseudoregister nur dann auf ein reales Register abgebildet werden, wenn sie nicht gleichzeitig benutzt werden.

Lebendigkeit formuliert diese Eigenschaft
Analyse der Lebendigkeit ist ein Beispiel für statische und semantische Analyse.

Die Analyse wird auf einem Kontrollflußgraphen (KFG) durchgeführt:

$\begin{array}{ll} & a := 0 \\ L1: & b := a+1 \\ & c := c+b \\ & a := b \cdot 2 \\ & \mbox{if} \ (a < N) \ \mbox{goto} \ L1 \\ & \mbox{return} \ c \end{array}$

	$e n t r y$
	I $\downarrow$
1	$a : = 0$
	II $\downarrow$
2	$b : = a + 1$	$\nwarrow$
	III $\downarrow$	$\ \uparrow$
3	$c : = c + b$	$\ \uparrow$
	IV $\downarrow$	$\ \uparrow$
4	$a:=b \cdot 2$	$\ \uparrow$
	V $\downarrow$	$\ \uparrow$
5	$a < N$	$\nearrow$ VII
	VI $\downarrow$
6	$\mbox{return} \ c$

Kante	a	b	c
I	0	0	x
II	x	0	x
III	0	x	x
IV	0	x	x
V	x	0	x
VI	0	0	x
VII	x	0	x

Kontrollflußgraphen

Definition

Ein Kontrollflußgraph ist ein markierter gerichteter Graph. Die Markierungen sind entry, exit, return c, a <rel_op> b, a $: =$ e. Jede Instruktion liefert einen Knoten.

Kanten

Markierung	eingehende Kanten	ausgehende Kanten
`entry`	0	1
`exit`	N	0
`return`	N	0
`a <rel_op> b`	N	2
`a:=e`	N	1

Über die eingehende Kanten werden mit $p r e d (n)$ die Nachfolgerknoten erreicht; über die ausgehenden Kanten erhält man mit $s u c c (n)$ die Vorgängerknoten.

Verhalten bei Konstruktion

$u s e [n]:$ Menge der Pseudoregister die von Knoten $n$ verwendet werden.
$d e f [n]:$ Pseudoregister die von Knoten $n$ definiert (und überschrieben) werden.

Instruktion	$u s e [n]$	$d e f [n]$
`return c`	${c}$	$\emptyset$
`a <rel_op> b`	${a, b}$	$\emptyset$
`a:=e`	$R e g s (e)$	${a}$
`entry,exit`	$\emptyset$	$\emptyset$

Lebendigkeit

Definition

Definition: Lebendigkeit

Ein Pseudoregister $r$ ist auf einer Kante des Kontrollflußgraphen lebendig falls es einen Pfad zu einem $n$ mit $r \in Use[n]$ gibt auf dem kein Knoten $n'$ mit $r \in Def[n]$ liegt.

$r \in live\mbox{-}in[n]$ , falls $r$ lebendig auf einer eingehenden Kante zu $n$ ist
$r \in live\mbox{-}out[n]$ , falls $r$ auf einer ausgehenden Kante lebendig ist

$\begin{array}{ll} \rightarrow & Use[n] \subseteq live\mbox{-}in[n] \\ \rightarrow & r \in live\mbox{-}out[n] \wedge r \notin Def[n] \rightarrow r \in live\mbox{-}in[n] \\ \rightarrow & r \in live\mbox{-}in[n'], n' \in succ[n] \rightarrow r \in live\mbox{-}out[n] \\ \end{array}$

Daraus ergeben sich die Datenflussgleichungen für die Lebendigkeit:

$live\mbox{-}in[n]=Use[n] \cup (live\mbox{-}out[n] \setminus Def[n])$
$live\mbox{-}out[n]=\bigcup_{n' \in Succ(n)} live\mbox{-}in[n']$

Die Lösung der Gleichungen erhalten wir durch Fixpunktiteration

Algorithmus: Fixpunktiteration für Datenflussgleichungen

$\begin{array}{rl} 1 & for \ each \ n \\ 2 & \ \ \ live\mbox{-}in[n] = \emptyset \\ 3 & \ \ \ live\mbox{-}out[n] = \emptyset \\ 4 & repeat \\ 5 & \ \ \ for \ each \ n \\ 6 & \ \ \ \ \ \ live\mbox{-}in'[n] = live\mbox{-}in[n] \\ 7 & \ \ \ \ \ \ live\mbox{-}out'[n] = live\mbox{-}out[n] \\ 8 & \ \ \ \ \ \ live\mbox{-}in[n] = Use[n] \cup (live\mbox{-}out[n] \setminus Def[n]) \\ 9 & \ \ \ \ \ \ live\mbox{-}out[n] = \bigcup_{n' \in Succ[n]} live\mbox{-}in[n'] \\ 10& until \ \forall n | live\mbox{-}in[n] = live\mbox{-}in'[n] \wedge live\mbox{-}out[n] = live\mbox{-}out'[n] \\ \end{array}$

Für die Rückwärtsanalyse müssen wir einfach die Zeilen 8 und 9 vertauschen.

Beispiel

	1		2		3
	in	out	in	out	in	out	...
1	$\emptyset$	$\emptyset$	$\emptyset$	a	$\emptyset$	a	...
2	a	$\emptyset$	a	c,b	a,c	c,b	...
3	c,b	$\emptyset$	c,b	b	c,b	b	...
4	b	$\emptyset$	b	a	b	a	...
5	a	a	a	c,a	a,c	c,a	...
6	c	$\emptyset$	c	$\emptyset$	c	$\emptyset$	...

$\rightarrow$ Rückwärtsanalyse: Information wird gegen den Kontrollflußgraph propagiert.

	1		2
1	a	a,c	c	a,c	...
2	a,c	c,b	a,c	b,c	...
3	c,b	b,c	b,c	b,c	...
4	b,c	a,c	b,c	a,c	...
5	a,c	c	a,c	a,c	...
6	c	$\emptyset$	c	$\emptyset$	...

Komplexität

Grundoperationen $\rightarrow$ Mengenrepräsentation

$N : =$ Größe des Programms (Anzahl an Instruktionen), $W : =$ Wortbreite

Operation	Bitvektor	geordnete Liste (ohne Wiederholungen)
Platzbedarf	$\frac{N}{W}$	$N$
Kopieren	$O (N)$	$O (N)$
$\cup$	xor: $O (N)$	$O (N)$
$\setminus$	and/neg: $O (N)$	$O (N)$
	Vorteilhaft bei nichtbesetzten Mengen	Vorteilhaft bei sparsam besetzten Mengen ( $\le \frac{N}{W}$ Elemente)

$N ~$ Anzahl an Variablen

erste Schleife: $O (N 2)$
innere Schleife: $O (N 2)$
repeat Schleife: $O (N N)$

Rhs der Datenflussgleichungen sind monoton steigend (Autoren-Anmerkung(Firefox): Was sind Rhs ?
). Wenn die until-Bedingung nicht erfüllt ist muss mindestens ein Element hinzugefügt worden sein. Das passiert maximal $2 \cdot N^2$ -mal.

Die Datenflussgleichungen haben eine kleinste Lösung (wegen der Monotonie). Jede Lösung kann durch eine Variable, die nirgends definiert wird vergrößert werden. $\rightarrow$ Es existiert keine eindeutige Lösung, aber aus der Monotonie kann eine eindeutige, kleinste Lösung gefolgert werden.

Für jede tatsächliche Lösung L1/L0 der Datenflussgleichungen gilt folgende Invariante der repeat-Schleife:

$\forall n.live\mbox{-}in[n] \subseteq L1[n]$

$\forall n.live\mbox{-}out[n] \subseteq L0[n]$

(informeller) Beweis:

bei Betreten der Schleife: ok
$\begin{array}{lcl} live\mbox{-}in[n] & = & Use[n] \cup (live\mbox{-}out[n] \setminus Def[n]) \\ & \subseteq & Use[n] \cup (L0[n] \setminus Def[n]) \\ & = & L1[n] \end{array}$
$\begin{array}{lcl} live\mbox{-}out[n] & = & \bigcup_{n' \in Succ[n]} live\mbox{-}in[n']\\ & \subseteq & \bigcup_{n' \in Succ[n]} L1[n'] \\ & = & L0[n] \end{array}$

$\rightarrow$ Der Algorithmus findet also die kleinste Lösung, da beim Verlassen der repeat-Schleife die Datenflussgleichungen erfüllt sind.

Registerallokation

Interferenzgraph

Definition: Interferenzgraph

Der Interferenzgraph (IG) ist ein ungerichteter Graph mit

Knoten $: =$ Menge der Pseudoregister
Kantenmenge E, sodass für gilt
- falls $m$ keine MOVE-Instruktion ist, dann $(\forall t \in Def[m]) \ (\forall s \in live\mbox{-}out[m] \setminus \{ t \}) \ (s,t) \in E$
- falls $m$ ist $t : = r$ gilt (MOVE-Instruktion), dann $(\forall s \in live\mbox{-}out[m] \setminus \{ t,r \}) \ (s,t) \in E$

Bemerkung: Weitere Constraints können durch den Interferenzgraph ausgedrückt werden:

falls eine Instruktion ist, deren Ergebnis nicht im Register z erzeugt werden kann, dann
- verwende Pseudoregister dem $z$ direkt zugeordnet ist
- $(t,z) \in E(IG)$
Caller-Save-Register werden als $D e f [C a l l - I n s t r u k t i o n e n]$ betrachtet
$\rightarrow$ Interferenz zwischen den Caller-Save-Registern und den lebendigen Registern
$\rightarrow$ Lebendige Register $\rightarrow$ Caller-Save-Register oder Speicher

Autoren-Anmerkung(Firefox): Was ist ein Caller-Save Register ? Vielleicht ein spezieller Typ von Register bei dem das Register vom Aufrufer gespeichert werden muss ?

$\rightarrow$ Zurückführung auf Graphfärbung des Interferenzgraphen.
Farbe $\hat{=}$ Maschinenregister
Färbung ist Abbildung von Knoten(IG) auf Menge der Farben, sodass benachbarte Knoten unterschiedliche Farben erhalten

$k$ Maschinenregister $\rightarrow$ k-Färbung gesucht.

Probleme:

k-Färbung zu finden ist NP-Vollständig.
falls eine k-Färbung nicht möglich ist müssen Pseudoregister im Speicher abgelegt werden. (Spilling)

Lemma: Graphfärbung, Kempe, ~1820

Sei $G = (V, E)$ ungerichtet und $v \in V$ mit $G r a d (V) < k$ . Falls $G \setminus \{v\}$ eine k-Färbung $F'$ besitzt, dann exisitiert ein $F$ mit: $F$ ist k-Färbung von $G$ .

Beweis: Färbungs-Lemma

Seien $\{ v_1, \ldots, v_n\} = {neighbors}_G(v) \Rightarrow n < k, v_i \in G'$ und $f$ eine Farbe.
$\Rightarrow |\{ F'v_1, \ldots, F'v_n \}|<k$
$\Rightarrow \exists f \notin \{ F'v_1, \ldots, F'v_n \}$ , also ist $F = F' [v \rightarrow f]$ eine k-Färbung von $G$ .

Algorithmus

Build

Erstelle den Interferenzgraphen.
Erzeuge einen Stack

Simplify

wähle Knoten $v$ mit $G r a d (v) < k$
entferne $v$ und push v (alle Kanten zu v werden ebenfalls entfernt und reduzieren dadurch den Grad anderer Knoten)
wiederhole solange wie möglich. Danach gibt es nur noch Knoten $v$ mit $Grad(v) \ge k$ (oder gar keine)

Spill

wähle Knoten $v$ mit $Grad(v) \ge k$
markiere $v$ als "potential spill"
entferne $v$ und push v (alle Kanten zu v werden ebenfalls entfernt und reduzieren dadurch den Grad anderer Knoten)
zurück zu Simplify und solange wiederholen bis der Interferenzgraph leer ist.

Select

let v = pop
falls $v$ durch Simplify entfernt wurde (also keine Markierung trägt) wähle eine Farbe für $v$
falls $v$ durch Spill entfernt wurde (also mit "potential spill" markiert ist) und färbbar ist , färbe $v$
ansonsten wird v als "actual spill" markiert und eine Speicherzelle dafür alloziiert. Außerdem wird der Code geändert:
- STORE nach jeder Definition von $v$
- LOAD vor jeder Benutzung von $v$
wiederhole bis der Stack leer ist.

End

Entweder ist der Stack nun leer und kein "actual spill" ist aufgetreten, oder der Code des Programms wurde geändert und der Algorithmus muss nochmal von Anfang an ausgeführt werden.

Vorgefärbte Register

Pseudoregister, die von vornherein bestimmten Registern zugeordnet sind (Argumentregister, Multiplikationsergebnis, etc.)
jedes vorgefärbte Register interferiert mit jedem anderen
dürfen nicht gespillt werden ( $\rightarrow$ Lebensbereiche klein halten mit MOVE) und werden von Simplify zuletzt gewählt damit Select ihnen zuerst die gewünschten Farben zuordnen kann.

Behandlung von `MOVE` / Coalescing (Verschmelzen)

Die Instruktion r:=s kann eliminiert werden falls $(r,s) \notin IG$
die zugehörigen Kanten im Interferenzgraphen werden verschmolzen $\rightarrow$ Der Grad erhöht sich $\rightarrow$ Die Färbbarkeit wird beeinträchtigt.

Vor Verschmelzung: 2-färbbar

$\longrightarrow$

Nach Verschmelzung: 3-färbbar

Also: Konservative Strategie

Verschmelze nur Register mit insgesamt nicht weniger als $k$ Nachbarn mit $Grad \ge k$ damit die k-Färbbarkeit erhalten bleibt.

Denn:(hinreichendes Kriterium)

Nach Entfernen der Kanten vom $G r a d < k$ (Simplify) verbleiben höchstens Nachbarn mit $Grad \ge k$ , also hat der verschmolzene Knoten einen $G r a d < k$ und kann somit von Simplify entfernt werden.

Registerallokation mit Verschmelzen

Build

Erstelle den Interferenzgraphen.
Erzeuge einen Stack
$\forall v:=s$ markiere $v$ und $s$ als "move-related".

Simplify

wähle unmarkierten Knoten $v$ mit $G r a d (v) < k$ (berücksichtige obrige Bemerkungen zur Verschmelzung)
entferne $v$ und push v (alle Kanten zu v werden ebenfalls entfernt und reduzieren dadurch den Grad anderer Knoten)

Coalescing

wähle markierten Knoten und verschmelze ihn mit "MOVE-Partner" (falls der Gesamtgrad < k ist )
entferne MOVE
entferne Markierung, falls der verschmolzene Knoten nicht mehr an MOVE beteiligt ist
gehe zu Simplify und wiederhole

Freeze

wähle markierten Knoten $v$ mit $G r a d (v) < k$
MOVE bleibt erhalten, Markierung wird entfernt
gehe zu Simplify und wiederhole

Spill

wie im normalen Algorithmus (Spill)
gehe zu Simplify und wiederhole bis der Graph leer ist

Select

wie im normalen Algorithmus (Select)

Registerallokation für Ausdrücke (Baumstruktur)

Baumstruktur

$t 1$ braucht m Register

$t 2$ braucht n Register

if max(m,n+1) > max(m+1,n)

then $t 1$ zuerst

else $t 2$ zuerst

Compilerbau/Kapitel 5: Codeerzeugung

Aus Halloserv Wiki

Inhaltsverzeichnis

Übersicht

Vorbereitung: Transformation des Codes

Instruktionsauswahl

Lebendigkeitsanalyse

Registerzuteilung

Instruktionsauswahl durch Patternmatching

Lebendigkeitsanalyse

Zustand des übersetzten Programs

Kontrollflußgraphen

Definition

Verhalten bei Konstruktion

Lebendigkeit

Definition

Beispiel

Komplexität

Registerallokation

Interferenzgraph

Algorithmus

Build

Simplify

Spill

Select

End

Vorgefärbte Register

Behandlung von MOVE / Coalescing (Verschmelzen)

Registerallokation mit Verschmelzen

Build

Simplify

Coalescing

Freeze

Spill

Select

Registerallokation für Ausdrücke (Baumstruktur)

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge

Behandlung von `MOVE` / Coalescing (Verschmelzen)