[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
Xinliang David Li via llvm-dev
llvm-dev at lists.llvm.org
Mon Jul 17 17:35:26 PDT 2017
At runtime, without the hoisting, the undef value will never be referenced,
but the speculative hoisting of the comparison introduces the real undef
reference. Another workaround is to disable such speculative LICM in the
first place. If it is hoisted, it should really be like:
if (some_cond)
t1 = (a == i)
else
t2 = undef
t = phi(t1, t2)
In this case, the condition is loop variant, so it is not possible.
David
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.
>
> >
> >>
> >>>
> >>>
> >>> 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
> >>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170717/936f9ca9/attachment-0001.html>
More information about the llvm-dev
mailing list