Static Single Assignment (kurz SSA) ist eine besondere Form der Zwischendarstellung in Compilern: Jede Variable wird im Code statisch genau einmal zugewiesen. Eine Variable, die im Quelltext mehrfach ihren Wert ändert, wird dabei in mehrere Versionen aufgeteilt – etwa x0, x1, x2. Dadurch wird der Datenfluss im Programm explizit sichtbar und viele Optimierungen werden deutlich einfacher.
Das Phi-Problem
Die Schwierigkeit entsteht an Stellen, an denen der Kontrollfluss zusammenläuft: Kommt der Wert von x aus dem if-Zweig oder aus dem else-Zweig? Für diesen Fall führt SSA die Phi-Funktion (φ) ein. Eine Phi-Funktion ist keine echte Rechenoperation, sondern wählt je nachdem, welcher Pfad vorher gelaufen wurde, den passenden Wert aus:
x1 = 1
x2 = 2
x3 = phi(x1, x2)Erst nach dieser Zusammenführung kann das Programm mit x3 weiterarbeiten. Phi-Knoten stehen immer an Verzweigungs-Zusammenflüssen und machen die Aufteilung der Variable statisch eindeutig.
Warum SSA Optimierungen vereinfacht
In der SSA-Form ist zu jeder Verwendung genau die eine definierende Zuweisung bekannt – Verwendung-Vereinigung-Ketten (use-def-Ketten) müssen nicht mehr mühsam berechnet werden. Das erleichtert unter anderem die Code-Optimierung: Dead-Code-Eliminierung entfernt Zuweisungen, deren Ergebnis nie verwendet wird; die Konstantenfaltung und -propagierung ersetzt Variablen, deren Wert feststeht, durch den Wert; und auch Umformungen von Schleifen profitieren. SSA ist seit den Arbeiten von Cytron, Ferrante, Rosen, Wegman und Zadeck (1988) das Fundament fast aller modernen Optimierer: LLVM arbeitet intern mit SSA, GCC mit der SSA-basierten Zwischenform GIMPLE, und auch JIT-Compiler wie die V8-Engine nutzen das Prinzip.
Von SSA zurück zum Maschinencode
Vor der Codegenerierung wird die SSA-Form in einer Phase namens SSA-Eliminierung wieder in normale Zuweisungen überführt – Phi-Funktionen werden durch Kopieranweisungen an den Verzweigungsstellen ersetzt. Die anschließende Registerallokation verteilt die nun eindeutigen Werte auf die CPU-Register. Wer die Pipeline eines Compilers nachvollzieht, trifft SSA als das moderne Herzstück zwischen semantischer Analyse und Codegenerierung.
Verwandte Grundlagen: Zwischendarstellung, Code-Optimierung, Registerallokation.