Grundlagen der Grundlagen der Übersetzung und Übersetzung und Optimierung von Optimierung von ProgrammiersprachenProgrammiersprachen

Seminar: Techniken der Code-Optimierung für

moderne Rechnerarchitekturen

Betreuer: Martin Schulz Referent: Markus Ibba

ÜbersichtÜbersicht

• Grundlagen der Übersetzung eines Grundlagen der Übersetzung eines ProgrammesProgrammes

• Konzepte zur OptimierungKonzepte zur Optimierung

• AusblickAusblick

Grundlagen der Grundlagen der Übersetzung eines Übersetzung eines ProgrammesProgrammes• Übersicht eines ÜbersetzungsvorgangesÜbersicht eines Übersetzungsvorganges

• Analyse des QuellprogrammsAnalyse des Quellprogramms– Lexikalische AnalyseLexikalische Analyse

– SyntaxanalyseSyntaxanalyse

– Semantische AnalyseSemantische Analyse

• FehlerbehandlungFehlerbehandlung

Übersicht eines Übersicht eines ÜbersetzungsvorgangesÜbersetzungsvorganges

Q uellprogramm (Zeichenfolge)

LexikalischeAnalyse

Syntax-Analyse

SemantischeAnalyse

Symbolfolge

Zw ischencode

Zw ischencode

Code-Erzeugung

Ausführbarer P rogrammcode

Symboltabelle Schnittstelle zumBetriebssystem

Analyse des Analyse des QuellprogrammsQuellprogramms

• Lexikalische Analyse (Scanner)Lexikalische Analyse (Scanner)(=Lineare Analyse)(=Lineare Analyse)

– Lesen des ZeichenstromesLesen des Zeichenstromes

– Aufteilung in Symbole (tokens)Aufteilung in Symbole (tokens)

– Aufbau der SymboltabelleAufbau der Symboltabelle

Lexikalische Analyse Lexikalische Analyse (Scanner)(Scanner)

• Aufbau der SymboltabelleAufbau der Symboltabelle

position = initial + rate * 100position = initial + rate * 100

0

LexemPtr Symbol

100 EO S

Analyse des Analyse des QuellprogrammsQuellprogramms

• Syntaxanalyse (Parser)Syntaxanalyse (Parser)(= hierarchische Analyse)(= hierarchische Analyse)

– Beschreibung der Syntax der Beschreibung der Syntax der ProgrammierspracheProgrammiersprache(kontextfreie Grammatiken, BNF)(kontextfreie Grammatiken, BNF)

– Zusammenfassen der Symbole zu Zusammenfassen der Symbole zu grammatikalischen Sätzengrammatikalischen Sätzen

Syntaxanalyse (Parser)Syntaxanalyse (Parser)

• Der Parse-BaumDer Parse-Baum

position = initial + rate * 100position = initial + rate * 100

Zuw eisung

Bezeichner Ausdruck

Ausdruck

AusdruckAusdruck

Ausdruck

position

=

+

*Bezeichner

initial

Bezeichner

rate

Zahl

100

Analyse des Analyse des QuellprogrammsQuellprogramms

• Semantische AnalyseSemantische Analyse– Konsistenz zwischen Deklaration und Konsistenz zwischen Deklaration und

Definition (Methoden, Variablen)Definition (Methoden, Variablen)

– Statische ÜberprüfungenStatische Überprüfungen• TypüberprüfungTypüberprüfung

• Überprüfung des KontrollflussesÜberprüfung des Kontrollflusses

• Überprüfung auf EindeutigkeitÜberprüfung auf Eindeutigkeit

FehlerbehandlungFehlerbehandlung

• Recovery-StrategienRecovery-Strategien– Panische RecoveryPanische Recovery

– Konstrukt-orientierte RecoveryKonstrukt-orientierte Recovery

– FehlerproduktionFehlerproduktion

– Globale KorrekturGlobale Korrektur

Konzepte zur OptimierungKonzepte zur Optimierung

-> Ziel: Laufzeit und/oder Größe eines -> Ziel: Laufzeit und/oder Größe eines Programmes reduzierenProgrammes reduzieren

