[llvm-dev] Missed optimization of bitwise expressions

[Sanjay Patel via llvm-dev]

 >> A | B | ~(A ^ B) --> -1

I added that one with:
https://reviews.llvm.org/rG4b30076f16fc

>> (A & B) ^ A --> A & ~B // perhaps this is not considered profitable?

If the 'and' has one use, we do prefer the form with 'not' because it
removes a use of 'A', it's better for analysis, and it's likely better for
codegen since multiple targets have an 'andn' instruction.
https://alive2.llvm.org/ce/z/yRpTcD

But in the larger example, the 'and' has an extra use, so we need to match
a longer pattern to see that the whole thing can be reduced.

On Wed, Dec 1, 2021 at 5:19 PM Mehrnoosh Heidarpour <
mehrnoosh.heidarpour at huawei.com> wrote:

> Hi Jay,
>
> Thank you for new missing simplifications!
> I will try to post new patches for these cases in the following days.
>
> About the last one in the missing cases, I think your comments are exactly
> the reason for missing this simplification opportunity;
>
> Thanks,
> Mehrnoosh
>
>
> -----Original Message-----
> From: Jay Foad [mailto:jay.foad at gmail.com]
> Sent: November 29, 2021 12:08 PM
> To: Sanjay Patel <spatel at rotateright.com>; Mehrnoosh Heidarpour <
> mehrnoosh.heidarpour at huawei.com>
> Cc: LLVM Developers Mailing List <llvm-dev at lists.llvm.org>; Stanislav
> Mekhanoshin <Stanislav.Mekhanoshin at amd.com>
> Subject: Re: Missed optimization of bitwise expressions
>
> Now that that one is fixed (thanks!) my script can't find any more cases
> that we fail to optimize where the input has two variables and three
> instructions.
>
> Moving on to the two-variable four-instruction cases, there are various
> missing simplifications like:
>
> A | B | ~(A ^ B) --> -1
> (A ^ B) & (~A | B) --> ~A & B
> (((A | B) ^ B) & A) ^ (A | B) --> B
> (((A & B) ^ A) & B) | (A & B) --> A & B
>
> Taking the last of these as an example:
> https://alive2.llvm.org/ce/z/wZtbjM
> I'm surprised that we don't simplify it in stages:
> 1. (A & B) ^ A --> A & ~B // perhaps this is not considered profitable?
> 2. (A & ~B) & B --> 0 // perhaps we don't manage to reassociate this to
> see that it contains B & ~B ?
> 3. 0 | (A & B) --> A & B
>
> Jay.
>
> On Tue, 16 Nov 2021 at 09:09, Jay Foad <jay.foad at gmail.com> wrote:
> >
> > Thanks for the fixes so far! Here's another simple two variable case:
> >
> > https://bugs.llvm.org/show_bug.cgi?id=52518 "[InstCombine] Failure to
> > simplify (~A|B)^A --> ~(A&B)"
> >
> >
> > Jay.
> >
> > On Thu, 11 Nov 2021 at 19:59, Jay Foad <jay.foad at gmail.com> wrote:
> > >
> > > OK, I've filed the first couple of beginner bugs:
> > > https://bugs.llvm.org/show_bug.cgi?id=52478
> > > https://bugs.llvm.org/show_bug.cgi?id=52479
> > >
> > > Thanks,
> > > Jay.
> > >
> > > On Thu, 11 Nov 2021 at 16:35, Sanjay Patel <spatel at rotateright.com>
> wrote:
> > > >
> > > > Nice test program! I don't know python well enough to understand
> > > > that yet, but no reason to be ashamed of hacks. :)
> > > >
> > > > If we're missing 2 variable logic reductions, those are common/easy
> enough that we should have those in instcombine. So yes, it would be great
> if you file bugs for those, and they could be marked with the 'beginner'
> keyword too as a potential easy patch for newcomers to LLVM.
> > > >
> > > > There's also a set of recent patch proposals for 3 variable logic
> reductions -- for example, https://reviews.llvm.org/D112276 -- these were
> inspired by a logic lookup table function as discussed in the comments.
> > > > The extra-use and commuted variations make these harder. IMO, this
> is where there should be a dedicated pass/solver for logic folds if we want
> those optimizations to be complete. Otherwise, there's an explosion of
> possible pattern match combinations.
> > > >
> > > >
> > > > On Thu, Nov 11, 2021 at 6:34 AM Jay Foad <jay.foad at gmail.com> wrote:
> > > >>
> > > >> Hi,
> > > >>
> > > >> I tried searching for small bitwise expressions using AND OR XOR
> > > >> and NOT that "opt -O3" fails to optimize to a simpler form. For
> example:
> > > >>
> > > >> (A^B)|~A --> ~(A&B)
> > > >> https://alive2.llvm.org/ce/z/HpWfzp
> > > >>
> > > >> A|B|(A^B) --> A|B
> > > >> https://alive2.llvm.org/ce/z/UCC6uM
> > > >>
> > > >> ((A|B)^C)&A --> A&~C (actually I don't understand why this one is
> > > >> OK, even if B might be poison, but alive2 says it is OK)
> > > >> https://alive2.llvm.org/ce/z/mkvW6p
> > > >>
> > > >> I can file bugs for specific examples but I wondered if there was
> > > >> any interest in a more systematic approach to finding these
> > > >> missed optimizations? My approach was to write some very hacky
> > > >> Python
> > > >> (https://gist.github.com/jayfoad/94f4c68fa3a9aa908db79dbd7e9df80d
> > > >> , please don't read it) to exhaustively generate programs; then
> > > >> take all the programs with a given truth table, run them all
> > > >> through "opt -O3", and check that they all got optimized to the
> > > >> same (or at least equally
> > > >> short) output.
> > > >>
> > > >> Thanks,
> > > >> Jay.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20211202/b8d698c6/attachment.html>