<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 09/11/2017 10:50 AM, Sean Silva via
llvm-dev wrote:<br>
</div>
<blockquote
cite="mid:CAHnXoan7mnPDHzD6nd6aTBwx9DZP=cSwkL3hvk-Qdj2+jBYmug@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<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
moz-do-not-send="true"
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-"><br>
> On Sep 8, 2017, at 11:27 PM, Daniel Berlin via
llvm-dev <<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org">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>
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.<br>
<br>
<blockquote
cite="mid:CAHnXoan7mnPDHzD6nd6aTBwx9DZP=cSwkL3hvk-Qdj2+jBYmug@mail.gmail.com"
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 moz-do-not-send="true"
href="https://www.youtube.com/watch?v=c7iP43an5_Q">https://www.youtube.com/watch?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>
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.<br>
<br>
-Hal<br>
<br>
<blockquote
cite="mid:CAHnXoan7mnPDHzD6nd6aTBwx9DZP=cSwkL3hvk-Qdj2+jBYmug@mail.gmail.com"
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-HOEnZb">
<div class="gmail-h5"><br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a moz-do-not-send="true"
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="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>