[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
Wei Mi via llvm-dev
llvm-dev at lists.llvm.org
Mon Jul 17 14:14:12 PDT 2017
On Mon, Jul 17, 2017 at 1:56 PM, Daniel Berlin <dberlin at dberlin.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?
Because condition "a == b" being loop unswitched described in the
problem above is generated from (*N == *O.N) below.
template <typename T, typename Walker>
struct generic_def_path_iterator
...
bool operator==(const generic_def_path_iterator &O) const {
if (N.hasValue() != O.N.hasValue())
return false;
return !N.hasValue() || *N == *O.N;
}
}
The outer loop is generated by the find_if below. It is trying to
compare current iterator with the end of range and see if the
searching has been finished.
// Find the node we started at. We can't search based on N->Last, since
// we may have gone around a loop with a different MemoryLocation.
auto Iter = find_if(def_path(Blocker->LastNode), [&](const DefPath &N) {
return defPathIndex(N) < PriorPathsSize;
});
And we use an empty iterator as the end of range. The
optional<ListIndex> N in struct generic_def_path_iterator contains
undef data field when it is initialized by None.
iterator_range<def_path_iterator> def_path(ListIndex From) {
return make_range(def_path_iterator(this, From), def_path_iterator());
}
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
>> >
>> >
>
>
More information about the llvm-dev
mailing list