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

Hal Finkel via llvm-dev llvm-dev at lists.llvm.org
Fri Jul 14 11:22:36 PDT 2017

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 



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>

More information about the llvm-dev mailing list