[LLVMdev] PHI nodes in machine code

[Misha Brukman]

On Thu, Jul 08, 2004 at 08:06:29PM +0400, Vladimir Prus wrote:
> Could anybody quickly explain why PHI nodes instructions are necessary
> in machine code? And why the code in LiveVariables.cpp which looks at
> those PHI nodes (line 249 and below) is necessary.

LLVM Machine code is in SSA.

Let's say you want to do

  r = a cond b

But doing this:

  if (a cond b) then
    r = 1
  else
    r = 0

gets you two definitions of r.  So we have machine PHI nodes merge the
two possible values into one for result of r.  These phis get removed
after register allocation. So you would write code like:

  if (a cond b) then
    r1 = 1
  else 
    r2 = 0
  
  r = phi(r1, r2)

> The reason I'm asking is that I try to support 64-bit comparison and I do it 
> by generating code like:
> 
>           //    if high1 cond high2: goto operand0
>           //    if high1 reverse_cond high2: goto operand1

the second if should just be an unconditional branch to operand1:
clearly, if (high1 cond high2) is false, the reverse condition is true.

>           //    if low cond high2: goto operand0
>           //    goto operand1

These would have to go into different blocks, as above you would have an
unconditional branch, which then changes your branches significantly...

> but this means that operand0 and operand1 (the successor basic blocks)
> suddenly get more predecessor than recorded in phi nodes, and
> LiveVariables.cpp asserts on that.

Naturally, as PHI nodes need to have as many entries as there are
predecessors.

> Of course, I can add another two basic block which will set some
> register to 0 or 1 and branch based on the value of that register, but
> maybe the above approach can work as well.

The above approach should work.  

-- 
Misha Brukman :: http://misha.brukman.net :: http://llvm.cs.uiuc.edu