llvm dev - Feb 2015 - [LLVMdev] Jump Theading/GVN bug - moving discussion to llvm-dev

>> all the zero paths from entry to %a pass by %b.
>
>
> That is a graph-wise definition, sure.
> So, this is an interesting definition, and maybe this is part of the source
> of the problem.
>
> For SSA, at least GCC requires that both "definition block dominates
use
> block" (which would be true here), *and*
> that "definition appears before use in block" (IE definition
locally
> dominates use).
>
> IE it has to pass both DT->dominates(block(%b), block(%a)) and
> DT->dominates(%b, %a).
>
> LLVM special cases "not reachable from entry", and says that no
matter what,
> #2 is true if %a is unreachable.
>
> The code is, IMHO, not even self-consistent
>
>
>    // Any unreachable use is dominated, even if Def == User.
>    if (!isReachableFromEntry(UseBB))
>      return true;
>
>    // Unreachable definitions don't dominate anything.
>    if (!isReachableFromEntry(DefBB))
>      return false;
>
>
>
> Riddle me this: If unreachable definitions dominate nothing, how are
> unreachable uses always dominated by their unreachable defs?
I think the comment is just just missing an "otherwise" at the start.

If we were to define dominance rules as you suggest, we would still accept

define void @f() {
bb0:
  ret void
bb1:
  %a = getelementptr inbounds i8* %b, i64 1
  ret void
bb2:
  %b = getelementptr inbounds i8* %a, i64 1
  ret void
}

Since bb1 dominates bb2 and bb2 dominates bb1, no?

It looks like a case where we would just be getting a bigger rug to
swipe dirt under. I think the definition we have is sound. It creates
odd cases, but, as you point out, it looks like we can just require
passes to cleanup such cases by deleting forward unreachable code.

Cheers,
Rafael

On Wed, Feb 25, 2015 at 10:41 AM, Rafael Espíndola <
rafael.espindola at gmail.com> wrote:
> >> all the zero paths from entry to %a pass by %b.
> >
> >
> > That is a graph-wise definition, sure.
> > So, this is an interesting definition, and maybe this is part of the
> source
> > of the problem.
> >
> > For SSA, at least GCC requires that both "definition block
dominates use
> > block" (which would be true here), *and*
> > that "definition appears before use in block" (IE definition
locally
> > dominates use).
> >
> > IE it has to pass both DT->dominates(block(%b), block(%a)) and
> > DT->dominates(%b, %a).
> >
> > LLVM special cases "not reachable from entry", and says that
no matter
> what,
> > #2 is true if %a is unreachable.
> >
> > The code is, IMHO, not even self-consistent
> >
> >
> >    // Any unreachable use is dominated, even if Def == User.
> >    if (!isReachableFromEntry(UseBB))
> >      return true;
> >
> >    // Unreachable definitions don't dominate anything.
> >    if (!isReachableFromEntry(DefBB))
> >      return false;
> >
> >
> >
> > Riddle me this: If unreachable definitions dominate nothing, how are
> > unreachable uses always dominated by their unreachable defs?
>
> I think the comment is just just missing an "otherwise" at the
start.
>
It also doesn't explain "why" it decided this is the case :)
>
> If we were to define dominance rules as you suggest, we would still accept
>
> define void @f() {
> bb0:
>   ret void
> bb1:
>   %a = getelementptr inbounds i8* %b, i64 1
>   ret void
> bb2:
>   %b = getelementptr inbounds i8* %a, i64 1
>   ret void
> }
>
> Since bb1 dominates bb2 and bb2 dominates bb1, no?
>
Yes, if we consider unreachable blocks to dominate everything (IE the
dom-tree is not acyclic), it is just as bad of a result.

>
> It looks like a case where we would just be getting a bigger rug to
> swipe dirt under.

Yes, you are likely right.

> I think the definition we have is sound. It creates
> odd cases, but, as you point out, it looks like we can just require
> passes to cleanup such cases by deleting forward unreachable code.
>
> Cheers,
> Rafael
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150225/1867473c/attachment.html>

