llvm dev - Jul 2017 - A bug related with undef value when bootstrap MemorySSA.cpp

On Mon, Jul 17, 2017 at 11:18 AM, Sanjoy Das via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>  Hi,
>
> On Mon, Jul 17, 2017 at 10:32 AM, Xinliang David Li <davidxl at
google.com>
> wrote:
> > The issue blocks another optimization patch and Wei has spent huge
> amount of
> > effort isolating the the bootstrap failure to this same problem. I
agree
> > with Wei that other developers may also get hit by the same issue and
the
> > cost of leaving this issue open for long can be very high to the
> community.
>
> I can't speak for others, but I am fine with adding a workaround for
> this.  However, I suspect isGuaranteedNotToBeUndefOrPoison in
> LoopUnswitch may regress other benchmarks.
>
Any other thoughts on a more minimal fix?
Otherwise, it sounds like we can only try to find the fix that does the
least damage.
We can't just leave it broken given it's triggering even in llvm
bootstraps
now :(
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170717/04d5e434/attachment.html>

On Mon, Jul 17, 2017 at 11:21 AM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>> On Mon, Jul 17, 2017 at 10:32 AM, Xinliang David Li <davidxl at
google.com>
>> wrote:
>> > The issue blocks another optimization patch and Wei has spent huge
>> > amount of
>> > effort isolating the the bootstrap failure to this same problem. I
agree
>> > with Wei that other developers may also get hit by the same issue
and
>> > the
>> > cost of leaving this issue open for long can be very high to the
>> > community.
>>
>> I can't speak for others, but I am fine with adding a workaround
for
>> this.  However, I suspect isGuaranteedNotToBeUndefOrPoison in
>> LoopUnswitch may regress other benchmarks.
>
> Any other thoughts on a more minimal fix?
I can't think of any good answers here.

The semantic we want is "branching on poison or undef is undefined
behavior" (which lets us do propagateEquality).  Given that, we could
be clever about implementing isGuaranteedNotToBeUndefOrPoison; for
instance if we have:

do {
  if (a != b) {
    ...
  }
} while (...);

then we can use post-domination to prove that "a != b" is not undef
(otherwise the loop is guaranteed to have undefined behavior).

(I hate to say this), a more aggressive fix is to introduce a "freeze"
intrinsic that freezes only an i1.  LoopUnswitch would wrap the loop
invariant condition in this after hoisting the branch.  This would be
a poor man's version of the more invasive patches Juneyoung already
has developed.

-- Sanjoy

Hello, some of the patches had conflicts with LLVM head, so I updated them.
If you experienced patch failure before then you can try it again.

I compiled your code (1.c) with LLVM r308173 with the 5 patches applied,
and it generated assembly like this. Now it contains store to c(%rip).
It tries to store a(%rip) + b(%rip) to c(%rip). I wish this translation is
now correct.

```
73   .globl  hoo                     # -- Begin function hoo
74   .p2align  4, 0x90
75   .type hoo, at function
76 hoo:                                    # @hoo
77   .cfi_startproc
78 # BB#0:
79   movq  a(%rip), %rax
80   movq  cnt(%rip), %rcx
81   cmpq  $0, i_hasval(%rip)
82   sete  %sil
83   xorl  %edx, %edx
84   .p2align  4, 0x90
85 .LBB1_1:                                # =>This Inner Loop Header:
Depth=1
86   testb $1, %sil
87   je  .LBB1_3
88 # BB#2:                                 #   in Loop: Header=BB1_1 Depth=1
89   movq  b(%rip), %rsi
90   addq  %rax, %rsi
91   movq  %rsi, c(%rip)
92   movq  $3, i_hasval(%rip)
93   incq  %rdx
94   xorl  %esi, %esi
95   cmpq  %rcx, %rdx
96   jl  .LBB1_1
97 .LBB1_3:
98   retq
```

IMHO, enhancing `isGuaranteedNotToBeUndefOrPoison` and using it as a
precondition in loop unswitching is
not enough. undef (and poison) value can be stored into memory, and also be
passed by a function argument.
`isGuaranteedNotToBeUndefOrPoison` will virtually return `false` for all
cases except the value is
some integer constant. Sanjoy's suggestion might be helpful (if I
understood correctly), but I'm
not sure how much it will be.

Best Regards,
Juneyoung Lee

On Tue, Jul 18, 2017 at 3:43 AM, Sanjoy Das via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On Mon, Jul 17, 2017 at 11:21 AM, Daniel Berlin <dberlin at
dberlin.org>
> wrote:
> >> On Mon, Jul 17, 2017 at 10:32 AM, Xinliang David Li <davidxl at
google.com
> >
> >> wrote:
> >> > The issue blocks another optimization patch and Wei has spent
huge
> >> > amount of
> >> > effort isolating the the bootstrap failure to this same
problem. I
> agree
> >> > with Wei that other developers may also get hit by the same
issue and
> >> > the
> >> > cost of leaving this issue open for long can be very high to
the
> >> > community.
> >>
> >> I can't speak for others, but I am fine with adding a
workaround for
> >> this.  However, I suspect isGuaranteedNotToBeUndefOrPoison in
> >> LoopUnswitch may regress other benchmarks.
> >
> > Any other thoughts on a more minimal fix?
>
> I can't think of any good answers here.
>
> The semantic we want is "branching on poison or undef is undefined
> behavior" (which lets us do propagateEquality).  Given that, we could
> be clever about implementing isGuaranteedNotToBeUndefOrPoison; for
> instance if we have:
>
> do {
>   if (a != b) {
>     ...
>   }
> } while (...);
>
> then we can use post-domination to prove that "a != b" is not
undef
> (otherwise the loop is guaranteed to have undefined behavior).
>
> (I hate to say this), a more aggressive fix is to introduce a
"freeze"
> intrinsic that freezes only an i1.  LoopUnswitch would wrap the loop
> invariant condition in this after hoisting the branch.  This would be
> a poor man's version of the more invasive patches Juneyoung already
> has developed.
>
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>


-- 

Juneyoung Lee
Software Foundation Lab, Seoul National University
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170718/a1f22eeb/attachment.html>

>> On Mon, Jul 17, 2017 at 11:18 AM, Sanjoy Das via llvm-dev 
>> <llvm-dev at lists.llvm.org> wrote:
>>  Hi,
>>
>> On Mon, Jul 17, 2017 at 10:32 AM, Xinliang David Li <davidxl at
google.com>
>> wrote:
>>> The issue blocks another optimization patch and Wei has spent huge 
>>> amount of
>>> effort isolating the the bootstrap failure to this same problem. I
agree
>>> with Wei that other developers may also get hit by the same issue
and
>>> the
>>> cost of leaving this issue open for long can be very high to the 
>>> community.
>>
>> I can't speak for others, but I am fine with adding a workaround
for
>> this.  However, I suspect isGuaranteedNotToBeUndefOrPoison in
>> LoopUnswitch may regress other benchmarks.
>
> Any other thoughts on a more minimal fix?
> Otherwise, it sounds like we can only try to find the fix that does the 
> least damage.
> We can't just leave it broken given it's triggering even in llvm 
> bootstraps now :(
Well, I don't think there's an easy fix for this..
The only suggestion I can help to improve isGuaranteedNotToBeUndefOrPoison() 
is to tweak the pass manager to say if all inter-procedural stuff is done 
such that this function can consider all arguments and global as 
non-poisonous. That probably will improve the precision significantly.
I can't think of any easy hack otherwise.

Nuno