match.pd: Add some __builtin_ctz (x) cmp cst simplifications [PR95527]

This patch adds some ctz simplifications (e.g. ctz (x) >= 3 can be done by
testing if the low 3 bits are zero, etc.).

In addition, I've noticed that in the CLZ case, the
 #ifdef CLZ_DEFINED_VALUE_AT_ZERO don't really work as intended, they
are evaluated during genmatch and the macro is not defined then
(but, because of the missing tm.h includes it isn't defined in
gimple-match.c or generic-match.c either).  And when tm.h is included,
defaults.h is included which defines a fallback version of that macro.

For GCC 12, I wonder if it wouldn't be better to say in addition to __builtin_c[lt]z*
is always UB at zero that it would be undefined for .C[LT]Z ifn too if it
has just one operand and use a second operand to be the constant we expect
at zero.

2021-04-27  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/95527
	* generic-match-head.c: Include tm.h.
	* gimple-match-head.c: Include tm.h.
	* match.pd (CLZ == INTEGER_CST): Don't use
	#ifdef CLZ_DEFINED_VALUE_AT_ZERO, only test CLZ_DEFINED_VALUE_AT_ZERO
	if clz == CFN_CLZ.  Add missing val declaration.
	(CTZ cmp CST): New simplifications.

	* gcc.dg/tree-ssa/pr95527-2.c: New test.

4 files changed, 138 insertions, 12 deletions

diff --git a/gcc/generic-match-head.c b/gcc/generic-match-head.c
index a063512..f426208 100644
--- a/gcc/generic-match-head.c
+++ b/gcc/generic-match-head.c
@@ -37,6 +37,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimplify.h"
 #include "optabs-tree.h"
 #include "dbgcnt.h"
+#include "tm.h"
 
 /* Routine to determine if the types T1 and T2 are effectively
    the same for GENERIC.  If T1 or T2 is not a type, the test
diff --git a/gcc/gimple-match-head.c b/gcc/gimple-match-head.c
index 84fbaef..b084a3157 100644
--- a/gcc/gimple-match-head.c
+++ b/gcc/gimple-match-head.c
@@ -43,6 +43,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "optabs-tree.h"
 #include "tree-eh.h"
 #include "dbgcnt.h"
+#include "tm.h"
 
 /* Forward declarations of the private auto-generated matchers.
    They expect valueized operands in canonical order and do not
diff --git a/gcc/match.pd b/gcc/match.pd
index bb1d623..19f4a78 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -6341,30 +6341,97 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
    (op (clz:s@2 @0) INTEGER_CST@1)
    (if (integer_zerop (@1) && single_use (@2))
     /* clz(X) == 0 is (int)X < 0 and clz(X) != 0 is (int)X >= 0.  */
-    (with { tree stype = signed_type_for (TREE_TYPE (@0));
+    (with { tree type0 = TREE_TYPE (@0);
+	    tree stype = signed_type_for (type0);
 	    HOST_WIDE_INT val = 0;
-#ifdef CLZ_DEFINED_VALUE_AT_ZERO
 	    /* Punt on hypothetical weird targets.  */
-	    if (CLZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (TREE_TYPE (@0)),
-					   val) == 2
+	    if (clz == CFN_CLZ
+		&& CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_TYPE_MODE (type0),
+					      val) == 2
 		&& val == 0)
 	      stype = NULL_TREE;
-#endif
 	  }
      (if (stype)
       (cmp (convert:stype @0) { build_zero_cst (stype); })))
     /* clz(X) == (prec-1) is X == 1 and clz(X) != (prec-1) is X != 1.  */
     (with { bool ok = true;
-#ifdef CLZ_DEFINED_VALUE_AT_ZERO
+	    HOST_WIDE_INT val = 0;
+	    tree type0 = TREE_TYPE (@0);
 	    /* Punt on hypothetical weird targets.  */
-	    if (CLZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (TREE_TYPE (@0)),
-					   val) == 2
-		&& val == TYPE_PRECISION (TREE_TYPE (@0)) - 1)
+	    if (clz == CFN_CLZ
+		&& CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_TYPE_MODE (type0),
+					      val) == 2
+		&& val == TYPE_PRECISION (type0) - 1)
 	      ok = false;
-#endif
 	  }
