fold-const.c (tree_nonzero_bits): New function.

        * fold-const.c (tree_nonzero_bits): New function.
        * fold-const.h (tree_nonzero_bits): Likewise.
        * match.pd (POPCOUNT): New patterns to fold BUILTIN_POPCOUNT and
        friends.  POPCOUNT(x&1) => x&1, POPCOUNT(x)==0 => x==0, etc.

        * gcc.dg/fold-popcount-1.c: New testcase.
        * gcc.dg/fold-popcount-2.c: New testcase.
        * gcc.dg/fold-popcount-3.c: New testcase.
        * gcc.dg/fold-popcount-4.c: New testcase.

From-SVN: r260689

9 files changed, 233 insertions, 0 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 1ae5e34..b2ce686 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2018-05-24  Roger Sayle  <roger@nextmovesoftware.com>
+
+        * fold-const.c (tree_nonzero_bits): New function.
+        * fold-const.h (tree_nonzero_bits): Likewise.
+        * match.pd (POPCOUNT): New patterns to fold BUILTIN_POPCOUNT and
+        friends.  POPCOUNT(x&1) => x&1, POPCOUNT(x)==0 => x==0, etc.
+
 2018-05-24  H.J. Lu  <hongjiu.lu@intel.com>
 
 	PR target/85900
diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index dc27744..0f57f07 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -14571,6 +14571,74 @@ c_getstr (tree src, unsigned HOST_WIDE_INT *strlen)
   return string + offset;
 }
 
+/* Given a tree T, compute which bits in T may be nonzero.  */
+
+wide_int
+tree_nonzero_bits (const_tree t)
+{
+  switch (TREE_CODE (t))
+    {
+    case INTEGER_CST:
+      return wi::to_wide (t);
+    case SSA_NAME:
+      return get_nonzero_bits (t);
+    case NON_LVALUE_EXPR:
+    case SAVE_EXPR:
+      return tree_nonzero_bits (TREE_OPERAND (t, 0));
+    case BIT_AND_EXPR:
+      return wi::bit_and (tree_nonzero_bits (TREE_OPERAND (t, 0)),
+			  tree_nonzero_bits (TREE_OPERAND (t, 1)));
+    case BIT_IOR_EXPR:
+    case BIT_XOR_EXPR:
+      return wi::bit_or (tree_nonzero_bits (TREE_OPERAND (t, 0)),
+			 tree_nonzero_bits (TREE_OPERAND (t, 1)));
+    case COND_EXPR:
+      return wi::bit_or (tree_nonzero_bits (TREE_OPERAND (t, 1)),
+			 tree_nonzero_bits (TREE_OPERAND (t, 2)));
+    CASE_CONVERT:
+      return wide_int::from (tree_nonzero_bits (TREE_OPERAND (t, 0)),
+			     TYPE_PRECISION (TREE_TYPE (t)),
+			     TYPE_SIGN (TREE_TYPE (TREE_OPERAND (t, 0))));
+    case PLUS_EXPR:
+      if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
+	{
+	  wide_int nzbits1 = tree_nonzero_bits (TREE_OPERAND (t, 0));
+	  wide_int nzbits2 = tree_nonzero_bits (TREE_OPERAND (t, 1));
+	  if (wi::bit_and (nzbits1, nzbits2) == 0)
+	    return wi::bit_or (nzbits1, nzbits2);
+	}
+      break;
+    case LSHIFT_EXPR:
+      if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
+	{
+	  tree type = TREE_TYPE (t);
+	  wide_int nzbits = tree_nonzero_bits (TREE_OPERAND (t, 0));
+	  wide_int arg1 = wi::to_wide (TREE_OPERAND (t, 1),
+				       TYPE_PRECISION (type));
+	  return wi::neg_p (arg1)
+		 ? wi::rshift (nzbits, -arg1, TYPE_SIGN (type))
+		 : wi::lshift (nzbits, arg1);
+	}
+      break;
+    case RSHIFT_EXPR:
+      if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
+        {
+	  tree type = TREE_TYPE (t);
+	  wide_int nzbits = tree_nonzero_bits (TREE_OPERAND (t, 0));
+	  wide_int arg1 = wi::to_wide (TREE_OPERAND (t, 1),
+				       TYPE_PRECISION (type));
+	  return wi::neg_p (arg1)
+		 ? wi::lshift (nzbits, -arg1)
+		 : wi::rshift (nzbits, arg1, TYPE_SIGN (type));
+        }
+      break;
+    default:
+      break;
+    }
+
+  return wi::shwi (-1, TYPE_PRECISION (TREE_TYPE (t)));
+}
+
 #if CHECKING_P
 
 namespace selftest {
diff --git a/gcc/fold-const.h b/gcc/fold-const.h
index 8e3ad51..337818a 100644
--- a/gcc/fold-const.h
+++ b/gcc/fold-const.h
@@ -181,6 +181,7 @@ extern tree const_unop (enum tree_code, tree, tree);
 extern tree const_binop (enum tree_code, tree, tree, tree);
 extern bool negate_mathfn_p (combined_fn);
 extern const char *c_getstr (tree, unsigned HOST_WIDE_INT *strlen = NULL);
+extern wide_int tree_nonzero_bits (const_tree);
 
 /* Return OFF converted to a pointer offset type suitable as offset for
    POINTER_PLUS_EXPR.  Use location LOC for this conversion.  */
diff --git a/gcc/match.pd b/gcc/match.pd
index 50f4c88..8a71141 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -4760,3 +4760,23 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (negate (IFN_FNMS@3 @0 @1 @2))
   (if (single_use (@3))
    (IFN_FMA @0 @1 @2))))
