<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 07/14/2017 12:44 PM, Sanjay Patel
wrote:<br>
</div>
<blockquote
cite="mid:CA+wODiuCX6Qnq=NGDMNwo5-WfeDAjsXt+4hArh562Bv7FtaF3g@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 Fri, Jul 14, 2017 at 10:54 AM,
Daniel Berlin <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.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 dir="ltr">
<div class="gmail_extra"><br>
<div class="gmail_quote"><span class="gmail-">
<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><br>
</span> 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. </div>
</blockquote>
<div><br>
</div>
</span>
<div>Sure, but to point out what you certainly
already know, that's almost every optimization you
can think of in a compiler.</div>
<div>For example, I can do PRE this way with no
issue (IE generate optimal results).<br>
</div>
<div>Same with reassociation, most CSE, etc.</div>
<div><br>
</div>
<div>A very large set of global stuff can be done by
"local transform repeated until fixpoint is
reached". It's just not optimal time-wise.</div>
<span class="gmail-">
<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">Certainly an interesting
question, but I suspect that the practical
answer is "what's in InstCombine."</div>
</blockquote>
<div><br>
</div>
</span>
<div>At least to me, that's clearly the wrong
answer, because instcombine already does a lot of
non-local stuff that could be done better
elsewhere.</div>
<span class="gmail-"></span></div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>Let me bring the discussion back to this particular
example. This *is* a local optimization; it's the most
basic 2-variable boolean logic optimization that's not an
instsimplify (where we return a constant or an existing
value).<br>
<br>
</div>
<div>I see 3 possibilities (let me know if there are
others):<br>
</div>
<div>1. Hard: Declare instcombine bankrupt and closed for
business because it has already gone over the cliff. We
should not add the new matcher type. We should go further
and remove the existing combine [ ((~A & B) | A) ->
(A | B) ] too because that's the responsibility of some
other pass. This might be the best theoretical solution,
but practically impossible until someone reinvents
instcombine as multiple different passes that have the
same optimization power that we have today?<br>
</div>
<div><br>
</div>
<div>2. Medium: Take the suggestion from PR27431 ( <a
moz-do-not-send="true"
href="https://bugs.llvm.org/show_bug.cgi?id=27431">https://bugs.llvm.org/show_bug.cgi?id=27431</a>
) to have CSE or GVN replace an inverted compare predicate
with an xor of an existing compare. I think this would
mean abandoning <a moz-do-not-send="true"
href="https://reviews.llvm.org/D35182">https://reviews.llvm.org/D35182</a>
and maybe removing that transform altogether to avoid
conflicting with the expected canonical form that includes
an xor. How this plays out with the rest of instcombine's
existing folds and other IR transforms is not clear to me
yet.<br>
<br>
</div>
<div>3. Easy: Add the new matcher and use it. It's then one
2-line patch after another to ensure that instcombine
won't miss these pattern variants no matter what form they
come in with. We acknowledge the added mass to
instcombine, but live with it for the perf gains...and
wait for the now better-performing machines to rewrite the
whole thing for us. :)<br>
</div>
</div>
</div>
</div>
</blockquote>
<br>
Not sure about this last part. It is really going to require work by
us to rewrite things. :-) In the mean time, I think we should go
ahead with this.<br>
<br>
-Hal<br>
<br>
<blockquote
cite="mid:CA+wODiuCX6Qnq=NGDMNwo5-WfeDAjsXt+4hArh562Bv7FtaF3g@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
</div>
</div>
</div>
</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>