<div dir="ltr"><div dir="ltr"><div>
>> A | B | ~(A ^ B) --> -1</div><div><br></div><div>I added that one with:</div><div><a href="https://reviews.llvm.org/rG4b30076f16fc" rel="noreferrer" target="_blank">https://reviews.llvm.org/rG4b30076f16fc</a></div><div><br></div><div>>> (A & B) ^ A --> A & ~B // perhaps this is not considered profitable?</div><div><br></div><div>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.<br></div><div><a href="https://alive2.llvm.org/ce/z/yRpTcD" target="_blank">https://alive2.llvm.org/ce/z/yRpTcD</a></div><div><br></div><div>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.<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Dec 1, 2021 at 5:19 PM Mehrnoosh Heidarpour <<a href="mailto:mehrnoosh.heidarpour@huawei.com" target="_blank">mehrnoosh.heidarpour@huawei.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Jay,<br>
<br>
Thank you for new missing simplifications!<br>
I will try to post new patches for these cases in the following days.<br>
<br>
About the last one in the missing cases, I think your comments are exactly the reason for missing this simplification opportunity;<br>
<br>
Thanks,<br>
Mehrnoosh<br>
<br>
<br>
-----Original Message-----<br>
From: Jay Foad [mailto:<a href="mailto:jay.foad@gmail.com" target="_blank">jay.foad@gmail.com</a>] <br>
Sent: November 29, 2021 12:08 PM<br>
To: Sanjay Patel <<a href="mailto:spatel@rotateright.com" target="_blank">spatel@rotateright.com</a>>; Mehrnoosh Heidarpour <<a href="mailto:mehrnoosh.heidarpour@huawei.com" target="_blank">mehrnoosh.heidarpour@huawei.com</a>><br>
Cc: LLVM Developers Mailing List <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>; Stanislav Mekhanoshin <<a href="mailto:Stanislav.Mekhanoshin@amd.com" target="_blank">Stanislav.Mekhanoshin@amd.com</a>><br>
Subject: Re: Missed optimization of bitwise expressions<br>
<br>
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.<br>
<br>
Moving on to the two-variable four-instruction cases, there are various missing simplifications like:<br>
<br>
A | B | ~(A ^ B) --> -1<br>
(A ^ B) & (~A | B) --> ~A & B<br>
(((A | B) ^ B) & A) ^ (A | B) --> B<br>
(((A & B) ^ A) & B) | (A & B) --> A & B<br>
<br>
Taking the last of these as an example: <a href="https://alive2.llvm.org/ce/z/wZtbjM" rel="noreferrer" target="_blank">https://alive2.llvm.org/ce/z/wZtbjM</a><br>
I'm surprised that we don't simplify it in stages:<br>
1. (A & B) ^ A --> A & ~B // perhaps this is not considered profitable?<br>
2. (A & ~B) & B --> 0 // perhaps we don't manage to reassociate this to see that it contains B & ~B ?<br>
3. 0 | (A & B) --> A & B<br>
<br>
Jay.<br>
<br>
On Tue, 16 Nov 2021 at 09:09, Jay Foad <<a href="mailto:jay.foad@gmail.com" target="_blank">jay.foad@gmail.com</a>> wrote:<br>
><br>
> Thanks for the fixes so far! Here's another simple two variable case:<br>
><br>
> <a href="https://bugs.llvm.org/show_bug.cgi?id=52518" rel="noreferrer" target="_blank">https://bugs.llvm.org/show_bug.cgi?id=52518</a> "[InstCombine] Failure to <br>
> simplify (~A|B)^A --> ~(A&B)"<br>
><br>
><br>
> Jay.<br>
><br>
> On Thu, 11 Nov 2021 at 19:59, Jay Foad <<a href="mailto:jay.foad@gmail.com" target="_blank">jay.foad@gmail.com</a>> wrote:<br>
> ><br>
> > OK, I've filed the first couple of beginner bugs:<br>
> > <a href="https://bugs.llvm.org/show_bug.cgi?id=52478" rel="noreferrer" target="_blank">https://bugs.llvm.org/show_bug.cgi?id=52478</a><br>
> > <a href="https://bugs.llvm.org/show_bug.cgi?id=52479" rel="noreferrer" target="_blank">https://bugs.llvm.org/show_bug.cgi?id=52479</a><br>
> ><br>
> > Thanks,<br>
> > Jay.<br>
> ><br>
> > On Thu, 11 Nov 2021 at 16:35, Sanjay Patel <<a href="mailto:spatel@rotateright.com" target="_blank">spatel@rotateright.com</a>> wrote:<br>
> > ><br>
> > > Nice test program! I don't know python well enough to understand <br>
> > > that yet, but no reason to be ashamed of hacks. :)<br>
> > ><br>
> > > 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.<br>
> > ><br>
> > > There's also a set of recent patch proposals for 3 variable logic reductions -- for example, <a href="https://reviews.llvm.org/D112276" rel="noreferrer" target="_blank">https://reviews.llvm.org/D112276</a> -- these were inspired by a logic lookup table function as discussed in the comments.<br>
> > > 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.<br>
> > ><br>
> > ><br>
> > > On Thu, Nov 11, 2021 at 6:34 AM Jay Foad <<a href="mailto:jay.foad@gmail.com" target="_blank">jay.foad@gmail.com</a>> wrote:<br>
> > >><br>
> > >> Hi,<br>
> > >><br>
> > >> I tried searching for small bitwise expressions using AND OR XOR <br>
> > >> and NOT that "opt -O3" fails to optimize to a simpler form. For example:<br>
> > >><br>
> > >> (A^B)|~A --> ~(A&B)<br>
> > >> <a href="https://alive2.llvm.org/ce/z/HpWfzp" rel="noreferrer" target="_blank">https://alive2.llvm.org/ce/z/HpWfzp</a><br>
> > >><br>
> > >> A|B|(A^B) --> A|B<br>
> > >> <a href="https://alive2.llvm.org/ce/z/UCC6uM" rel="noreferrer" target="_blank">https://alive2.llvm.org/ce/z/UCC6uM</a><br>
> > >><br>
> > >> ((A|B)^C)&A --> A&~C (actually I don't understand why this one is <br>
> > >> OK, even if B might be poison, but alive2 says it is OK) <br>
> > >> <a href="https://alive2.llvm.org/ce/z/mkvW6p" rel="noreferrer" target="_blank">https://alive2.llvm.org/ce/z/mkvW6p</a><br>
> > >><br>
> > >> I can file bugs for specific examples but I wondered if there was <br>
> > >> any interest in a more systematic approach to finding these <br>
> > >> missed optimizations? My approach was to write some very hacky <br>
> > >> Python <br>
> > >> (<a href="https://gist.github.com/jayfoad/94f4c68fa3a9aa908db79dbd7e9df80d" rel="noreferrer" target="_blank">https://gist.github.com/jayfoad/94f4c68fa3a9aa908db79dbd7e9df80d</a><br>
> > >> , please don't read it) to exhaustively generate programs; then <br>
> > >> take all the programs with a given truth table, run them all <br>
> > >> through "opt -O3", and check that they all got optimized to the <br>
> > >> same (or at least equally<br>
> > >> short) output.<br>
> > >><br>
> > >> Thanks,<br>
> > >> Jay.<br>
</blockquote></div></div>