[LLVMdev] PHI nodes in machine code

[Chris Lattner]

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

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?

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/