Phi nodes

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Phi nodes

ST-7
Hi

Thanks for your answers so far. I am currently stumbling into new questions.
Naive as i am, i thought that the llvm-bytecode is allways in SSA form. But
this doesn't seem to be the case. At least there are no phi instructions
embedded if the bytecode drops out of llvm-gcc?
Looking into the archives this has been discussed before:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2005-August/004730.html
So there is stated that LLVM IR is always in SSA form. I thought that the SSA
form includes PHI nodes at the beginning of each block. But these PHI nodes
are not there. Or is this Phi node only necessary if the input for the
variable is multi sourced?

Slightly confused
ST
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Phi nodes

Anton Korobeynikov
Hello.

> Thanks for your answers so far. I am currently stumbling into new questions.
> Naive as i am, i thought that the llvm-bytecode is allways in SSA form. But
> this doesn't seem to be the case. At least there are no phi instructions
> embedded if the bytecode drops out of llvm-gcc?
Yes. llvm-gcc generates just memory references. PHI nodes are
constructed later via mem2reg pass.

> Looking into the archives this has been discussed before:
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2005-August/004730.html
> So there is stated that LLVM IR is always in SSA form.
Exactly.

> I thought that the SSA form includes PHI nodes at the beginning of each block.
What for? PHI nodes are necessary to track "multi sources" variable
assignments.

> Or is this Phi node only necessary if the input for the
> variable is multi sourced?
Exactly.

--
With best regards, Anton Korobeynikov.

Faculty of Mathematics & Mechanics, Saint Petersburg State University.


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Phi nodes

Reid Spencer-2
In reply to this post by ST-7
Hi ST,

On Wed, 2007-03-28 at 15:36 +0200, ST wrote:
> Hi
>
> Thanks for your answers so far. I am currently stumbling into new questions.
> Naive as i am, i thought that the llvm-bytecode is allways in SSA form.

Bytecode is merely a reflection of the LLVM IR C++ objects. If the LLVM
IR is in SSA form then so is the bytecode.

> But
> this doesn't seem to be the case. At least there are no phi instructions
> embedded if the bytecode drops out of llvm-gcc?

Correct, for -O0, but not for -O2 or higher.  This is done for
convenience of the code generator in llvm-gcc. Instead of emitting SSA
variables and having to track the PHI nodes in the code generator,
llvm-gcc just issues alloca/load/store like any normal variable. It is
expected that the mem2reg pass will clean this all up and SSAize the
code. Try something like:

llvm-gcc -emit-llvm -c FILE.c -o - | opt -mem2reg | llvm-dis -o -

to see what mem2reg does to clean up the SSAness.

> Looking into the archives this has been discussed before:
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2005-August/004730.html
> So there is stated that LLVM IR is always in SSA form. I thought that the SSA
> form includes PHI nodes at the beginning of each block. But these PHI nodes
> are not there. Or is this Phi node only necessary if the input for the
> variable is multi sourced?

Recall that in SSA a given register can be defined exactly once. This
means there are no "variables" (everything is immutable after initial
definition).  The PHI nodes are needed to get around this restriction.
They coalesce different values for a given variable into a new register
name.  I suggest you read the SSA article on Wikipedia.

The PHI node is needed to join two values defined in two (or more)
different blocks. If no such joins are needed then PHI nodes are not
needed. Since the llvm-gcc front end is doing explicit alloca/store/load
operations, there is never a need for PHI nodes because SSA registers
are not being used (fully).  This is still in SSA form (e.g. each load
from an alloca'd memory location needs a different register name), its
just that its not using SSA well.  Again, this is for convenience of
code generation (not having to track PHIs in the generator) and llvm-gcc
expects mem2reg to put everything back into full SSA form with lots of
PHI nodes.

If you run mem2reg you will see many alloca/load/store disappear and PHI
nodes appear.

>
> Slightly confused
> ST

Hope the confusion is dispelled now :)

Reid.

> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev