Code-Erzeugung

Seminar „Übersetzung von künstlichen Sprachen“ SS09

Code-ErzeugungArne Kostulski

( [email protected] )

2


1. Abgrenzung, Motivation, Einordnung2. Grundlagen3. Code-Repräsentation4. Code-Erzeugung5. Fazit und weiterführende Themen

3


1. Abgrenzung, Motivation, Einordnung2. Grundlagen3. Code-Repräsentation4. Code-Erzeugung5. Fazit und weiterführende Themen

4


Abgrenzung und Motivation

Effizienz durch Automatisierung

5


Einordnung innerhalb des Kompilierungsprozesses

6



7



1.

8



1.2.

3.

9


1. Abgrenzung, Motivation, Einordnung2. Grundlagen * Zielgrößen * Entwurfsfaktoren * Kernaufgaben * Referenzmaschine3. Code-Repräsentation4. Code-Erzeugung 5. Fazit und weiterführende Themen

10


Zielgrößen

Semantische Korrektheit

LaufzeiteffizienzVirtuelle SpeichernutzungPhysische Speichernutzung

Kompilierzeit

Heuristiken für komplexe Optimierungsprobleme

konträr

11


Speicherhierarchie

12


Speicherhierarchie

13


Registerverwendung

AufgabenRegisterzuteilungRegisterauswahl

ZielTotale Lade- und Speicherzeiten minimieren

Architekturparameter

Registeranzahl

Kernaufgabe

Registerverwendung

14


Instruktionsselektion

AufgabeAuswahl von Instruktionskombination

ZielMinimiere totale Instruktionskosten!

BeispielZwischencode: a := a + 1

Zielcode: LD R, aADD R, R, #1ST a, R

121

111

∑ 4 ∑ 3


Befehlssatz

Kernaufgabe

Instruktionsselektion

LD R, aINC aST a, R

15



Anzahl der Prozessorkerne

Kernaufgabe

Instruktionsanordnung

Instruktionsanordnung

AufgabeBefehlsfolgen reorganisieren

ZieleCode-VereinfachungBessere RegisterausnutzungParallelisierung unabhängiger Befehle

16


Instruction Set Architecture (ISA)Complex Instruction Set Computer (CISC)Reduced Set Computer (RISC)Very Long Instruction Word (VLIW)


RegisteranzahlBefehlssatzAnzahl der Prozessorkerne

Kernaufgaben

RegisterzuteilungInstruktionsselektionInstruktionsanordnung

Kernaufgaben und ISA

17


Abstrakte Zielmaschine - Zielsprache

Notation für Operationen:

Bsp.: MUL R3, R1, R2

OP <destination>, <source>, <source>, mit

<destination> = Ri

| { Kleinbuchstabe }<source> = Ri

| { Kleinbuchstabe } | „#“ { Ziffer }

OP = ADD | SUB | MUL | DIV

Ausnahmen:LD R, x ST x, R

18


Abstrakte Zielmaschine

DefinitionZielspracheUniversalregister: R1, …,Rn

Administrative Register separatAdressierungen

19


1. Abgrenzung, Motivation, Einordnung 2. Grundlagen3. Code-Repräsentation * Basisblöcke * Flussgraphen * DAG4. Code-Erzeugung 5. Fazit und weiterführende Themen

20


Code-Repräsentation: Basisblöcke

Strukturierung des ZwischencodesKontrollflussVariablenverwendung

BasisblockMinimale Sequenz von InstruktionenBlockanfänge definiert durch:

a) Die erste Instruktion des Zwischencodes.b) Jede direkte Nachfolge-Instruktion eines Sprunges.c) Jede Zielinstruktion eines (bedingen oder unbedingten) Sprungbefehls.

21


Code-Repräsentation: BasisblöckeBeispiel

a) Die erste Instruktion des Zwischencodes.

22


// B1: Fall a)

// B2: Fall c)

// B3: Fall b)

// B4: Fall b)

// B5: Fall b)

// B6: Fall b)


a) Die erste Instruktion des Zwischencodes.

23


// B1: Fall a)

// B2: Fall c)

// B3: Fall b)

// B4: Fall b)

// B5: Fall b)

// B6: Fall b)


b) Jede direkte Nachfolge-Instruktion eines Sprunges.

24


// B1: Fall a)

// B2: Fall c)

// B3: Fall b)

// B4: Fall b)

// B5: Fall b)

// B6: Fall b)


b) Jede direkte Nachfolge-Instruktion eines Sprunges.

