llvm dev - Nov 2021 - Missed optimization of bitwise expressions

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.

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.