<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Sep 11, 2017 at 9:48 AM, Hal Finkel 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 bgcolor="#FFFFFF"><span class="gmail-">
<p><br>
</p>
<div class="gmail-m_-6448026609262279667moz-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_-6448026609262279667gmail-"><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></div></blockquote><div>FWIW: I completely agree. At least as you are using it here, which is in the sense of "system is built to apply a set of transformation. Fixed point iteration ensures that all such transformations that can occur, do, even if they are only exposed as a result of earlier transformations".</div><div><br></div><div>In that sense, a vast majority of our passes do or should be using fixed point iteration. </div><div>The usual concern is cost, and it requires careful engineering (as you say below) to ensure you are doing this in an effective manner. IE ad-hoc solutions work but rarely scale, it requires a good understanding of theory and engineering to get something that will scale really well and work well</div><div><br></div><div>Integrating multiple transformations/capabilities into a single pass is much trickier than one would expect. You can easily screw stuff up by doing things you think might only improve things.<br></div><div><br></div><div>A simple example from value numbering <a href="https://pastebin.com/Tp11bfCa">https://pastebin.com/Tp11bfCa</a></div><div><br></div><div>Note that if we ignore unreachable edges at first and just shove it in the algorithm, we no longer get optimal answers in certain cases. Even though we only changed exactly one initial state, and we're trying to make things better! </div><div>This is fixable, but requires a lot of thought to see that this will happen in the first case.</div><div><br></div><div>(the reason in this case is because the algorithm relies on the TOP state to resolve cycles. There is no perfect comes-before iteration ordering in this case. By changing the initial state that fed the cycle, without resetting that cycle to TOP, it can no longer resolve the cycle to the optimal answer. )</div><div><br></div><div><br></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"><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></div></blockquote><div><br></div><div>Completely agree on this </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">
<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.<br></div></blockquote><div><br></div><div>Also completely agree.</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">
<br>
-Hal<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_-6448026609262279667gmail-HOEnZb">
<div class="gmail-m_-6448026609262279667gmail-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_-6448026609262279667mimeAttachmentHeader"></fieldset>
<br>
<pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a class="gmail-m_-6448026609262279667moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a class="gmail-m_-6448026609262279667moz-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_-6448026609262279667moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</span></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></div>