• Übersicht eines Übersetzungsvorganges Übersicht eines Übersetzungsvorganges eines optimierenden Compilerseines optimierenden Compilers– AnalyseAnalyse

– CodetransformationCodetransformation

• OptimierungstechnikenOptimierungstechniken

Idee einer OptimierungIdee einer Optimierung

• Anwendungsprogrammierer braucht Anwendungsprogrammierer braucht kein umfangreiches Wissen über die kein umfangreiches Wissen über die Maschinenarchitektur auf der er Maschinenarchitektur auf der er programmiert.programmiert.

• Hardwarehersteller brauchen nur Hardwarehersteller brauchen nur noch Schnittstelle für den Compiler noch Schnittstelle für den Compiler selber zu designen.selber zu designen.

Übersicht eines Übersicht eines ÜbersetzungsvorgangesÜbersetzungsvorganges

Lexikalische Analyse

Syntaxanalyse

Kontrollflußanalyse

Datenfluß- undAbhängigkeitsanalyse

Codetransform ation

Codeerzeugung

Q uellprogram m

Sym bole

‘Front-end’

Analyse

Sym boltabelle

CFG

Transform ation

Zw ischencode

‘Back-end’

SSA / PDG

‚‚Control dependence‘Control dependence‘

1:1: if (3 == a)if (3 == a)

2:2: b = 10; b = 10;

Abhängigkeit zwischen Ausdruck 1 Abhängigkeit zwischen Ausdruck 1 und 2.und 2.

-> Generierung des ‚Control Flow -> Generierung des ‚Control Flow Graph‘ (CFG).Graph‘ (CFG).

CFG - Control Flow GraphCFG - Control Flow Graph

Entry

Exit

c = a + bd = c * a

c > d ?

c = c + d d = a

a < b ?

a = a * 2

‚‚Data dependence‘Data dependence‘

a = c * 10;a = c * 10;

d = 2 * a + c;d = 2 * a + c;

‚‚flow flow dependence‘dependence‘

e = f * 4 + g;e = f * 4 + g;

g = 2 * h;g = 2 * h;

‚‚anti anti dependence‘dependence‘

a = b * c;a = b * c;

a = d + e;a = d + e;

‚‚output output dependence‘dependence‘

• Die Datenflußanalyse wird im 3. Vortrag behandelt

CodetransformationCodetransformation

-> Bestandteil jeder Optimierung-> Bestandteil jeder Optimierung

• Allgemeiner Ablauf einer Allgemeiner Ablauf einer TransformationTransformation

• Beispiel einer TransformationBeispiel einer Transformation

Allgemeiner Ablauf einer Allgemeiner Ablauf einer TransformationTransformation

• Programmstück finden, welches sich Programmstück finden, welches sich für die Optimierung eignetfür die Optimierung eignet

• Sicherstellen, daß die Sicherstellen, daß die Transformation die Semantik des Transformation die Semantik des Programmes nicht ändertProgrammes nicht ändert

• Programm transformierenProgramm transformieren

Beispiel einer Beispiel einer TransformationTransformation

Beispiel einer Beispiel einer TransformationTransformation

Beispiel einer Beispiel einer TransformationTransformation

• Fehler 1: ÜberlaufFehler 1: Überlauf

Eingabe: b[k] = max. Floatzahl - 1.0;Eingabe: b[k] = max. Floatzahl - 1.0;

a[1] = -2.0;a[1] = -2.0;Überlauf bei C = b[k] + 2.0;Überlauf bei C = b[k] + 2.0;

• Fehler 2: ErgebnisabweichungFehler 2: Ergebnisabweichung

Unterschiede im Ergebnis durch dieUnterschiede im Ergebnis durch dieVertauschung der AdditionsreihenfolgeVertauschung der Additionsreihenfolge

Beispiel einer Beispiel einer TransformationTransformation

• Fehler 3: ZugriffsfehlerFehler 3: Zugriffsfehler

Eingabe: k = m + 1;Eingabe: k = m + 1; n = 0; n = 0;

