Lokale Optimierungen (Basic Block)

Typischerweise führt der Compiler innerhalb eines Basic Blocks folgende Optimierungen durch:

Konstantenfaltung: konstante Ausdrücke werden zur Compile-Zeit ausgewertet. Beispiel: 3 * 7 → 21
Konstantenpropagation: bekannte konstante Werte werden in Folgeausdrücke eingesetzt. Beispiel: x = 5; y = x + 2; → y = 7
Algebraische Vereinfachung: Ausdrücke werden über Rechenregeln reduziert. Beispiele: x * 1 → x, x + 0 → x, x - x → 0 (wenn definiert)
Common Subexpression Elimination (CSE): identische Teilausdrücke werden nur einmal berechnet. Beispiel: a = b * c; d = b * c;
Copy Propagation: reine Weiterreich-Zuweisungen werden aufgelöst. Beispiel: b = a; c = b; → c = a;
Dead Code Elimination (DCE): Berechnungen ohne beobachtbaren Nutzen werden entfernt. Beispiel: x = a + b; (wenn x nicht verwendet wird)
Redundante Loads und Stores: wiederholte Speicherzugriffe werden vermieden, sofern keine Seiteneffekte (z. B. volatile-Zugriffe oder Funktionsaufrufe) oder Aliasse vorliegen. Beispiel: x = *p; y = *p;

Ein einziges C Beispiel, in dem die Punkte zusammen vorkommen:

#include <stdint.h>

int main() {
    // Konstantenfaltung
    int folded = 3 * 7;                 // 21

    // Konstantenpropagation
    int k = 5;
    int propagated = k + 2;             // 7

    // Algebraische Vereinfachung
    int x = 123;
    int algebra = (x * 1) + (x + 0) + (x - x);  // x + x + 0

    // CSE: gemeinsamer Teilausdruck
    int b = 7, c = 9;
    int cse1 = b * c + 1;
    int cse2 = b * c + 2;               // b*c kann einmal berechnet werden

    // Copy Propagation
    int a = folded;
    int tmp = a;
    int copied = tmp;                   // wird zu copied = a

    // Redundante Loads: zweimal derselbe Load
    int v = 5;
    int *p = &v;
    int load1 = *p;
    int load2 = *p;                     // zweiter Load kann entfallen

    // Dead Code: Ergebnis wird nicht verwendet
    int dead = (folded + propagated) * (b - c);
    (void)dead;

    return folded + propagated + algebra + cse1 + cse2 + copied + load1 + load2;
}

Übersetzt man das Programm mit dem Schalter -O2, reduziert der Compiler das gesamte Programm effektiv auf:

"main":
        mov     eax, 434
        ret

Kontrollflussbasierte Optimierungen (innerhalb einer Funktion)

Diese Optimierungen wirken über einzelne Basic Blocks hinaus, bleiben aber auf den Gültigkeitsbereich einer Funktion beschränkt. Der Compiler analysiert den Kontrollflussgraphen und nutzt Informationen über Verzweigungen, Sprungziele und erreichbare Codepfade.

Typischerweise gehören dazu:

Entfernen unerreichbaren Codes: Codepfade, die logisch nicht erreicht werden können, werden vollständig entfernt. Beispiel: if (0) { ... }
Vereinfachung von Bedingungen: Bedingungen mit bekanntem Wahrheitswert werden reduziert. Beispiel: if (x == x) → true (für definierte Fälle)
Branch Folding: Verzweigungen mit identischem Ziel werden zusammengeführt. Beispiel: if (c) goto L; else goto L; → goto L;
Zusammenfassen von Sprungketten: Mehrere aufeinanderfolgende Sprünge werden zu einem direkten Sprung vereinfacht. Beispiel: goto A; A: goto B; → goto B;
If-Conversion: Kleine bedingte Codeabschnitte werden in bedingte Zuweisungen oder bedingte Instruktionen umgewandelt, um Sprünge zu vermeiden. Beispiel: if (c) x = a; else x = b;
Switch-Optimierungen: switch-Anweisungen werden je nach Fallstruktur als Sprungtabelle, binäre Suche oder Vergleichskette umgesetzt.

Typischer Effekt: weniger Sprünge, kürzere Sprungketten, besser vorhersehbarer Kontrollfluss.

Schleifenoptimierungen

Schleifenoptimierungen wirken auf wiederholte Ausführungspfade innerhalb einer Funktion. Da Schleifen häufig den größten Anteil der Laufzeit verursachen, liegt hier ein wesentlicher Fokus moderner Compiler. Der Compiler analysiert Schleifengrenzen, Abhängigkeiten und Invarianten und versucht, unnötige Arbeit aus der Schleife zu entfernen oder die Iterationen effizienter auszuführen.

Typischerweise gehören dazu:

Loop-Invariant Code Motion (LICM): Berechnungen, deren Ergebnis sich innerhalb der Schleife nicht ändert, werden vor die Schleife verlagert. Beispiel: for (...) y = a * b;
Strength Reduction: teure Operationen werden durch billigere ersetzt, oft in Verbindung mit Induktionsvariablen. Beispiel: i * 4 → offset += 4 bei fortlaufender Induktionsvariable
Optimierung von Induktionsvariablen: überflüssige Zähl- oder Hilfsvariablen werden entfernt oder zusammengeführt. Beispiel: mehrere Zähler mit fester Beziehung
Loop Unrolling: mehrere Iterationen werden zu einer zusammengefasst, um Sprung Overhead zu reduzieren. Beispiel: vier Schleifendurchläufe pro Iteration
Loop Peeling: erste oder letzte Iterationen werden aus der Schleife herausgelöst, um Randbedingungen zu vereinfachen.
Loop Unswitching: invariante Bedingungen werden aus der Schleife gezogen, wodurch mehrere spezialisierte Schleifen entstehen. Beispiel: if (flag) außerhalb der Schleife
Loop Fusion und Loop Fission: Schleifen werden zusammengelegt oder aufgeteilt, um Cache-Verhalten oder Abhängigkeiten zu verbessern.
Vektorisierung (SIMD): mehrere Iterationen werden parallel ausgeführt, wenn keine Abhängigkeiten bestehen.

