[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp

Juneyoung Lee via llvm-dev llvm-dev at lists.llvm.org
Sat Jul 22 14:36:43 PDT 2017


What if it is hard to find the condition of the guard?

`a` can contain undefined value as well. Optimizations like

```
store %ptr, %v
%w = load %ptr
use(%w)
->
store %ptr, %v
use(%v)
```

can transform load from `a` into `undef`.

Best Regards,
Juneyoung Lee

On Wed, Jul 19, 2017 at 9:21 AM, Xinliang David Li via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

>
>
> On Tue, Jul 18, 2017 at 4:15 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>
>>
>> On 07/18/2017 06:03 PM, David Majnemer via llvm-dev wrote:
>>
>> I doubt it is possible for us to try and make any fix which is predicated
>> on eagerly treating undef in a particular way, refinement will always cause
>> these problems to come about...
>>
>> Given what I've seen in LLVM (and what I've learned from other
>> compilers), we probably have two choices:
>> 1. Rework undef so that it is an instruction, not a constant. This will
>> make it easy to unswitch, etc. because it would be stable. This approach is
>> used by other production quality compilers and is workable. Would also
>> result in a lot of churn.
>> 2. Keep undef as a constant, introduce freeze. Churn would mostly be
>> restricted to correctness fixes instead of to core IR representation.
>>
>> Note that option #1 is basically a short-hand for freeze(undef).
>>
>> We don't need to fix all the problems at the same time but I think we
>> need to start somewhere. I don't think there are any good shortcuts.
>>
>>
>> I agree; I don't think there are any good shortcuts here. Sadly, I think
>> we should follow our traditional policy: revert to green. Whatever commit
>> actually triggers the self-hosting bug, revert it (or effectively revert it
>> by disabling whatever it is by default). Then we should proceed with fixing
>> the underlying problem with all due haste.
>>
>>  -Hal
>>
>>
> In this case, should the compiler not generate the reference to undefined
> value in the first place (i.e, from guarded to unguarded)?   GCC also
> hoists the comparison a == i outside the loop, but its use is properly
> guarded:
>
>
>   long i, k;
>  if (hasval) {
>    i = b;
>  }
>
>  k = 0;
>
>  if (hasval) {
>    t = (a == i);
>    if (t) {
>       if (i_hasval != hasval)
>         return;
>
>        m = m + 1;
>        c = a + d + e + f;
>        return;
>     } else {  /* if (t) --> false */
>      do {
>       if (i_hasval != hasval)
>         return;
>       m = m + 1;
>       c = a + b;
>       i_hasval = 3;
>       k++;
>     } while (k < cnt);
>
>   } else { /* if (hasval) -->false */
>
>     do {
>       if (i_hasval != hasval)
>         return;
>       c = a + b;
>       i_hasval = 3;
>       k++;
>   } while (k < cnt);
>   }
>
>
> David
>
>
>>
>>
>> On Tue, Jul 18, 2017 at 3:40 PM, Wei Mi via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> On Mon, Jul 17, 2017 at 5:11 PM, Wei Mi <wmi at google.com> wrote:
>>> > On Mon, Jul 17, 2017 at 2:09 PM, Sanjoy Das
>>> > <sanjoy at playingwithpointers.com> wrote:
>>> >> Hi,
>>> >>
>>> >> On Mon, Jul 17, 2017 at 1:56 PM, Daniel Berlin via llvm-dev
>>> >> <llvm-dev at lists.llvm.org> wrote:
>>> >>>
>>> >>>
>>> >>> On Mon, Jul 17, 2017 at 1:53 PM, Wei Mi <wmi at google.com> wrote:
>>> >>>>
>>> >>>> It seems MemorySSA.cpp is the only real code where we found the
>>> >>>> problem happening.
>>> >>>
>>> >>>
>>> >>> This is doubtful, ¸FWIW :)
>>> >>>
>>> >>>>
>>> >>>> Is it possible to change the source of
>>> >>>> MemorySSA.cpp to hide the problem and buy some time for now? Now we
>>> >>>> use an empty generic_def_path_iterator with Optional<ListIndex> N
>>> >>>> being initialized by None as the end of range. Can we initialize the
>>> >>>> Optional var with a special value instead of None?
>>> >>>>
>>> >>>>   iterator_range<def_path_iterator> def_path(ListIndex From) {
>>> >>>>     return make_range(def_path_iterator(this, From),
>>> def_path_iterator());
>>> >>>>   }
>>> >>>>
>>> >>>
>>> >>> Why does this work?
>>> >>
>>> >> Fwiw, I don't think this is a good idea.  If it can happen in
>>> >> MemorySSA it can happen in other organic C++ source code too - think
>>> >> about what you're going to tell other folks who run into this issue,
>>> >> where such a workaround may be difficult to achieve or explain.
>>> >>
>>> >> -- Sanjoy
>>> >
>>> > Talked with David offline and he suggested a simple workaround
>>> > solution. For the case in MemorySSA.cpp, we have "if (a == b)" with b
>>> > being defined by a phi, and the phi has an undef operand. We can
>>> > recognize the simple pattern and give up loop unswitch for it. The
>>> > idea is not to use isGuaranteedNotToBeUndefOrPoison to prove
>>> > correctness, but just to rule out some patterns where such error may
>>> > appear.
>>> >
>>> > I admit the solution is far from ideal, but at least it is very simple
>>> > to implement, and serves to mitigate the immediate correctness issue
>>> > while avoiding performance regression. What do you think?
>>> >
>>> > Thanks,
>>> > Wei.
>>>
>>> I tried the idea and it worked for the simple case, but didn't work
>>> when compiling MemorySSA.cpp. That is because for the following
>>> pattern:
>>>
>>> foo(c) {
>>>   b = phi(c, undef)
>>>   t = (a == b)
>>>   loop:
>>>     if (t)
>>>   end loop
>>> }
>>>
>>> cfgsimplify will convert it to
>>> foo(c) {
>>>   b = select i1 cond i32 c, undef
>>>   t = (a == b)
>>>   loop:
>>>     if (t)
>>>   end loop
>>> }
>>>
>>> And instcombine can remove the select and generate:
>>> foo(c) {
>>>   t = (a == c)
>>>   loop:
>>>     if (t)
>>>   end loop
>>> }
>>>
>>> Now c is a param so loop unswitch kicks in. However, the argument of
>>> foo is undef too, so we run into the problem again.
>>>
>>> Wei.
>>>
>>> >
>>> >>
>>> >>>
>>> >>>>
>>> >>>>
>>> >>>> On Mon, Jul 17, 2017 at 1:37 PM, Daniel Berlin <dberlin at dberlin.org
>>> >
>>> >>>> wrote:
>>> >>>> > I think everyone agrees pretty much everything short of "Fix
>>> undef" will
>>> >>>> > not
>>> >>>> > fix the problem for good.
>>> >>>> > I think we are more trying to hide it well enough that we get the
>>> months
>>> >>>> > we
>>> >>>> > need for various folks to work on the larger proposals.
>>> >>>> > Which sucks, but not sure we have a better answer, because i
>>> don't think
>>> >>>> > we
>>> >>>> > are going to commit the freeze/etc patches tomorrow.
>>> >>>> >
>>> >>>> >
>>> >>>> > On Mon, Jul 17, 2017 at 1:34 PM, Juneyoung Lee
>>> >>>> > <juneyoung.lee at sf.snu.ac.kr>
>>> >>>> > wrote:
>>> >>>> >>
>>> >>>> >> 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
>>> >>>> >
>>> >>>> >
>>> >>>
>>> >>>
>>> >>>
>>> >>> _______________________________________________
>>> >>> LLVM Developers mailing list
>>> >>> llvm-dev at lists.llvm.org
>>> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>> >>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
>>
>>
>>
>> _______________________________________________
>> LLVM Developers mailing listllvm-dev at lists.llvm.orghttp://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>> --
>> Hal Finkel
>> Lead, Compiler Technology and Programming Languages
>> Leadership Computing Facility
>> Argonne National Laboratory
>>
>>
>
> _______________________________________________
> 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/20170723/b126716e/attachment.html>


More information about the llvm-dev mailing list