[LLVMdev] Re: phi nodes

[Chris Lattner]

Note, I'm CC'ing the list as it's important LLVM design kind of material.

On Thu, 5 Feb 2004, Michael Kahl wrote:
> I note that in your representation of phi nodes, you key the incoming
> value to the incoming block.  Both appear explicitly (in pairs) in the
> operand list.  There is even a method
> "llvm::PHINode::getIncomingValueForBlock" which performs this
> computation.

yup.

> There are several potential problems with this approach, so I wonder how
> you have addressed them.  The most significant issue is that this
> representation works only if all of the predecessor blocks are unique.
> (Otherwise, the incoming values for the second and subsequent
> occurrences of the same predecessor won't be seen!)

That's sort-of true.  To handle this, we require that if there are
duplicate predecessors that they all have the same incoming value.  In
other words, you can't have something like this in LLVM:

  br bool %cond, label %Block, label %Block

Block:
  %Y = phi int [%whatever, 1], [%whatever, 2]

You can't have two different values coming in based on the value of the
condition code.  The reason for this is that, if you allow this, there is
no way to "translate out of SSA" at register allocation time.  The LLVM
verifier will catch this if an optimizer attempts to form this for some
reason.

> Does your CFG permit parallel edges?

Yes, of course.  :)

> The second problem is that it is very inefficient to search for the
> right position in the phi every time.  Of course, this only matters if
> there are blocks with many predecessors, but that happens more often
> than you might imagine, particularly with exception handlers.

True, this is an excellent point.  So far we haven't found this to be an
real issue, even in cases where the PHI nodes can have thousands of
entries (there are some horrible cases involving setjmp/longjmp in large
functions that this happens with).

Basically transformations just have to be careful about scanning the PHI
argument list.  When SCCP was naive about this, for example, it was _very_
slow.  Fixing it wasn't particularly hard, and we take optimizer
efficiency very seriously.  If this becomes an issue, we can potentially
come up with a better data structure for this, but I think what we have is
pretty reasonable.

> Perhaps there is an unstated guarantee that the order of the blocks
> mentioned in a phi node must match the parent block's predecessor list?

Unfortunately this is not really possible.  The predecessor list is
unordered, so it does not provide a stable order for PHI entries.  The
only thing that is stable is the order of blocks in a function.  However,
we don't want to use this to provide an ordering for blocks in a PHI node
because then we would have to hack on all of the PHI's in a function
whenever we moved a block... which _would_ be expensive.  :)

-Chris

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