Code-Optimierung Philipp Bergener Seminar „Übersetzung künstlicher Sprachen“

Code-OptimierungPhilipp BergenerSeminar „Übersetzung künstlicher Sprachen“

2

Agenda

Einführung

Grundlagen

Datenflussanalyse

Methoden zur Code-Optimierung

Zusammenfassung

3

Ziele und Anforderungen

Verbesserung des Codes, der bei direkter, „naiver“ Übersetzung entsteht

OptimierungsmöglichkeitenVerbesserung der Ausführgeschwindigkeit

Verringerung des Speicherbedarfs zur Laufzeit

Verkleinerung des erzeugten Codes

AnforderungenSemantik des Programms muss erhalten bleiben

Aufwand für Optimierung muss sich lohnen

4

Systematisierung

Nach Zeitpunkt für Code-Optimierung:• Nach Zwischen-Codeerzeugung: Eher allgemeine Methoden• Nach Maschinen-Codeerzeugung: Eher maschinenspezifisch

Globale vs. lokale Optimierung• Lokal: Nur Ausschnitt (Basisblock) wird betrachtet• Global: Mehrere Basisblöcke werden betrachtet

5

Agenda

Einführung

Grundlagen

Datenflussanalyse

Methoden zur Code-Optimierung

Zusammenfassung

6

Drei-Adress-Code

Zur Darstellung des Zwischencodes

Maximal 3 Adressen pro Befehl

Typen von Befehlen• Zuweisung: x = y op z

op: arithmetisch (+,-,*,/) oder logisch (AND, OR)• Kopieranweisungen: x = y• Unbedingte Sprünge: goto L (L Sprungmarke)• Bedingte Sprünge: if x goto L bzw. ifFalse x goto L

oder if x relop y bzw. ifFalse x relop y (relop: <, ==, >, etc.)• Indizierte Kopieranweisungen: x = a[i] bzw. a[i] = x

a[i]: Speicherstelle i Einheiten hinter a

7

Basisblöcke und FlussgraphenBasisblöcke

Strukturieren den CodeEigenschaften eines Basisblocks:

Kann nur durch die erste Anweisung betreten werdenWird ohne Sprünge durchlaufen. Sprünge nur in der letzten Anweisung

Ein Basisblock beginntBei der ersten CodezeileBei Zeilen, die Ziel von Sprüngen sindBei Zeilen, die auf Sprünge folgen

Flussgraphen stellen Kontrollfluss grafisch darBasisblöcke sind Knoten2 zusätzliche Knoten Eingang und Ausgang

8

Beispiel: Binäre Suchepublic Ingeger