Typischer Effekt: weniger Schleifendurchläufe, weniger Sprünge, bessere Cache Nutzung und höhere Rechenparallelität.

Interprozedurale Optimierungen

Interprozedurale Optimierungen wirken über einzelne Funktionen hinaus. Der Compiler betrachtet Aufrufer und Aufgerufene gemeinsam und analysiert den Aufrufgraphen. Dadurch können Optimierungen durchgeführt werden, die bei isolierter Betrachtung einzelner Funktionen nicht möglich sind.

Typischerweise gehören dazu:

Inlining: Funktionsaufrufe werden durch den Funktionsrumpf ersetzt, um Call Overhead zu vermeiden und weitere Optimierungen zu ermöglichen. Beispiel: kleine Hilfsfunktionen
Partielles Inlining: nur häufig ausgeführte Pfade einer Funktion werden inline eingebettet.
Interprozedurale Konstantenpropagation: konstante Argumente werden funktionsübergreifend ausgewertet. Beispiel: f(3) ermöglicht spezialisierte Version von f
Analyse von Funktionsattributen: Eigenschaften wie Seiteneffektfreiheit oder Nicht-Rückkehr werden erkannt und genutzt. Beispiel: als rein deklarative Funktionsattribute (z. B. „keine Seiteneffekte“).
Devirtualisierung: indirekte Funktionsaufrufe werden zu direkten Aufrufen, wenn das Ziel eindeutig bestimmbar ist. Beispiel: Funktionszeiger mit nur einem möglichen Ziel
Entfernen unbenutzter Funktionen: Funktionen ohne Aufrufer werden eliminiert, sofern sie keine externen Effekte haben.

Typischer Effekt: weniger Funktionsaufrufe, mehr Kontext für Optimierungen und oft deutlich effizienterer Code.

Ganzprogramm- und Link-Time-Optimierungen

Diese Optimierungen nutzen Informationen über das gesamte Programm oder über mehrere Übersetzungseinheiten hinweg. Sie werden typischerweise während des Linkens oder in einer speziellen Link-Time-Optimierungsphase durchgeführt und setzen voraus, dass dem Compiler ausreichend globale Informationen zur Verfügung stehen.

Typischerweise gehören dazu:

Cross-Module Inlining: Funktionen werden auch über Datei- und Modulgrenzen hinweg inline eingebettet.
Globale Dead Code Elimination: unbenutzte Funktionen, globale Variablen und Datenstrukturen werden entfernt.
Whole-Program Constant Propagation: globale Konstanten und bekannte Initialwerte werden programmweit weiterverbreitet.
Verbesserte Alias-Analyse: mit vollständiger Sicht auf alle Zugriffe kann der Compiler präzisere Annahmen treffen.
Identical Code Folding (ICF): identische Funktionen oder Codeabschnitte werden zusammengelegt, um Codegröße zu reduzieren.
Bessere Aufrufgraph-Analyse: genauere Bestimmung möglicher Aufrufpfade, insbesondere bei Funktionszeigern.

Typischer Effekt: weniger toter Code, besseres Inlining, kleinere oder schnellere Binärdateien.

Hinweis: Diese Optimierungen erfordern in der Regel explizite Aktivierung, etwa durch Link-Time-Optimierung (LTO). Ohne LTO bleibt der Compiler auf Informationen einzelner Übersetzungseinheiten beschränkt.

Backend-Optimierungen und Codegenerierung

Bis hierher ging es um Optimierungen nach Reichweite im Programm. Das beschreibt, welchen Programmkontext der Compiler betrachtet: einzelnen Basic Block, Funktion, mehrere Funktionen oder das ganze Programm. Diese Sicht beschreibt, was optimiert wird, aber noch nicht, wie daraus effizienter Maschinencode entsteht.

Backend-Optimierungen arbeiten näher an der Zielarchitektur. Sie setzen auf einer bereits optimierten Zwischenrepräsentation auf und entscheiden, welche Maschineninstruktionen erzeugt werden, wie Register genutzt und in welcher Reihenfolge Instruktionen ausgeführt werden. Diese Optimierungen sind weitgehend unabhängig von der zuvor betrachteten Reichweite und stark von der konkreten CPU-Architektur abhängig.

Typische Backend-Optimierungen sind:

Registerallokation: bestimmt, welche Werte in Registern gehalten und welche in den Speicher ausgelagert werden müssen.
Spill-Optimierung: versucht, zusätzliche Speicherzugriffe durch ungünstige Registerbelegung zu minimieren.
Instruction Selection: wählt für abstrakte Operationen passende Maschineninstruktionen der Zielarchitektur aus.
Instruction Combining: fasst mehrere einfache Operationen zu einer einzelnen Maschineninstruktion zusammen.
Peephole-Optimierungen: ersetzt kurze, ineffiziente Instruktionsfolgen durch äquivalente, kürzere Varianten.
Instruction Scheduling: ordnet Instruktionen neu an, um Pipeline-Latenzen zu überdecken und Stalls zu vermeiden.
Code-Layout-Optimierung: beeinflusst die Anordnung von Funktionen und Basic Blocks im Speicher, um Cache- und Sprungvorhersage zu verbessern.

Diese Optimierungen bestimmen maßgeblich die Qualität des erzeugten Maschinencodes, ohne die semantische Bedeutung des Programms zu verändern.