[llvm-dev] failing to optimize boolean ops on cmps

Daniel Berlin via llvm-dev llvm-dev at lists.llvm.org
Fri Jul 14 10:53:38 PDT 2017

On Fri, Jul 14, 2017 at 10:44 AM, Sanjay Patel <spatel at rotateright.com>

> On Fri, Jul 14, 2017 at 10:54 AM, Daniel Berlin <dberlin at dberlin.org>
> wrote:
>>> 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.
>> Sure, but to point out what you certainly already know, that's almost
>> every optimization you can think of in a compiler.
>> For example, I can do PRE this way with no issue (IE generate optimal
>> results).
>> Same with reassociation, most CSE, etc.
>> 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.
>> Certainly an interesting question, but I suspect that the practical
>>> answer is "what's in InstCombine."
>> 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.
> Let me bring the discussion back to this particular example.

Sure, i'm happy to admit we've digressed pretty far :)

> 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).
Right, but it also creates new instructions which will later be subject to
more combining :)

> I see 3 possibilities (let me know if there are others):
> 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?
> Do you believe the latter will *ever* happen until we become more
stringent about instcombine?
There has to be some middle ground.

2. Medium: Take the suggestion from PR27431 ( https://bugs.llvm.org/show_
> bug.cgi?id=27431 ) to have CSE or GVN replace an inverted compare
> predicate with an xor of an existing compare. I think this would mean
> abandoning https://reviews.llvm.org/D35182 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.
> 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. :)

I'm not opposed to this, but everything i've ever seen in compilers tells
me we will beat this horse well past the point it's dead.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170714/5f7e5944/attachment.html>

More information about the llvm-dev mailing list