<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 07/14/2017 10:27 AM, Daniel Berlin
wrote:<br>
</div>
<blockquote
cite="mid:CAF4BwTVZO4E5tCOmG+NrAqHZUg-aPnwuowNR+U_26Z2tvHu3gQ@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 Thu, Jul 13, 2017 at 6:18 PM, 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="gmail-">
<p><br>
</p>
<div
class="gmail-m_6822423217570635499moz-cite-prefix">On
07/13/2017 06:40 PM, Daniel Berlin via llvm-dev
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Ah yes, it can only return one
instruction and you need two.
<div><br>
<div>
<div>NewGVN could still handle it if
instsimplify was changed to return the right
binary operators because it has
infrastructure that can handle insertion.<br>
</div>
<div>(it would need a little work).</div>
<div><br>
</div>
<div><br>
</div>
<div>(At this point, InstCombine seems to have
become worse to me than GCC's combining
infrastructure, so i'd really like to see if
we can stop putting things there. Otherwise,
we just go farther down the path of 'let's
just make everything one big graph rewrite)</div>
</div>
</div>
</div>
</blockquote>
<br>
</span> Perhaps something of a digression:<br>
<br>
My general impression is that if InstCombine were
actually doing a principled graph rewrite, then we
wouldn't have these problems.</div>
</blockquote>
<div><br>
</div>
<div>Define "these problems"?<br>
<br>
</div>
<div>:)</div>
<div>I mean, you are right it would be better in general. </div>
<div>But the notion of adding more and more graph rewrites
to a single part of the compiler, to get second/third/etc
order effects, is endless. Pretty much everything can be
expressed as a set of graph rewrites. There is no
principled stopping point. IE You have to decide what you
want each pass to do, and if you have one pass whose job
is "perform all possible graph rewrites", that pass is in
fact, your compiler :)</div>
<div><br>
</div>
<div>That's not such a bad thing, mind you, there are entire
libraries/languages centered around this (see, e.g.,
stratego, <a moz-do-not-send="true"
href="https://en.wikipedia.org/wiki/Stratego/XT">https://en.wikipedia.org/wiki/Stratego/XT</a>
and <a moz-do-not-send="true"
href="http://www.metaborg.org/en/latest/source/langdev/meta/lang/stratego/strategoxt/index.html">http://www.metaborg.org/en/latest/source/langdev/meta/lang/stratego/strategoxt/index.html</a>),
but it should be a deliberate thing.</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">e problem we have, however, is that
we have phase-ordering problems (even within the
fixed-point iteration scheme): Patterns being matched
depend on a canonical form, instructions nearly matching
those patterns might be created, and then suboptimally
consumed (i.e. further transformed), before being
subject to the canonicalizing transformation(s) that
would make the better pattern actually match.<br>
<br>
Except for TableGen'ing the whole thing, and making an
actual graph automaton to match the patterns, it's not
clear to me how to efficiently fix this </div>
</blockquote>
<div><br>
</div>
<div>That is what people used to do, make parsing grammars,
etc.</div>
<div>Stratego is also quite efficient at term rewriting,
from what i remember.<br>
</div>
</div>
</div>
</div>
</blockquote>
<br>
AFAIK, that's true.<br>
<br>
<blockquote
cite="mid:CAF4BwTVZO4E5tCOmG+NrAqHZUg-aPnwuowNR+U_26Z2tvHu3gQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<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">. In the mean time, what we've been
doing in practice, is that we have InstCombine patterns
depend on canonical forms, until we hit some
phase-ordering problem, and then we extend the pattern
in question to match some non-canonical forms. We might
do this here as well (if that's the problem here), but
at some point I suspect we'll end up redoing everything.<br>
</div>
</blockquote>
<div><br>
</div>
<div>The question i would have is "how do you know when you
are done?". As I said, pretty much everything can be
expressed as a graph transform, and the more it gets added
here, the more people want to run instcombine 50 times
because cse/gvn/you name it "doesn't do what they want".</div>
<div><br>
</div>
</div>
</div>
</div>
</blockquote>
<br>
I think you're done when you get everything that you have that fits
into a model of local transformations and that should be run to a
fixed point. Certainly an interesting question, but I suspect that
the practical answer is "what's in InstCombine." To do more in this
sense probably requires some more-general scheme (e.g. equality
saturation).<br>
<br>
-Hal<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>