25


// B1: Fall a)

// B2: Fall c)

// B3: Fall b)

// B4: Fall b)

// B5: Fall b)

// B6: Fall b)


c) Jede Zielinstruktion eines (bedingen oder unbedingten) Sprungbefehls.

26


// B1: Fall a)

// B2: Fall c)

// B3: Fall b)

// B4: Fall b)

// B5: Fall b)

// B6: Fall b)


c) Jede Zielinstruktion eines (bedingen oder unbedingten) Sprungbefehls.

27


Code-Repräsentation: BasisblöckeErgebnis

// B1: Fall a)

// B2: Fall c)

// B3: Fall b)

// B4: Fall b)

// B5: Fall b)

// B6: Fall b)

28


Code-Repräsentation: Flussgraphen

Flussgraph gerichteter, zyklischer Graph G=(V,E) mit Knotenmenge V: Menge aller Basisblöcke (Block als Blackbox)Kantenmenge E: e(Bi, Bj) Є E genau dann, wenn:

a) Bj folgt direkt auf Bi in der Programmfolge und Bi ohne unbedingten Sprung.

b) Bj ist Ziel eines Sprungbefehls.

29



B1

B2

B3

B4

B5

B6

Beispiel:a) Bj folgt direkt auf Bi in der Programmfolge und Bi enthält keinen

unbedingten Sprung.

30



B1

B2

B3

B4

B5

B6

Beispiel:b) Bj ist Ziel eines Sprungbefehls.

31


Code-Repräsentation: Blockoptimierung mit DAG

Innendarstellung eines Blocksgerichteter, azyklischer Graph (DAG)

ZieleRegisterausnutzung verbessernCode-VereinfachungToten Code eliminieren

Elemente

Initiale Variable

Operation Label

32



DAG-Konstruktion

1. a := b * c2. c := a + d3. b := a * b

Erzeuge

- Blatt / Blätter- Operationssymbol- Kanten- Label

33



DAG-Konstruktion

1. a := b * c2. c := a + d3. b := a * b

Erzeuge

- Blatt / Blätter - Operationssymbol- Kanten- Label

34



DAG-Konstruktion

1. a := b * c2. c := a + d3. b := a * b

Erzeuge

- Blatt / Blätter - Operationssymbol- Kanten- Label

35



Code-Vereinfachung

, d1. a := b * c2. c := a + d3. b := a * b4. d := a + d

1. a := b * c2. c := a + d3. b := a * b4. d := c

Erzeuge

- Blätter- Operationssymbol- Kanten- Label

36



Lebendigkeit von Variablen

Eine Variable x ist lebendig in Anweisung Ai (1 ≤ i < n), wenn:x in Anweisung A1 ein Wert zugewiesen wird,x in Anweisung An als Operand benutzt bzw. gelesen wird,x zwischen A1 und An kein Wert zugewiesen wird.

x hat bei Ai die nächste Verwendung in An, wenn An der erste Lesezugriff auf x nach A1 ist.Eine am Basisblockende lebendige Variable heißt live on exit.

37



Toter CodeInstruktionen mit nicht benötigten Ergebnissen

Beispielc, d nicht live on exit

XX

X

X

38


1. Abgrenzung, Motivation, Einordnung 2. Grundlagen3. Code-Repräsentation4. Code-Erzeugung * Elementare Code-Erzeugung * Globale Registerzuteilung * Optimale Code-Erzeugung * Peephole-Optimierung5. Fazit und weiterführende Themen

39


Elementare Code-Erzeugung

Register-DeskriptorZuordnungen: Register Variablennamen

Adressen-DeskriptorZuordnungen: Variablen Speicheradresse

Annahmen für ZielmaschineLD und ST explizitkeine globalen Register

Variablen mit nächster Verwendung am Blockanfang zu ladenlive on exit-Variablen zu speichern

40



Hilfsfunktion getReggetReg(B) mit Drei-Adress-Befehl BFür a := b OP c

Lade nötige VariablenFühre den Befehl OP Ra, Rb, Rc aus.

Fallunterscheidungen für Code-Erzeugung1. LD R, a2. ST a, R3. a := b OP c4. a := b

41



Register-Deskriptor Adress-Deskriptor

¬live on exit live on exit

Zwischencode Zielcode Regel R1 R2 R3 a b c d

Beispiel: a := b * c

42


Elementare Code-ErzeugungRegister-

Deskriptor

Adress-Deskriptor

¬lebendig

Blockende

