llvm dev - Feb 2016 - Is a PHI use of another PHI in the same block valid?

Over in pr26718, we ran across a case where input IR had one PHI within 
a basic block using the value of another PHI within the same basic block 
(without a backedge).  There has been some disagreement as to whether 
this is valid IR.  I believe it is not.

The verifier currently accepts the following code without error:

define void @f() {
entry:
   br label %next

next:
   %y = phi i32 [ 0, %entry ]
   %x = phi i32 [ %y, %entry ]
   ret void
}

Looking at the code, this may be an oversight - due to a special casing 
of the dominance relation within a single basic block - but that's not 
/obviously/ true.  Thus, we need to clarify what the intended semantics are.

The lang ref seems pretty clear about this:
"For the purposes of the SSA form, the use of each incoming value is 
deemed to occur on the edge from the corresponding predecessor block to 
the current block (but after any definition of an ‘invoke‘ instruction’s 
return value on the same edge)."

But David pointed out that various bits of the optimizer appear to have 
code and test cases covering exactly this case.

So, is this legal IR?  Or not?

Philip


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160226/871b7c3b/attachment.html>

For people not following the PR, Joseph has pointed out some issues
with what the verifier currently accepts in an excellent writeup on
the bug: https://llvm.org/bugs/show_bug.cgi?id=26718#c9

On Fri, Feb 26, 2016 at 9:02 AM, Philip Reames via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Over in pr26718, we ran across a case where input IR had one PHI within a
> basic block using the value of another PHI within the same basic block
> (without a backedge).  There has been some disagreement as to whether this
> is valid IR.  I believe it is not.
>
> The verifier currently accepts the following code without error:
>
> define void @f() {
> entry:
>   br label %next
>
> next:
>   %y = phi i32 [ 0, %entry ]
>   %x = phi i32 [ %y, %entry ]
>   ret void
> }
>
> Looking at the code, this may be an oversight - due to a special casing of
> the dominance relation within a single basic block - but that's not
> obviously true.  Thus, we need to clarify what the intended semantics are.
>
> The lang ref seems pretty clear about this:
> "For the purposes of the SSA form, the use of each incoming value is
deemed
> to occur on the edge from the corresponding predecessor block to the
current
> block (but after any definition of an ‘invoke‘ instruction’s return value
on
> the same edge)."
>
> But David pointed out that various bits of the optimizer appear to have
code
> and test cases covering exactly this case.
>
> So, is this legal IR?  Or not?
>
> Philip
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>


-- 
Sanjoy Das
http://playingwithpointers.com

On 2/26/2016 11:02 AM, Philip Reames via llvm-dev wrote:
>
> So, is this legal IR?  Or not?
I don't know if the IR spec mentions this case, but it simply makes no 
sense.  PHI nodes indicate values on entry to the block.  Their ordering 
in the IR only exists because instructions are arranged in an ordered 
list, but the relative ordering of PHIs has no meaning.

-Krzysztof

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

On 2/26/2016 11:15 AM, Krzysztof Parzyszek via llvm-dev
wrote:
>
> I don't know if the IR spec mentions this case, but it simply makes no
> sense.
It would make sense if there was a back edge to this block---then the 
value used in the PHI would be the value on exit from this block.

-Krzysztof

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

If we decide not to be legal, should we change the verify to reject
it? What happens to the test cases that currently test this very
situation (eg. Transforms/LoopVectorize/phi-hang.ll)?

The change as suggested by Philip is:

-  Assert(InstsInThisBlock.count(Op) || DT.dominates(Op, U),
+  Assert((!isa<PHINode>(I) && InstsInThisBlock.count(Op)) ||
+         DT.dominates(Op, U),
+         "Instruction does not dominate all uses!", Op, &I);

Michael


2016-02-26 18:02 GMT+01:00 Philip Reames <listmail at
philipreames.com>:
> Over in pr26718, we ran across a case where input IR had one PHI within a
> basic block using the value of another PHI within the same basic block
> (without a backedge).  There has been some disagreement as to whether this
> is valid IR.  I believe it is not.
>
> The verifier currently accepts the following code without error:
>
> define void @f() {
> entry:
>   br label %next
>
> next:
>   %y = phi i32 [ 0, %entry ]
>   %x = phi i32 [ %y, %entry ]
>   ret void
> }
>
> Looking at the code, this may be an oversight - due to a special casing of
> the dominance relation within a single basic block - but that's not
> obviously true.  Thus, we need to clarify what the intended semantics are.
>
> The lang ref seems pretty clear about this:
> "For the purposes of the SSA form, the use of each incoming value is
deemed
> to occur on the edge from the corresponding predecessor block to the
current
> block (but after any definition of an ‘invoke‘ instruction’s return value
on
> the same edge)."
>
> But David pointed out that various bits of the optimizer appear to have
code
> and test cases covering exactly this case.
>
> So, is this legal IR?  Or not?

If we decide not to be legal, should we change the verify to reject
it? What happens to the test cases that currently test this very
situation (eg. Transforms/LoopVectorize/phi-hang.ll)?

The change as suggested by Philip is:

-  Assert(InstsInThisBlock.count(Op) || DT.dominates(Op, U),
+  Assert((!isa<PHINode>(I) && InstsInThisBlock.count(Op)) ||
+         DT.dominates(Op, U),
+         "Instruction does not dominate all uses!", Op, &I);

Michael


2016-02-26 18:02 GMT+01:00 Philip Reames <listmail at
philipreames.com>:
> Over in pr26718, we ran across a case where input IR had one PHI within a
> basic block using the value of another PHI within the same basic block
> (without a backedge).  There has been some disagreement as to whether this
> is valid IR.  I believe it is not.
>
> The verifier currently accepts the following code without error:
>
> define void @f() {
> entry:
>   br label %next
>
> next:
>   %y = phi i32 [ 0, %entry ]
>   %x = phi i32 [ %y, %entry ]
>   ret void
> }
>
> Looking at the code, this may be an oversight - due to a special casing of
> the dominance relation within a single basic block - but that's not
> obviously true.  Thus, we need to clarify what the intended semantics are.
>
> The lang ref seems pretty clear about this:
> "For the purposes of the SSA form, the use of each incoming value is
deemed
> to occur on the edge from the corresponding predecessor block to the
current
> block (but after any definition of an ‘invoke‘ instruction’s return value
on
> the same edge)."
>
> But David pointed out that various bits of the optimizer appear to have
code
> and test cases covering exactly this case.
>
> So, is this legal IR?  Or not?
>
> Philip
>
>

FWIW, I just ran "ninja check" with the proposed change.
Transforms/LoopVectorize/phi-hang.ll is the only one that fails.

Michael


2016-02-26 18:29 GMT+01:00 Michael Kruse <llvmdev at
meinersbur.de>:
> If we decide not to be legal, should we change the verify to reject
> it? What happens to the test cases that currently test this very
> situation (eg. Transforms/LoopVectorize/phi-hang.ll)?
>
> The change as suggested by Philip is:
>
> -  Assert(InstsInThisBlock.count(Op) || DT.dominates(Op, U),
> +  Assert((!isa<PHINode>(I) && InstsInThisBlock.count(Op)) ||
> +         DT.dominates(Op, U),
> +         "Instruction does not dominate all uses!", Op, &I);
>
> Michael
>
>
> 2016-02-26 18:02 GMT+01:00 Philip Reames <listmail at
philipreames.com>:
>> Over in pr26718, we ran across a case where input IR had one PHI within
a
>> basic block using the value of another PHI within the same basic block
>> (without a backedge).  There has been some disagreement as to whether
this
>> is valid IR.  I believe it is not.
>>
>> The verifier currently accepts the following code without error:
>>
>> define void @f() {
>> entry:
>>   br label %next
>>
>> next:
>>   %y = phi i32 [ 0, %entry ]
>>   %x = phi i32 [ %y, %entry ]
>>   ret void
>> }
>>
>> Looking at the code, this may be an oversight - due to a special casing
of
>> the dominance relation within a single basic block - but that's not
>> obviously true.  Thus, we need to clarify what the intended semantics
are.
>>
>> The lang ref seems pretty clear about this:
>> "For the purposes of the SSA form, the use of each incoming value
is deemed
>> to occur on the edge from the corresponding predecessor block to the
current
>> block (but after any definition of an ‘invoke‘ instruction’s return
value on
>> the same edge)."
>>
>> But David pointed out that various bits of the optimizer appear to have
code
>> and test cases covering exactly this case.
>>
>> So, is this legal IR?  Or not?
>>
>> Philip
>>
>>