<div dir="ltr">The sinking in InstCombine also has a bogus single use check on the front of it. Why does it matter how many uses there are as long as they are all in the same basic block?</div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature" data-smartmail="gmail_signature">~Craig</div></div>
<br><div class="gmail_quote">On Mon, Sep 11, 2017 at 1:32 PM, Sean Silva 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 dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="h5">On Mon, Sep 11, 2017 at 9:48 AM, 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="m_1263622554119702471gmail-">
<p><br>
</p>
<div class="m_1263622554119702471gmail-m_2013382646027069855moz-cite-prefix">On 09/11/2017 10:50 AM, Sean Silva via
llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Mon, Sep 11, 2017 at 8:14 AM,
Daniel Neilson 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"><br>
Just thinking out loud…. I’m really not familiar with the
vast majority of what instcombine does, so please excuse
me if my naiveté is too obvious. I can’t help but notice
all of the uses of ‘and’ in Daniel B’s description of what
instcombine is right now:<br>
<span class="m_1263622554119702471gmail-m_2013382646027069855gmail-"><br>
> On Sep 8, 2017, at 11:27 PM, Daniel Berlin via
llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>
wrote:<br>
><br>
> FWIW, Before getting to "how to do it", I think
InstCombine needs an actual goal.<br>
> Right now it's "do a bunch of instruction
combination and canonicalization and random kinds of
semi-local optimization with some weird analysis and
other stuff in the middle.<br>
> Iterate this as hard as we can"<br>
> Nobody can really draw any real dividing line for
what should be there or not except based on how easy or
expensive it is to shove it in.<br>
> That's a recipe for pass creep.<br>
<br>
</span>This makes me wonder… is it sensible to be talking
about splitting up instcombine into multiple separate
passes? Would such a thing even be possible? For example,
split by functionality into separate passes that each do
one of:<br>
* instruction combinations<br>
* canonicalization<br>
* semi-local optimizations<br>
* etc…<br>
</blockquote>
</div>
</div>
</div>
</blockquote>
<br></span>
The problem is that all of these are really the same thing. Almost
all canonicalizations are also simplifications, the common
underlying factor being that they're mostly-local transformations
that likely enable other optimizations.<span class="m_1263622554119702471gmail-"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<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">
<br>
Or something like that.<br>
<br>
As separate passes, each would probably have a natural
way to be implemented effectively and those
implementations might vary.<br>
</blockquote>
<div><br>
</div>
<div>One obstacle to that is that currently instcombine has
an internal fixed-point iteration that it does.</div>
<div><br>
</div>
<div>So when splitting it into separate passes we would need
to either add fixed-point iteration to the pass manager
running the separate instcombine passes (extending the
pass management in this way is doable and has been
explored in the past, e.g. <a href="https://www.youtube.com/watch?v=c7iP43an5_Q" target="_blank">https://www.youtube.com/watch?<wbr>v=c7iP43an5_Q</a>
) or demonstrate/measure that we don't regress without the
fixed-point iteration across separate instcombine passes.</div>
</div>
</div>
</div>
</blockquote>
<br></span>
I agree, but I'll add that I view the fixed-point iteration here to
be an asset. It increases the robustness and consistency of the
compiler, and allows later passes to depend on the canonicalization
(*) without worrying about phase-ordering effects (**).<br>
<br>
(*) In my experience, the largest problem we have in this regard is
our lack of documentation on what our canonical form is.<br>
(**) To be clear, we still have phase-ordering effects within
InstCombine. Using a better system for dealing with the rewriting
rules, I hope, will help. Nevertheless, these effects are much rarer
than if we ran InstCombine only as discrete passe. <br>
<br>
I'd like to see us do more fixed-point iteration in our optimization
pipeline, and our past work has shown this would be practical (i.e.,
only a few iterations will be needed in practice), but even that
won't remove the advantages of using a fixed-point iteration within
InstCombine.<br>
<br>
Regardless, I think that if we had a model for what InstCombine did
(i.e., as a graph-rewriting system), then it would be clear what
could be part of that system and what couldn't. Otherwise, I think
that the real challenge here is figuring out the underlying
structural foundations to make the process efficient and sound.</div></blockquote><div><br></div></div></div><div>As a data point for this, I did a quick walkthrough of the top-level of instcombine, and one thing that stuck out to me is that it tries to sink instructions in certain "easy" scenarios. That doesn't fit a graph rewriting system.</div><div><br></div><div>As a side note, TryToSinkInstruction does a whole-BB scan to check safety for sinking loads, which will go quadratic (in the number of loads) on an input like:</div><div><br></div><div>```</div><div><div>void use(int);</div><div>void foo(int *p, int *q, bool b) {</div><div>int p0 = p[0];</div><div>int p1 = p[1];</div><div>int p2 = p[2];</div><div>int p3 = p[3];</div><div>if (b) {</div><div>use(p0);</div><div>use(p1);</div><div>use(p2);</div><div>use(p3);</div><div>}</div><div>}</div></div><div>```</div><div>(script attached)</div><div><br></div><div>The commit where it was introduced (<a href="https://reviews.llvm.org/rL18677" target="_blank">https://reviews.llvm.org/<wbr>rL18677</a> / <a href="https://reviews.llvm.org/rL18692" target="_blank">https://reviews.llvm.org/<wbr>rL18692</a> yes that's from 2004) indicated that it actually caught a bunch of cases in SPEC, but it isn't clear that it's really providing much value integrated into the fixed-point iteration compared to an appropriate standalone global code motion pass (which would not have the quadratic complexity and would be more general to boot).</div><div><br></div><div>-- Sean Silva</div><span class=""><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"><span class="m_1263622554119702471gmail-HOEnZb"><font color="#888888"><br>
<br>
-Hal</font></span><span class="m_1263622554119702471gmail-"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>-- Sean Silva</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">
<br>
-Daniel<br>
<br>
---<br>
Daniel Neilson, Ph.D.<br>
Azul Systems<br>
<div class="m_1263622554119702471gmail-m_2013382646027069855gmail-HOEnZb">
<div class="m_1263622554119702471gmail-m_2013382646027069855gmail-h5"><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>
</div>
<br>
<fieldset class="m_1263622554119702471gmail-m_2013382646027069855mimeAttachmentHeader"></fieldset>
<br>
<pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a class="m_1263622554119702471gmail-m_2013382646027069855moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a class="m_1263622554119702471gmail-m_2013382646027069855moz-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>
</span><span class="m_1263622554119702471gmail-"><pre class="m_1263622554119702471gmail-m_2013382646027069855moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</span></div>
</blockquote></span></div><br></div></div>
<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></blockquote></div><br></div>