Re: Phi nodes?

Phi nodes are an artifact of an SSA representation (Single Static
Assignment). They are used internally by the compiler to get around
certain nastiness of the control flow graph and SSA's represenation of
internal variables.


Basically, in SSA, you transform the uses of internal temporaries (objects
on the stack and registers) so that they are only assigned to once (not
multiple times). Every time you overwrite a variable, you create a new
one. This has some nice things in the liveness analysis and makes some
advanced optimizations possible (I won't go into this because I don't
understand the specifics well enough to comment).


What the phi nodes do is allow you to use two different versions of the
same variable in different branches of code. What I mean:


if ( some condition ) a = 1;
else a = 2;


b = a;


In the SSA representation, every time you assign to a, a new variable
would be created. So in SSA this code would look like:


if ( some condition ) a1 = 1;
else a2 = 2;


b = ????


You see the problem is that after you get past the two branches of the if
statement, you don't know which value of a to use! So that's why we insert
a phi statement for the sake of the compiler:


if ( some condition ) a1 = 1;
else a2 = 2;


b = phi(a1, a2);


The phi statement "picks" which value of a (a1 or a2) is the correct one
based on the previous flow graph. It is important to note that this is for
the sake of the compiler's internal represenation ONLY. This code isn't
executed, because it would not be logical how to truly implement a phi
statement in actual deterministic code.


So basically, phi statements are what cleans up the internal
representation of SSA format inside a compiler, so that it doesn't get
confused on what version of a variable needs to be used following multiple
control flows.


Clear as mud?


-Ben


_________________________________________________
  Close Windows and Open Doors - www.redpants.org


On 22 May 2001, VBDis wrote:


> Can somebody please explain me, what Phi nodes are, and what's their
> use in the .NET IL?
>
> I'm going to write a simple decompiler for IL files, and would like to
> know whether the Phi nodes are helpful herefor.
>
> DoDi

Return to the comp.compilers page.
Search the comp.compilers archives again.