lebendig

Blockende


1. a := b * c b c d

2. LD R1, b 1 b b,R1 c d

3. LD R2, c 1 b c b,R1 c, R2 d

4.a := b OP c (mit den Registern Ra, Rb, Rc)4.1 Falls b bzw. c nicht im Register, führe LD Rb, b bzw. LD Rc, c aus.[…]

5.LD R, a1.1 Der Inhalt von R im Register-Deskriptor ist durch a zu ersetzen1.2 Füge im Adress-Deskriptor R zu a hinzu.

43


Elementare Code-ErzeugungRegister-

Deskriptor

Adress-Deskriptor

¬lebendig

Blockende

lebendig

Blockende


1. a := b * c b c d

2. LD R1, b 1 b b,R1 c d

3. LD R2, c 1 b c b,R1 c, R2 d

4. MUL R2, R1, R2 3 b c, a R2 b,R1 c, R2 d

4. a := b OP c (mit den Registern Ra, Rb, Rc)4.1 Falls b bzw. c nicht im Register, führe LD Rb, b bzw. LD Rc, c aus.4.2 Der Inhalt von Ra im Register-Deskriptor ist durch a zu ersetzen.4.3 Der Inhalt von a im Adress-Deskriptor ist durch Ra zu ersetzen.4.4 Entferne Ra von allen anderen Variablen im Adress-Deskriptor.

44



Register-

Deskriptor

Adress-Deskriptor

¬lebendig

Blockende

lebendig

Blockende


4. MUL R2, R1, R2 3 b a R2 b,R1 c, R2 d

5. EXIT

6. ST a, R2 c a a, R2 b, R1 c d

2.ST a, RDer Inhalt von a im Adress-Deskriptor ist durch R zu ersetzen.

45


Globale Register

ProblemViele Hauptspeicherzugriffe

ST a, R1

LD R1, a

LösungST a, R1

LD R1, a

ProblemST a, R1

if … then goto …LD R1, a

46


Globale Register

BeispielBetrachte Variable bLesezugriff

LD R, a

47


Globale Register

BeispielBetrachte Variable bLesezugriff

LD R, aSchreibzugriff

live on exit

LösungRegisterinhalte überdauern Basisblöcke

Registerzuteilung?Bewertung:

48


Graphfärbung

ProblemRegister vollRegisterauswahl?

Lebensspanne für ideelle Register

Hier: Graph 2-fach färbbarKollisionen unvermeidbar Zwischenspeicherung

49


InstruktionsselektionIdee: Alternative Instruktionskombinationen

+Ma

C1Ri

=

50


Optimale Code-Erzeugung

ZielCode mit minimaler RegisteranzahlBerücksichtigt

RegisterzuteilungRegisterauswahlInstruktionsanordnung

BasisDirected Acyclic Graph (DAG)

Procedere:1. Annotiere Ershov-Nummern an Graph-Knoten2. Führe Generierungsalgorithmus aus

51



Ershov-Nummer für Knoten v:

val(v) =

a := b * cc := a * bd := a + de := c + d

52




val(v) =

a := b * cc := a * bd := a + de := c + d

1 1

1

53




val(v) =

a := b * cc := a * bd := a + de := c + d

1 1

12

54




val(v) =

a := b * cc := a * bd := a + de := c + d

1 1

12

2 2

3

55


Optimale Code-Erzeugunggencode(v, b)1. if v hat Kindknoten vl, vr mit label(vl) = label(vr) then

1.1 k := label(vl)1.2 Rb+k := gencode(vr, b+1)1.3 Rb+k-1 := gencode(vl, b)1.4 print(name(v), Rb+k, Rb+k-1, Rb+k)

2. else if v hat Kindknoten vl, vr mit label(vl) < label(vr) then2.1 k := label(vr)2.2 Rb+k-1 := gencode(vr, b)2.3 m := label(vl)2.4 Rb+m-1 := gencode(vl, b)2.5 print(name(v), Rb+k-1, Rb+m-1, Rb+k-1)

3. else if v hat Kindknoten vl, vr mit label(vl) > label(vr) then3.1 k := label(vl)3.2 Rb+k-1 := gencode(vl, b)3.3 m := label(vr)3.4 Rb+m-1 := gencode(vr, b)3.5 print(name(v), Rb+k-1, Rb+k-1, Rb+m-1)

4. else // v ist Blattknoten4.1 print(„LD“, Rb, name(v))

gencode-Algorithmus

fRegel Code v b vl vr k R1 R2 R3

