Compilerbau/Kapitel 6: Lebendigkeitsanalyse

Aus Halloserv Wiki

Dieses Kaptiel wird in Codeerzeugung integriert und bald gelöscht - verwenden sie statt dessen 5. Codeerzeugung !

(Appd, Kapitel 10)

Inhaltsverzeichnis

1 Zustand des übersetzten Programs
2 Kontrollflußgraphen
- 2.1 Definition
- 2.2 Verhalten bei Konstruktion
3 Lebendigkeit
4 Interferenzgraph
5 Registerallokation

Zustand des übersetzten Programs

Folge von Instruktionen über Pseudoregister
Annahme: Mschine 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:

unleserlich-Stücke:

$\begin{array}{ll} & a := 0 \\ L1: & \delta := 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$
	$\downarrow$
1	$a : = 0$
	$\downarrow$
2	$b : = a + 1$	$\nwarrow$
	$\downarrow$	$\ \uparrow$
3	$c : = c + δ$	$\ \uparrow$
	$\downarrow$	$\ \uparrow$
4	$a:=\delta \cdot 2$	$\ \uparrow$
	$\downarrow$	$\ \uparrow$
5	$a < N$	$\nearrow$
	$\downarrow$
6	$\mbox{return} \ c$

$a$	$δ$	$c$
0	0	x
x	0	x
0	x	x
0	x	x
x	0	x
0	0	x
x	0	x

Kontrollflußgraphen

Definition

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

Kanten

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

Über die eingehende Kanten werden mit $s u c c (n)$ die Nachfolgerknoten erreicht; über die ausgehenden Kanten erhält man mit $p r e d (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 relop b`	${a, b}$	$\emptyset$
`a:=e`	$R e g s (e)$	${a}$

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 \in 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] \cap 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

Diese Beispiele sind nicht korrekt! Sie müssen nachgerechnet werden. Hier steht teilweise b anstelle von $δ$ ! Firefox 23:24, 4. Sep. 2007 (CEST)

	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,δ$	$a, c$	$δ, c$	...
$3$	$c,δ$	$δ, c$	$δ, c$	$δ, c$	...
$4$	$b, c$	$a, c$	$b, c$	$a, c$	...
$5$	$a, c$	$c$	$a, c$	$a, c$	...
$6$	$c$	$\emptyset$	$c$	$\emptyset$	...

$\begin{array}{lccccc} & \bold{1} & \bold{1} & \bold{2} & \bold{2} & \\ \bold{1} & a & a,c & c & a,c & ... \\ \bold{2} & a,c & c,\delta & a,c & \delta,c & ... \\ \bold{3} & c,\delta & \delta,c & \delta,c & \delta,c & ... \\ \bold{4} & b,c & a,c & b,c & a,c & ... \\ \bold{5} & a,c & c & a,c & a,c & ... \\ \bold{6} & c & \emptyset & c & \emptyset & ... \\ \end{array}$

Diese Beispiele sind nicht korrekt! Sie müssen nachgerechnet werden. Hier steht teilweise b anstelle von $δ$ ! Eine Tabelle ist wegen Ansichttest doppelt ! Firefox 23:45, 4. Sep. 2007 (CEST)

Komplexität

Hier fehlen zusätzliche Erklärungen. Fraglich was diese Tabelle zu bedeuten hat... Firefox 23:24, 4. Sep. 2007 (CEST)

Grundoperationen $\rightarrow$ Mengenrepräsentation

	Bitvektor	geordnete Liste (ohne Wiederholungen)
Platz	$\frac{N}{W}$	$N$
Kopie	$O (N)$	$O (N)$
$\cup$	Bitweise oder $O (N)$	$O (N)$
$\setminus$	and/neg $O (N)$	$O (N)$

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-Konstruktion 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-Konstruktion), 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 Konstruktion 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 t r . e n]$ betrachtet (unleserlich)
$\rightarrow$ Interferenz zwischen den Caller-Save-Registern und den lebendigen Registern
$\rightarrow$ Lebendige Register $\rightarrow$ Caller-Save-Register oder Speicher

Registerallokation

$\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. (Spillung)

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 $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'$
$\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]$ K-Färbung von $G$ .