Vorlesung Compilertechnik
Sommersemester 2008
Optimierung
M. Schölzel
Einbettung der Optimierung in den
Compiler
Gründe für die Optimierung:


Vom Frontend generierter Zwischencode ist ineffizient, da er aus der Struktur des
Quellprogramms entstanden ist und sich nicht an der Zielarchitektur orientiert.
Programmierer schreiben "verbesserungsfähigen" Quellcode.
Kontextprüfung
Quelltext
Scanner
Frontend
Parser
Zielcodeabhängige
Optimierungen
Zwischen
code und
Symboltabelle
Zielcodeerzeugung
Backend

Zielcode
Zielcodeunabhängige
Optimierungen
2
Maschinenabhängig Maschinenunabhängig
Klassifizierung der Optimierung
Eliminierung redunEliminierung redundanter Berechnungen,
danter Berechnungen,
Berechnung konstanter
Berechnung konstanter
Ausdrücke,
Ausdrücke
Codeverschiebung
Registerplanung,
Zielcodeauswahl
Lokal
Registerplanung
Global
3
Grundbegriffe (1)






S = (N,E,q,s) sei ein Steuerflussgraph.
N = {b0,…,bn} sind die Basisblöcke im Steuerflussgraphen, wobei
ir0(bi),…,ir#(bi)(bi) die Folge der 3-Adress-Code-Anweisungen in bi ist.
Über b0 = q wird S betreten und über b1 = s (z.B. return) verlassen.
Eine Programmposition ist ein Tupel (i,j) wobei damit die Position
unmittelbar vor der 3-Adress-Code-Anweisung irj(bi) gemeint ist.
Mit (0,0) wird Startposition und mit (1,0) Stoppposition bezeichnet.
Ein Pfad  im Steuerflussgraphen von Programmposition (i,j) zur
Programmposition (m,n) ist eine Folge 0,…,k von 3-Adress-CodeAnweisungen, für die gilt:

0…k kann in 3-Adress-Code-Folgen 0…c = 0…k zerlegt werden, so
dass:


