Phi-Funktion (Compilerbau)
Die Phi-Funktion (φ-Funktion) ist ein Konstrukt im Compilerbau.
Bei der internen Darstellung von Programmcode in der Static-Single-Assignment-Darstellung wird jede Variable nur einmal geschrieben. Da so in alternativen Zweigen verschiedene Variablen geschrieben werden, muss nach der Vereinigung des Kontrollflusses (z. B. nach einem if/then/else) das Problem gelöst werden, dass späterer Code nur auf eine Variable zugreifen kann.
Gelöst wird das Problem über die Phi-Funktion, die ihre Parameter abhängig vom tatsächlich genommenen Kontrollfluss als Ergebnis zurückgibt.
Sie ist keine deterministische Funktion, da ihr Ergebnis von nicht parametrisierten Nebeneffekten abhängt. Aus dem Ausdruck phi(a_1, a_2)
allein lässt sich nicht folgern, ob das Ergebnis a_1
oder a_2
ist.
Beispiel
[Bearbeiten | Quelltext bearbeiten]Der Code-Block
if (c)
a = b + d;
else
a = e + f;
x = 2 * a;
wird in der SSA-Form mit Hilfe der Phi-Funktion zu:
if (c_1)
a_1 = b_1 + d_1;
else
a_2 = e_1 + f_1;
x_1 = 2 * phi(a_1, a_2);
Literatur
[Bearbeiten | Quelltext bearbeiten]- Appel, Andrew W.: Modern Compiler Implementation in ML. Cambridge University Press, 1999, ISBN 0-521-58274-1.
- Cooper, Keith D.; and Torczon, Linda: Engineering a Compiler. Morgan Kaufmann, 2003, ISBN 1-55860-698-X.
- Muchnick, Steven S.: Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997, ISBN 1-55860-320-4.