Konstantenpropagation

Konstantenpropagation bezeichnet eine Optimierung in Compilern, bei der bekannte Konstantenwerte in Variablen erkannt und an deren Stellen genutzt werden. Ziel ist es, durch Ersetzen von Variablen durch Werte aus Konstantenberechnungen weitere Optimierungen wie Constant Folding oder Dead-Code-Elimination zu ermöglichen.

Technisch handelt es sich um eine datengesteuerte Analyse (data-flow analysis). Für jeden Punkt im Programm wird eine Abbildung der Variablen auf Werte geführt: entweder ein konkreter Konstantenwert oder ein Sonderwert wie Unknown. Der Join-Operator verbindet Pfade, sodass eine Variable nur dann als Konstante erhalten bleibt, wenn alle Pfade denselben Wert liefern; andernfalls wird der Wert Unknown. Die Transferfunktion aktualisiert die Abbildung bei Zuweisungen: Ist die rechte Seite konstant oder lässt sie sich aus Konstanten berechnen, erhält die Variable diesen Konstant, sonst wird sie Unknown. Die Analyse wird typischerweise auf Zwischenrepräsentationen wie SSA durchgeführt.

Nach der Analyse werden Konstanten in den Code eingefügt und einfache Ausdrücke vorgerendert. Dadurch ergeben sich oft weitere Optimierungen, etwa durch Reduktion redundanter Berechnungen oder bessere Registernutzung.

Vorteile umfassen mögliche Laufzeit- und Codegrößenreduktionen sowie bessere Voraussetzungen für weitere Optimierungen. Grenzen ergeben sich bei Features wie Zeigerarithmetik, Speicher- oder I/O-Seiteffekten, Aliasing oder Interaktionen mit Funktionen; komplexe oder interprocedurale Propagation kann teuer sein und liefert nicht immer bessere Ergebnisse. In vielen Compilern ist Konstantenpropagation deshalb lokal oder in SSA-Form implementiert.

Beispiel: a = 5; b = a + 2; c = b * 3. Nach Konstantenpropagation erhält man b = 7 und c = 21; weitere Optimierungen wie Dead-Code-Elimination können folgen.