On 02/25/2015 10:41 AM, Rafael Espíndola wrote:
>>> all the zero paths from entry to %a pass by %b.
>>
>> That is a graph-wise definition, sure.
>> So, this is an interesting definition, and maybe this is part of the
source
>> of the problem.
>>
>> For SSA, at least GCC requires that both "definition block
dominates use
>> block" (which would be true here), *and*
>> that "definition appears before use in block" (IE definition
locally
>> dominates use).
>>
>> IE it has to pass both DT->dominates(block(%b), block(%a)) and
>> DT->dominates(%b, %a).
>>
>> LLVM special cases "not reachable from entry", and says that
no matter what,
>> #2 is true if %a is unreachable.
>>
>> The code is, IMHO, not even self-consistent
>>
>>
>>     // Any unreachable use is dominated, even if Def == User.
>>     if (!isReachableFromEntry(UseBB))
>>       return true;
>>
>>     // Unreachable definitions don't dominate anything.
>>     if (!isReachableFromEntry(DefBB))
>>       return false;
>>
>>
>>
>> Riddle me this: If unreachable definitions dominate nothing, how are
>> unreachable uses always dominated by their unreachable defs?
> I think the comment is just just missing an "otherwise" at the
start.
>
> If we were to define dominance rules as you suggest, we would still accept
>
> define void @f() {
> bb0:
>    ret void
> bb1:
>    %a = getelementptr inbounds i8* %b, i64 1
>    ret void
> bb2:
>    %b = getelementptr inbounds i8* %a, i64 1
>    ret void
> }
>
> Since bb1 dominates bb2 and bb2 dominates bb1, no?
I think this a great example of how our current definition is 
nonsensical and confusing.  :)

On the surface, it seems like having reachable code dominate unreachable 
code should work, but then we get constructs like this:

define void @f() {
bb0:
   br i1 true, label %bb1, label %bb2
bb1:
   %a = getelementptr inbounds i8* %b, i64 1
   ret void
bb2:
   %b = getelementptr inbounds i8* %a, i64 1
   ret void
bb3:
   icmp eq i8* %a, %b
   ret void
  }

In this case, bb3 is dominated by all of bb1, bb2, and bb3 even though 
there is no path which goes from bb2 to bb3 or vice versa. This seems 
problematic.

What would be implications of making dominates assert is given an 
unreachable block?  This seems like it would help isolate a lot of 
bugs.  Callers need to know about unreachable blocks anyways, so why not 
just make that explicit?

(To be clear, this proposal is *independent* of how we decide to handle 
unreachable code *between* passes.  This can happen *within* a
pass.)
>
> It looks like a case where we would just be getting a bigger rug to
> swipe dirt under. I think the definition we have is sound. It creates
> odd cases, but, as you point out, it looks like we can just require
> passes to cleanup such cases by deleting forward unreachable code.
>
> Cheers,
> Rafael
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

> What would be implications of making dominates assert is given an
> unreachable block?  This seems like it would help isolate a lot of bugs.
I think that's a great idea.

Having said that, I think the major problem is with passes
*implicitly* assuming the acyclicity of the dominator relation (this
assumption is violated by graphs with unreachable blocks).  For
instance, such the assert you suggest would not have triggered in the
GVN case that started this thread.

-- Sanjoy

>> define void @f() {
>> bb0:
>>    ret void
>> bb1:
>>    %a = getelementptr inbounds i8* %b, i64 1
>>    ret void
>> bb2:
>>    %b = getelementptr inbounds i8* %a, i64 1
>>    ret void
>> }
>>
>> Since bb1 dominates bb2 and bb2 dominates bb1, no?
>
> I think this a great example of how our current definition is nonsensical
> and confusing.  :)
It is. It is just hard to come up with a definition that doesn't just hide
the
confusion in a slightly more complicated case. Except:
> What would be implications of making dominates assert is given an
> unreachable block?  This seems like it would help isolate a lot of bugs.
> Callers need to know about unreachable blocks anyways, so why not just make
> that explicit?
That is, making (A dominates B) undefined if A is unreachable. To be clear,
you propose changing only the utility function that passes use, correct?
The verifier would still use the current version and @f above would still
be considered valid.

It is probably worth the experiment :-)

Cheers,
Rafael