Phi-Funktion (Compilerbau)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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);
  • 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.