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 <ro...@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
--
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" } } */
