'Re: [llvm-dev] Missed optimization of bitwise expressions'

[prev in list] [next in list] [prev in thread] [next in thread] 

List:       llvm-dev
Subject:    Re: [llvm-dev] Missed optimization of bitwise expressions
From:       Jay Foad via llvm-dev <llvm-dev () lists ! llvm ! org>
Date:       2021-12-23 15:34:48
Message-ID: CANd1uZ=Lue-8RnufybzQ98qVzHatMXzcvBkSUQ6RRTd85wvCLw () mail ! gmail ! com
[Download RAW message or body]

Thanks for the latest fixes!

Here are the simplest two-variable cases I can find that still fail to simplify:

~(A & B) | (A ^ B) --> ~(A & B) // https://alive2.llvm.org/ce/z/-jzu59
A ^ B ^ (~A & B) --> A & ~B // https://alive2.llvm.org/ce/z/urNC2y
(A ^ B) & (A | ~B) --> A & ~B // https://alive2.llvm.org/ce/z/33AjHg

Jay.

On Thu, 2 Dec 2021 at 15:55, Jay Foad <jay.foad@gmail.com> wrote:
> 
> > > > A | B | ~(A ^ B) --> -1
> > 
> > I added that one with:
> > https://reviews.llvm.org/rG4b30076f16fc
> 
> Thanks! Here are some more cases that should simplify to 0 or -1:
> 
> ((A | B) ^ A) & ((A | B) ^ B) --> 0 // https://alive2.llvm.org/ce/z/AjkF-5
> (A ^ B) | (~A | B) --> -1 // https://alive2.llvm.org/ce/z/QNfhLP
> 
> Jay.
> 
> On Thu, 2 Dec 2021 at 14:06, Sanjay Patel <spatel@rotateright.com> wrote:
> > 
> > > > 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@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@gmail.com]
> > > Sent: November 29, 2021 12:08 PM
> > > To: Sanjay Patel <spatel@rotateright.com>; Mehrnoosh Heidarpour \
> > >                 <mehrnoosh.heidarpour@huawei.com>
> > > Cc: LLVM Developers Mailing List <llvm-dev@lists.llvm.org>; Stanislav \
> > >                 Mekhanoshin <Stanislav.Mekhanoshin@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@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@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@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@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.
_______________________________________________
LLVM Developers mailing list
llvm-dev@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

[prev in list] [next in list] [prev in thread] [next in thread] 