a) k := label(v1) v1 1 v2 v3 3

b) R3:= gencode(v1, 1) v1 1 v2 v3 3

1.1 k := label(v2) v1 1 v2 v3 2

1.2 R3 := gencode(v3, 2) v1 1 v2 v3 2

3.1 k := label(v4) v3 2 v4 v5 2

3.2 R3 := gencode(v4, 2) v3 2 v4 v5 2

1.1 k := label(v6) v4 2 v6 v7 1

1.2 R3 := gencode(v7, 3) v7 3 - - 1

4.1 print(„LD“, R3, c) v7 3 - - 1 c0

1.3 R2 := gencode(v6, 2) v6 2 - - 1 c0

4.1 print(„LD“, R2, b) v6 2 - - 1 b0 c0

1.4 print(„MUL“, R3, R2, R3) v4 2 v6 v7 1 b0 a

3.3 m := label(v5) // m := 1 v3 2 v4 v5 2 b0 a

3.4 R2 := gencode(v5, 2) v3 2 v4 v5 2 b0 a

4.1 print(„LD“, R2, d) v5 2 - - 1 d0 a

3.5 print(„ADD“, R3, R2, R3) v3 2 v4 v5 2 d0 d

1.3 R2 := gencode(v2, 1) v1 1 v2 v3 2 d0 d

2.1 k := label(v4) v2 1 v6 v4 2 d0 d

2.2 R2 := gencode(v4, 2) v2 1 v6 v4 2 d0 d

Beispiel

56


gencode


Regel Code v b vl vr k R1 R2 R3

LD R3, c

LD R2, b

1 1

12

2 2

3

57



MUL“, R3, R2, R3 1 1

12

2 2

3

58



1 1

12

2 2

3

1 1

12

2 2

3

59


…c := a * bd := a + de := c + da := b * cST a, R1

LD R1, ac := a * bd := a + de := c + d…

ProblemKomplexität

IdeeLokale Suche im “Gucklock”

BeispielViele HauptspeicherzugriffeST a, R1

LD R1, a

Peephole Optimization

60


1. Abgrenzung, Motivation, Einordnung 2. Grundlagen3. Code-Repräsentation * Basisblöcke * Flussgraphen4. Code-Erzeugung 5. Fazit und weiterführende Themen

61


Fazit

GelöstElementare CodeerzeugungErzeugung mit minimaler Registeranzahl

AnsätzeRegisterverwendungInstruktionsselektionInstruktionsanordnung

OffenErweiterte HeuristikenParallelisierungJust-In-Time-Compilation

62


Diskussion

63


Code-Repräsentation

DAG-KonstruktionFür jeden Drei-Adress-Befehl der Form a := b OP c eines Basisblocks B:

1. Suche nach Vorkommen von b und c in Blättern, Knoten und Labels des Graphs (dies entspricht einer vorigen Benutzung der Variablen). Erzeuge für nicht existierende Variablen neue Blätter mit ihrem Variablennamen und dem Index 0 als Kennzeichnung der Erstverwendung.

2. Erzeuge für OP einen Knoten mit dem Operationssymbol und setze b als linken, c als rechten Kindknoten für OP.

3. Füge a als Label an OP an.

BACKUP

64



Eintragung in die Deskriptoren1. LD R, a

1.1 Der Inhalt von R im Register-Deskriptor ist durch a zu ersetzen.1.2 Füge im Adress-Deskriptor R zu a hinzu.

2. ST a, RDer Inhalt von a im Adress-Deskriptor ist durch R zu ersetzen.

3. a := b OP c (mit den Registern Ra, Rb, Rc)3.1 Falls b bzw. c nicht im Register, führe LD Rb, b bzw. LD Rc, c aus.3.2 Der Inhalt von Ra im Register-Deskriptor ist durch a zu ersetzen.3.3 Der Inhalt von a im Adress-Deskriptor ist durch Ra zu ersetzen.3.4 Entferne Ra von allen anderen Variablen im Adress-Deskriptor.

4. a := b (mit den Registern Ra, Rb)4.1 Falls b nicht im Register, führe LD Rb, b aus (siehe 1.).4.2 Der Inhalt von Rb im Register-Deskriptor ist durch a zu ergänzen.4.3 Der Inhalt von a im Adress-Deskriptor ist durch Rb zu ersetzen.

BACKUP

65


Elementare Code-ErzeugungRegister-Deskriptor Adress-Deskriptor

¬lebendig

Blockende

