Phi function (compiler construction)

from Wikipedia, the free encyclopedia

The Phi function (φ function) is a construct in compiler construction .

With the internal representation of program code in the static single assignment representation , each variable is only written once. Since different variables are written in alternative branches, after the control flow has been combined (e.g. after an if / then / else), the problem that later code can only access one variable must be solved.

The problem is solved by the Phi function, which returns its parameters as a result depending on the control flow actually taken.

It is not a deterministic function, since its result depends on non-parameterized side effects . It phi(a_1, a_2) cannot be inferred from the expression alone whether the result is a_1or a_2is.

example

The code block 

if (c)
   a = b + d;
else
   a = e + f;
x = 2 * a;

becomes in the SSA form with the help of the Phi function: 

if (c_1)
   a_1 = b_1 + d_1;
else
   a_2 = e_1 + f_1;
x_1 = 2 * phi(a_1, a_2);

literature

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