match.pd: Simplify popcount(X&Y)+popcount(X|Y) as popcount(X)+popcount(Y)

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).

2023-05-11  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.

4 files changed, 100 insertions, 0 deletions

diff --git a/gcc/match.pd b/gcc/match.pd
index bc083be..dde9576 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -7797,6 +7797,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" } } */