-     (if (ok && wi::to_wide (@1) == (TYPE_PRECISION (TREE_TYPE (@0)) - 1))
-      (op @0 { build_one_cst (TREE_TYPE (@0)); })))))))
+     (if (ok && wi::to_wide (@1) == (TYPE_PRECISION (type0) - 1))
+      (op @0 { build_one_cst (type0); })))))))
+
+/* CTZ simplifications.  */
+(for ctz (CTZ)
+ (for op (ge gt le lt)
+      cmp (eq eq ne ne)
+  (simplify
+   /* __builtin_ctz (x) >= C -> (x & ((1 << C) - 1)) == 0.  */
+   (op (ctz:s @0) INTEGER_CST@1)
+    (with { bool ok = true;
+	    HOST_WIDE_INT val = 0;
+	    if (!tree_fits_shwi_p (@1))
+	      ok = false;
+	    else
+	      {
+		val = tree_to_shwi (@1);
+		/* Canonicalize to >= or <.  */
+		if (op == GT_EXPR || op == LE_EXPR)
+		  {
+		    if (val == HOST_WIDE_INT_MAX)
+		      ok = false;
+		    else
+		      val++;
+		  }
+	      }
+	    bool zero_res = false;
+	    HOST_WIDE_INT zero_val = 0;
+	    tree type0 = TREE_TYPE (@0);
+	    int prec = TYPE_PRECISION (type0);
+	    if (ctz == CFN_CTZ
+		&& CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_TYPE_MODE (type0),
+					      zero_val) == 2)
+	      zero_res = true;
+	  }
+     (if (val <= 0)
+      (if (ok && (!zero_res || zero_val >= val))
+       { constant_boolean_node (cmp == EQ_EXPR ? true : false, type); })
+      (if (val >= prec)
+       (if (ok && (!zero_res || zero_val < val))
+	{ constant_boolean_node (cmp == EQ_EXPR ? false : true, type); })
+       (if (ok && (!zero_res || zero_val < 0 || zero_val >= prec))
+	(cmp (bit_and @0 { wide_int_to_tree (type0,
+					     wi::mask (val, false, prec)); })
+	     { build_zero_cst (type0); })))))))
+ (for op (eq ne)
+  (simplify
+   /* __builtin_ctz (x) == C -> (x & ((1 << (C + 1)) - 1)) == (1 << C).  */
+   (op (ctz:s @0) INTEGER_CST@1)
+    (with { bool zero_res = false;
+	    HOST_WIDE_INT zero_val = 0;
+	    tree type0 = TREE_TYPE (@0);
+	    int prec = TYPE_PRECISION (type0);
+	    if (ctz == CFN_CTZ
+		&& CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_TYPE_MODE (type0),
+					      zero_val) == 2)
+	      zero_res = true;
+	  }
+     (if (tree_int_cst_sgn (@1) < 0 || wi::to_widest (@1) >= prec)
+      (if (!zero_res || zero_val != wi::to_widest (@1))
+       { constant_boolean_node (op == EQ_EXPR ? false : true, type); })
+      (if (!zero_res || zero_val < 0 || zero_val >= prec)
+       (op (bit_and @0 { wide_int_to_tree (type0,
+					   wi::mask (tree_to_uhwi (@1) + 1,
+						     false, prec)); })
+	   { wide_int_to_tree (type0,
+			       wi::shifted_mask (tree_to_uhwi (@1), 1,
+						 false, prec)); })))))))
 
 /* POPCOUNT simplifications.  */
 /* popcount(X) + popcount(Y) is popcount(X|Y) when X&Y must be zero.  */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr95527-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr95527-2.c
new file mode 100644
index 0000000..b4ae2be
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr95527-2.c
@@ -0,0 +1,57 @@
+/* PR tree-optimization/95527 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original" } */
+/* { dg-final { scan-tree-dump "a & 7\\) == 0" "original" } } */
+/* { dg-final { scan-tree-dump "b & 63\\) != 0" "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0;" 2 "original" } } */
+/* { dg-final { scan-tree-dump-times "return 1;" 2 "original" } } */
+/* { dg-final { scan-tree-dump "g & 15\\) == 8" "original" } } */
+/* { dg-final { scan-tree-dump "h & 255\\) != 128" "original" } } */
+
+int
+f1 (int a)
+{
+  return __builtin_ctz (a) >= 3;
+}
+
+int
+f2 (int b)
+{
+  return __builtin_ctz (b) < 6;
+}
+
+int
+f3 (int c)
+{
+  return __builtin_ctz (c) < 0;
+}
+
+int
+f4 (int d)
+{
+  return __builtin_ctz (d) >= 0;
+}
+
+int
+f5 (int e)
+{
+  return __builtin_ctz (e) >= __SIZEOF_INT__ * __CHAR_BIT__;
+}
+
+int
+f6 (int f)
+{
+  return __builtin_ctz (f) < __SIZEOF_INT__ * __CHAR_BIT__;
+}
+
+int
+f7 (int g)
+{
+  return __builtin_ctz (g) == 3;
+}
+
+int
+f8 (int h)
+{
+  return __builtin_ctz (h) != 7;
+}