<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">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="gmail-">
<p><br>
</p>
<div class="gmail-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="gmail-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="gmail-"><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>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">https://reviews.llvm.org/rL18677</a> / <a href="https://reviews.llvm.org/rL18692">https://reviews.llvm.org/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><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="gmail-HOEnZb"><font color="#888888"><br>
<br>
-Hal</font></span><span class="gmail-"><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="gmail-m_2013382646027069855gmail-HOEnZb">
<div class="gmail-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="gmail-m_2013382646027069855mimeAttachmentHeader"></fieldset>
<br>
<pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a class="gmail-m_2013382646027069855moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a class="gmail-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="gmail-"><pre class="gmail-m_2013382646027069855moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</span></div>
</blockquote></div><br></div></div>