+
+/* POPCOUNT simplifications.  */
+(for popcount (BUILT_IN_POPCOUNT BUILT_IN_POPCOUNTL BUILT_IN_POPCOUNTLL
+	       BUILT_IN_POPCOUNTIMAX)
+  /* popcount(X&1) is nop_expr(X&1).  */
+  (simplify
+    (popcount @0)
+    (if (tree_nonzero_bits (@0) == 1)
+      (convert @0)))
+  /* popcount(X) + popcount(Y) is popcount(X|Y) when X&Y must be zero.  */
+  (simplify
+    (plus (popcount:s @0) (popcount:s @1))
+    (if (wi::bit_and (tree_nonzero_bits (@0), tree_nonzero_bits (@1)) == 0)
+      (popcount (bit_ior @0 @1))))
+  /* popcount(X) == 0 is X == 0, and related (in)equalities.  */
+  (for cmp (le eq ne gt)
+       rep (eq eq ne ne)
+    (simplify
+      (cmp (popcount @0) integer_zerop)
+      (rep @0 { build_zero_cst (TREE_TYPE (@0)); }))))
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 8a6fe20..f7d0c3a 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,10 @@
+2018-05-24  Roger Sayle  <roger@nextmovesoftware.com>
+
+        * gcc.dg/fold-popcount-1.c: New testcase.
+        * gcc.dg/fold-popcount-2.c: New testcase.
+        * gcc.dg/fold-popcount-3.c: New testcase.
+        * gcc.dg/fold-popcount-4.c: New testcase.
+
 2018-05-24  Marek Polacek  <polacek@redhat.com>
 
 	PR c++/85847
diff --git a/gcc/testsuite/gcc.dg/fold-popcount-1.c b/gcc/testsuite/gcc.dg/fold-popcount-1.c
new file mode 100644
index 0000000..32bb7e2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-popcount-1.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original" } */
+
+int test_eqzero(unsigned int a)
+{
+  return __builtin_popcount(a) == 0;
+}
+
+int test_eqzerol(unsigned long b)
+{
+  return __builtin_popcountl(b) == 0;
+}
+
+int test_eqzeroll(unsigned long long c)
+{
+  return __builtin_popcountll(c) == 0;
+}
+
+int test_nezero(unsigned int d)
+{
+  return __builtin_popcount(d) != 0;
+}
+
+int test_nezerol(unsigned long e)
+{
+  return __builtin_popcountl(e) != 0;
+}
+
+int test_nezeroll(unsigned long long f)
+{
+  return __builtin_popcountll(f) != 0;
+}
+
+/* { dg-final { scan-tree-dump-times "popcount" 0 "original" } } */
+
diff --git a/gcc/testsuite/gcc.dg/fold-popcount-2.c b/gcc/testsuite/gcc.dg/fold-popcount-2.c
new file mode 100644
index 0000000..27557da
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-popcount-2.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cddce1" } */
+
+int test_andone(unsigned int a)
+{
+  return __builtin_popcount(a&1);
+}
+
+int test_andonel(unsigned long b)
+{
+  return __builtin_popcountl(b&1);
+}
+
+int test_andonell(unsigned long long c)
+{
+  return __builtin_popcountll(c&1);
+}
+
+int test_oneand(unsigned int d)
+{
+  return __builtin_popcount(1&d);
+}
+
+int test_oneandl(unsigned long e)
+{
+  return __builtin_popcountl(1&e);
+}
+
+int test_oneandll(unsigned long long f)
+{
+  return __builtin_popcountll(1&f);
+}
+
+/* { dg-final { scan-tree-dump-times "popcount" 0 "cddce1" } } */
+
diff --git a/gcc/testsuite/gcc.dg/fold-popcount-3.c b/gcc/testsuite/gcc.dg/fold-popcount-3.c
new file mode 100644
index 0000000..eda0077
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-popcount-3.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cddce1" } */
+
+int test_combine(unsigned int a, unsigned int b)
+{
+  return __builtin_popcount(a&8) + __builtin_popcount(b&2);
+}
+
+/* { dg-final { scan-tree-dump-times "popcount" 1 "cddce1" } } */
+
diff --git a/gcc/testsuite/gcc.dg/fold-popcount-4.c b/gcc/testsuite/gcc.dg/fold-popcount-4.c
new file mode 100644
index 0000000..424c3d8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-popcount-4.c
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cddce1" } */
+
+int test_shiftmax(unsigned int a)
+{
+  return __builtin_popcount(a>>(8*sizeof(a)-1));
+}
+
+int test_shiftmaxl(unsigned long b)
+{
+  return __builtin_popcountl(b>>(8*sizeof(b)-1));
+}
+
+int test_shiftmaxll(unsigned long long c)
+{
+  return __builtin_popcountll(c>>(8*sizeof(c)-1));
+}
+
+int test_shift7(unsigned char d)
+{
+  return __builtin_popcount(d>>7);
+}
+
+int test_shift7l(unsigned char e)
+{
+  return __builtin_popcountl(e>>7);
+}
+
+int test_shift7ll(unsigned char f)
+{
+  return __builtin_popcountll(f>>7);
+}
+
+int test_shift15(unsigned short g)
+{
+  return __builtin_popcount(g>>15);
+}
+
+int test_shift15l(unsigned short h)
+{
+  return __builtin_popcountl(h>>15);
+}
+
+int test_shift15ll(unsigned short i)
+{
+  return __builtin_popcountll(i>>15);
+}
+
+/* { dg-final { scan-tree-dump-times "popcount" 0 "cddce1" } } */
+