z = ir0(baz)…ir#(baz)(baz) für 1  z < c und
(0 = irj(ba )…ir#(ba )(ba ) und c = ir0(bac)…irn-1(bac) falls c > 0) oder
(0 = irj(ba )…irn-1(ba ) falls c = 0) und
0
0

0
0
0
(ba0, ba1),(ba1, ba2),…,(bac-1, bac)  E
4
Grundbegriffe (2)




Verwendung einer Variablen v:
Eine Variable v wird in der Zwischencodeanweisung iri(j) verwendet,
falls iri(j) eine der Formen x := v, x :=  v, x := y  v, x := v  y,
x := @v, @v := x, return v, if v then goto label, x := (Type) v,
x := call f(…,v,…) hat.
Definition einer Variablen v:
Eine Variable v wird in der Zwischencodeanweisung iri(j) definiert,
falls iri(j) eine der Formen v := … hat.
Eine definierende Anweisung für v ist eine Anweisung, die v definiert.
Eine verwendende Anweisung für v ist eine Anweisung, die v
verwendet.
5
Copy/Constant Propagation

Ersetze die Verwendung der Variablen y in einer Anweisung iri(j) durch z falls:





auf allen Pfaden von Programmposition (0,0) zur Programmposition (j,i), eine Anweisung
irn(m) = "y := z" existiert und
es auf allen Pfaden von Positionen (m,n+1) zur Position (j,i) keine definierende Anweisung für
y und z gibt.
Nach der Ersetzung kann es sein, dass die Variable y nicht mehr benutzt wird.
z darf eine Variable (copy propagation) oder Konstante (constant propagation) sein.
Constant Folding: Ersetze Zwischencodeanweisungen der Form x := y  z bzw.
x :=  z durch x := k, falls y und z konstant sind und k das Ergebnis der Operation 
ist.
t0 := 8
y := t0
t0 := 7
x := t0
t1 := x
t2 := y
t3 := t1 + t2
z := t3
t0 := 8
y := 8
t1 := x
t2 := y
t3 := t1 + t2
z := t3
t0 := y
t1 := x
t0 := 7
x := 7
t1 := 7
t2 := 8
t3 := 7 + 8
z := 15
t1 := x
t2 := 8
t3 := t1 + 8
x := t3
t0 := 8
t1 := x
6
Dead-Code Elimination

Eine Zwischencodeanweisung iri(j) = "x := e" kann aus dem
Zwischencode entfernt werden, falls



für alle Programmpositionen (m,n) an denen x verwendet wird und alle
Pfade von (j,i+1) nach (m,n) gilt: x wird auf diesen Pfaden definiert.
Dabei ist e ein beliebiger Ausdruck des Zwischencodes oder
kein Pfad von (0,0) nach (j,i) existiert.
Es kann neuer Dead-Code entstehen.
t0 := 8
y := 8
t0 := 7
x := 7
t1 := 7
t2 := 8
t3 := 7 + 8
z := 15
y := 8
t1 := x
t2 := 8
t3 := t1 + 8
x := t3
t1 := x
x := 7
t3 := t1 + 8
x := t3
z := 15
t0 := 8
t1 := x
t0 := 8
t1 := x
7
Global Common-Subexpression
Elimination

Die Zuweisung iri(j) = "x := e" mit dem Ausdruck e kann durch x := t ersetzt werden,
falls:




auf allen Pfaden von Programmposition (0,0) zur Programmposition (j,i), eine Anweisung
irn(m) = "y := e" existiert und
es auf allen Pfaden von Positionen (m,n) zur Position (j,i) keine definierenden Anweisungen
für die Verwendungen in e gibt und
an allen Positionen (m,n+1) die Anweisung "t := y" eingefügt wird.
Es entstehen neue Kopierbefehle.
y := 4 * i
x := 6 * j
j := j +1
y := 4 * i
x := 6 * j
x' := x
m := 5 * y
n := 6 * j
x := x * 5
i := i + 1
n := 6 * j
m := i + 1
j := j +1
m := 5 * y
n := x'
x := x * 5
i := i + 1
n := 6 * j
m := i + 1
8
Global Code Motion



Es sei L die Menge der Knoten des Steuerflussgraphen, die auf einem Zykel liegen
und d  L der einzige Knoten der nicht zu L gehört und eine Kante zu einem Knoten
in L besitzt.
Eine Anweisung iri(j) = "x := e" kann im Block bj  L durch x := t ersetzt und am Ende
des Blocks d t := e eingefügt werden, falls kein Block in L eine Definition einer
Verwendung in e enthält.
Es entstehen neue Kopierbefehle.
y := 4 * i
x := 6 * j
x' := x
m' := 5 * y
y := 4 * i
x := 6 * j
x' := x
j := j +1
m := 5 * y
n := x'
x := x * 5
i := i + 1
n := 6 * j
m := i + 1
j := j +1
m := m'
n := x'
x := x * 5
i := i + 1
n := 6 * j
m := i + 1
9
Strength-Reduction in Schleifen



Suchen einer Variablen x (Induktionsvariablen), die in jedem
Schleifendurchlauf um eine Konstante c erhöht wird.
Suchen nach einer Berechnung y := f(x), wobei f(x + c) – f(x) = dx
Statt f(x) in jeder Iteration zu berechnen, wird in jeder Iteration zu y
dx addiert.
y := 4 * i
x := 6 * j
x' := x
m := 5 * y
n := x'
x'' := x * i
y := 4 * i
x := 6 * j
x' := x
m := 5 * y
n := x'
j := j +1
z := x * i
i := i + 2
n := 6 * j
m := i + 1
j := j +1
z := x''
t := 2 * x
x'' := x'' + t
i := i + 2
n := 6 * j
m := i + 1
10
Datenflussanalyse

Beobachtung: In den meisten Beispielen wurden
Informationen der folgenden Art genutzt:


auf allen Pfaden zur Programmposition (j,i) existiert eine
Anweisung der Art … und
auf allen Pfaden zwischen diesen Anweisungen und der Position
(j,i) existiert keine Anweisung der Art … .
Information I gilt hier
auch nicht mehr.
Information I
gilt noch
Information I gilt
auch hier…
… und hier.
…
t0 := t1 – t9
…
Erzeugt eine
Information I
…
t3 := t1 + t2
…
… und hier…
…
t2 := t3 * t5
…
Zerstört die
Information I
Information I gilt
hier nicht mehr.
11
Grundprinzip der Datenflussanalyse


Informationen I breiten sich entweder mit oder gegen den Steuerfluss aus.
Für jeden Basisblock b gibt es:





Eingehenden Informationen: in(b),
ausgehende Informationen: out(b),
erzeugte Informationen: gen(b),
zerstörte Informationen: kill(b).
Abhängig von der Ausbreitungsrichtung der Informationen sind:

Vorwärtsanalyse:



Rückwärtsanalyse:




in(b) = out(b1)  out(b2)  …  out(bn), wobei die bi die Steuerflussvorgänger von b sind
und
out(b) = (in(b) – kill(b))  gen(b)
(Transferfunktion genannt)
out(b) = in(b1)  in(b2)  …  in(bn), wobei die bi die Steuerflussnachfolger von b sind und
in(b) = (out(b) – kill(b))  gen(b)
(Transferfunktion genannt)
Durch den Steuerflussgraphen wird eine Mengengleichungssystem definiert.
Falls der Steuerflussgraph Zyklen enthält, ist das Mengengleichungssystem
rekursiv; Lösung durch Fixpunktiteration.
12
Beispiel: Reaching Definitions





Bei Verwendung einer Programmvariablen an Position (i,j) interessiert, an welchen
Programmpositionen der Wert der Variablen definiert wurde.
Menge aller Informationen: (()V)
Vorwärtsanalyse mit  := 
gen(bi) := {((i,j),v) | irj(i) ist letzte Definition von v in bi}
kill(bi) := {((m,n),v) | m, n   und bi enthält eine Definition von v}
gen(b2) = {((2,0),t0), ((2,1),t1), ((2,2),t2)}
kill(b3) = {((m,n),t0), ((m,n),t1), ((m,n),t2)}
b0
in(b2) =

in(b3) =

{((2,0),t0),
((2,1),t1), ((2,2),t2)}
in(b4) =

{((2,0),t0),
((2,1),t1), ((2,2),t2)} 
{((4,0),t3), ((4,1),t4), ((4,2),t2)}
b2 t0 := a
t1 := b
gen(b3) = {((3,1),t0)}
t2 := t0 + t1
in(b1) =

{((3,1),t0)}
{((2,1),t1),
((2,2),t2),

((3,1),t0), ((2,0),t0),
{((4,0),t3),
((4,0),t3), ((4,1),t4), ((4,2),t2)}
kill(b3) = {((m,n),t0)}
out(b0) = 
b3 t0 := t2 – t0
t0 := b
b4 t3 := t2
t4 := t3 * t2
t2 := t2 – t4
out(b2) = {((2,0),t0),

((2,1),t1), ((2,2),t2)}
out(b3) = {((2,1),t1),

{((3,1),t0)}
((2,2),t2), ((3,1),t0)}
out(b4) = {((2,0),t0),

{((4,0),t3),
((4,1),t4), ((4,2),t2)}
((2,1),t1)}

{((4,0),t3), ((4,1),t4), ((4,2),t2)}
b1
gen(b4) = {((4,0),t3), ((4,1),t4), ((4,2),t2)}
kill(b4) = {((m,n),t3), ((m,n),t4), ((m,n),t2)}
13
Anwendung Reaching Definition




Erkennung der Benutzung einer Variablen vor ihrer
Definition.
Definiere out(b0) := {((0,0),v) | v hat Verwendung im
Steuerflussgraph}.
Berechne Reaching Definitions.
Falls bei einer Verwendung von v die Information ((0,0),v)
vorhanden ist, dann kann es einen Pfad zu dieser
Verwendung geben, auf dem v nicht initialisiert wird.
14
Beispiel: Lebendige Variablen





An einer Programmposition (i,j) interessiert für eine Variable v, ob es einen Pfad zu einer
Programmposition gibt, an der v verwendet wird, ohne auf diesem Pfad definiert zu werden.
Menge aller Informationen: (V)
Rückwärtsanalyse mit  := 
gen(bi) := {v | irj(i) ist Verwendung von v und für alle 0  k < j gilt: irk(i) ist keine Defintion von v}
kill(bi) := {v | v wird in bi definiert}
gen(b2) = {a,b}
b0
in(b0) = in(b2)
in(b2) = (in(b3)  in(b4) – kill(b2))  gen(b2)
kill(b2) = {t0,t1,t2}
b2 t0 := a
t1 := b
gen(b3) = {b, t2, t0}
t2 := t0 + t1
gen(b4) = {t2}
in(b3) = (in(b1) – kill(b3))  gen(b3)
kill(b4) = {t2,t3,t4}
in(b4) = ((in(b4)  in(b1)) – kill(b4))  gen(b4)
kill(b3) = {t0}
b3 t0 := t2 – t0
t0 := b
b4 t3 := t2
t4 := t3 * t2
t2 := t2 – t4
b1
gen(b4) = 
kill(b4) = 
15
Anwendung Lebendige Variablen

Registerallokation:



Treffen der Spill-Entscheidung in Basisblöcken.
Bestimmung der zu sichernden Variablen am Ende
eines Basisblocks.
Globale Registerallokation durch Graphfärbung:

Konstruktion eines Interferenzgraphen




Variablen sind Knoten
Eine Kante zwischen zwei Knoten existiert gdw. es eine
Programmposition gibt, an der beide Variablen lebendig sind.
Färbung des Interferenzgraphen liefert eine
Registerallokation (Jede Farbe entspricht einem
Prozessorregister).
Details…
16
Beispiel: Reaching Copies






An einer Position (i,j) interessiert, ob auf allen Pfaden von (0,0) nach
(i,j) eine Anweisung x := y liegt und auf allen Pfaden von diesen
Anweisungen nach (i,j) weder x noch y definiert werden.
Menge aller Informationen: ({x := y | x ist Variable, y ist Variable
oder Konstante})
Vorwärtsanalyse mit  := 
gen(bi) := {x := y | nach irj(i) = "x := y" folgt keine Definition von x oder
y in bi}
kill(bi) := {x := y, y := x | bi enthält eine Definition von x und y ist
Konstante oder Variable}
Ist an einer Programmposition irj(i) = "z := e" die Information
x := y verfügbar und e enthält eine Verwendung von x, dann kann x
durch y ersetzt werden.
17
Beispiel: Available Expressions





An einer Programmposition (i,j) ist ein Ausdruck e
verfügbar, falls e auf allen Pfaden von Position (0,0) nach
(i,j) berechnet wurde und für jeden dieser Pfade gilt, dass
nach der letzten Berechnung von e die verwendeten
Variablen in e bis zur Position (i,j) nicht definiert wurden.
Menge aller Informationen: Menge aller Teilmengen von
Ausdrücken.
Vorwärtsanalyse mit  := .
gen(bi) := {e | irj(i) = "t := e" und für alle j < k  #(bi) gilt:
irk(i) ist keine Definition einer Verwendung in e}
kill(bi) := {e | eine Verwendung in e wird in bi definiert}
18
Rahmenwerk zur Datenflussanalyse (DFA)

DFA-Rahmenwerk: (D, I, , F) besteht aus:


Der Richtung D der Analyse (vorwärts oder rückwärts)
Einem Halbverband (I, ), d.h. für alle x, y, z  I







xx=x
xy=yx
x  (y  z) = (x  y)  z
es ex. ein   I, so dass für alle x  I gilt   x = x
Einer Menge F, die für jeden Basisblock des Steuerflussgraphen eine
Transferfunktion f : I  I enthält, die monoton und stetig ist.
Induzierte Ordnung auf I: x  y gdw. x  y = y
Voraussetzungen für den Fixpunktsatz von Tarski und Knaster sind
erfüllt. Damit existiert der kleinste Fixpunkt und kann durch Iteration
berechnet werden, weil:


(I, ) ist eine vollständig geordnete Menge, weil für alle
x, y  I gilt: x  y ist kleinste oberer Schranke von x und y.
Jedes f  F ist monoton und stetig.
19
(I,) ist eine geordnete Menge



Reflexivität:
x  x gilt wegen x  x = x.
Antisymmetrisch:
x  y und y  x  x  y = y und y  x (= x  y) =
x  x = y.
Transitivität:
x  y und y  z  x  y = y und
y  z = z  z = (x  y)  z = x  (y  z) =
x  z  x  z.
20
(I,) ist eine vollständig geordnete Menge

Wir zeigen: Für alle x, y  I ist z = x  y die kleinste obere
Schranke von x und y:




x  z  x  z = x  (x  y) = (x  x)  y) =
x  y = z.
y  z  y  z = y  (x  y) = y  (y  x) =
(y  y)  x) = y  x = x  y = z.
Angenommen x  u und y  u, dann x  u = u und y  u = u und z
u=uu=uu=xuyu=xuy=zuzu
Damit ist für jede endliche nicht leere Kette K  I mit
K = {k1, k2, k3,…,kn} k1  k2  k3  …  kn die kleinste
obere Schranke von K.
21
Fixpunktiteration


