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.

1 files changed, 79 insertions, 12 deletions

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.  */