[LLVMdev] Copy Instructions?

[Owen Anderson]

On Jan 28, 2009, at 9:06 AM, David Greene wrote:
>>> In this particular example another solution would be to reorder  
>>> the phis
>>> but I don't think that will work in the general case.
>>
>> PHI nodes don't have an ordering, at least conceptually; they're not
>> real instructions.
>
> They don't have an ordering?  So what does your above code mean?  I  
> would have
> expected it to mean that y is either the value of y.0 or the value  
> from the
> phi immediate preceeding it.  Is that not correct?
>
> If my understanding is correct then the code is wrong.  The original  
> code
> looks something like this:
>
> x = 0
> y = 0
> do
>  [...use x and y...]
>  y = x
>  x = expr
> end do
>
> So y should get the previous value of x, not the value updated at  
> the end of
> the loop body.
>
> If there truly is no ordering then perhaps Prakash is correct and  
> this is an
> out-of-SSA problem.  I'd appreciate your opinion on this.  I read  
> the Briggs
> SPE paper a long time ago.  Time to dust it off.

Eli is correct in that, in theory, PHI nodes in SSA form are  
unordered, i.e. all PHIs in a given basic block are evaluated  
simultaneously.  In that case, the correct code would be:

x.0 = 0
y.0 = 0
do
	x = phi(x.0, x.1)
	y = phi(y.0, x)
	x.1 = ...
	...
end do

LLVM does not implement this simultaneous evaluation for practical  
reasons.  Most situations can be resolved by reordering the PHI nodes,  
though the swap copy still remains:

x.0 = 0
y.0 = 0
do
	x = phi(x.0, y)
	y = phi(y.0, x) // NOT CORRECT WITH ORDERED PHIS!
	...
end do

In this case, you can resolve it by inserting an extra PHI node:

x.0 = 0
y.0 = 0
do
	foo = phi(undef, x)
	x = phi(x.0, y)
	y = phi(y.0, foo) // CORRECT WITH ORDERED PHIS!
	...
end do

--Owen