Es ist der Fixpunkt einer Funktion F
(out(b0),…,out(bm)) = F((out(b0),…,out(bm))) bzw.
(in(b0),…,in(bm)) = F((in(b0),…,in(bm))) gesucht.
Durch den Steuerflussgraphen wird für jede Komponente out(bi) bzw. in(bi)
eine Mengengleichung erzeugt:





Vorwärtsanalyse:
out(bi) = fi(out(bk1)…out(bkn)), wobei bk1,…,bkn die Steuerflussvorgänger von bi
sind und 0  kj  m.
Rückwärtsanalyse:
in(bi) = fi(in(bk1)…in(bkn)), wobei bk1,…,bkn die Steuerflussvorgänger von bi sind
und 0  kj  m.
Wir schreiben kurz: (b0,…,bm) = F((b0,…,bm)) und abstrahieren von der
Richtung.
Die induzierte Ordnung auf I wird zu einer Ordnung auf Im+1 erweitert:
(a0,…,am)  (b0,…,bm) gdw. j: 0  j  m  aj  bj. Analog wird der Operator
 für einen Vektor erweitert.
Unter der Voraussetzung, dass die Transferfunktionen fi monoton und stetig
sind, ist es F auch (Beweis folgt).
22
Monotonie von F



F monoton gdw. aus (a0,…,am)  (b0,…,bm) folgt
F(a0,…,am)  F(b0,…,bm).
a = (a0,…,am)  (b0,…,bm) = b gdw. i: ai  bi.
Für jedes ai und bi gilt nun:




