Re: Phi nodes?

Niall Dalton <ndalton@ics.uci.edu>
31 May 2001 02:43:31 -0400

          From comp.compilers

Related articles
Phi nodes? vbdis@aol.com (2001-05-22)
Re: Phi nodes? ndalton@ics.uci.edu (Niall Dalton) (2001-05-29)
Re: Phi nodes? titzer@expert.cc.purdue.edu (Ben L. Titzer) (2001-05-30)
Re: Phi nodes? ndalton@ics.uci.edu (Niall Dalton) (2001-05-31)
| List of all articles for this month |

From: Niall Dalton <ndalton@ics.uci.edu>
Newsgroups: comp.compilers
Date: 31 May 2001 02:43:31 -0400
Organization: University of California, Irvine
References: 01-05-064 01-05-083
Keywords: design
Posted-Date: 31 May 2001 02:43:31 EDT

> 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;


As you go on to show, assuming there are assignments to the variables,
then you get new names on each path. However, if there are no
assignments but only uses then they will all use the same name.


For example the 'a' variable:
if (a1 = 0) then
    c1 := a1 + 1
else
    c2 := a1 + 2
end


but if we rename due to control flow splits (symmetric to the renaming
at join points) then more optimizations could be enabled.


if (a1 = 0) {split a1 into a2 and a3} then
    c1 := a2 + 1
else
    c2 := a3 + 2
end


and we can see that a2 is always 0 and c1 is always 1, though we may not
be able to say anything about the value a3/c2. Standard SSA constant
propagation algorithms can be modified slightly to push the constants into
the branches. I believe that the IBM VLIW research compiler uses a
technique like this, I think they phrased it as "fully pinned", that is
the IR is kept in SSA/reverse SSA form. Does anyone know the origin of
this technique?


niall


--
----------------------------------------------------------------------
Niall Dalton ndalton@ics.uci.edu
University of California, Irvine http://www.ics.uci.edu/~ndalton


Post a followup to this message

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