llvm dev - Jul 2017 - failing to optimize boolean ops on cmps

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>

On Fri, Jul 14, 2017 at 10:44 AM, Sanjay Patel <spatel at rotateright.com>
wrote:
>
>
> 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>

On 07/14/2017 12:44 PM, Sanjay Patel wrote:
>
>
> On Fri, Jul 14, 2017 at 10:54 AM, Daniel Berlin <dberlin at dberlin.org 
> <mailto: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. :)
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.

  -Hal
>
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170714/0a619002/attachment.html>

>
>
> 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.
>
FWIW: My problem is, when put in this framework, we will repeatedly make
this same decision, this same way, again and again, and never actually get
even started on fixing it :)

IE "it's just another small patch!"
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170714/8ae964ac/attachment.html>