<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 03:50 PM, Craig Topper
wrote:<br>
</div>
<blockquote
cite="mid:CAF7ks-OCOpt0=N+vGY6RktmptSg0HdEM5=fc2wdziMwjmM1qAA@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<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>
</blockquote>
<br>
It shouldn't. At least at this point in time, we should be able to
do this in a better way. The other problem with this transformation
for loads, besides being inefficient and seemingly over specific, is
that it is not information preserving (it sinks loads that we then
can't re-hoist). As a result, we should consider doing this later in
the pipeline (or preserving the point-of-validity information some
other way).<br>
<br>
-Hal<br>
<br>
<blockquote
cite="mid:CAF7ks-OCOpt0=N+vGY6RktmptSg0HdEM5=fc2wdziMwjmM1qAA@mail.gmail.com"
type="cite">
<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
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: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
moz-do-not-send="true"
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
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="m_1263622554119702471gmail-m_2013382646027069855gmail-"><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"
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
moz-do-not-send="true"
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
moz-do-not-send="true"
href="https://reviews.llvm.org/rL18677"
target="_blank">https://reviews.llvm.org/<wbr>rL18677</a>
/ <a moz-do-not-send="true"
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 moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org"
target="_blank">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="m_1263622554119702471gmail-m_2013382646027069855mimeAttachmentHeader"></fieldset>
<br>
<pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a moz-do-not-send="true" class="m_1263622554119702471gmail-m_2013382646027069855moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a moz-do-not-send="true" 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>
</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>
</div></div>
______________________________<wbr>_________________
LLVM Developers mailing list
<a moz-do-not-send="true" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<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>
</blockquote></div>
</div>
</blockquote>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre></body></html>