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

Sanjay Patel via llvm-dev llvm-dev at lists.llvm.org
Fri Jul 14 10:44:26 PDT 2017

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. 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).

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?

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. :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170714/96d0572a/attachment.html>

More information about the llvm-dev mailing list