binsearch(Integer k) {Integer m,l,r;//Anfangl = 0;r = N-1;

do {m = (l+r)/2;if(k < a[m])

r = m-1;else

l = m+1;while((k != a[m])||(l<r));//Ende...

end

Eingang

l = 0r = N-1

t1 = l+rm = t1/2t2 = 8*mt3 = a[t2]ifFalse k<t3 goto B4

Ausgang

l = m+1r = m-1goto B5

if l<r goto B2

t4 = 8*mt5 = a[t4]ifFalse k==t5 goto B2

B1

B2

B3 B4

B5

B6

9

Agenda

Einführung

Grundlagen

Datenflussanalyse

Methoden zur Code-Optimierung

Zusammenfassung

10

Datenflussanalyse

Viele Optimierungsansätze brauchen Informationen über Datenfluss im Programm

Programm ist eine Folge von Zuständen

Zustand: unter anderem aktuelle Werte der Variablen

Anweisungen sind Zustandsübergänge

Durch Sprünge sind Zustände nicht immer eindeutig

Nur der für ein Problem relevante Teil des Zustandes betrachtet

Es wird nicht unterschieden auf welchem Pfad ein Programmpunkt erreicht wird

11

Bestandteile eines Datenflussproblems

Datenflussproblem ist 4-Tupel (D, V, ^, F)

Datenflussrichtung D {Vorwärts, Rückwärts}Gibt an ob Informationen mit oder gegen Informationsfluss fließen

Domäne V relevanter Teil des Zustandes

Konfluenzoperator ^ (z.B. )Zum Übergang zwischen Blöcken

Menge von Transferfunktionen F F: V V

Für ganze Basisblöcke

12

Verfügbare Definitionen

Fragestellung: Welche Definition für eine Variable ist an einem bestimmten Programmpunkt gültig

Datenflussrichtung: D = VorwärtsDomäne: Potenzmenge der Menge aller DefinitionenKonfluenzoperator: , also IN[B] = P Vorgänger von BOUT[P]Transferfunktion:• genB: Menge generierter Definitionen in Block B• killB: Menge gelöschter Definitionen in Block B• Dann OUT[B] = genB (IN[B] - killB)

13

Verfügbare Definitionen

l = 0 (d1)r = N-1 (d2)

l = m+1 (d8)

r = m-1 (d7)goto B5

B1

B3

B4

gen[B1]={d1, d2}kill[B1]={d7,d8}

gen[B3]={d7}kill[B3]={d2}

gen[B4]={d8}kill[B4]={d1}

...

...

...B2

14

Aktive Variablen

Eine Variable x ist aktiv an Punkt p, wenn der Wert von x in p entlang eines Pfades von p an benutzt kann und wird. Andernfalls ist sie passiv.

Datenflussrichtung: D = RückwärtsDomäne: Potenzmenge der Menge aller VariablenKonfluenzoperator: ,

also OUT[B] = P Nachfolger von BIN[P]Transferfunktion:• defB: Menge der Variablen, die in Block B definiert werden• useB: Menge der Variablen, die in B benutzt werden (bevor sie neu

definiert werden)• Dann: IN[B] = useB (OUT[B] - defB)

15

Verfügbare Ausdrücke

Ein Ausdruck der Form x op y ist an einem Punkt p verfügbar, wenn der Ausdruck auf jedem Pfad zu p berechnet wird und weder x noch y danach überschrieben werden

Datenflussrichtung: D = Vorwärts

Domäne: Potenzmenge der Menge aller Ausdrücke

Konfluenzoperator: also IN[B] = P Vorgänger von BOUT[P]

Transferfunktion:• e_genB: Menge aller Ausdrücke, die in B (neu) berechnet werden

• e_killB: Menge aller Ausdrücke, die in B ungültig werden

• Dann: OUT[B] = e_genB (IN[B] - e_killB)

16

Halbverband

Ein Datenflussproblem bildet einen HalbverbandEigenschaften eines Halbverbands:

x ^ x = xx ^ y = y ^ xx ^ (y ^ z) = (x ^ y) ^ z x, y, z V

Halbverbände haben oberstes Element T mitT ^ x = x x VFür : T = Für : T = Basismenge der Potenzmenge

17

Algorithmus zum Lösen von Datenflussproblemen

Zusätzlich noch Startmenge v (meist )

OUT[Eingang]=vEingang;

for(jeden Block B außer Eingang) OUT[B] = T;

while(min. ein OUT wird geändert)

for(jeden Block B außer Eingang) {

IN[B]=^P Vorgänger von pOUT[P];

OUT[B]=fB(IN[B]);

}

Für D = RückwärtsIN und OUT vertauschen

Ausgang statt Eingang

18

Agenda

Einführung

Grundlagen

Datenflussanalyse

Methoden zur Code-Optimierung

Zusammenfassung

19

Eliminierung gemeinsamer Teilausdrücke

Gemeinsamer Teilausdruck: Vorkommen von Ausdruck E der schon einmal berechnet wurde und sich nicht mehr geändert hat.

Ziel: wiederholte Berechnungen des gleichen Ausdrucks vermeiden

Ermitteln mit Verfügbaren Ausdrücken

Eliminierung• Teilausdruck in Hilfsvariable speichern• Dann statt Teilausdruck Hilfsvariable verwenden

20

Eliminierung gemeinsamer Teilausdrücke

t1 = l+rm = t1/2t2 = 8*mt3 = a[t2]ifFalse k<t3 goto B4

t4 = 8*mt5 = a[t4]ifFalse k==t5 goto B2

t1 = l+rm = t1/2h1 = 8*mt2 = h1t3 = a[t2]ifFalse k<t3 goto B4

t4 = h1t5 = a[t4]ifFalse k==t5 goto B2

......

B2B2

B5 B5

l = m+1r = m-1goto B5

B3 B4

l = m+1r = m-1goto B5

B3 B4

... ...

21

Weitergabe von Kopien

Durch andere Optimierungsverfahren entstehen Kopien der Form x = y

Ziel: y anstelle von x benutzen

Dadurch kann die Kopieranweisung überflüssig werden

Lösung mit Verfügbaren Definitionen:• Ersetzung ist in p möglich,

wenn x und y noch gleichen Wert besitzen• Dazu müssen sowohl die Definition x = y

als auch die Definition für y, die in x = y galt, gültig in p sein• Außerdem dürfen keine anderen Definitionen x und y p erreichen

22

Weitergabe von Kopien

t1 = l+rm = t1/2h1 = 8*mt2 = h1t3 = a[t2]ifFalse k<t3 goto B4

t4 = h1t5 = a[t4]ifFalse k==t5 goto B2

t1 = l+rm = t1/2h1 = 8*mt2 = h1t3 = a[h1]ifFalse k<t3 goto B4

t4 = h1t5 = a[h1]ifFalse k==t5 goto B2

... ...B2 B2

B5B5

l = m+1r = m-1goto B5

B3 B4l = m+1r = m-1

goto B5

B3 B4

......

23

Eliminierung von totem Code

Toter Code:• Anweisungen, die nie erreicht werden• Zuweisungen, die nie benutzt werden

Entsteht durch andere Optimierungen oder (selten) durch Programmierfehler

Identifizierung über aktive VariablenBeispiel:

x = true... //Hier keine Zuweisungen an xif x goto L1a = b + c //Toter Code

L1: b = 2 * c

24

Optimierung von Schleifen

Programme verbringen einen Großteil ihrer Zeit in Schleifen

Optimierung von Schleifen daher besonders wichtig

2 Ansätze zur Optimierung von SchleifenExport schleifeninvarianter Variablen

Eliminierung von Induktionsvariablen

25

Optimierung von Schleifen

Identifikation von Schleifen

Dominator: Knoten d dominiert Knoten n (d dom n), wenn jeder Pfad im Flussgraph von Eingang zu n über d führt

Rückwärtskante: Kante n → d mit d dom n

Natürliche Schleife einer Rückwärtskante n → d:Alle Knoten von denen n erreicht werden kann ohne durch d zu laufen

26

Optimierung von Schleifen

Eingang

l = 0r = N-1

t1 = l+rm = t1/2t2 = 8*mt3 = a[t2]ifFalse k<t3 goto B4

Ausgang

l = m+1r = m-1goto B5

if l<r goto B2

t4 = 8*mt5 = a[t4]ifFalse k==t5 goto B2

B1

B2

B3 B4

B5

B6

27

Optimierung von Schleifen

Eingang

l = 0r = N-1

t1 = l+rm = t1/2t2 = 8*mt3 = a[t2]ifFalse k<t3 goto B4

Ausgang

l = m+1r = m-1goto B5

if l<r goto B2

t4 = 8*mt5 = a[t4]ifFalse k==t5 goto B2

B1

B2

B3 B4

B5

B6

28

Optimierung von Schleifen

Eingang

l = 0r = N-1

t1 = l+rm = t1/2t2 = 8*mt3 = a[t2]ifFalse k<t3 goto B4

Ausgang

l = m+1r = m-1goto B5

if l<r goto B2

t4 = 8*mt5 = a[t4]ifFalse k==t5 goto B2

B1

B2

B3 B4

B5

B6

29

Optimierung von Schleifen

Export schleifeninvarianter Variablen:Variable ist schleifeninvariant, wenn in Schleife keine Zuweisung an sie erfolgtEin Ausdruck ist schleifeninvariant, wenn er nur aus schleifeninvarianten Variablen bestehtDiese sollen aus der Schleife herausgezogen werden

while (i < max) dox := 3*y //3*y ist

schleifeninvariantz := x+jj := i*2i := i+1

end

30

Optimierung von Schleifen

Eliminierung von Induktionsvariablen

Induktionsvariable, die sich bei jedem Schleifendurchlauf um den gleichen, konstanten Wert ändert

Diese sollen (bis auf eine) eliminiert werden

x := 3*y x := 3*y

while (i < max) do j := 2*i

z := x+j while (j < 2*max) do

j := i*2 z := x+j

i := i+1 j := j+2

end end

i := max

31

Konstantenfaltung

Konstanten verbessern die Lesbarkeit von Programmen

Auf Ebenen des Zwischencodes nicht nötig

Daher: Variablen, die an einer Stelle immer den gleichen Wert haben durch diesen ersetzen

Ausdrücke, die nur aus Konstanten bestehen, können dann ebenfalls berechnet werden

Ermittlung von Konstanten auch mit Datenflussanalyse möglich

32

Konstantenfaltung

Beispiel:N = 10 //Konstante...x = 2 //Wert in nächster Anweisung immer gleichy = N*x //N und x können ersetzt werden

N = 10...x = 2y = 10*2 //Ausdruck kann jetzt berechnet werden

33

Algebraische Umformungen

Ersetzen von langsameren Befehlen durch schnellere

Ausnutzen von mathematischen Gesetzen

Beispiele• x*2n → x shiftl n• x + 0 oder x * 1 → x• x2 → x*x• 2*x → x+x• x/4 → x * 0,25

34

Agenda

Einführung

Grundlagen

Datenflussanalyse

Methoden zur Code-Optimierung

Zusammenfassung

35

Zusammenfassung

Direkt übersetzter Code kann noch weiter optimiert werden

Es gibt verschiedene Ansätze zur Optimierung

Datenflussanalyse bildet eine wichtige Grundlage für viele dieser Ansätze

Es gibt weitere Optimierungsmethoden, z.B.• für Maschinen-Code• für OO-Sprachen

36

Fragen

Vielen Dank für die

Aufmerksamkeit

Fragen?