<div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="gmail-m_-6762133072327193080HOEnZb"><div class="gmail-m_-6762133072327193080h5"><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></blockquote><div><br></div><div><br></div><div>Fundamentally, as already discussed thoroughly, the problem is caused by eager hoisting of non-executed predicate (involving undef) by the loop unswitching, so if the use of SELECT output is in a compare (may be speculated hoisted), it is not safe to simplify 'select cond, c, undef' into 'c', unless there is a way in IR to annotate such simplified value (a bit indicating the potential undef source). If it turns out to be a performance problem, the simplification can be delayed until very late, for instance in CGP. Can you try that with your unswitch patch to see if it works end-to-end? Other problems may be exposed too though.</div><div><br></div><div>thanks,</div><div><br></div><div>David</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
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="gmail-m_-6762133072327193080HOEnZb"><div class="gmail-m_-6762133072327193080h5"><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" target="_blank">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" target="_blank">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 `isGuaranteedNotToBeUndefOrPoi<wbr>son` 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>
>>>> >> `isGuaranteedNotToBeUndefOrPoi<wbr>son` 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" target="_blank">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" target="_blank">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" target="_blank">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" target="_blank">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" target="_blank">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>
</div></div></blockquote></div><br></div></div>