lebendig Blockende


1. a := b * c b c d

2. LD R1, b 1 b b,R1 c d

3. LD R2, c 1 b c b,R1 c,R2 d

4. MUL R2, R1, R2 3 b a R2 b,R1 c,R2 d

5. c := a + d

6. LD R3, d 1 b a d R2 b,R1 c R3

7. ADD R3, R2, R3 3 b a c R2 b,R1 R3 R3

8. EXIT

9. ST c, R1 c a c,d R2 b c,R1 R3

10. ST d, R3 c a c,d R2 b c,R1 d,R3

BACKUP

66


Elementare Code-ErzeugungRegister-Deskriptor Adress-Deskriptor

¬lebendig

Blockende

lebendig Blockende



11. MUL R1, R2, R1 3 c a c,d R2 b,R1 R1 R3

12. EXIT

13. ST c, R1 c a c,d R2 b c,R1 R3


15. c d

BACKUP

67


BACKUP Optimale CodeerzeugungFunktionsaufruf:a) k := label(vroot)b) Rk := gencode(vroot, 1)Funktionsdeklaration:gencode(v, b)1. if v hat Kindknoten vl, vr mit label(vl) = label(vr) then1.1. k := label(vl)1.2. Rb+k := gencode(vr, b+1)1.3. Rb+k-1 := gencode(vl, b)1.4. print(name(v), Rb+k, Rb+k-1, Rb+k)2. else if v hat Kindknoten vl, vr mit label(vl) < label(vr) then2.1. k := label(vr)2.2. Rb+k-1 := gencode(vr, b)2.3. m := label(vl)2.4. Rb+m-1 := gencode(vl, b)2.5. print(name(v), Rb+k-1, Rb+m-1, Rb+k-1)3. else if v hat Kindknoten vl, vr mit label(vl) > label(vr) then3.1. k := label(vl)3.2. Rb+k-1 := gencode(vl, b)3.3. m := label(vr)3.4. Rb+m-1 := gencode(vr, b)3.5. print(name(v), Rb+k-1, Rb+k-1, Rb+m-1)4. else // v ist Blattknoten4.1. print(„LD“, Rb, name(v))

68


BACKUP Optimale CodeerzeugungRegel Code v b vl vr k R1 R2 R3

a) k := label(v1) v1 1 v2 v3 3

b) R3:= gencode(v1, 1) v1 1 v2 v3 3

1.1 k := label(v2) v1 1 v2 v3 2

1.2 R3 := gencode(v3, 2) v1 1 v2 v3 2

3.1 k := label(v4) v3 2 v4 v5 2

3.2 R3 := gencode(v4, 2) v3 2 v4 v5 2

1.1 k := label(v6) v4 2 v6 v7 1

1.2 R3 := gencode(v7, 3) v7 3 - - 1

4.1 print(„LD“, R3, c) v7 3 - - 1 c0

1.3 R2 := gencode(v6, 2) v6 2 - - 1 c0

4.1 print(„LD“, R2, b) v6 2 - - 1 b0 c0

1.4 print(„MUL“, R3, R2, R3) v4 2 v6 v7 1 b0 a

3.3 m := label(v5) // m := 1 v3 2 v4 v5 2 b0 a

3.4 R2 := gencode(v5, 2) v3 2 v4 v5 2 b0 a

4.1 print(„LD“, R2, d) v5 2 - - 1 d0 a

3.5 print(„ADD“, R3, R2, R3) v3 2 v4 v5 2 d0 d

1.3 R2 := gencode(v2, 1) v1 1 v2 v3 2 d0 d

2.1 k := label(v4) v2 1 v6 v4 2 d0 d

2.2 R2 := gencode(v4, 2) v2 1 v6 v4 2 d0 d

69


BACKUP Optimale Codeerzeugung

… … siehe Schritte 6-12 mit b=1 … … … … . … … …

2.3 m := label(v6) // m := 1 v2 1 v6 v4 2 b0 a d

2.4 R1 := gencode(v6, 1) v2 1 v6 v4 2 b0 a d

4.1 print(„LD“, R1, b) v6 1 - - 1 b0 a d

2.5 print(„MUL“, R2, R1, R2) v2 1 v6 v4 2 b0 c d

1.4 print(„ADD“, R3, R2, R3) v1 1 v2 v3 2 b0 c e

Date post:	23-Feb-2016
Category:	Documents
Upload:	aquila
View:	33 times
Download:	0 times

Code-Erzeugung

Documents