Es seien ak1,…,akn bzw. bk1,…,bkn die Komponenten in a bzw. b,
die den in/out-Resultaten der Steuerflussvorgänger/-nachfolger
von ai bzw. bi entsprechen.
Wegen akj  bkj ist ak1…akn  bk1…bkn. (Bew. durch Induktion;
im Schritt: a  b  a  b = b und a'  b'  a'  b' = b'  b  b' = a
 b  a'  b' = (a  a')  (b  b')  (a  a')  (b  b')).
Wegen der Monotonie der Transferfunktion fi gilt dann
fi(ak1…akn)  fi(bk1…bkn)
Und damit F(a0,…,am)  F(b0,…,bm)
23
Stetigkeit von F




F stetig gdw. F(a0,…,am)  F(b0,…,bm) =
F(a0b0,…,ambm).
Es seien ai' und bi' die i-ten Komponenten des Resultats
von F(a) bzw. F(b), d.h.:
b'i = fi(bk1,…,bkn ) und a'i = fi(ak1,…,akn)
Wegen der Stetigkeit von fi gilt: a'i  b'i
= fi(ak1,…,akn)  fi(bk1,…,bkn)
= fi(ak1)… fi(akn)fi(bk1)…fi(bkn)
= fi(ak1) fi(bk1)…fi(akn)fi(bkn)
= fi(ak1bk1)…fi(aknbkn)
= fi(ak1bk1,…,aknbkn).
fi(ak1bk1,…,aknbkn) ist auch die i-te Komponente des
Resultats von F(a0b0,…,ambm)
24
Ende der Optimierung
Ende der Vorlesung
Beispiel
Steuerflussgraph/Interferenzgraph
d:= d+1
r := 2*d
s := 3*c
t := r+s
e := t+5
d := 0
a := 1
c := 3
(d)
(a,d)
(a,d,c)
f := c
(a,c,f,d)
(c,d)
(c,d,r)
(d,s,r)
(d,t)
(d,e)
d:= a+f
u := c
v := u+1
w := v+1
e := v
c:= d+3
a := e*c
(d,c)
(d,c,a)
z:= a+d
(z)
u
v
t
w
(c,d)
(d,u)
(d,v)
(d,w)
(d,e)
e
a
d
s
f
c
r
z
26
Färbung des Interferenzgraphen


