* [PATCH] match.pd: Simplify popcount(X&Y)+popcount(X|Y) as popcount(X)+popcount(Y)
@ 2023-05-10 21:53 Roger Sayle
2023-05-10 23:20 ` Jeff Law
0 siblings, 1 reply; 2+ messages in thread
From: Roger Sayle @ 2023-05-10 21:53 UTC (permalink / raw)
To: 'GCC Patches'; +Cc: 'Marc Glisse'
[-- Attachment #1: Type: text/plain, Size: 939 bytes --]
This patch teaches match.pd to simplify popcount(X&Y)+popcount(X|Y) as
popcount(X)+popcount(Y), and the related simplifications that
popcount(X)+popcount(Y)-popcount(X&Y) is popcount(X|Y). As surprising
as it might seem, this idiom is common in cheminformatics codes
(for Tanimoto coefficient calculations).
This patch has been tested on x86_64-pc-linux-gnu with make bootstrap
and make -k check, both with and without --target_board=unix{-m32}, with
no new failures. Ok for mainline?
2023-05-10 Roger Sayle <roger@nextmovesoftware.com>
gcc/ChangeLog
* match.pd <popcount optimizations>: Simplify popcount(X|Y) +
popcount(X&Y) as popcount(X)+popcount(Y). Likewise, simplify
popcount(X)+popcount(Y)-popcount(X&Y) as popcount(X|Y), and
vice versa.
gcc/testsuite/ChangeLog
* gcc.dg/fold-popcount-8.c: New test case.
* gcc.dg/fold-popcount-9.c: Likewise.
* gcc.dg/fold-popcount-10.c: Likewise.
Thanks in advance,
Roger
--
[-- Attachment #2: patchmp.txt --]
[-- Type: text/plain, Size: 3813 bytes --]
diff --git a/gcc/match.pd b/gcc/match.pd
index ceae1c3..accae2a 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -7771,6 +7771,25 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(bit_and (POPCOUNT @0) integer_onep)
(PARITY @0))
+/* popcount(X&Y) + popcount(X|Y) is popcount(x) + popcount(Y). */
+(simplify
+ (plus:c (POPCOUNT:s (bit_and:s @0 @1)) (POPCOUNT:s (bit_ior:cs @0 @1)))
+ (plus (POPCOUNT @0) (POPCOUNT @1)))
+
+/* popcount(X) + popcount(Y) - popcount(X&Y) is popcount(X|Y). */
+/* popcount(X) + popcount(Y) - popcount(X|Y) is popcount(X&Y). */
+(for popcount (POPCOUNT)
+ (for log1 (bit_and bit_ior)
+ log2 (bit_ior bit_and)
+ (simplify
+ (minus (plus:s (popcount:s @0) (popcount:s @1))
+ (popcount:s (log1:cs @0 @1)))
+ (popcount (log2 @0 @1)))
+ (simplify
+ (plus:c (minus:s (popcount:s @0) (popcount:s (log1:cs @0 @1)))
+ (popcount:s @1))
+ (popcount (log2 @0 @1)))))
+
/* PARITY simplifications. */
/* parity(~X) is parity(X). */
(simplify
diff --git a/gcc/testsuite/gcc.dg/fold-popcount-10.c b/gcc/testsuite/gcc.dg/fold-popcount-10.c
new file mode 100644
index 0000000..fa8a52a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-popcount-10.c
@@ -0,0 +1,28 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#define popc __builtin_popcount
+
+int foo1(unsigned int x, unsigned int y)
+{
+ return popc (x) + popc (y) - popc (x|y);
+}
+
+int foo2(unsigned int x, unsigned int y)
+{
+ return popc (y) + popc (x) - popc (x|y);
+}
+
+int foo3(unsigned int x, unsigned int y)
+{
+ return (popc (x) - popc (x|y)) + popc (y);
+}
+
+int foo4(unsigned int x, unsigned int y)
+{
+ return (popc (y) - popc (x|y)) + popc (x);
+}
+
+/* { dg-final { scan-tree-dump-not " \\| " "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & " 4 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "popcount " 4 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-popcount-8.c b/gcc/testsuite/gcc.dg/fold-popcount-8.c
new file mode 100644
index 0000000..9599a3c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-popcount-8.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int foo1(unsigned int x, unsigned int y)
+{
+ return __builtin_popcount (x&y) + __builtin_popcount (x|y);
+}
+
+int foo2(unsigned int x, unsigned int y)
+{
+ return __builtin_popcount (x&y) + __builtin_popcount (y|x);
+}
+
+int foo3(unsigned int x, unsigned int y)
+{
+ return __builtin_popcount (x|y) + __builtin_popcount (x&y);
+}
+
+int foo4(unsigned int x, unsigned int y)
+{
+ return __builtin_popcount (x|y) + __builtin_popcount (y&x);
+}
+
+/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " \\| " "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-popcount-9.c b/gcc/testsuite/gcc.dg/fold-popcount-9.c
new file mode 100644
index 0000000..a9ffa62
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-popcount-9.c
@@ -0,0 +1,28 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#define popc __builtin_popcount
+
+int foo1(unsigned int x, unsigned int y)
+{
+ return popc (x) + popc (y) - popc (x&y);
+}
+
+int foo2(unsigned int x, unsigned int y)
+{
+ return popc (y) + popc (x) - popc (x&y);
+}
+
+int foo3(unsigned int x, unsigned int y)
+{
+ return (popc (x) - popc (x&y)) + popc (y);
+}
+
+int foo4(unsigned int x, unsigned int y)
+{
+ return (popc (y) - popc (x&y)) + popc (x);
+}
+
+/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\| " 4 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "popcount " 4 "optimized" } } */
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] match.pd: Simplify popcount(X&Y)+popcount(X|Y) as popcount(X)+popcount(Y)
2023-05-10 21:53 [PATCH] match.pd: Simplify popcount(X&Y)+popcount(X|Y) as popcount(X)+popcount(Y) Roger Sayle
@ 2023-05-10 23:20 ` Jeff Law
0 siblings, 0 replies; 2+ messages in thread
From: Jeff Law @ 2023-05-10 23:20 UTC (permalink / raw)
To: Roger Sayle, 'GCC Patches'; +Cc: 'Marc Glisse'
On 5/10/23 15:53, Roger Sayle wrote:
>
> This patch teaches match.pd to simplify popcount(X&Y)+popcount(X|Y) as
> popcount(X)+popcount(Y), and the related simplifications that
> popcount(X)+popcount(Y)-popcount(X&Y) is popcount(X|Y). As surprising
> as it might seem, this idiom is common in cheminformatics codes
> (for Tanimoto coefficient calculations).
I'd read the ChangeLog before reading this paragraph. My first thought
was "will these ever be useful". Thanks for referring back to real code
as a justification.
>
> This patch has been tested on x86_64-pc-linux-gnu with make bootstrap
> and make -k check, both with and without --target_board=unix{-m32}, with
> no new failures. Ok for mainline?
>
>
> 2023-05-10 Roger Sayle <roger@nextmovesoftware.com>
>
> gcc/ChangeLog
> * match.pd <popcount optimizations>: Simplify popcount(X|Y) +
> popcount(X&Y) as popcount(X)+popcount(Y). Likewise, simplify
> popcount(X)+popcount(Y)-popcount(X&Y) as popcount(X|Y), and
> vice versa.
>
> gcc/testsuite/ChangeLog
> * gcc.dg/fold-popcount-8.c: New test case.
> * gcc.dg/fold-popcount-9.c: Likewise.
> * gcc.dg/fold-popcount-10.c: Likewise.
OK.
jeff
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2023-05-10 23:21 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-05-10 21:53 [PATCH] match.pd: Simplify popcount(X&Y)+popcount(X|Y) as popcount(X)+popcount(Y) Roger Sayle
2023-05-10 23:20 ` Jeff Law
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).