diff mbox series

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

Message ID 02ac01d98389$e92e1590$bb8a40b0$@nextmovesoftware.com
State New
Headers show
Series match.pd: Simplify popcount(X&Y)+popcount(X|Y) as popcount(X)+popcount(Y) | expand

Commit Message

Roger Sayle May 10, 2023, 9:53 p.m. UTC 
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
--

Comments

Jeff Law May 10, 2023, 11:20 p.m. UTC | #1 
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
diff mbox series

Patch

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