Gesucht Färbung I : V  R mit I(u) 
I(v) gdw. {u,v}  E, wobei R die Menge
der Prozessorregister ist.
Finden einer Färbung durch schrittweises
Entfernen von Knoten v mit adjazenten
Kanten, falls v mit echt weniger als |R|
Knoten adjazent ist:
Falls kein Knoten mit weniger als |R|
Nachbarn existiert, dann Spillentscheidung
treffen.
Falls I zum leeren Graphen reduziert wurde,
Einfügen der Knoten mit Kanten in
umgekehrter Reihenfolge und Färben der
Knoten.


w
v
u
t
e d4 z d1 d2 d3 s
r
c
f
u
v
t
w
e
a
d
s
f
c
r
z
I = (V, E), R = {0,1,2}
w
v
u
t
e
a
d
s
d4
f
c
r
z
d1
d2
a
d3 27
Spillen
Spillen von d
d := 0
a := 1
c := 3
f := c
d:= d+1
r := 2*d
s := 3*c
t := r+s
e := t+5
(c,d)
(c,d,r)
(d,s,r)
(d,t)
(d,e)
c:= d+3
a := e*c
z:= a+d
(d)
(a,d)
(a,d,c)
d := 0
@&d := d
a := 1
c := 3
(d)
()
(a,d)
(a,c)
f := c
(a,c,f)
(a,c,f,d)
d:= a+f
u := c
v := u+1
w := v+1
e := v
(d,c)
(d,c,a)
(z)
(c,d)
(d,u)
(d,v)
(d,w)
(d,e)
d1 := @&d
d1:= d1+1
@&d := d1
r := 2*d
s := 3*c
t := r+s
e := t+5
(c,d1)
(c,d1)
(c)
(c,r)
(s,r)
(t)
(e)
d2 := a+f
@&d := d2
u := c
v := u+1
w := v+1
e := v
d3 := @&d
c:= d3+3
a := e*c
(d3,c)
(c)
(c,a)
d4 := @&d
z:= a+d
(d4)
(z)
(c,d2)
(c)
(u)
(v)
(w)
(e)
28
Auswahl der Spillvariablen

Falls ein Interferenzgraph nicht weiter reduziert werden kann, dann
wird aus den verbleibenden Knoten der ausgewählt, für den
spillCost (v )
, wobei spillCost (v ) =
deg(v )




å
10deepth ( p )
p Î DefUse ( v )
minimal ist. Dabei sind DefUse(v) alle Programmpositionen, an
denen v verwendet/definiert wird. und deepth(p) die
Schachtelungstiefe der innersten Schleife, die die Programmposition
p enthält.
Vor/nach allen Verwendungen/Definitionen von v wird Spillcode in
den Zwischencode eingefügt.
Interferenzgraph muss neu konstruiert werden.
Es können mehrere solcher Iterationen erforderlich sein, bis eine
Färbung des Interferenzgraphen gefunden wird.
Variablen zwischen deren Definition und Verwendung keine anderen
Variablen sterben, werden nicht gespillt.
29

b - WWW-Docs for TU