[llvm-dev] Missed optimization of bitwise expressions

Tue Nov 16 11:21:38 PST 2021

[AMD Official Use Only]

As for the undef, here is the example: https://alive2.llvm.org/ce/z/YxoiqS
A logically correct transformation “(~a & b & c) | ~(b | c) -> ~((a & b) | (b ^ c))” has issue with undef inputs. I.e. our logic isn’t really binary, our truth tables shall also have undef columns. This makes logical solver prospects even more questionable. Then I am not sure if we shall count poison as well.
Speaking of LUT with 256 expressions it seems to be possible to optimize in a much smaller set of transforms than 256. I have few and I see that the rest of the 256 cases started to converge.

Stas

From: David Jones <david.jones at metrics.ca>
Sent: Tuesday, November 16, 2021 5:08
To: Jay Foad <jay.foad at gmail.com>
Cc: Sanjay Patel <spatel at rotateright.com>; LLVM Developers Mailing List <llvm-dev at lists.llvm.org>; Mekhanoshin, Stanislav <Stanislav.Mekhanoshin at amd.com>
Subject: Re: [llvm-dev] Missed optimization of bitwise expressions

[CAUTION: External Email]
For any number of inputs, you can build a look-up table (LUT).

Some processor architectures have LUT instructions.  For those, your built LUT can be used directly.

Otherwise, for each of the 256 possible LUTs you can precompute the "optimal" representation for the target. This may depend on what the target offers - e.g. some processors have an "and not" instruction that may allow a more compact sequence. For any of the 256 LUTs (and counterparts arising from the permutation of inputs) you can cache the resulting target-mapped tree.

The only issue I see is undef/poison in an operand.  Can this break an optimization, esp. if there is internal reconvergence in the logic tree?

For expressions of more than 2-3 distinct variables you can use technology mappng to construct an arbitrarily deep tree of LUTs, and then technology-map to the target architecture. It's likely that the few applications that would benefit already do some of this optimization internally.

On Tue, Nov 16, 2021 at 7:55 AM Jay Foad via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
> If we're missing 2 variable logic reductions, those are common/easy enough that we should have those in instcombine.

I think I agree with this. There should be 16 canonical forms for the
bitwise functions on two variables, including degenerate cases like
"false" as well as the interesting ones like A&~B, ~A^B etc. It seems
reasonable that we should be able to simplify AND OR and XOR on any
pair of canonical forms, and produce another canonical form as the
result.

For three variables there would be 256 canonical forms, which seems
far less tractable.

Jay.

On Thu, 11 Nov 2021 at 16:35, Sanjay Patel <spatel at rotateright.com<mailto: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<https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Freviews.llvm.org%2FD112276&data=04%7C01%7CStanislav.Mekhanoshin%40amd.com%7C5ec65a3ce4f5400ecf2b08d9a9021883%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637726650083401834%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=bXXCbPjP2wItWRrS8ZeOcYUgMLIWiqg4hsEefHJJHQU%3D&reserved=0> -- 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<mailto: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<https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Falive2.llvm.org%2Fce%2Fz%2FHpWfzp&data=04%7C01%7CStanislav.Mekhanoshin%40amd.com%7C5ec65a3ce4f5400ecf2b08d9a9021883%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637726650083401834%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=hD8fsnGKnZ0lNIMJKR8Zp7JJoLxDzXWCEQ1S3A1aIJ0%3D&reserved=0>
>>
>> A|B|(A^B) --> A|B
>> https://alive2.llvm.org/ce/z/UCC6uM<https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Falive2.llvm.org%2Fce%2Fz%2FUCC6uM&data=04%7C01%7CStanislav.Mekhanoshin%40amd.com%7C5ec65a3ce4f5400ecf2b08d9a9021883%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637726650083411826%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=lHLBiLEpC%2BvCHUzp4%2FCsr11%2F5CCRi7Y8G1v9kAjai6I%3D&reserved=0>
>>
>> ((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<https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Falive2.llvm.org%2Fce%2Fz%2FmkvW6p&data=04%7C01%7CStanislav.Mekhanoshin%40amd.com%7C5ec65a3ce4f5400ecf2b08d9a9021883%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637726650083411826%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=coKiJt2Do0mX1RXVcTVk0yRtf7GaLm7fBoEA%2BAqPu%2BQ%3D&reserved=0>
>>
>> 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<https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgist.github.com%2Fjayfoad%2F94f4c68fa3a9aa908db79dbd7e9df80d&data=04%7C01%7CStanislav.Mekhanoshin%40amd.com%7C5ec65a3ce4f5400ecf2b08d9a9021883%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637726650083421808%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=gzDSa4XqFGaNOiZLT1mnYsr2WxQpgLRh5egO%2FCVD2Q4%3D&reserved=0>,
>> 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 at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=04%7C01%7CStanislav.Mekhanoshin%40amd.com%7C5ec65a3ce4f5400ecf2b08d9a9021883%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637726650083421808%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=LAV4auH%2B4J52PsOtmh6NDp%2BUAelRBrh25yLwtmWvJlw%3D&reserved=0>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20211116/7348118f/attachment-0001.html>