<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 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 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 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><br> </div></div></div></div>