Referenz zu b[k] nicht definiert.Referenz zu b[k] nicht definiert.

Tritt im Original durch n = 0 nicht Tritt im Original durch n = 0 nicht auf.auf.

OptimierungstechnikenOptimierungstechniken

• Partial Evaluation (Early Optimizations)Partial Evaluation (Early Optimizations)

-> nur bei einigen Datenflußanalyse -> nur bei einigen Datenflußanalyse notwendignotwendig

• Redundancy EliminationRedundancy Elimination

-> Entfernung redundanter Codestücke-> Entfernung redundanter Codestücke

-> Daten- und Kontrollflußanalyse -> Daten- und Kontrollflußanalyse notwendignotwendig

Partial EvaluationPartial Evaluation

• Constant FoldingConstant Folding

• Algebraic Simplification Algebraic Simplification

• ReassociationReassociation

• Constant PropagationConstant Propagation

• Copy PropagationCopy Propagation

• Statement SubstitutionStatement Substitution

• Induction Variable EliminationInduction Variable Elimination

• Function CloningFunction Cloning

Constant FoldingConstant Folding

Konstante Ausdrücke werden zurKonstante Ausdrücke werden zurÜbersetzungszeit ausgerechnet.Übersetzungszeit ausgerechnet.

X = 3 * 2; X = 3 * 2;

-> X = 6;-> X = 6;

-> Es ist keine Datenflußanalyse -> Es ist keine Datenflußanalyse notwendignotwendig

Algebraic SimplificationAlgebraic Simplification

Vereinfachung algebraischer AusdrückeVereinfachung algebraischer Ausdrücke

X = (Y + 1) / N;X = (Y + 1) / N;

wobei N = 1;wobei N = 1;

zu X = (Y + 1);zu X = (Y + 1);

-> Keine Datenflußanalyse notwendig-> Keine Datenflußanalyse notwendig

ReassociationReassociation

Umgruppierung von Additionen und Umgruppierung von Additionen und Multiplikationen in einem AusdruckMultiplikationen in einem Ausdruck

Kann die Anzahl der ‚Common Kann die Anzahl der ‚Common Subexpressions‘ vergrößern.Subexpressions‘ vergrößern.

Keine Datenflußanalyse notwendigKeine Datenflußanalyse notwendig

Constant PropagationConstant Propagation

Konstanten im Programm werden Konstanten im Programm werden durchdurch

ihren eigentlichen Wert ersetzt.ihren eigentlichen Wert ersetzt.

Hierzu wird das Ergebnis derHierzu wird das Ergebnis derDatenflußanalyse benötigt.Datenflußanalyse benötigt.

Copy PropagationCopy Propagation

Eliminiert redundante Kopien einerEliminiert redundante Kopien einerVariable.Variable.

-> Benötigt die Ergebnisse der -> Benötigt die Ergebnisse der Datenflußanalyse.Datenflußanalyse.

-> Es wird eine Tabelle verwendet, um -> Es wird eine Tabelle verwendet, um die einzelnen Instruktionen (copy die einzelnen Instruktionen (copy instructions) zu speichern.instructions) zu speichern.

Copy Propagation - ACPCopy Propagation - ACP

Table of available copy instructions.Table of available copy instructions.

Position Code Before ACP Code AfterNULL

1 b <- a b <- a{<b,a>}

2 c <- b + 1 c <- a + 1{<b,a>}

3 d <- b d <- a{<b,a>,<d,a>}

4 b <- d + c b <- a + c{<d,a>}

5 b <- d b <- a{<d,a>,<b,a>}

Statement SubstitutionStatement Substitution(Forward Substitution)(Forward Substitution)

Ersetzung einer Variable durch ihreErsetzung einer Variable durch ihreDefinition.Definition.

-> Allgemeine Form von ‚Copy -> Allgemeine Form von ‚Copy Propagation‘Propagation‘

-> Kann die Analyse von Ausdrücken -> Kann die Analyse von Ausdrücken innerhalb einer Schleife innerhalb einer Schleife vereinfachenvereinfachen

Induction Variable Induction Variable EliminationElimination

-> Entfernen der Index-Variable-> Entfernen der Index-Variable

- Folgt meist auf ‚Strength Reduction - Folgt meist auf ‚Strength Reduction of Induction Variable Expressions‘of Induction Variable Expressions‘

Function CloningFunction Cloning

Konstante Argumente einer FunktionKonstante Argumente einer Funktionwerden in einer Kopie durch ihren Wertwerden in einer Kopie durch ihren Wertersetzt.ersetzt.

-> Constant Propagation-> Constant Propagation

Dies erhöht zwar die Codegröße, dieDies erhöht zwar die Codegröße, diekopierten Funktionen können aber zum kopierten Funktionen können aber zum

TeilTeilwesentlich schneller ausgeführt werden.wesentlich schneller ausgeführt werden.

Function Cloning - BeispielFunction Cloning - Beispiel

Redundancy EliminationRedundancy Elimination

• Loop-invariant Code MotionLoop-invariant Code Motion

• Unreachable Code EliminationUnreachable Code Elimination

• Useless Code EliminationUseless Code Elimination

• Dead Variable EliminationDead Variable Elimination

• Common-Subexpression EliminationCommon-Subexpression Elimination

Loop-invariant Code Loop-invariant Code MotionMotion

Ausdrücke, welche ihren Wert in Ausdrücke, welche ihren Wert in keinerkeiner

Iteration ändern, werden außerhalb Iteration ändern, werden außerhalb derderSchleife gestellt.Schleife gestellt.

-> Datenflußanalyse notwendig-> Datenflußanalyse notwendig

Unreachable Code Unreachable Code EliminationElimination

Ein Codestück wird unerreichbar Ein Codestück wird unerreichbar durch:durch:– Bedingungen,welche immer true oder Bedingungen,welche immer true oder

immer false sindimmer false sind

– Schleifen, welche nie durchlaufen Schleifen, welche nie durchlaufen werdenwerden

-> Datenflußanalyse notwendig-> Datenflußanalyse notwendig

Useless Code EliminationUseless Code Elimination

‚‚Unnütze‘ Codestücke werden zum Unnütze‘ Codestücke werden zum TeilTeil

durch andere Optimierungendurch andere Optimierungen(z.B.: Unreachable Code Elimination)(z.B.: Unreachable Code Elimination)verursacht.verursacht.

-> Datenflußanalyse notwendig-> Datenflußanalyse notwendig

Dead Variable EliminationDead Variable Elimination

Nicht benutzte Variablen werden entfernt.Nicht benutzte Variablen werden entfernt.

Folgt meist auf die Optimierungen:Folgt meist auf die Optimierungen:– Unreachable Code EliminationUnreachable Code Elimination

– Useless Code EliminationUseless Code Elimination

Durch die Datenflußanalyse kannDurch die Datenflußanalyse kannfestgestellt werden, ob die Variable nochfestgestellt werden, ob die Variable nochbenutzt wird.benutzt wird.

Common-Subexpression Common-Subexpression Elimination (CSE)Elimination (CSE)

-> Identische Ausdrücke (Berechnungen) -> Identische Ausdrücke (Berechnungen) können gespeichert werden, damit der können gespeichert werden, damit der entsprechende Wert nicht neu berechnet entsprechende Wert nicht neu berechnet werden muß.werden muß.

-> Datenflußanalyse notwendig-> Datenflußanalyse notwendig

Common-Subexpression Common-Subexpression Elimination (CSE) - Elimination (CSE) - BeispielBeispiel

Entry

b < - a + 2c < - 4 * b b < c ?

b < - 1

d < - a + 2

Exit

Y

N

B1

B2

B3

Entry

t1 < - a + 2b < - t1c < - 4 * b b < c ?

b < - 1

d < - t1

Exit

B1

B3

B2Y

N

AusblickAusblick

• Weitere OptimierungenWeitere Optimierungen– Function InliningFunction Inlining

– Schleifen-Optimierungen (Vortrag 4)Schleifen-Optimierungen (Vortrag 4)

• Laufzeitsysteme (Vortrag 8)Laufzeitsysteme (Vortrag 8)