[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
Wei Mi via llvm-dev
llvm-dev at lists.llvm.org
Tue Jul 18 15:40:12 PDT 2017
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
>>>
More information about the llvm-dev
mailing list