[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
Xinliang David Li via llvm-dev
llvm-dev at lists.llvm.org
Tue Jul 18 17:21:02 PDT 2017
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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170718/a47fed6b/attachment.html>
More information about the llvm-dev
mailing list