<div dir="ltr">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...<div><br></div><div>Given what I've seen in LLVM (and what I've learned from other compilers), we probably have two choices:</div><div>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.</div><div>2. Keep undef as a constant, introduce freeze. Churn would mostly be restricted to correctness fixes instead of to core IR representation.</div><div><br></div><div>Note that option #1 is basically a short-hand for freeze(undef).</div><div><br></div><div>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.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jul 18, 2017 at 3:40 PM, Wei Mi via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On Mon, Jul 17, 2017 at 5:11 PM, Wei Mi <<a href="mailto:wmi@google.com">wmi@google.com</a>> wrote:<br>
> On Mon, Jul 17, 2017 at 2:09 PM, Sanjoy Das<br>
> <<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.<wbr>com</a>> wrote:<br>
>> Hi,<br>
>><br>
>> On Mon, Jul 17, 2017 at 1:56 PM, Daniel Berlin via llvm-dev<br>
>> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
>>><br>
>>><br>
>>> On Mon, Jul 17, 2017 at 1:53 PM, Wei Mi <<a href="mailto:wmi@google.com">wmi@google.com</a>> wrote:<br>
>>>><br>
>>>> It seems MemorySSA.cpp is the only real code where we found the<br>
>>>> problem happening.<br>
>>><br>
>>><br>
>>> This is doubtful, ¸FWIW :)<br>
>>><br>
>>>><br>
>>>> Is it possible to change the source of<br>
>>>> MemorySSA.cpp to hide the problem and buy some time for now? Now we<br>
>>>> use an empty generic_def_path_iterator with Optional<ListIndex> N<br>
>>>> being initialized by None as the end of range. Can we initialize the<br>
>>>> Optional var with a special value instead of None?<br>
>>>><br>
>>>> iterator_range<def_path_<wbr>iterator> def_path(ListIndex From) {<br>
>>>> return make_range(def_path_iterator(<wbr>this, From), def_path_iterator());<br>
>>>> }<br>
>>>><br>
>>><br>
>>> Why does this work?<br>
>><br>
>> Fwiw, I don't think this is a good idea. If it can happen in<br>
>> MemorySSA it can happen in other organic C++ source code too - think<br>
>> about what you're going to tell other folks who run into this issue,<br>
>> where such a workaround may be difficult to achieve or explain.<br>
>><br>
>> -- Sanjoy<br>
><br>
> Talked with David offline and he suggested a simple workaround<br>
> solution. For the case in MemorySSA.cpp, we have "if (a == b)" with b<br>
> being defined by a phi, and the phi has an undef operand. We can<br>
> recognize the simple pattern and give up loop unswitch for it. The<br>
> idea is not to use isGuaranteedNotToBeUndefOrPois<wbr>on to prove<br>
> correctness, but just to rule out some patterns where such error may<br>
> appear.<br>
><br>
> I admit the solution is far from ideal, but at least it is very simple<br>
> to implement, and serves to mitigate the immediate correctness issue<br>
> while avoiding performance regression. What do you think?<br>
><br>
> Thanks,<br>
> Wei.<br>
<br>
</div></div>I tried the idea and it worked for the simple case, but didn't work<br>
when compiling MemorySSA.cpp. That is because for the following<br>
pattern:<br>
<br>
foo(c) {<br>
b = phi(c, undef)<br>
t = (a == b)<br>
loop:<br>
if (t)<br>
end loop<br>
}<br>
<br>
cfgsimplify will convert it to<br>
foo(c) {<br>
b = select i1 cond i32 c, undef<br>
t = (a == b)<br>
loop:<br>
if (t)<br>
end loop<br>
}<br>
<br>
And instcombine can remove the select and generate:<br>
foo(c) {<br>
t = (a == c)<br>
loop:<br>
if (t)<br>
end loop<br>
}<br>
<br>
Now c is a param so loop unswitch kicks in. However, the argument of<br>
foo is undef too, so we run into the problem again.<br>
<div class="HOEnZb"><div class="h5"><br>
Wei.<br>
<br>
><br>
>><br>
>>><br>
>>>><br>
>>>><br>
>>>> On Mon, Jul 17, 2017 at 1:37 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>><br>
>>>> wrote:<br>
>>>> > I think everyone agrees pretty much everything short of "Fix undef" will<br>
>>>> > not<br>
>>>> > fix the problem for good.<br>
>>>> > I think we are more trying to hide it well enough that we get the months<br>
>>>> > we<br>
>>>> > need for various folks to work on the larger proposals.<br>
>>>> > Which sucks, but not sure we have a better answer, because i don't think<br>
>>>> > we<br>
>>>> > are going to commit the freeze/etc patches tomorrow.<br>
>>>> ><br>
>>>> ><br>
>>>> > On Mon, Jul 17, 2017 at 1:34 PM, Juneyoung Lee<br>
>>>> > <<a href="mailto:juneyoung.lee@sf.snu.ac.kr">juneyoung.lee@sf.snu.ac.kr</a>><br>
>>>> > wrote:<br>
>>>> >><br>
>>>> >> Hello, some of the patches had conflicts with LLVM head, so I updated<br>
>>>> >> them. If you experienced patch failure before then you can try it<br>
>>>> >> again.<br>
>>>> >><br>
>>>> >> I compiled your code (1.c) with LLVM r308173 with the 5 patches<br>
>>>> >> applied,<br>
>>>> >> and it generated assembly like this. Now it contains store to c(%rip).<br>
>>>> >> It tries to store a(%rip) + b(%rip) to c(%rip). I wish this translation<br>
>>>> >> is<br>
>>>> >> now correct.<br>
>>>> >><br>
>>>> >> ```<br>
>>>> >> 73 .globl hoo # -- Begin function hoo<br>
>>>> >> 74 .p2align 4, 0x90<br>
>>>> >> 75 .type hoo,@function<br>
>>>> >> 76 hoo: # @hoo<br>
>>>> >> 77 .cfi_startproc<br>
>>>> >> 78 # BB#0:<br>
>>>> >> 79 movq a(%rip), %rax<br>
>>>> >> 80 movq cnt(%rip), %rcx<br>
>>>> >> 81 cmpq $0, i_hasval(%rip)<br>
>>>> >> 82 sete %sil<br>
>>>> >> 83 xorl %edx, %edx<br>
>>>> >> 84 .p2align 4, 0x90<br>
>>>> >> 85 .LBB1_1: # =>This Inner Loop Header:<br>
>>>> >> Depth=1<br>
>>>> >> 86 testb $1, %sil<br>
>>>> >> 87 je .LBB1_3<br>
>>>> >> 88 # BB#2: # in Loop: Header=BB1_1<br>
>>>> >> Depth=1<br>
>>>> >> 89 movq b(%rip), %rsi<br>
>>>> >> 90 addq %rax, %rsi<br>
>>>> >> 91 movq %rsi, c(%rip)<br>
>>>> >> 92 movq $3, i_hasval(%rip)<br>
>>>> >> 93 incq %rdx<br>
>>>> >> 94 xorl %esi, %esi<br>
>>>> >> 95 cmpq %rcx, %rdx<br>
>>>> >> 96 jl .LBB1_1<br>
>>>> >> 97 .LBB1_3:<br>
>>>> >> 98 retq<br>
>>>> >> ```<br>
>>>> >><br>
>>>> >> IMHO, enhancing `<wbr>isGuaranteedNotToBeUndefOrPois<wbr>on` and using it as a<br>
>>>> >> precondition in loop unswitching is<br>
>>>> >> not enough. undef (and poison) value can be stored into memory, and<br>
>>>> >> also<br>
>>>> >> be passed by a function argument.<br>
>>>> >> `<wbr>isGuaranteedNotToBeUndefOrPois<wbr>on` will virtually return `false` for<br>
>>>> >> all<br>
>>>> >> cases except the value is<br>
>>>> >> some integer constant. Sanjoy's suggestion might be helpful (if I<br>
>>>> >> understood correctly), but I'm<br>
>>>> >> not sure how much it will be.<br>
>>>> >><br>
>>>> >> Best Regards,<br>
>>>> >> Juneyoung Lee<br>
>>>> >><br>
>>>> >> On Tue, Jul 18, 2017 at 3:43 AM, Sanjoy Das via llvm-dev<br>
>>>> >> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
>>>> >>><br>
>>>> >>> On Mon, Jul 17, 2017 at 11:21 AM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>><br>
>>>> >>> wrote:<br>
>>>> >>> >> On Mon, Jul 17, 2017 at 10:32 AM, Xinliang David Li<br>
>>>> >>> >> <<a href="mailto:davidxl@google.com">davidxl@google.com</a>><br>
>>>> >>> >> wrote:<br>
>>>> >>> >> > The issue blocks another optimization patch and Wei has spent<br>
>>>> >>> >> > huge<br>
>>>> >>> >> > amount of<br>
>>>> >>> >> > effort isolating the the bootstrap failure to this same problem.<br>
>>>> >>> >> > I<br>
>>>> >>> >> > agree<br>
>>>> >>> >> > with Wei that other developers may also get hit by the same issue<br>
>>>> >>> >> > and<br>
>>>> >>> >> > the<br>
>>>> >>> >> > cost of leaving this issue open for long can be very high to the<br>
>>>> >>> >> > community.<br>
>>>> >>> >><br>
>>>> >>> >> I can't speak for others, but I am fine with adding a workaround<br>
>>>> >>> >> for<br>
>>>> >>> >> this. However, I suspect isGuaranteedNotToBeUndefOrPois<wbr>on in<br>
>>>> >>> >> LoopUnswitch may regress other benchmarks.<br>
>>>> >>> ><br>
>>>> >>> > Any other thoughts on a more minimal fix?<br>
>>>> >>><br>
>>>> >>> I can't think of any good answers here.<br>
>>>> >>><br>
>>>> >>> The semantic we want is "branching on poison or undef is undefined<br>
>>>> >>> behavior" (which lets us do propagateEquality). Given that, we could<br>
>>>> >>> be clever about implementing isGuaranteedNotToBeUndefOrPois<wbr>on; for<br>
>>>> >>> instance if we have:<br>
>>>> >>><br>
>>>> >>> do {<br>
>>>> >>> if (a != b) {<br>
>>>> >>> ...<br>
>>>> >>> }<br>
>>>> >>> } while (...);<br>
>>>> >>><br>
>>>> >>> then we can use post-domination to prove that "a != b" is not undef<br>
>>>> >>> (otherwise the loop is guaranteed to have undefined behavior).<br>
>>>> >>><br>
>>>> >>> (I hate to say this), a more aggressive fix is to introduce a "freeze"<br>
>>>> >>> intrinsic that freezes only an i1. LoopUnswitch would wrap the loop<br>
>>>> >>> invariant condition in this after hoisting the branch. This would be<br>
>>>> >>> a poor man's version of the more invasive patches Juneyoung already<br>
>>>> >>> has developed.<br>
>>>> >>><br>
>>>> >>> -- Sanjoy<br>
>>>> >>> ______________________________<wbr>_________________<br>
>>>> >>> LLVM Developers mailing list<br>
>>>> >>> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
>>>> >>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
>>>> >><br>
>>>> >><br>
>>>> >><br>
>>>> >><br>
>>>> >> --<br>
>>>> >><br>
>>>> >> Juneyoung Lee<br>
>>>> >> Software Foundation Lab, Seoul National University<br>
>>>> ><br>
>>>> ><br>
>>><br>
>>><br>
>>><br>
>>> ______________________________<wbr>_________________<br>
>>> LLVM Developers mailing list<br>
>>> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
>>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
>>><br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div>