[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
Hal Finkel via llvm-dev
llvm-dev at lists.llvm.org
Tue Jul 18 16:15:26 PDT 2017
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
>
> On Tue, Jul 18, 2017 at 3:40 PM, Wei Mi via llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>
> On Mon, Jul 17, 2017 at 5:11 PM, Wei Mi <wmi at google.com
> <mailto:wmi at google.com>> wrote:
> > On Mon, Jul 17, 2017 at 2:09 PM, Sanjoy Das
> > <sanjoy at playingwithpointers.com
> <mailto: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 <mailto:llvm-dev at lists.llvm.org>> wrote:
> >>>
> >>>
> >>> On Mon, Jul 17, 2017 at 1:53 PM, Wei Mi <wmi at google.com
> <mailto: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 <mailto: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
> <mailto: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 <mailto:llvm-dev at lists.llvm.org>>
> wrote:
> >>>> >>>
> >>>> >>> On Mon, Jul 17, 2017 at 11:21 AM, Daniel Berlin
> <dberlin at dberlin.org <mailto:dberlin at dberlin.org>>
> >>>> >>> wrote:
> >>>> >>> >> On Mon, Jul 17, 2017 at 10:32 AM, Xinliang David Li
> >>>> >>> >> <davidxl at google.com <mailto: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 <mailto:llvm-dev at lists.llvm.org>
> >>>> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> <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 <mailto:llvm-dev at lists.llvm.org>
> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> >>>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> <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
--
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/dd276f0e/attachment.html>
More information about the llvm-dev
mailing list