<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jul 18, 2017 at 4:15 PM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div bgcolor="#FFFFFF"><span class="gmail-">
<p><br>
</p>
<div class="gmail-m_3495894165902984330moz-cite-prefix">On 07/18/2017 06:03 PM, David Majnemer
via llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<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>
</blockquote>
<br></span>
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.<br>
<br>
-Hal<div><div class="gmail-h5"><br></div></div></div></blockquote><div><br></div><div>In this case, should the compiler not generate the reference to undefined value in the first place (i.e, from guarded to unguarded)? GCC also hoists the comparison a == i outside the loop, but its use is properly guarded:</div><div><br></div><div><br></div><div><div> <font face="monospace, monospace">long i, k;</font></div><div><font face="monospace, monospace"> if (hasval) {</font></div><div><font face="monospace, monospace"> i = b;</font></div><div><font face="monospace, monospace"> }</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace"> k = 0;</font></div></div><div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace"> if (hasval) {</font></div><div><font face="monospace, monospace"> t = (a == i);</font></div><div><font face="monospace, monospace"> if (t) {</font></div><div><font face="monospace, monospace"> if (i_hasval != hasval)</font></div><div><font face="monospace, monospace"> return;</font></div><div><font face="monospace, monospace"> </font></div><div><font face="monospace, monospace"> m = m + 1;</font></div><div><font face="monospace, monospace"> c = a + d + e + f;</font></div><div><font face="monospace, monospace"> return;</font></div><div><font face="monospace, monospace"> } else { /* if (t) --> false */ </font></div></div><div><font face="monospace, monospace"> do {<br> if (i_hasval != hasval)<br> return;<br> m = m + 1;<br> c = a + b;<br> i_hasval = 3;<br> k++;<br> } while (k < cnt);<br></font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace"> } else { /* if (hasval) -->false */</font></div><div><font face="monospace, monospace"><br></font></div><div><span style="font-family:monospace"> do {</span><br style="font-family:monospace"><span style="font-family:monospace"> if (i_hasval != hasval)</span><br style="font-family:monospace"><span style="font-family:monospace"> return;</span><br style="font-family:monospace"><span style="font-family:monospace"> </span><span style="font-family:monospace"> c = a + b;</span><br style="font-family:monospace"><span style="font-family:monospace"> i_hasval = 3;</span><br style="font-family:monospace"><span style="font-family:monospace"> k++;</span><br style="font-family:monospace"><span style="font-family:monospace"> } while (k < cnt);</span></div><div> }</div><div><br></div><div><br></div><div>David</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"><div bgcolor="#FFFFFF"><div><div class="gmail-h5">
<br>
<blockquote type="cite">
<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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div class="gmail-m_3495894165902984330HOEnZb">
<div class="gmail-m_3495894165902984330h5">On Mon, Jul 17, 2017 at 5:11 PM, Wei Mi
<<a href="mailto:wmi@google.com" target="_blank">wmi@google.com</a>>
wrote:<br>
> On Mon, Jul 17, 2017 at 2:09 PM, Sanjoy Das<br>
> <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.co<wbr>m</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" target="_blank">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" target="_blank">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_itera<wbr>tor>
def_path(ListIndex From) {<br>
>>>> return
make_range(def_path_iterator(t<wbr>his, 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="gmail-m_3495894165902984330HOEnZb">
<div class="gmail-m_3495894165902984330h5"><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>
______________________________<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>
</div>
</div>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset class="gmail-m_3495894165902984330mimeAttachmentHeader"></fieldset>
<br>
<pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a class="gmail-m_3495894165902984330moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a class="gmail-m_3495894165902984330moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</div></div><span class="gmail-HOEnZb"><font color="#888888"><pre class="gmail-m_3495894165902984330moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</font></span></div>
</blockquote></div><br></div></div>