Upload
hildebrand-strecker
View
107
Download
0
Embed Size (px)
Citation preview
1
Vorlesung, Wintersemester 2009/10 M. Schölzel
Optimierungstechniken in modernen Compilern
Grundlagen
2
Vorlesung, Wintersemester 2009/10 M. Schölzel
Grundlagen
Aufbau eines Compilers
Überblick über die Analysephase
3Optimierungstechniken in modernen Compilern Grundlagen
Aufbau eines Compilers
ParserQuell-text
Quell-text Scanner
Zwischencode und
Symbol- tabelle
Zwischencode und
Symbol- tabelle
Ziel-code
Ziel-code
Zielcode-erzeugung
Zielcodeunab-hängige
Optimierungen
Kontext-prüfung
ZielcodeabhängigeOptimierungen
Frontend
Backen
d
Steuerfluss im Compiler
Datenfluss im Compiler
4Optimierungstechniken in modernen Compilern Grundlagen
Zeichenketten
Es sei eine abzählbare Menge von Zeichen, Alphabet genannt.
Eine Zeichenkette w ist eine totale Funktion:
Für w schreiben wir auch: w(0)…w(n-1) n ist die Länge der Zeichenkette. Es gibt genau eine Zeichenkette der Länge 0;
diese wird mit bezeichnet. Eine Zeichenkette wird auch Wort genannt.
: {0, , 1} , mit - ® S ÎK ¥w n n
5Optimierungstechniken in modernen Compilern Grundlagen
Formale Sprache
n: Menge aller Zeichenketten über mit der Länge n:
*: Menge aller endlichen Zeichenfolgen über einem Alphabet :
+: Menge aller nicht leeren endlichen Zeichenfolgen über einem Alphabet :
Formale Sprache L: L *
{ }{ }: | : 0, , 1n w w nS = - ® SK
* :Î
S = S¥
U n
n
{0}
: n
n
+
Î -
S = S¥U
6Optimierungstechniken in modernen Compilern Grundlagen
Grammatik
Mittel zur konstruktiven Definition einer Sprache. Wichtig für den Compilerbau: Neben den Worten, die zu
einer Sprache gehören, wird auch eine Struktur der Worte definiert.
Grammatik G = (, M, R, S) mit M = , S M und R (( M)* - *) ( M)* endlich
Bezeichnungen: Grundsymble/Terminalsymbole/Terminals M Metasymbole/Nicht-Terminalsymbole/Nonterminals V := M Vokabular Worte * sind terminale Worte (Zeichenketten) Worte ( M)* - * sind nichtterminale Worte
(Zeichenketten) Jede Regel (l,r) R besitzt eine linke Seite l und eine rechte
Seite r (auch Alternative genannt)
7Optimierungstechniken in modernen Compilern Grundlagen
Ableitungsrelation
Durch die Regeln R einer Grammatik ist eine Ableitungsrelation definiert:
Statt (, ) schreiben wir auch für den Ableitungsschritt von nach
Eine Folge von Ableitungsschritten , ,…, n-1n wird kurz als …n-1n geschrieben und als Ableitung bezeichnet.
Durch Bildung des reflexiven und transitiven Abschlusses * von kann die durch G erzeugte Sprache definiert werden als:
Mit n wird eine Ableitung mit genau n Schritten bezeichnet Insbesondere folgt aus 0 , dass = Mit + wird eine Ableitung mit mindestens einem Schritt
bezeichnet.
{ }: ( , ) und und ( , ) Ra b a j cy b j dy c d®= = = Î
{ }* *( ) : |( , ) und = Î ® Î SL G Sa a a
8Optimierungstechniken in modernen Compilern Grundlagen
Geordneter Baum
Eine Knotenmenge B * ist ein geordneter Baum, falls gilt:
B ist endlich, Wenn i B, dann auch ( ist der Vater des Knotens i), mit *
und i , Wenn (i+1) B, dann auch i (i ist der linke Bruder des Knotens
(i+1)), mit * und i . Beispiel:
0 1
0.0 0.1 0.2
0 1
1.0 1.1 1.2
B = {, 0, 1,0.0, 0.1, 0.2} B = {, 0, 1,1.0, 1.1, 1.2}
9Optimierungstechniken in modernen Compilern Grundlagen
Syntaxbaum
Sei : B V eine Markierung der Knoten eines geordneten Baums mit den Symbolen einer kfG G = (, M, S, R). Dann ist (B, ) genau dann ein Syntaxbaum, falls gilt:
() = S B: Falls () = A M dann i mit (A,[A,i]) R so dass
für alle j mit 0 j < |[A,i]| gilt: (.j) = [A,i,j] .|[A,i]| B
B: Falls () = a , dann gilt .0 B Achtung: Nicht jedes Blatt im konkreten
Syntaxbaum ist mit einem Terminalsymbol beschriftet!
10Optimierungstechniken in modernen Compilern Grundlagen
Beispiel Syntaxbaum
Grammatik G = ({+, –, *, /, n, (, )}, A, M, T}, R, A), wobeiR = { (A, A+M), (A, A–M), (A, M),
(M, M*T), (M, M / T), (M, T),(T, n), (T, ( A ))}
A
A + M
M
T
n
M * T
nT
n
11Optimierungstechniken in modernen Compilern Grundlagen
Bedeutung eines Programms
Jedem syntaktisch korrekten Programm P der Sprache L ist durch eine Semantikfunktion .L eine Bedeutung PL = BP zugeordnet.
Eine Bedeutung kann im Sinne der denotationalen Semantik als eine Funktion BP verstanden werden, die einer gegebenen Startbelegung der Programmvariablen im Programm P ihre Belegung zuordnet nachdem das Programm terminierte, falls das Programm unter der gegebenen Startbelegung terminiert.
Für eine Eingangsbelegung e der Programmvariablen ist BP(e) = a die Belegung dieser Variablen nachdem P terminiert.
Für eine Programmvariable v kann durch e(v) bzw. a(v) ihre Eingangs-/Ausgangsbelegung ermittelt werden.
Beispiel:
main() { if(t) c = c+1}
BP(e) = a, wobei folgender Zusammenhang gilt:
( ) ( )
( ), falls ( ) 0( )
( ) 1, sonst
a t e t
ec e ta c
ec
=
ì =ïïï= íï +ïïî
Programm P:
12Optimierungstechniken in modernen Compilern Grundlagen
Analysephase - Frontend
Aufgabe des Frontends: Q und Z seien zwei Alphabete Q Q
* sei eine Quellsprache Z Z
* sei eine Zwischensprache Das Frontend berechnet eine Funktion
comp : Q* Z {error} mit
Eine mögliche Zwischensprache ist die Menge der Syntaxbäume.
§ ¨ § ¨ mit , falls ( )
, sonst
ZQz q z q Qcomp q
error
ì = Îïïï= íïïïî
13Optimierungstechniken in modernen Compilern Grundlagen
Synthesephase
Im Backend werden in der Regel viele verschieden Zwischensprachen verwendet. Mögliche Transformationen der Zwischensprachenformate im Backend:
In klassischen Compilern transformiert das Backend bedeutungserhaltend ein Zwischensprachenprogramm irp in ein Zielprogramm zp. D.h. z.B.: irp3AC = zpZC
Klassische Optimierungsverfahren transformieren den Zwischencode ebenfalls bedeutungserhaltend.
Das kann eine sehr starke Einschränkung für Optimierungen sein. Abschwächung: Nur für die interessierenden Ausgabevariablen v müssen die Semantikfunktionen bedeutungsgleich für alle Eingabebelegungen e sein: pQ(e)(v) = pZ(e)(v) .
Syntax-baum
3-Adress-Code
SSA-Code
Steuer-fluss-graph
DAG …
Optimierungen
Optimierungen Optimierungen
Optimierungen
Optimierungen
Zielcode
Optimierungen
.SSA.DAG
.3AC
.ZC
14Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
main() { for(i = 0; i++; i < 10) p = p + c;}
main() { for(i = 10; i--; i) p = p + c;}
Ursprüngliches Programm P Transformiertes Programm P'
Für eine Eingangsbelegung e und BP(e) = a gilt der Zusammenhang:( ) 10
( ) ( )
( ) ( ) 10 ( )
a i
a c ec
a p e p ec
=
=
= + ×
Für eine Eingangsbelegung e und BP'(e) = a gilt der Zusammenhang:( ) 0
( ) ( )
( ) ( ) 10 ( )
a i
a c ec
a p e p ec
=
=
= + ×
Sollte oben angegebene Transformation bedeutungserhaltend sein, ist sie unzulässig.Falls sie nur bedeutungserhaltend für die interessierenden Ausgabevariablen c und p sein soll, ist sie zulässig.
15
Vorlesung, Wintersemester 2009/10 M. Schölzel
Grundlagen
Zwischencodeformate
16Optimierungstechniken in modernen Compilern Grundlagen
3-Adress-Code (3AC)
Folge von 3-Adress-Code-Anweisungen mit Markierungen. Anweisungsarten:
Zuweisungen:• Binäranweisungen: x := y z• Unäranweisungen: x := y• Kopieranweisungen: x:=y, x:=k, @x:=y, x:=@y, x:=&y• Castoperationen: x := (Type) y
Sprunganweisungen:• Unbedingte Sprünge: goto index• Bedingte Sprünge: if x then Label• Funktionsaufrufe: x := call FLabel(y1,…,yn)• Funktionsbeendigung: return x, return
Markierungen: Funktionslabel: Function Label: Sprunglabel (mehrere Label hintereinander zulässig): Label1:
Labe2:... Dabei sind: k Konstante, x, y, yi und z Variablen, wobei Variablen
unterschieden werden in: Programmvariablen (lokal, global) Temporäre Variablen (immer lokal)
17Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: 3AC
int f(int n){ int fak = 1; while(n > 0) { fak = fak * n; n = n – 1; } return fak;}
Function f: t0 := 1 fak = t0while_0_cond: t1 := n t2 := 0 t3 := t1 > t2 t4 := not t3 if t4 then while_0_end t5 := fak t6 := n t7 := t5 * t6 fak := t7 t8 := n t9 := 1 t10 := t8 – t9 n := t10 goto while_0_condwhile_0_end: t11 := fak return t11
18Optimierungstechniken in modernen Compilern Grundlagen
Unterschiedliche 3AC-Abstraktionsniveaus
Hohes Abstraktionsniveau Feldzugriffe bleiben erhalten. Ermöglicht z.B. Abhängigkeitsanalyse von Feldzugriffen.
Mittleres Abstraktionsniveau Feldzugriffe sind in elementare Adressoperationen aufgelöst. Ermöglicht einfache Registerallokation und Codeauswahl.
Niedriges Abstraktionsniveau Variablen wurde auf verfügbare Register abgebildet. Parameterübergaben in Stapeloperationen umgewandelt. Ermöglicht direkte Übersetzung in Zielcodeerzeugung; bereits architekturabhängig.
t0 = 3t10 = a[i+2*j] + b[j]a[i+2*j] = t10 + t0
t0 = 3t1 = 2*jt2 = i+t1t3 = jt10 = a[t2] + b[t3]a[t2] = t10 + t0
t0 = 3t1 = 2*jt2 = i+t1t3 = jt4 = &at5 = t4 + t2t6 = @t5t7 = &bt8 = t7 + t3t9 = @t8t10 = t6 + t9t11 = t10 + t0@t5 = t1Abstraktionsniveau
19Optimierungstechniken in modernen Compilern Grundlagen
Prinzip der Transformation Syntaxbaum in 3-Adress-Code
Für jede Knotenart (jede Art entspricht einer Regel in der Grammatik) im Syntaxbaum gibt es ein Schema, wie aus den 3-Adress-Code-Sequenzen der Söhne die 3-Adress-Code-Sequenz des Vaters gebildet wird.
Generierung des 3-Adress-Codes kann dann Bottom-Up erfolgen.
Expr
Expr
Expr
Expr
ExprIDENT
INTLIT IDENT
Assign
id=a
iVal=2 id=b
ir=(t0:=a,t0)
ir=(t1:=2,t1)
ir=( t1:=2 t2:=b t3:=t1*t2,t3)
ir=(t2:=b,t2)
ir=( t0:=at1:=2 t2:=b t3:=t1*t2t4:=t0+t3,t4)
IDENT id=c
LVal id=c
ir= t0:=at1:=2 t2:=b t3:=t1*t2t4:=t0+t3c:=t4
{ int a,b,c; … c := a+2*b; …}
Quelltextfragment:
Syntaxbaum für den Ausdruck c := a+2*b:
20Optimierungstechniken in modernen Compilern Grundlagen
Steuerflussgraph
Modellierung aller potentiell möglichen Abarbeitungsfolgen der Anweisungen einer Funktion.
Steuerflussgraph S = (N,E,q,s): q ist die Anweisung über die die Funktion betreten wird. s ist die Anweisung über die die Funktion verlassen wird
(Transformation notwendig, falls mehrere return-Anweisungen in einer Funktion existieren).
N ist Knotenmenge: Zu jeder Anweisung der Funktion gibt es genau einen Knoten,
Kantenmenge E N N {0,1} mit• (a,b,0) E gdw. b folgt im 3AC direkt auf a und a ist Zuweisung
oder bedingter Sprung oder Funktionsaufruf,• (a,b,1) E gdw. a ist bedingter oder unbedingter Sprung zum
Label l und b ist mit Sprunglabel l markiert.
21Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
Function f:t0 := 1fak = t0while_0_cond:t1 := nt2 := 0t3 := t1 > t2t4 := not t3if t4 then while_0_end t5 := fakt6 := nt7 := t5 * t6fak := t7t8 := nt9 := 1t10 := t8 – t9n := t10goto while_0_condwhile_0_end:t11 := fakreturn t11
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
22Optimierungstechniken in modernen Compilern Grundlagen
Basisblöcke
Ein Basisblock ist eine Folge maximaler Länge von Anweisungen im 3-Adress-Code, für die gilt:
Nur die erste Anweisung darf mit einem Sprunglabel markiert sein (d.h., dass ein Sprung in einen Basisblock nur zu seiner ersten Anweisung führen kann) und
nur die letzte Anweisung darf eine Sprunganweisung sein (d.h., dass alle Anweisungen des Basisblocks ausgeführt werden, wenn die erste Anweisung ausgeführt wird).
Function f: t0 := 1 fak = t0while_0_cond: t1 := n t2 := 0 t3 := t1 > t2 t4 := not t3 if t4 then while_0_end t5 := fak t6 := n t7 := t5 * t6 fak := t7 t8 := n t9 := 1 t10 := t8 – t9 n := t10 goto while_0_condwhile_0_end: t11 := fak return t11
23Optimierungstechniken in modernen Compilern Grundlagen
Bilden von Basisblöcken im Steuerflussgraphen
Dabei sind: Pred(n) = {m | x {0,1} und (m,n,x) E} Succ(n) = {m | x {0,1} und (n,m,x) E}
Basisblöcke bi mit 0 i n sind Äquivalenzklassen, die eine Äquivalenzrelation bb definieren mit a bb b gdw. a bi und b bi.
Eingabe: Steuerflussgraph (N,E,q,s)Ausgabe: Zerlegung der Knoten in Basisblöcke B = {b0,…,bn}
currBB = 0;B = while(es ex. k N, das noch keinem Basisblock zugeordnet wurde) do Wähle ein k N, das noch keinem Basisblock zugeordnet wurde bcurrBB = {k} while(es ex. ein Knoten m bcurrBB und n bcurrBB und Pred(n) = {m} und Succ(m) = {n}) do bcurrBB = bcurrBB {m} od while(es ex. ein Knoten m bcurrBB und n bcurrBB und Succ(n) = {m} und Pred(m) = {n}) do bcurrBB = bcurrBB {m} od B := B {bcurrBB} currBB = currBB + 1;od
24Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
25Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
26Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
27Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
28Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
29Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
30Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
31Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
32Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
33Optimierungstechniken in modernen Compilern Grundlagen
Klassischer Steuerflussgraph
Im Steuerflussgraphen (N,E,q,s) wird N durch die Äquivalenzrelation bb in Äquivalenzklassen [a] = {b | a bb b} zerlegt.
Dadurch ergibt sich der klassische Steuerflussgraph (N/bb,E/bb,[q],[s]) mit:
N/bb = {[a] | a N} ist die Menge der Basisblöcke, (p,q) E/bb gdw. p,q N/bb und a p b q mit
(a,b) E, [q] ist der Basisblock, der q enthält, [s] ist der Basisblock, der s enthält.
34Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fakt5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
return t11
goto while_0_cond
10
1
t0 := 1fak = t0
t1 := nt2 := 0t3 := t1 > t2t4 := not t3if t4 then while_0_end
t11 := fakreturn t11
t5 := fakt6 := nt7 := t5 * t6fak := t7t8 := nt9 := 1t10 := t8 – t9n := t10goto while_0_cond
35Optimierungstechniken in modernen Compilern Grundlagen
Notationen N/bb = {b0,...,bn}:
über b0 wird die Funktion betreten, über b1 wird die Funktion verlassen.
|bi| Anzahl der Anweisungen in Basisblock i. Basisblock bi enthält die Anweisungsfolge ir1(i),...,ir|bi|
(i). Falls bi aus dem Kontext hervorgeht, auch kurz ir1,...,ir|bi|
, Eine Programmposition ist ein Tupel (i,j), wobei damit die
Position nach der j-ten (vor der (j+1)-ten) Anweisung im Basisblock i gemeint ist:
(0,0) Position vor der ersten Anweisung einer Funktion. (1,|b1|) Position nach der letzten Anweisung einer Funktion.
Ein Anweisungsfolge a1,...,ak ist ein Pfad im klassischen Steuerflussgraphen (N/bb, E/bb,[q],[s]) von Programmposition (i,j) zur Programmposition (m,n), falls:
k: 1 k < k (ak,ak+1) E und irj+1(i) = a1 und irn(m) = ak.
36Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
t0 := 1fak = t0
t1 := nt2 := 0t3 := t1 > t2t4 := not t3if t4 then while_0_end
t11 := fakreturn t11
t5 := fakt6 := nt7 := t5 * t6fak := t7t8 := nt9 := 1t10 := t8 – t9n := t10goto while_0_cond
b0
b2
b1b3
|b2| = 5
ir2(2),ir3(2),ir4(2) = t2:=0,t3:=t1>t2,t4:=not t3
Programmposition (1,1)
Programmposition (3,7)
Anweisungen auf dem Pfad von Programmposition (3,7) nach Position (1,1)
37Optimierungstechniken in modernen Compilern Grundlagen
……
Qualität des Modells
Steuerflussgraph modelliert alle möglichen Abarbeitungspfade des Programms, unabhängig davon, ob alle diese Pfade bei der Ausführung des Programms betreten werden können.
Falls Turingmaschine i auf Eingabe i nach n Schritten stoppt, dann gibt es eine Eingabe n, so dass 4 nach 2 ausgeführt wird, sonst nicht.
if (TMi(i)n) then 4
Eingabe von n0
2
3 4
…1
38
Vorlesung, Wintersemester 2009/10 M. Schölzel
Grundlagen
Datenflussanalyse
39Optimierungstechniken in modernen Compilern Grundlagen
Definition/Verwendung einer Variablen
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) die Form 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.
Erreichende Definition: Die Definition einer Programmvariablen v erreicht eine Verwendung von v, falls es einen Pfad im Steuerflussgraphen von dieser Definition zur Verwendung gibt, auf dem keine andere Definition von v liegt.
40Optimierungstechniken in modernen Compilern Grundlagen
Beispiel Erreichende Definitionen
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
0
3
4
6
7
8
10
9
Definition zu einer Verwendung ist in unverzweigtem Steuerfluss einfach zu
finden.
t0 := 1
fak = t0
t1 := n
t2 := 0
t3 := t1 > t2
t4 := not t3
if t4 then while_0_end
t11 := fak
return t11
t5 := fak
t6 := n
t7 := t5 * t6
fak := t7
t8 := n
t9 := 1
t10 := t8 – t9
n := t10
Definition zu einer Verwendung ist bei Verzweigungen im Steuerfluss schwieriger zu finden.
41Optimierungstechniken in modernen Compilern Grundlagen
Grundidee Datenflussanalyse am Beispiel der Erreichenden Definitionen
t1 := 1
t1 := n
t3 := t1 > t2
if t3 then while_0_end
Es gibt eingehende Informationen I in einen Knoten: I = in(2)
Durch die Anweisung(en) in einem Knoten werden Informationen
zerstört: I := I – Kill(2)
Durch die Anweisung(en) in einem Knoten werden neue Informationen
generiert: I := I Gen(2)
0
1
2
t2 := 2
Es entstehen ausgehende Informationen an einen Knoten: out(2)
3
4
in(2) = {(t2,0),(t1,1)}
out(2) = {(t2,0),(t1,2)}Gen(2) = {(t1,2)}
Kill(2) = {(t1,i) | i }
42Optimierungstechniken in modernen Compilern Grundlagen
Transferfunktion für einen Basisblock
Steuerfluss in einem Basisblock i mit den Anweisungen ir0(i),…,ir#i(i) ist bekannt.
Damit ist die Transferfunktion für diesen Basisblock:
Vereinfachung der Transferfunktion zu out(i) = (in(i) – kill(i)) gen(i).
t1 := 1
t1 := n
t3 := t1 > t2
if t3 then while_0_end
0
1
2
t2 := 2
3
4
0 0 1 0 # #( ) ( ) ( ( )) ( ( )) ( ( )) ( ( )) ( ( )) ( ( ))i iout i in i Kill ir i Gen ir i Kill ir i Gen ir i Kill ir i Gen ir i= - È - È - - ÈK
in(i)
- Kill(0) Gen(0)
- Kill(1) Gen(1)
- Kill(2) Gen(2)
- Kill(3) Gen(3)
- Kill(4) Gen(4)
out(i)
43Optimierungstechniken in modernen Compilern Grundlagen
Datenflussanalyse bei Verzweigungen im Steuerflussgraphen
Ausgehende Informationen out(i) gelangen zu jedem Steuerflussnachfolger von i.
Treffen Informationen von mehreren Steuerflussvorgängern zusammen, müssen diese zu einer eingehenden Information zusammengefasst werden.
…t3 := t1 + t2…
…t0 := t1 – t9…
…t2 := t3 * t5…
Transformiert eingehende Informatione
n
Ausgehende Informationen
II
I
Hier müssen Informationen
kombiniert werden
Transformiert eingehende Informatione
n
Transformiert eingehende Informatione
n
44Optimierungstechniken in modernen Compilern Grundlagen
Grundprinzip Datenflussanalyse
Informationen I breiten sich entweder mit oder gegen den Steuerfluss aus.
Für jeden Knoten 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:
• 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) Rückwärtsanalyse:
• 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.
45Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Erreichende Definitionen
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}
t0 := at1 := bt2 := t0 + t1
t0 := t2 – t0t0 := b
t3 := t2t4 := t3 * t2t2 := t2 – t4
in(b2) =
in(b3) =
in(b4) =
in(b1) = gen(b3) = {((3,1),t0)}
kill(b3) = {((m,n),t0)}
gen(b4) = {((4,0),t3), ((4,1),t4), ((4,2),t2)}
kill(b4) = {((m,n),t3), ((m,n),t4), ((m,n),t2)}
gen(b2) = {((2,0),t0), ((2,1),t1), ((2,2),t2)}
kill(b2) = {((m,n),t0), ((m,n),t1), ((m,n),t2)}
out(b0) =
out(b2) =
out(b3) =
out(b4) =
{((2,0),t0), ((2,1),t1), ((2,2),t2)}
{((2,0),t0), ((2,1),t1), ((2,2),t2)}
{((4,0),t3), ((4,1),t4), ((4,2),t2)}
{((3,1),t0)}
{((4,0),t3), ((4,1),t4), ((4,2),t2)}
{((2,0),t0), ((2,1),t1), ((2,2),t2)}
{((3,1),t0)}
{((4,0),t3), ((4,1),t4), ((4,2),t2)}
{((2,0),t0), ((2,1),t1), ((2,2),t2)}
{((2,1),t1), ((2,2),t2), ((3,1),t0)}
{((2,0),t0), ((2,1),t1)}
{((4,0),t3), ((4,1),t4), ((4,2),t2)}
{((2,0),t0), ((2,1),t1), ((2,2),t2)}
{((2,0),t0), ((2,1),t1), ((2,2),t2)}
{((4,0),t3), ((4,1),t4), ((4,2),t2)}
{((2,1),t1), ((2,2),t2), ((3,1),t0), ((2,0),t0),
((4,0),t3), ((4,1),t4), ((4,2),t2)}
b2
b3 b4
b1
b0
46Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Lebendigkeit
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}
t0 := at1 := bt2 := t0 + t1
t0 := t2 – t0t0 := b
t3 := t2t4 := t3 * t2t2 := t2 – t4
gen(b3) = {b, t2, t0}
kill(b3) = {t0}
gen(b1) =
kill(b1) =
gen(b2) = {a,b}
kill(b2) = {t0,t1,t2} gen(b4) = {t2}
kill(b4) = {t2,t3,t4}
in(b0) = in(b2)
in(b2) = (in(b3) in(b4) – kill(b2)) gen(b2)
in(b3) = (in(b1) – kill(b3)) gen(b3)
in(b4) = ((in(b4) in(b1)) – kill(b4)) gen(b4)
b2
b3 b4
b1
b0
47
Vorlesung, Wintersemester 2009/10 M. Schölzel
Grundlagen
Zwischencodeformate (fortgesetzt)
48Optimierungstechniken in modernen Compilern Grundlagen
SSA-Code
Eigenschaften: Jede Variable wird statisch genau einmal definiert. Vorteil für viele Analysen: Jede
Benutzung einer Variablen hat nur genau eine Definition. An solchen Punkten, an denen der Steuerfluss zusammentrifft, müssen -Funktionen
eingefügt werden, die verschiedene Instanzen derselben Variablen zusammenführen. Zwei Schritte zur Konstruktion von SSA-Code:
Programmpositionen finden, an denen eine -Funktion eingefügt werden muss. Variablenumbenennung (Indizierung), um eindeutige Namen für jede Definition zu
erzeugen.
… := v
v := … v := …
… := v
v := …
… := v
v := … := v
v := … := v
v3 := (v1,v2)… := v3
v2 := …v1 := …
v4 := …
v5 := (v3,v4) … := v5
… := v4
49Optimierungstechniken in modernen Compilern Grundlagen
Dominator
Block x dominiert Block y (x dom y) genau dann im Steuerflussgraphen, wenn jeder Pfad vom Startknoten zum Block y durch Block x führt.
Doms(y) := {x | x dom y} Block x dominiert Block y streng (x sdom y), wenn
x dom y und x y.
Beispiel: 5 dominiert 5, 6, 7, 8 5 dominiert streng 6, 7, 8 6 dominiert 6 6 dominiert streng nicht dominiert von 5: 0, 1, 2, 3, 4, 9 nicht streng dominiert von 5: 0, 1, 2, 3, 4, 5, 9 Doms(3) = {0, 2, 3} Doms(4) = {0, 4}
0
3
4
5
6 7
8
9
2
1
50Optimierungstechniken in modernen Compilern Grundlagen
Berechnung von Doms
Berechnung der Information Doms(x) für Steuerflussgraphen S = (N,E,q,s) durch eine Datenflussanalyse mit den Parametern:
Menge aller Informationen: (N) Vorwärtsanalyse mit := gen(bi) := {i} kill(bi) := Starten mit in(bi) = N für i > 0 und in(b0) =
51Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Berechnung Doms
Der direkte Dominator idom(x) eines Blocks x in einem Steuerflussgraphen ist der Block y Doms(x) – {x}, so dass für jeden Block z Doms(x) – {x} gilt: z Doms(y).
1
2
3
4
5 6
7
8
9 10
Steuerflussgraph
out(0) = {0} = {0}
out(1) = (out(0) out(9)) {1} = {0,1}
out(2) = out(1) {2} = {0,1,2}
out(3) = (out(2) out(1) out(8) out(4)) {3}= {0,1,3}
out(4) = (out(3) out(7)) {4} = {0,1,3,4}
out(5) = (out(4)) {5} = {0,1,3,4,5}
out(6) = (out(4)) {6} = {0,1,3,4,6}
out(7) = (out(5) out(6) out(10)) {7} = {0,1,3,4,7}
out(8) = out(7) {8} = {0,1,3,4,7,8}
out(9) = out(8) {9} = {0,1,3,4,7,8,9}
out(10) = out(8) {10} = {0,1,3,4,7,8,10}
idom(x)
0
1
1
3
4
4
4
7
8
8
out(x) Doms(x)
52Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominatorbaum
1
2
3
4
5 6
7
8
9 10
1
2 3
4
5 6 7
8
6 7
9 10
Steuerflussgraph Dominatorbaum (grafische Darstellung der idom-Relation).
idom(x)
0
1
1
3
4
4
4
7
8
8
1
2
3
4
5
6
7
8
9
10
x0
53Optimierungstechniken in modernen Compilern Grundlagen
Dominanzgrenze (Dominance Frontier)
Die Dominanzgrenze DF(x) eines Blocks x ist die Menge der Blöcke y im Steuerflussgraphen S = (N,E,q,s) für die gilt:
p N: (p,y) E und x dom p und (x,y) sdom, d.h. y ist nicht streng dominiert von x.
Eigenschaft der Knoten in DF (x): Falls ein Block y zu DF(x) gehört, dann gibt es vom Startknoten
des Steuerflussgraphen einen Pfad nach y, der durch x führt und einen Pfad, der nicht durch x führt.
Intuition: DF(x) sind auf den von x ausgehenden Pfaden die ersten Blöcke, die von x aus erreicht werden können, aber nicht von x dominiert werden.
y DF(x) ist damit ein Knoten, an dessen Beginn eine -Funktion für jede in x definierte Variable eingefügt werden muss, weil Definitionen dieser Variablen von unterschiedlichen Programmpositionen y erreichen können.
54Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominanzgrenze
1
2
3
4
5 6
7
8
9 10
Steuerflussgraph
x dominiertnicht streng
dominiert von x
1 {1,…,10} {1}
DF(x)
{1}
1
2 3
4
5 6 7
8
6 7
9 10
Dominatorbaum
55Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominanzgrenze
1
2
3
4
5 6
7
8
9 10
1
2 3
4
5 6 7
8
6 7
9 10
Steuerflussgraph Dominatorbaum
x dominiert
1 {1,…,10}
DF(x)
2 {2} {3}{1,…,10}
nicht strengdominiert von x
{1} {1}
56Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominanzgrenze
1
2
3
4
5 6
7
8
9 10
1
2 3
4
5 6 7
8
6 7
9 10
Steuerflussgraph Dominatorbaum
x dominiert
1 {1,…,10}
DF(x)
2 {2} {3}
3 {3,…,10} {1,3}{1,2,3}
nicht strengdominiert von x
{1,…,10}
{1} {1}
57Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominanzgrenze
1
2
3
4
5 6
7
8
9 10
1
2 3
4
5 6 7
8
6 7
9 10
Steuerflussgraph Dominatorbaum
x dominiert
1 {1,…,10}
DF(x)
2 {2} {3}
3 {3,…,10} {1}
4 {4,…,10} {1,3}
{1}
58Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominanzgrenze
1
2
3
4
5 6
7
8
9 10
1
2 3
4
5 6 7
8
6 7
9 10
Steuerflussgraph Dominatorbaum
x dominiert
1 {1,…,10}
DF(x)
2 {2} {3}
3 {3,…,10} {1}
4 {4,…,10} {1,3}
5 {5} {7}
{1}
59Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominanzgrenze
1
2
3
4
5 6
7
8
9 10
1
2 3
4
5 6 7
8
6 7
9 10
Steuerflussgraph Dominatorbaum
x dominiert
1 {1,…,10}
DF(x)
2 {2} {3}
3 {3,…,10} {1}
4 {4,…,10} {1,3}
5 {5} {7}
6 {6} {7}
{1}
60Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominanzgrenze
1
2
3
4
5 6
7
8
9 10
1
2 3
4
5 6 7
8
6 7
9 10
Steuerflussgraph Dominatorbaum
x dominiert
1 {1,…,10}
DF(x)
2 {2} {3}
3 {3,…,10} {1}
4 {4,…,10} {1,3}
5 {5} {7}
6 {6} {7}
7 {7,8,9,10} {1,3,4,7}
{1}
61Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominanzgrenze
1
2
3
4
5 6
7
8
9 10
1
2 3
4
5 6 7
8
6 7
9 10
Steuerflussgraph Dominatorbaum
x dominiert
1 {1,…,10}
DF(x)
2 {2} {3}
3 {3,…,10} {1}
4 {4,…,10} {1,3}
5 {5} {7}
6 {6} {7}
7 {7,8,9,10} {1,3,4}
8 {8,9,10} {1,3,7}
{1}
62Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominanzgrenze
1
2
3
4
5 6
7
8
9 10
1
2 3
4
5 6 7
8
6 7
9 10
Steuerflussgraph Dominatorbaum
x dominiert
1 {1,…,10}
DF(x)
2 {2} {3}
3 {3,…,10} {1}
4 {4,…,10} {1,3}
5 {5} {7}
6 {6} {7}
7 {7,8,9,10} {1,3,4}
8 {8,9,10} {1,3,7}
9 {9} {1}
{1}
63Optimierungstechniken in modernen Compilern Grundlagen
Beispiel: Dominanzgrenze
1
2
3
4
5 6
7
8
9 10
1
2 3
4
5 6 7
8
6 7
9 10
Steuerflussgraph Dominatorbaum
x dominiert
1 {1,…,10}
DF(x)
2 {2} {3}
3 {3,…,10} {1}
4 {4,…,10} {1,3}
5 {5} {7}
6 {6} {7}
7 {7,8,9,10} {1,3,4}
8 {8,9,10} {1,3,7}
9 {9} {1}
10 {10} {7}
{1}
64Optimierungstechniken in modernen Compilern Grundlagen
-Funktionen einfügen
Für jede definierte Variable v in Block x muss eine -Funktion in jedem Block y DF(x) eingefügt werden.
Wird eine -Funktion für eine Variable v in einem Block y DF(x) eingefügt, ist das eine neue Definition für v.
Damit muss auch in jeden Block z DF(y) eine -Funktion für v eingefügt werden.
… := v
v := … v := …
… := v
… := v
v := … v := …3: 4: 5: 6:
7: 8:
DF(3) = {7} DF(4) = {7} DF(5) = {8} DF(6) = {8}
9:
DF(8) = {9}DF(7) = {9}
65Optimierungstechniken in modernen Compilern Grundlagen
Algorithmus -Funktionen einfügen
PutPhiHere(x)..Menge der Variablen für die in Block x eine -Funktion eingefügt werden muss
Def(x)..Menge der in Block x definierten Variablen
Steuerflussgraph S = (N,E,q,s)
for each x N do
toProcess := DF(x)
alreadyProcessed :=
while es existiert y toProcess do
PutPhiHere(y) := PutPhiHere(y) Def(x)
alreadyProcessed := alreadyProcessed {y}
toProcess := (toProcess (DF(y)) – alreadyProcessed
od
od
66Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
v := … := v
v := … v := …
v := … := v
v := … := v
v := … v := …3: 4: 5: 6:
7: 8:
9:
67Optimierungstechniken in modernen Compilern Grundlagen
Variablenumbenennung
Für jede Variable v: Durchnummerieren der Definitionen von v mittels num(v,i,j), wobei (i,j) Programmposition der Definition von v ist.
Erreichende Defintionen für Steuerflussgraph mit -Funktionen berechnen (v := wird wie eine Definition für v behandelt).
Jede Verwendung von v wird wegen der Konstruktion nur noch von einer Definition (i,j) erreicht:
Umbenennung dieser Verwendung von v in vnum(v,i,j).
Eine -Funktionen für v wird im Allgemeinen von mehreren Definitionen (i0,j0),…,(in,jn) erreicht:
Ersetze v := durch v := (vnum(v,i0,j0),…,vnum(v,in,jn)).
Durch Dead-Code-Eliminierung können überflüssige -Funktionen entfernt werden.
68Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
v5 := … := v
v2 := … v3 := …
v4 := … := v
v6 := … := v
v0 := … v1 := …3: 4: 5: 6:
7: 8:
9:
Durchnummerieren der Definitionen von v
69Optimierungstechniken in modernen Compilern Grundlagen
Beispiel (Fortsetzung)
v5 := … := v
v2 := … v3 := …
v4 := … := v
v6 := … := v
v0 := … v1 := …3: 4: 5: 6:
7: 8:
9:
Berechnung der erreichenden Definitionen
((3,0),v0), ((4,0),v1)((5,0),v2), ((6,0),v3)
((8,0),v5)((7,0),v4)
((7,0),v4), ((8,0),v5)
((9,0),v6)
70Optimierungstechniken in modernen Compilern Grundlagen
Beispiel (Fortsetzung)
v5 := (v2,v3)… := v5
v2 := … v3 := …
v4 := (v0,v1)… := v4
v6 := (v4,v5)… := v6
v0 := … v1 := …3: 4: 5: 6:
7: 8:
9:
Umbenennung
((3,0),v0), ((4,0),v1)((5,0),v2), ((6,0),v3)
((8,0),v5)((7,0),v4)
((7,0),v4), ((8,0),v5)
((9,0),v6)
71Optimierungstechniken in modernen Compilern Grundlagen
Erweiterung des Steuerflussgraphen um SSA-Kanten
SSA-Kante (q,s) gibt es genau dann, wenn die Anweisung im Knoten q die Variable v definiert und die Anweisung im Knoten s die Variable v verwendet.
v5 := (v2,v3)
v2 := … v3 := …
v4 := (v0,v1)
v6 := (v4,v5)
v0 := … v1 := …
… := v4
… := v6
… := v5
72Optimierungstechniken in modernen Compilern Grundlagen
Variablenumbenennung ohne iterative Analyse
renameVariable(x,b) x ... Umzubenennende Variable b ... Basisblock im Steuerflussgraphen V ... Stack mit Versionsnummern der Variable x
rollback = Top(V)for each s b do if s ist keine -Anweisung then Ersetze alle Verwendungen von x in s durch xTop(V) fi if s definiert x then Ersetze Definition von v durch vcurrVersion; push(currVersion,V); currVersion++; fiodfor each succ Succ(b) do b sei j-ter Vorgänger von succ und x := (...) Phi-Funktion für x in succ Setze j-tes Argument von x := (...) auf xTop(V);odfor each c, wobei c Kind von b im Dominatorbaum ist do renameVariable(x,c)odwhile (Top(V) rollBack) do Pop(V) od
for each Variable x do currVersion = 1; push(0,V) renameVariable(x,0)od
Aufruf durch:
73Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i := 0read n
i = ()n = ()n 1
even(n)
n := n / 2 n := 3n + 1
n := ()i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0
74Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i := 0read n1
i = ()n = ( ,n1)n 1
even(n)
n := n / 2 n := 3n + 1
n := ()i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1
75Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n2 = ( ,n1)n2 1
even(n)
n := n / 2 n := 3n + 1
n := ()i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1,2
76Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = ( ,n1)n 1
even(n2)
n := n / 2 n := 3n + 1
n := ()i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1,2
77Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = ( ,n1)n 1
even(n2)
n3 := n2 / 2 n := 3n + 1
n := (n3, )i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1,2,3
78Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = ( ,n1)n 1
even(n2)
n3 := n2 / 2 n := 3n + 1
n := (n3, )i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1,2
79Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = ( ,n1)n 1
even(n2)
n3 := n2 / 2 n4 := 3n2 + 1
n := (n3, n4)i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1,2,4
80Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = ( ,n1)n 1
even(n2)
n3 := n2 / 2 n4 := 3n2 + 1
n := (n3, n4)i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1,2
81Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = (n5,n1)n 1
even(n2)
n3 := n2 / 2 n4 := 3n2 + 1
n5 := (n3, n4)i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1,2,5
82Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = (n5,n1)n 1
even(n2)
n3 := n2 / 2 n4 := 3n2 + 1
n5 := (n3, n4)i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1,2
83Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = (n5,n1)n 1
even(n2)
n3 := n2 / 2 n4 := 3n2 + 1
n5 := (n3, n4)i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1
84Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = (n5,n1)n 1
even(n2)
n3 := n2 / 2 n4 := 3n2 + 1
n5 := (n3, n4)i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1
85Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = (n5,n1)n 1
even(n2)
n3 := n2 / 2 n4 := 3n2 + 1
n5 := (n3, n4)i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0,1
86Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
i1 := 0read n
i2 = ()n = (n5,n1)n 1
even(n2)
n3 := n2 / 2 n4 := 3n2 + 1
n5 := (n3, n4)i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
0
2
14 6 75 6
3 7j n
j n
Steuerflussgraph mit -Funktionen Dominatorbaum
V = 0
87Optimierungstechniken in modernen Compilern Grundlagen
Anwendung des SSA-Codes
Die Informationen Erreichende Definitionen und Nächste Verwendung sind direkt an den SSA-Kanten ablesbar.
Vereinfachung der Eliminierung toten Codes: Knoten, die eine Variable definieren und keine
weiteren Seiteneffekte verursachen und von denen keine SSA-Kante ausgeht, können gelöscht werden (einschließlich der eingehenden SSA-Kanten).
Dadurch können weitere Knoten ohne ausgehende SSA-Kanten entstehen.
Vereinfachung der Konstantenpropagierung.
88Optimierungstechniken in modernen Compilern Grundlagen
Konstantenpropagierung
Steuerflussgraph ist in SSA-Form und jeder Knoten enthält genau eine Anweisung.
W sei eine Liste aller Knoten im Steuerflussgraphen Solange W nicht leer ist:
• Entferne Knoten s aus W• Falls s die Form v := (c1, …,ck) hat und c1 = c2 = … = ck sind
Konstanten:– Ersetze s durch v := c1
• Falls s die Form v := c hat und c eine Konstante ist:– Lösche s aus dem Graphen– Für jeden Knoten t, der v verwendet:
» Ersetze in t v durch c » Füge t zur Liste W hinzu
Verbesserung durch Bedingte Konstantenpropagierung: Konstantenpropagierung und Eliminierung von Blöcken, die wegen eines konstanten Ausdrucks in einer bedingten Verzweigung nicht erreicht werden können.
89Optimierungstechniken in modernen Compilern Grundlagen
Zusammenfassung SSA-Code
Explizite Darstellung von Definition und Verwendung einer Variablen. Dadurch Vereinfachung von:
Konstantenpropagierung, Eliminierung toten Codes, Vorwärtsersetzung von Ausdrücken (später), Finden von Induktionsvariablen, Verschiebung von schleifeninvariantem Code.
Verschiedene Optimierungsalgorithmen benötigen keine Datenflussanalyse mehr. Sie arbeiten mit dem Dominatorbaum oder der Dominanzgrenze. Dadurch werden globale Optimierungsverfahren teilweise so einfach wie lokale.
Nicht alle Optimierungsverfahren profitieren vom SSA-Code; z.B. Lebendigkeitsanalyse.
90Optimierungstechniken in modernen Compilern Grundlagen
Anwendung des Dominators: Erkennen von Schleifen
Eine Schleife (natural loop) im Steuerflussgraphen ist gekennzeichnet durch:
Eine Menge L von Knoten, die auf einem Zykel im Steuerflussgraphen liegen.
Es gibt einen ausgezeichneten Knoten h in L, der der einzige Knoten in L mit einem Vorgängerknoten v L ist. Der Knoten h wird Kopf genannt.
Eine Kante (t,h) im Steuerflussgraphen ist eine Rücksprungkante in der Schleife L, falls h der Kopf von L ist und t L.
91Optimierungstechniken in modernen Compilern Grundlagen
Finden von Schleifen
Berechnung der Relation dom. Finden von Rücksprungkanten durch Tiefensuche im
Steuerflussgraphen (N,E,q,s) mit dfs(N,E,q):
Für jede Rücksprungkante (t,h) Berechnung der Knoten, die zur Schleife mit Kopf h gehören durch:
succsessors := Succ(h); Lh := {h}; Löschen des Knotens h mit allen adjazenten Kanten aus dem
Steuerflussgraphen. Für jeden Knoten u, der Nachfahre eines Knotens in successors ist:
• Falls (u,t) E+, dann Lh := Lh {u}.
dfs(N,E,node,fromNode) { if alreadyVisited(node) then if (node dom fromNode) then addToLoopHeads(fromNode, node) fi return; fi alreadVisited(node) = True; for each (node,dest) E do dfs(N,E,dest,node) od}
92Optimierungstechniken in modernen Compilern Grundlagen
Beispieli := 0read n
n 1
even(n)
n := n / 2 n := 3n + 1
i := i + 1
print(i)
Stopp
0
2
3
4 5
6
7
1
dfs(N,E,node,fromNode) { if alreadyVisited(node) then if (node dom fromNode) then addToLoopHeads(fromNode, node) fi return; fi alreadVisited(node) = True; for each (node,dest) E do dfs(N,E,dest,node) od}
Besuchsreihenfolge der Knoten:0, 2, 3, 4, 6, 2, 5, 6, 7, 1
2 dom 6
6 dom 5
succsessors = {3,7}Rücksprungkante = (6,2); Kopf = 2
L2 = {2,3,4,5,6}
93
Vorlesung, Wintersemester 2009/10 M. Schölzel
Grundlagen
Modellierung von Abhängigkeiten
94Optimierungstechniken in modernen Compilern Grundlagen
Steuerflussabhängigkeiten
Steuerflussabhängigkeiten:Im Steuerflussgraphen ist Knoten b steuerflussabhängig von Knoten a, falls:
ein Pfad a,s1,...,sn,b für n 0 im Steuerflussgraphen existiert, so dass alle Knoten s1,...,sn von b postdominiert werden und
a nicht von b postdominiert wird.
0
1
2 3
4
5 6
Knoten steuerflussabhängig von
0123456
--002,320,2
95Optimierungstechniken in modernen Compilern Grundlagen
Datenabhängigkeiten
Datenabhängigkeiten: Im Steuerflussgraphen ist eine Anweisungen b von Anweisung a datenabhängig genau dann, wenn:
a und b auf dasselbe Datum zugreifen und mindestens eine dieser Anweisungen schreibend auf das Datum zugreift und
ein Pfad von Anweisung a zu Anweisung b existiert. Wenn b von a datenabhängig ist, dann wird a Quelle
und b Senke der Abhängigkeit genannt. Datenabhängigkeiten ergeben sich durch die
Reihenfolge, in der auf Daten lesend und schreibend zugegriffen wird.
Steuerfluss- und Datenabhängigkeiten erzwingen eine Reihenfolge bei der Abarbeitung der Anweisungen, die nicht verändert werden darf, da sonst die Bedeutung des Programms verändert werden kann.
96Optimierungstechniken in modernen Compilern Grundlagen
Arten von Datenabhängigkeiten
Im Folgenden: Anweisung b kann nach Anweisung a ausgeführt werden: Fluss-Abhängigkeit (True Dependency, Flow Dependency, RAW): Eine Anweisung
b ist genau dann fluss-abhängig von Anweisung a, wenn a ein Datum schreibt, das von b gelesen wird:
Anti-Abhängigkeit (Antidependency, WAR): Eine Anweisung b ist genau dann anti-abhängig von Anweisung a, wenn a ein Datum liest, das von b geschrieben wird:
Ausgabe-Abhängigkeit (Output Dependency, WAW): Eine Anweisung b ist genau dann Ausgabe-abhängig von Anweisung a, wenn a ein Datum schreibt, das auch von b geschrieben wird:
a: t2 = t0 + t1b: t4 = t2 + t3
b: t4 = t2 + t3a: t2 = t0 + t1
a: t0 = xb: x = t1
b: x = t1a: t0 = x
a: x = t0b: x = t1…c: t4 = x
b: x = t1a: x = t0…c: t4 = x
Falscher Wert wird genutzt.
Falscher Wert wird genutzt.
Falscher Wert wird genutzt.
97Optimierungstechniken in modernen Compilern Grundlagen
Geschachtelte normalisierte Schleifen
Betrachtung des inneren Schleifenkörpers eines Schleifennestes mit einer Indexvariable je Schleife.
d ist die Schachtelungstiefe. ik ist die Indexvariable in Schachtelungsebene k. Lk ist die untere Grenze der Schachtelungsebene k. Uk ist die obere Grenze der Schachtelungsebene k. hk und tk sind Anweisungsfolgen ohne Steuerflussanweisungen.
for i1 = L1 to U1 step 1 do h1; for i2 = L2 to U2 step 1 do ... for id = Ld to Ud step 1 do hd; od ... od t1
od
98Optimierungstechniken in modernen Compilern Grundlagen
Normalisierung der Indexvariablen
Jede Indexvariable ist normalisiert. Das heißt sie wird in jeder Iteration um 1 erhöht.
Transformation einer Schleife l durch folgenden Algorithmus möglich:
Ersetze den Schleifenkopf for i = L to U step Sdurch for i' = 0 to (U–L)/S step 1
Ersetze jede Benutzung von i im Schleifenkörper durch (i' * S + L)
Füge unmittelbar nach der Schleife l die Anweisung i = i' * S + L ein.
99Optimierungstechniken in modernen Compilern Grundlagen
Indexvektor / Iterationsraum
Iterationsraum:I = {(i1,...,id) | Lk ik Uk für alle 1 k d}
Ein Indexvektor (i1,...,id) I repräsentiert eine Belegung der Laufvariablen eines Schleifennestes der Tiefe d.
Lexikografische Ordnung der Vektoren in I:(i1,...,id) < (j1,...,jd), falls
es existiert ein k mit 1 k d und ik < jk und für alle 1 n < k: in = jn.
Jeder Indexvektor entspricht einer Abarbeitung des Schleifenkörpers hd.
Lexikografische Ordnung der Indexvektoren entspricht der durch den Programmierer spezifizierten Abarbeitungsreihenfolge des Schleifenkörpers hd bei Abarbeitung des Schleifennestes.
100Optimierungstechniken in modernen Compilern Grundlagen
Beispiel Iterationsraum
Als Instanz einer Anweisung wird eine Ausführung dieser Anweisung bei der Programmabarbeitung bezeichnet.
Menge aller Instanzen der Anweisungen in einem Schleifennest:{sv | s ist Anweisung und v I}.
for i = 0 to 3 step 1 do for j = 0 to 2 step 1 do a[i][j] = b[j]; b[j] = b[j] + 1; odod
i = 0
i = 1
i = 2
i = 3
j = 0 j = 1 j = 2
j = 0 j = 1 j = 2
j = 0 j = 1 j = 2
j = 0 j = 1 j = 2
I = { (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2), (3,0), (3,1),(3,2)}
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
a[i][j] = b[j];b[j] = b[j] + 1;
101Optimierungstechniken in modernen Compilern Grundlagen
Abhängigkeiten in Schleifen (1)
In einem Schleifenkörper existiert eine Abhängigkeit von Anweisung s zu Anweisung t genau dann, wenn:
zwei Iterationsvektoren u und v mit u < v oder u = v existieren und ein nicht leerer Pfad von su nach tu existiert und Instanz su von s greift auf Speicherposition m zu und Instanz tv von t greift auf Speicherposition m zu und einer dieser beiden Zugriffe ist ein schreibender Zugriff.
Beispiele: for i = 2 to 4 step 1 do for j = 2 to 3 step 1 do(s) a = i * j;(t) b = a * a; od od
(t) besitzt eine Fluss-Abhängigkeit von (s) wegen a=i*j(n,m) und b=a*a(n,m).(s) besitzt eine Anti-Abhängigkeit von (t) wegen a=i*j(n,m) und b=a*a(u,v) und (u,v) (n,m)(s) besitzt eine Ausgabe-Abhängigkeit von (s) wegen a=i*j(n,m) und a=i*j(u,v) für (u,v) < (n,m)(t) besitzt eine Ausgabe-Abhängigkeit von (t) wegen b=a*a(n,m) und b=a*a(u,v) für (u,v) < (n,m)
102Optimierungstechniken in modernen Compilern Grundlagen
Abhängigkeiten in Schleifen (2) for i = 2 to 4 step 1 do for j = 2 to 3 step 1 do(s) a[i][j] = a[i][j] * 2;(t) a[i-1][j-1] = a[i][j] - 2; od od
i = 2j = 2
i = 2j = 3
i = 3j = 2
i = 3j = 3
i = 4j = 2
i = 4j = 3
1,1 1,2 1,3
2,1 2,2 2,3
i
j
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
3,1 3,2 3,3
4,1 4,2 4,3
s(2,2) s(2,3)
s(3,2) s(3,3)
s(4,3)s(4,2)
s(2,2) s(2,3)
s(3,2) s(3,3)
s(4,3)s(4,2)
t(2,2) t(2,3)
t(3,2) t(3,3)
t(4,3)t(4,2)
t(2,2) t(2,3)
t(3,2) t(3,3)
t(4,3)t(4,2)
(t) besitzt eine Fluss-Abhängigkeit von (s).
(t) besitzt eine Ausgabe-Abhängigkeit von (s).
(t) besitzt eine Anti-Abhängigkeit von (s).
Feld a:
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
a[i][j] = a[i][j] * 2
a[i-1][j-1] = a[i][j] - 2
103Optimierungstechniken in modernen Compilern Grundlagen
Distanzvektor
Distanzvektor:Falls eine Abhängigkeit von su nach tv existiert, dann ist der Distanzvektor d(u,v) definiert als: d(u,v)k = vk – uk, wobei 1 k n und n die Länge der Vektoren u und v ist.
Ein Distanzvektor charakterisiert den Abstand zweier datenabhängiger Anweisungsinstanzen bezüglich ihres Abstandes im Iterationsraum der Schleife.
Beispiel:1,1 1,2 1,3
2,1 2,2 2,3
i
j
3,1 3,2 3,3
4,1 4,2 4,3
s(2,2) s(2,3)
s(3,2) s(3,3)
s(4,3)s(4,2)
s(2,2) s(2,3)
s(3,2) s(3,3)
s(4,3)s(4,2)
t(2,2) t(2,3)
t(3,2) t(3,3)
t(4,3)t(4,2)
t(2,2) t(2,3)
t(3,2) t(3,3)
t(4,3)t(4,2)
Feld a:
Distanz für s(2,2) und t(2,2):d((2,2),(2,2)) = (0,0)
Distanz für s(3,2) und t(4,3):d((3,2),(4,3)) = (1,1)
104Optimierungstechniken in modernen Compilern Grundlagen
Richtungsvektor
Falls eine Abhängigkeit von su nach tv existiert, dann ist der Richtungsvektor D(u,v) definiert als:
Der Richtungsvektor abstrahiert von der Distanz und reduziert die Abhängigkeit auf die Relation zwischen den Komponenten der Richtungsvektoren.
Beispiel:
, falls
( , ) , falls
, falls
k k
k k k
k k
u v
D u v u v
u v
for i = 1 to N step 1 do for j = 1 to M step 1 do for k = 1 to L step 1 do a[i+1][j][k-1] = a[i][j][k] * 2; od odod
a[i+1][j][k-1](x,y,z)
a[i][j][k](x+1,y,z-1)
Schreibender Zugriff mit Indexvektor (x,y,z) auf Feldelement a[x+1][y][z-1]:
Lesender Zugriff auf a[x+1][y][z-1] mit Indexvektor (x+1,y,z-1):
Richtungsvektor: D((x,y,z),(x+1,y,z-1)) = (<,=,>)
Flussabhängigkeit
105Optimierungstechniken in modernen Compilern Grundlagen
Anzahl der Abhängigkeiten bei Betrachtung der Anweisungsinstanzen
Eine Abhängigkeit zwischen jedem Paar von Anweisungsinstanzen, das auf dieselbe Speicheradresse zugreift:
for i = 1 to 10 step 1 do for j = 1 to 10 step 1 do a[i+1][j] = a[i][j] * 2; od od
i = 1 j = 1
a[i+1][j] = a[i][j] * 2
j = 2
a[i+1][j] = a[i][j] * 2
j = 10
a[i+1][j] = a[i][j] * 2...
i = 2 j = 1
a[i+1][j] = a[i][j] * 2
j = 2
a[i+1][j] = a[i][j] * 2
j = 10
a[i+1][j] = a[i][j] * 2...
i = 10 j = 1
a[i+1][j] = a[i][j] * 2
j = 2
a[i+1][j] = a[i][j] * 2
j = 10
a[i+1][j] = a[i][j] * 2...
...
1,1 1,2 1,10
2,1 2,2 2,10
3,1 3,2 3,10
11,1 11,2 11,10
Feld a:Insgesamt
90 Abhängigkei
ten!
106Optimierungstechniken in modernen Compilern Grundlagen
Anzahl der Abhängigkeiten bei Betrachtung der Distanzvektoren
Zusammenfassen aller Abhängigkeiten mit demselben Distanzvektor zwischen Instanzen derselben zwei Anweisungen :
for i = 1 to 10 step 1 do for j = 1 to 10 step 1 do a[i+1][j] = a[i][j] * 2; odod
a[i+1][j](x,y)
a[i][j](x+1,y)
Schreibender Zugriff mit Indexvektor (x,y) auf Feldelement a[x+1][y]:
Lesender Zugriff auf a[x+1][y] mit Indexvektor (x+1,y):
Richtungsvektor für jede Abhängigkeit: D((x,y),(x+1,y)) = (<,=)
Distanzvektor für jede Abhängigkeit: d((x,y),(x+1,y)) = (1,0)
Insgesamt 1 Abhängigkeit!
107Optimierungstechniken in modernen Compilern Grundlagen
Anzahl der Abhängigkeiten bei Betrachtung der Richtungsvektoren
for j = 1 to 10 step 1 do for i = 1 to 7 step 1 do a[j][i] = b[i][j] * 2; c[i][j] = a[j][8-i] + 4; odod
j
i = 1
a[j][i] = ...... = a [8-i]...
j,1 j,2
i = 2
a[j][i] = ...... = a [8-i]...
i = 3
a[j][i] = ...... = a [8-i]...
i = 4
a[j][i] = ...... = a [8-i]...
i = 5
a[j][i] = ...... = a [8-i]...
i = 6
a[j][i] = ...... = a [8-i]...
i = 7
a[j][i] = ...... = a [8-i]...
j,3 j,4 j,5 j,6 j,7
RAW, (0,6), (=,<)
RAW, (0,4), (=,<)
RAW, (0,2), (=,<)
RAW, (0,0), (=,=)
WAR, (0,2), (=,<)
WAR, (0,4), (=,<)
WAR, (0,6), (=,<)
a[j][i] = b[i][j] * 2;
c[i][j] = a[j][8-i] + 4;
(=,<) (=,=) (=,<)
108Optimierungstechniken in modernen Compilern Grundlagen
Unterteilung von Abhängigkeiten in Schleifen
Schleifenunabhängige Abhängigkeiten:Anweisung t besitzt eine schleifenunabhängige Abhängigkeit von Anweisung s, gdw. t auf Speicherposition m in Iteration u und s auf Speicherposition m in Iteration v zugreift und u = v und es existiert ein nicht leerer Pfad von s nach t.
Schleifengetragene Abhängigkeiten:Anweisung t besitzt eine schleifengetragene Abhängigkeit von s, gdw. s auf Speicherposition m in Iteration u und t auf Speicherposition m in Iteration v zugreift und u < v.
j
i = 1
a[j][i] = ...... = a [8-i]...
j,1 j,2
i = 2
a[j][i] = ...... = a [8-i]...
i = 3
a[j][i] = ...... = a [8-i]...
i = 4
a[j][i] = ...... = a [8-i]...
i = 5
a[j][i] = ...... = a [8-i]...
i = 6
a[j][i] = ...... = a [8-i]...
i = 7
a[j][i] = ...... = a [8-i]...
j,3 j,4 j,5 j,6 j,7
109Optimierungstechniken in modernen Compilern Grundlagen
Schleifengetragene Abhängigkeiten
Eine schleifengetragene Abhängigkeit von s nach t ist rückwärtsgerichtet, gdw. t im Schleifenkörper vor s steht
oder s = t, vorwärtsgerichtet, wenn t hinter s steht.
j
i = 1
a[j][i] = ...... = a [8-i]...
j,1 j,2
i = 2
a[j][i] = ...... = a [8-i]...
i = 3
a[j][i] = ...... = a [8-i]...
i = 4
a[j][i] = ...... = a [8-i]...
i = 5
a[j][i] = ...... = a [8-i]...
i = 6
a[j][i] = ...... = a [8-i]...
i = 7
a[j][i] = ...... = a [8-i]...
j,3 j,4 j,5 j,6 j,7
110Optimierungstechniken in modernen Compilern Grundlagen
Level einer schleifengetragenen Abhängigkeit
Der Level einer schleifengetragenen Abhängigkeit von su nach tv ist i, falls, D(u,v)i = < und für alle 1 k < i D(u,v)k = =.
Charakterisierung einer Menge von Abhängigkeiten durch die erste Schleife im Schleifennest möglich, für die es verschiedene Iterationen gibt, zwischen denen Abhängigkeiten bestehen.
Beispiel: Alle schleifengetragenen Abhängigkeiten haben Richtungsvektor (=,<) und damit den Level 2.
j=1
i = 1
a[j][i] = ...... = a [8-i]...
i = 2
a[j][i] = ...... = a [8-i]...
i = 3
a[j][i] = ...... = a [8-i]...
i = 4
a[j][i] = ...... = a [8-i]...
i = 5
a[j][i] = ...... = a [8-i]...
i = 6
a[j][i] = ...... = a [8-i]...
i = 7
a[j][i] = ...... = a [8-i]...
j=10
i = 1
a[j][i] = ...... = a [8-i]...
i = 2
a[j][i] = ...... = a [8-i]...
i = 3
a[j][i] = ...... = a [8-i]...
i = 4
a[j][i] = ...... = a [8-i]...
i = 5
a[j][i] = ...... = a [8-i]...
i = 6
a[j][i] = ...... = a [8-i]...
i = 7
a[j][i] = ...... = a [8-i]...
...
111Optimierungstechniken in modernen Compilern Grundlagen
Abhängigkeitsgraph
Abhängigkeitsgraph (N,D,A,O,level): N ist Knotenmenge; jeder Knoten repräsentiert eine Anweisung, D N N Flussabhängigkeiten, A N N Antiabhängigkeiten, O N N Ausgabeabhängigkeiten, level : D A O () ist Beschriftung der Kanten, wobei k level(s,t) bedeutet:
• k = 0: schleifenunabhängige Abhängigkeit, • k > 0: schleifengetragene Abhängigkeit mit Level k.
Beispiel (von Folie 107):
for j = 1 to 10 step 1 do for i = 1 to 7 step 1 do(s) a[j][i] = b[i][j] * 2;(t) c[i][j] = a[j][8-i] + 4; od od
a[j][i] = b[i][j] * 2;
c[i][j] = a[j][8-i] + 4;
(=,<) (=,=) (=,<)
{0,2}D {2}A
N = {s,t}D = {(s,t)}A = {(t,s)}O = level((s,t)) = {0,2} level((t,s)) = {2}
s
t
112Optimierungstechniken in modernen Compilern Grundlagen
Zulässigkeit einer Umordnung
Eine Umordnung der Anweisungen im Quellprogramm kann die Ausführungsreihenfolge der Anweisungsinstanzen eines Schleifennests ändern. Es werden aber nach der Umordnung bei jeder möglichen Programmausführung nur genau die Anweisungsinstanzen ausgeführt, die auch in dem nicht umgeordneten Programm ausgeführt worden sind.
Eine Umordnung erhält eine Abhängigkeit, falls nach der Umordnung die Quelle der Abhängigkeit noch vor der Senke ausgeführt wird.
Jede Umordnung eines Programms, die jede Abhängigkeit erhält, erhält auch die Bedeutung des Programms. Eine solche Transformation wird zulässig genannt.
s1
sn
...
s11 sn1...Ausführungsreihenfolge der Anweisungsinstanzen für |I| = k:
s12 sn2... s1k snk......
s11 sn1...Ausführungsreihenfolge der Anweisungsinstanzen nach Umordnung:
s21 s2k...s1k snk......Umordnung
s1
sn
...
s11sn1 ...Umordnung der Anweisungsinstanzen für |I| = k:
s21 s2k... s1ksnk... ...
s12Zulässig!
Unzulässig!
113Optimierungstechniken in modernen Compilern Grundlagen
Schleifentransformationen
Eine Umordnung, die nur die Ausführungsreihenfolge der Iterationen der Level-k-Schleife ändert, ist zulässig, falls die Level-k-Schleife keine Abhängigkeiten trägt.
Folgerungen: Iterationen können auf verschiedenen Prozessoren ohne
Synchronisation verteilt werden. Anweisungen verschiedener Iterationen können parallel ausgeführt
werden.
1 2 n
Iterationen der Level-(k+1)-SchleifeIterationen der Level-k-Schleife
Iterationen der Level-(k-1)-Schleife
114
Vorlesung, Wintersemester 2009/10 M. Schölzel
Grundlagen
Testen auf Abhängigkeiten
115Optimierungstechniken in modernen Compilern Grundlagen
Voraussetzung zur Allokation von Feldern
Betrachtung von Feldzugriffen auf n-dimensionale Felder im innersten Schleifenkörper mit n > 0.
Dabei gilt: Die Speicherbereiche verschieden benannter Felder sind disjunkt (gilt nicht zwingend für C/C++):
for(i1 = L1; i1 < U1; i1++)
for(i2 = L2; i2 < U2; i2++)
A[i1][i2] = B[i2][i1];
int A[100][100];
int B[100][100];
for(i1 = L1; i1 < U1; i1++)
for(i2 = L2; i2 < U2; i2++)
A[i1+i2] = B[i2];
int A[100];
int* B = A;
116Optimierungstechniken in modernen Compilern Grundlagen
Voraussetzung für Ausdrücke zur Indizierung
Indizierungen sind affine Ausdrücke in den Indexvariablen: Für eine Schleife der Form for i1 = L1 to U1 step 1 do
for i2 = L2 to U2 step 1 do
...
for id = Ld to Ud step 1 do
Schleifenfreier Schleifenkörper;
sind Ausdrücke der Form a0 + a1*i1 + a2*i2 + ... + ad*id
affin (lineare Funktion), wobei a0,...,ad Konstanten sind oder invariant in allen d Schleifen.
Zum Beispiel nicht zulässig: nicht-lineare Funktionen in den Indexvariablen (es müsste eine
allgemeine diophantische Gleichung gelöst werden; unentscheidbar).
Indizierungen, die keine Funktion in den Indexvariablen sind; z.B.: a[b[i]].
117Optimierungstechniken in modernen Compilern Grundlagen
Prinzip des Testens von Abhängigkeiten zwischen Feldzugriffen (Beispiel)
Abhängigkeiten zwischen Anweisungen eines Schleifenkörpers in verschiedenen Iterationen:
Ein Schreibzugriff auf eine skalare Variable x erzeugt eine Abhängigkeit zu allen Schreib-/Lesezugriffen auf x in der nächsten Schleifeniteration.
Ein Schreibzugriff auf ein Feld erzeugt eine Abhängigkeit zu einem Feldzugriff in einer (möglicherweise folgenden) Iterationen nur dann, wenn dort dasselbe Element indiziert wird.
Beispiel: for(i = 0; i < 20; i++) A[2*i] = A[3*i+5]
Offensichtlich erfolgt ein Zugriff auf dasselbe Element genau dann, wenn ein i1 und i2 existiert, so dass
• 2 i1 = 3 i2+5• und 0 i1 19 und 0 i2 19.
Finden dieser Belegungen für i1 und i2 entspricht dem Lösen einer linearen diophantischen Gleichung.
118Optimierungstechniken in modernen Compilern Grundlagen
Prinzip des Testens von Abhängigkeiten zwischen Feldzugriffen
Gegeben sind zwei Anweisungen mit Zugriffen auf Elemente desselben Feldes.
Für jedes Paar von Feldzugriffen von denen mindestens ein Zugriff schreibend ist, wird ein Gleichungssystem aus den Ausdrücken aufgestellt, die zur Indizierung verwendet werden.
Versuche zu beweisen, dass keine ganzzahlige Lösung des Gleichungssystems innerhalb der Schleifengrenzen existiert; d.h. Für alle u, v I ist u auf der linken und v auf der rechten Seite eingesetzt, keine Lösung:
Gelingt der Beweis, können Datenabhängigkeiten zwischen den Anweisungen des Anweisungspaares ausgeschlossen werden.
Kann bewiesen werden, dass eine ganzzahlige Lösung innerhalb der Schleifengrenzen existiert, dann gibt es eine Datenabhängigkeit.
Kann weder der Beweis noch der Gegenbeweis erbracht werden, dann wird die konservative Annahme getroffen, dass eine Abhängigkeit existiert.
119Optimierungstechniken in modernen Compilern Grundlagen
Klassifizierung von Indizierungspaaren
Betrachtung von Paaren von Feldzugriffen der Form (A[e1]...[en], A[e'1]...[e'n]) mit den Indizierungsausdrücken ei und e'i für 1 i n.
ei und e'i werden Indizierungspaar genannt. IV(e) = {i | i ist Indexvariable, die in e vorkommt} Indexpaar (e, e') heißt:
ZIV (zero index variable), falls IV(e) IV(e') = , SIV (single index variable), falls |IV(e) IV(e')| = 1, MIV (multiple index variable), falls
|IV(e) IV(e')| > 1. Bilden des Gleichungssystem durch:
ei = e'i für 1 i n, wobei alle Indexvariablen in e'1,...,e'n werden durch ein Apostroph so
umbenannt werden, dass sich ihre Namen von denen in e1,...,en unterscheiden.
120Optimierungstechniken in modernen Compilern Grundlagen
Gruppierung von Indexpaaren
Es seien (ei, e'i) mit 1 i n die Indizierungspaare eines Zugriffs auf ein n-dimensionales Feld.
Konstruktion von Gruppen durch: Erzeuge neue Gruppe G mit einem beliebigen Paar (a,b), das noch keiner Gruppe zugeordnet wurde Solange es weitere Paare (a,b) mit (IV(a) IV(b)) (IV(c) IV(d)) für (c,d) G gibt, nimm (a,b) in G auf Wiederhole die ersten zwei Schritte, bis alle Paare einer Gruppe angehören.
Ein Paar (a, b) heißt separierbar, falls es einziges Element in seiner Gruppe ist; ansonsten heißen die Paare in der Gruppe gekoppelt.
Beispiel: (A[i][j][j],A[i][j][k]) (i,i) ist separierbar, (j,j) und (j,k) sind gekoppelt.
Abhängigkeitstest kann separat für jede Gruppe durchgeführt werden.
Falls für eine Gruppe gezeigt werden kann, dass das zugehörige Gleichungssystem keine ganzzahlige Lösung besitzt, dann gibt es keine Datenabhängigkeit zwischen dem Indexpaar.
121Optimierungstechniken in modernen Compilern Grundlagen
Testen von Abhängigkeiten
Für jedes Paar von Feldzugriffen, die eine Abhängigkeit verursachen können:
Zerlege die Indizierungen in minimal gekoppelte Gruppen. Klassifiziere die Gruppen nach: ZIV, SIV, MIV. Für jede separate Gruppe:
• Wende einen geeigneten Abhängigkeitstest (ZIV, SIV, MIV) an, um entweder die Unabhängigkeit zu beweisen oder einen Richtungsvektor für die Indexvariablen in der Gruppe zu erzeugen.
Für gekoppelte Gruppe:• Wende einen Test für mehrfache Indizierungen an, um
Richtungsvektoren zu erzeugen.• Falls einer der Tests eine Unabhängigkeit nachweist, sind keine
weiteren Tests erforderlich. Kombiniere alle Richtungsvektoren zu einer Menge von
Richtungsvektoren für das getestete Paar von Feldzugriffen.
122Optimierungstechniken in modernen Compilern Grundlagen
Beispiele for j = 1 to 10 step 1 do for i = 1 to 10 step 1 do a[i+1][j] = a[i][j] * 2; od od
Paar von Feldzugriffen
Minimal gekoppelte Gruppen (jeweils separat): ([i+1],[i]) und ([j],[j])
SIV SIV
SIV-Test ergibt: ([i+1],[i])
Quelle Senkei+1 = i' ergibt Distanz 1; also Richtung: <
for i = 1 to 10 step 1 do for j = 1 to 10 step 1 do a[i+1][5] = a[i][n] * 2; od od
Paar von Feldzugriffen
Minimal gekoppelte Gruppen (jeweils separat): ([i+1],[i]) und ([5],[n])
SIV ZIV
SIV-Test für ([i+1],[i]) ergibt Richtung <
SIV-Test ergibt: ([j],[j])
Quelle Senkej = j' ergibt Distanz 0; also Richtung: =
ZIV-Test für ([5],[n]) ergibt: Abhängigkeit für n=5 möglich; also:Alle Richtungen möglich, Richtungsvektoren: {(<,<), (<,=), (<,>)}
Richtungsvektoren: {(=,<)}
123Optimierungstechniken in modernen Compilern Grundlagen
ZIV-Test für separierbare Paare
Wenn (e,e') ZIV, dann sind beide Ausdrücke in allen Schleifendurchläufen konstant.
Falls symbolische Auswertung von e – e' den Wert 0 ergibt, dann besteht eine Abhängigkeit. Aber: Keine Rückschlüsse auf Richtungsvektor einer Indexvariablen möglich.
Falls symbolische Auswertung von e – e' einen konstanten Wert verschieden von 0 ergibt, dann besteht keine Abhängigkeit.
Ansonsten konnte weder bewiesen noch widerlegt werden, ob eine Abhängigkeit existiert und es muss eine konservative Annahme getroffen werden.
124Optimierungstechniken in modernen Compilern Grundlagen
Test für starke separierbare SIV Paare
Indexpaar (e,e') ist stark SIV, falls e = a i + c und e' = a i + c'. Es ergibt sich durch Umbenennen und Gleichsetzen das Gleichungssystem:
a i + c = a i' + c'd = i – i' = (c' – c)/a
d ist die Anzahl der Schleifeniterationen zwischen zwei Zugriffen auf dasselbe Feldelement (relevant für Modulo-Scheduling).
Eine Abhängigkeit existiert genau dann, wenn 0 < |d| U – L und ganzzahlig ist oder
d = 0 und e und e' zu verschiedenen Anweisungen gehören. Falls |d| > 0 ist Richtung für i: < Falls d > 0 ist e Quelle Falls d < 0 ist e' Quelle Falls d = 0 und e und e' zu verschiedenen
Anweisungen s und s' gehören, dannist s genau dann Quelle, wenn s vor s'steht.
i, i'
ai+c
e, e'
ai'+c'
Zugriff auf dasselbe Element
d
125Optimierungstechniken in modernen Compilern Grundlagen
Test für separierbare weak-zero-SIV Paare
Indexpaar (e,e') ist weak-zero-SIV, falls: es die Form e = 0 i + c und e' = a' i + c' oder (1) e = a i + c und e' = 0 i + c' hat. (2)
Es ergibt sich o.B.d.A. für (1): i = (c – c')/a'
Eine Abhängigkeit existiert genau dann, wenn i ist ganzzahlig und L i U.
i
e'
a'i+c'
c
126Optimierungstechniken in modernen Compilern Grundlagen
Test für separierbare weak-crossing-SIV Paare
Indexpaar (e,e') ist weak-crossing-SIV, falls: es die Form e = a i + c und e' = a' i + c' hat und a' = -a gilt.
Schnittpunkt befindet sich bei i = i'. Wegen a' = a ergibt sich:i = (c' – c)/2a
Eine Abhängigkeit existiert genau dann, wenn i ist ganzzahlig oder hat als Nachkommawert eine 0.5 und L i U.
i, i'
e'
L U -ai'+c'
ai+c
i = i'
e = e'
e
127Optimierungstechniken in modernen Compilern Grundlagen
Test für separierbare weak-SIV
Indexpaar (e,e') ist weak-SIV, falls es die Form e = a i + c und e' = a' i + c' hat.
Es ergibt sich durch Umbenennen und Gleichsetzen: a i + c = a' i' + c'
Eine Abhängigkeit mit Richtung D {<,=,>} existiert genau dann, wenn ganzzahlige i und i' existieren mit a i + c = a' i' + c' und L i, i' U und i D i'.
e ist Quelle der Abhängigkeit, gdw. D = < oder D = = und e vor e' im Quelltext steht.
i, i'
e,e'
L U
a'i'+c' ai+c
128Optimierungstechniken in modernen Compilern Grundlagen
Test für separierbare MIV Paare
Indexpaar (e,e') ist MIV, falls es die Form e = a1i1 + ... + adid + c und e' = e = a'1i1 + ... + a'did + c' hat.
Es ergibt sich durch Gleichsetzen: 0 = a1i1 + ... + adid - a'1i'1 - ... - a'di'd + (c - c') bzw.(a1i1 - a'1i'1) + ... + (adid - a'di'd) = c' - c
Eine Abhängigkeit für den Richtungsvektor (D1,...,Dn) existiert genau dann, wenn
ganzzahlige ik und ik' für obige Gleichung mit 1 k d existieren und Lk ik, ik' Uk und ik Dk ik'.
Um zu testen, ob eine Abhängigkeit für einen bestimmten Richtungsvektor existiert, aufzählen aller möglichen Richtungsvektoren und Test für jeden Richtungsvektor ausführen.
129Optimierungstechniken in modernen Compilern Grundlagen
Testen von Abhängigkeiten mit Richtungsvektor beim MIV-Test
Verbesserung durch schrittweise Präzisierung der Richtungsvektoren möglich. Allgemeinster Richtungsvektor: (*,*,...,*).
Richtung * an Position k in D bedeutet, dass beim Testen jede der Relationen ik < ik', ik = ik' bzw. ik > ik' gelten darf.
try((e,e'),D,k,dvlist) { if not check((e,e'),D)) then return dvlist fi if k = n then return dvlist {D} fi for each d {<, =, >} do Dk := d dvlist := try((e,e'),D,k+1,dvlist) od}
(*,*,*)
(<,*,*) (=,*,*) (>,*,*)
(<,<,*) (<,=,*) (<,>,*)Falls Test hier schon keine Abhängigkeit entdeckt.
130Optimierungstechniken in modernen Compilern Grundlagen
GCD-Test (a1i1 - a'1i'1) + ... + (adid - a'di'd) = c' - c ist eine lineare diophantische Gleichung;
vereinfacht: a1 i1 + a2 i2 + ... + an in = c. GCD-Test liefert eine notwendige und hinreichende Bedingung zur Existenz einer
ganzzahligen Lösung einer linearen diophantischen Gleichung. Damit: Falls GCD-Test erfolgreich, dann existiert eine ganzzahlige Lösung, diese muss aber nicht
die untere/obere Schranke Lk/Uk einhalten. Falls GCD-Test fehlschlägt, dann existiert keine Abhängigkeit zwischen den Feldzugriffen
aus denen das Indexpaar hervorgegangen ist. Die lineare diophantische Gleichung
a1 i1 + a2 i2 + ... + an in = cbesitzt genau dann eine ganzzahlige Lösung in i1,...,in, wenn ggt(|a1|,...,|an|) c teilt.
Dabei ist
Beispiel: Paar von Feldzugriffen: (A[4*i],A[5-2*i]) Gleichungssystem: 2i' + 4i = 5 ggt(2,4) = 2, wobei 2 nicht 5 teilt.
Problem: Oft ist ggt(|a1|,...,|an|) = 1.
1 2 3
1 1 2 2 1
1 2 2 1 1 2
1 2 1 1 2 2 1
1 2 2
ggt(ggt( , ), , , ), falls 2
, falls 2 und und div 0
ggt( , , ) , falls 2 und und div 0
ggt( , mod ), falls 2 und und div 0
ggt( mod , ), falls 2 un
n
n
a a a a n
a n a a a a
a a a n a a a a
a a a n a a a a
a a a n
>
= £ =
= = £ =
= £ ¹
=
K
K
2 1 1 2d und div 0a a a a
ìïïïïïïïïïïíïïïïïïï £ ¹ïïïî
131Optimierungstechniken in modernen Compilern Grundlagen
Test mit Banerjee Ungleichung Wir betrachten wieder Indexpaare (e,e') der Form
f(i1,...,id) = e = a1i1 + ... + adid + c und g(i'1,...,i'd) = e'= a'1i'1 + ... + a'di'd + c'.
Abhängigkeit für Richtungsvektor (D1,...,Dn) existiert genau dann, wenn ganzzahlige Werte für i1,...,id,i'1,...,i'd mit Lik
ik Uik und Li'k
i'k Ui'k und
ik Dk ik' für 1 k d existieren, so dass:h(i1,...,id,i'1,...,i'd) := f(i1,...,id) - g(i'1,...,i'd) = (a1i1 - a'1i'1) + ... + (adid - a'di'd)+ (c - c') = 0
Ganzzahlige Lösung existiert nur dann, wenn es eine Lösung in gibt. Eine Lösung in existiert für die stetige Funktion h genau dann, wenn:
min{h(i1,...,id,i'1,...,i'd)} 0 und 0 max{h(i1,...,id,i'1,...,i'd)}, wobei Lik
ik Uik und Li'k
i'k Ui'k und ik Dk ik' für 1 k d.
Finden des Minimums/Maximums durch separate Minimierung (MINk(Dk)) bzw. Maximierung (MAXk(Dk)) der Terme (akik - a'ki'k) unter Beachtung der Richtung Dk.
Bedingung für eine Abhängigkeit:1 1
( ) ( )d d
k k k kk k
MIN D c' c MAX D= =
£ - £å å
132Optimierungstechniken in modernen Compilern Grundlagen
Minimierung/Maximierung mit Richtung =
Minimum MINk(=) von akik - a'ki'k ergibt sich durch:
Maximum MAXk(=) von akik - a'ki'k ergibt sich durch:
( ) , falls ( )
( ) , falls
' 'k k k k k
k ' 'k k k k k
a a U a aMIN
a a L a a
ìï - × <ïï= = íï - × ³ïïî
( ) , falls ( )
( ) , falls
' 'k k k k k
k ' 'k k k k k
a a U a aMAX
a a L a a
ìï - × ³ïï= = íï - × <ïïî
133Optimierungstechniken in modernen Compilern Grundlagen
Minimierung/Maximierung mit Richtung *
Minimum MINk(*) von akik - a'ki'k ergibt sich durch:
Maximum MAXk(*) von akik - a'ki'k ergibt sich durch:
, falls 0 und 0
, falls 0 und 0(*)
, falls 0 und 0
, falls 0 und 0
' 'k k k k k k
' 'k k k k k k
k ' 'k k k k k k
' 'k k k k k k
a L a U a a
a U a U a aMIN
a U a L a a
a L a L a a
ìï × - × ³ ³ïïïï × - × < ³ïïï= íï × - × < <ïïïï × - × ³ <ïïïî
, falls 0 und 0
, falls 0 und 0(*)
, falls 0 und 0
, falls 0 und 0
' 'k k k k k k
' 'k k k k k k
k ' 'k k k k k k
' 'k k k k k k
a U a L a a
a L a L a aMAX
a L a U a a
a U a U a a
ìï × - × ³ ³ïïïï × - × < ³ïïï= íï × - × < <ïïïï × - × ³ <ïïïî
134Optimierungstechniken in modernen Compilern Grundlagen
Minimierung mit Richtung <
Minimum MINk(<) von akik - a'ki'k ergibt sich durch:
MAXk(<), MINk(>) MAXk(>) von akik - a'ki'k ergeben sich entsprechend.
, falls 0 und 0
( 1) , falls 0 und 0
( ) ( 1) , falls 0 und 0 und
( 1), falls 0 und 0 und
( 1), fall
' 'k k k k k k
' 'k k k k k k
' ' 'k k k k k k k k k
' ' 'k k k k k k k k
'k k k k
a L a U a a
a U a U a a
MIN a U a U a a a a
a L a L a a a a
a L a L
× - × ³ ³
× - - × < ³
< = × - - × < < <
× - × + < < ³
× - × + s 0 und 0'k ka a
ìïïïïïïïïïïïíïïïïïïïï ³ <ïïîï
135Optimierungstechniken in modernen Compilern Grundlagen
Test für gekoppelte Paare
Jedes Paar (e1,e'1),...,(en,e'n) in einer Gruppe kann zunächst separat mit einem der vorgestellten Tests getestet werden.
Falls bereits für ein Paar gezeigt werden kann, dass das zugehörige Gleichungssystem keine ganzzahlige Lösung in den gegebenen Grenzen besitzt, dann besitzt auch das Gleichungssystem zur Gruppe keine solche Lösung. Es existieren also keine Datenabhängigkeiten zwischen den zugehörigen Feldzugriffen.
Falls aber Lösungen existieren, dann gemeinsame Betrachtung dieser Lösungen durch Einsetzen des Gleichungssystems zu (ei,e'i) in das Gleichungssystem zu (ej,e'j), falls (IV(ei,) IV(ej,)) (IV(e'i) IV(e'j)) .
136Optimierungstechniken in modernen Compilern Grundlagen
Beispiel anhand des GCD-Tests
A[x+z][3*x+z] und A[2*x][99-2*x]
(I) x – 2x' + z = 0
(II) 3x + 2x' + z = 99
gcd(1,|-2|,1) = 1 und 1 teilt 0.
gcd(3,2,1) = 1 und 1 teilt 99.
2x + 4x' = 99 gcd(2,4) = 2 und 2 teilt nicht 99
Feldzugriffe im Programm:
Notwendige Bedingungen, damit dasselbe Element referenziert wird:
Zugriff auf dasselbe Element kann nicht ausgeschlossen werden!
Gemeinsame Betrachtung der zwei Feldzugriffe durch Einsetzen von (I) in (II):
Zugriff auf dasselbe Element kann ausgeschlossen werden!
137Optimierungstechniken in modernen Compilern Grundlagen
Komplexeres Beispiel (1)
for i = 1 to 100 step 1 do x[i] = y[i] + 10 (s1) for j = 1 to 100 step 1 do b[j] = a[j][N] (s2) for k = 1 to 100 step 1 do a[j+1][k] = b[j] + c[j][k] (s3) od y[i+j] = a[j+1][N] (s4) odod
Feldzugriffspaar(b[j],b[j])
(a[j][N],a[j+1][k])
Schleifennest(i,j)
(i,j)
Klassifizierungstarkes SIV Paar
d = (c' – c)/a = 1; Richtungen: j = {<}, i = {*}
d = (c' – c)/a = 0; Richtungen: j = {=}, i = {*} Zusammensetzen: {(<,=),(=,=),(>,=)}Flussabhängigkeit s2 -> s3 mit {(<,=),(=,=)}Antiabhängigkeit s3 -> s2 mit {(<,=)}
Test
starkes SIV Paar
weak-zero SIV N = k möglich, damit i = {*}, j = {*} mögliche Richtungen: i = *, j = <Zusammensetzen: {(<,<),(=,<),(>,<)}
138Optimierungstechniken in modernen Compilern Grundlagen
Komplexeres Beispiel (2)
for i = 1 to 100 step 1 do x[i] = y[i] + 10 (s1) for j = 1 to 100 step 1 do b[j] = a[j][N] (s2) for k = 1 to 100 step 1 do a[j+1][k] = b[j] + c[j][k] (s3) od y[i+j] = a[j+1][N] (s4) odod
(y[i],y[i+j])
(a[j+1][N],a[j+1][k])
(i)
(i,j)
1i + 0j = 1i' + 1j'Test für (*,*) durch: MIN1(*) = -99, MIN2(*) = -100 MAX1(*) = 99, MAX2(*) = -1Test für (=,*) durch: MIN1(=) = 0, MIN2(*) = -100 MAX1(=) = 0, MAX2(*) = -1; ...
d = 0 Richtungen: i = {*}, j = {=}
Feldzugriffspaar SchleifennestKlassifizierung
Teststarkes SIV Paar
weak-zero SIV N = k möglich, damit i = {*}, j = {*} mögliche Richtungen: i = {*}, j = {=}Zusammensetzen: {(<,=),(=,=),(>,=)}
d = 0 Richtungen: i = {*}, j = {=}