[LLVMdev] PHI nodes in machine code

[Vladimir Prus]

Chris Lattner wrote:
> On Fri, 9 Jul 2004, Vladimir Prus wrote:
> > Misha Brukman wrote:
> > > LLVM Machine code is in SSA.
> >
> > This explains quite a lot. I though it's possible to just reduce convert
> > phis into copy instructions in predecessors -- all of which will have the
> > same destination register.
>
> There are algorithms for eliminating PHI nodes, but they aren't quite so
> simple.  Consider what happens when you have phi nodes in a block like
> this:
>
>    Loop:
>       A = phi (B, Loop), (0, OutOfLoop)
>       B = phi (A, Loop), (1, OutOfLoop)
>
>       ...
>       br Loop
>
> No matter how you insert copies in the predecessors, you can't maintain
> the semantics of the phis (which are simultaneous assignment).  This is
> obviously possible to handle, it's just not entirely trivial.  FWIW, this
> is known as the "swap problem".

Thanks for explaning!

> More importantly, SSA is useful for the code generator.  It makes live
> variable analysis almost trivial for example, and is a natural
> representation to use for other reasons: you have to have an infinite # of
> regs before register allocation, why not make them SSA?

Yes, this is reasonable thing.

- Volodya