Optimierung in Übersetzern - Cheatsheet

Definition und Grundkonzepte der Datenflussanalyse

Definition:

Analyse der Flüsse von Datenwerten durch ein Programm; bestimmt, wie Daten beeinflusst werden (definiert, verwendet, etc.).

Details:

• Hauptziele: Erkennung von undefinierten Variablen, Toter Code, Reduzierung redundanter Berechnungen.
• Wichtige Konzepte:
  • Def-Use-Ketten: Paare von Programmstellen, wo eine Variable definiert und benutzt wird.
  • Cfg (Control Flow Graph): Darstellung der Kontrolle in einem Programm.
  • Lebensbereichsanalyse: Bestimmung der Lebensdauer von Variablen.
  • Abhängigkeiten: Abhängigkeitsanalysen wie Datenabhängigkeit und Kontrolleabhängigkeit.
  • Transferfunktionen: Definiert, wie Informationen durch Programmteile fließen.
  • Fixpunktiterationen: Methoden zur Berechnung von Datenflussinformationen über Schleifen hinweg.

Kontrollflussgraphen und deren Bedeutung

Definition:

Visualisierung von Programmstruktur; zeigt Kontrollfluss zwischen den Anweisungen.

Details:

• Knoten: Anweisungen oder Basisblöcke.
• Kanten: Kontrollfluss (z.B. Sprünge, Verzweigungen).
• Wichtig für Optimierungen: z.B. Schleifenentfaltung, Totcode-Eliminierung.
• Erlaubt Analyse von Pfadabdeckung, Schleifeninvarianten.
• Werkzeuge: Graphviz, LLVM.

Intraprozedurale und interprozedurale Analyse

Definition:

Analyse von Programmen auf verschiedenen Ebenen: innerhalb einer Prozedur (intraprozedural) und zwischen mehreren Prozeduren (interprozedural).

Details:

• Intraprozedurale Analyse: Bezieht sich auf die Analyse innerhalb einer einzelnen Funktion oder Methode.
• Interprozedurale Analyse: Analysiert die Interaktionen und Datenflüsse zwischen mehreren Funktionen oder Methoden.
• Ziel: Verbesserung der Codeoptimierung durch tiefere Einblicke in den Programmablauf und Datenfluss.
• Typische Techniken: Datenflussanalyse, Kontrollflussanalyse, Abhängigkeitsanalysen.
• Intraprozedurale Analyse: Lokale Optimierungen wie tote Code-Eliminierung, Schleifenoptimierungen.
• Interprozedurale Analyse: Globale Optimierungen wie Inline-Ersetzung, konstante Propagation über Funktionsgrenzen.
• Komplexität: Interprozedurale Analysen sind meist komplexer und rechenintensiver.

Zwischenrepräsentationen und ihre Verwendung im Übersetzerbau

Definition:

Abstrakte Strukturen, die den Zwischenschritt zwischen Quell- und Zielcode darstellen.

Details:

• Zwischenrepräsentation (IR) ermöglicht maschinenunabhängige Optimierungen.
• Gemeinsame IR-Typen: abstrakte Syntaxbäume (AST), drei-Adress-Code (TAC).
• Erlaubt detaillierte Analyse und Transformation vor der Codegenerierung.
• Ermöglicht Optimierungen wie Schleifenvereinfachung und tote Code-Eliminierung.

Loop-Unrolling und Loop-Fusion

Definition:

Loop-Unrolling und Loop-Fusion sind Compiler-Optimierungstechniken zur Verbesserung der Programmausführung durch Reduzierung der Schleifen-Overheads und Verbesserung der Cache-Ausnutzung.

Details:

• Loop-Unrolling: Schleife wird teilweise oder vollständig aufgelöst, um die Schleifenoverhead zu senken
• Vorteile: Reduzierte Schleifensteuerungsaufwände, bessere Pipeline-Auslastung
• Loop-Fusion: Kombiniert zwei oder mehr Schleifen mit ähnlichen Grenzen zu einer einzigen Schleife
• Vorteile: Reduzierung der Schleifenanzahl, verbesserte Datenlokalität

Graphenfärbungsalgorithmen für die Registerallokation

Definition:

Graphfärbungsansatz zur Zuweisung von Registerressourcen in einem Compiler.

Details:

• Graph G: Knoten entsprechen Variablen, Kanten 'interferieren' signalisieren gleichzeitige Verwendung
• Färbung: Weise jedem Knoten (Variable) eine Farbe (Register) zu
• Ziel: Minimierung der benötigten Registeranzahl
• Chaitin's Algorithmus als Basisansatz
• Heuristiken zur Spillcode-Entscheidung
• K(=Anzahl Register)-färbbarer Graph → erfolgreiche Allokation ohne Spill
• SLR (Simplify, Spill, Select, Assign) Zyklus

Branch-Prediction Optimierungen

Definition:

Optimierungen zur Vorhersage und Verbesserung der Ausführung von Verzweigungen im Code.

Details:

• Ziel: Minimierung von Pipeline-Störungen durch falsche Sprungvorhersagen.
• Statische Vorhersage: basierend auf festen Regeln (z.B. Rückwärts-Sprünge immer als genommen vorhergesagt).
• Dynamische Vorhersage: basierend auf der Historie von Verzweigungen (z.B. Zweibitmusterzähler).
• Branch Target Buffer (BTB): Puffer zur Speicherung von Zieladressen vorhergesagter Verzweigungen.
• Branch History Table (BHT): Tabelle zur Verfolgung der Ausführungsverläufe für bessere Vorhersagegenauigkeit.
• Prediktionseinheit im Prozessor: spezieller Hardwareteil zur Ausführung dieser Optimierungen.
• Verwendung von If-Conversion-Techniken: bedingte Verzweigungen in bedingte Anweisungen umwandeln.

Pipeline-Optimierungen und deren Auswirkungen

Definition:

Verbesserungen in der Instruktionsverarbeitung durch parallele Ausführungsschritte zur Reduktion von Wartezeiten und Erhöhung der CPU-Effizienz.

Details:

• Nutzen von Instruktionspipelines zur parallelen Ausführung von Befehlen.
• Unterteilung von Instruktionszyklen in verschiedene Stufen (Fetch, Decode, Execute, Memory Access, Write Back).
• Reduzieren von Pipeline-Stalls durch Techniken wie Branch Prediction und Out-of-Order Execution.
• Verbesserung der Durchsatzrate und Gesamtleistung der CPU.
• Erhöhung der Komplexität des Prozessordesigns.
• Erforderlich für Hochleistungsanwendungen und -prozessoren.