re PR target/29776 (result of ffs/clz/ctz/popcount/parity are already sign-extended)

	PR target/29776
	* fold-const.c (tree_call_nonnegative_warnv_p): Return true
	for BUILT_IN_C{LZ,LRSB}*.
	* tree.h (CASE_INT_FN): Add FN##IMAX case.
	* tree-vrp.c (extract_range_basic): Handle
	BUILT_IN_{FFS,PARITY,POPCOUNT,C{LZ,TZ,LRSB}}*.  For
	BUILT_IN_CONSTANT_P if argument isn't (D) of PARM_DECL,
	fall thru to code calling set_value*.
	* builtins.c (expand_builtin): Remove *IMAX cases.
	(fold_builtin_bitop): For BUILT_IN_CLRSB* return NULL_TREE
	if width is bigger than 2*HWI.

	* libgcc2.c (__floattisf): Avoid undefined signed overflow.

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

From-SVN: r200731

7 files changed, 259 insertions, 21 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 176ecf4..cc23efb 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2013-07-06  Jakub Jelinek  <jakub@redhat.com>
+
+	PR target/29776
+	* fold-const.c (tree_call_nonnegative_warnv_p): Return true
+	for BUILT_IN_C{LZ,LRSB}*.
+	* tree.h (CASE_INT_FN): Add FN##IMAX case.
+	* tree-vrp.c (extract_range_basic): Handle
+	BUILT_IN_{FFS,PARITY,POPCOUNT,C{LZ,TZ,LRSB}}*.  For
+	BUILT_IN_CONSTANT_P if argument isn't (D) of PARM_DECL,
+	fall thru to code calling set_value*.
+	* builtins.c (expand_builtin): Remove *IMAX cases.
+	(fold_builtin_bitop): For BUILT_IN_CLRSB* return NULL_TREE
+	if width is bigger than 2*HWI.
+
 2013-07-05  Vladimir Makarov  <vmakarov@redhat.com>
 
 	PR rtl-optimization/55342
diff --git a/gcc/builtins.c b/gcc/builtins.c
index 6bd045c..78b0d84 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -6107,7 +6107,6 @@ expand_builtin (tree exp, rtx target, rtx subtarget, enum machine_mode mode,
       break;
 
     CASE_INT_FN (BUILT_IN_FFS):
-    case BUILT_IN_FFSIMAX:
       target = expand_builtin_unop (target_mode, exp, target,
 				    subtarget, ffs_optab);
       if (target)
@@ -6115,7 +6114,6 @@ expand_builtin (tree exp, rtx target, rtx subtarget, enum machine_mode mode,
       break;
 
     CASE_INT_FN (BUILT_IN_CLZ):
-    case BUILT_IN_CLZIMAX:
       target = expand_builtin_unop (target_mode, exp, target,
 				    subtarget, clz_optab);
       if (target)
@@ -6123,7 +6121,6 @@ expand_builtin (tree exp, rtx target, rtx subtarget, enum machine_mode mode,
       break;
 
     CASE_INT_FN (BUILT_IN_CTZ):
-    case BUILT_IN_CTZIMAX:
       target = expand_builtin_unop (target_mode, exp, target,
 				    subtarget, ctz_optab);
       if (target)
@@ -6131,7 +6128,6 @@ expand_builtin (tree exp, rtx target, rtx subtarget, enum machine_mode mode,
       break;
 
     CASE_INT_FN (BUILT_IN_CLRSB):
-    case BUILT_IN_CLRSBIMAX:
       target = expand_builtin_unop (target_mode, exp, target,
 				    subtarget, clrsb_optab);
       if (target)
@@ -6139,7 +6135,6 @@ expand_builtin (tree exp, rtx target, rtx subtarget, enum machine_mode mode,
       break;
 
     CASE_INT_FN (BUILT_IN_POPCOUNT):
-    case BUILT_IN_POPCOUNTIMAX:
       target = expand_builtin_unop (target_mode, exp, target,
 				    subtarget, popcount_optab);
       if (target)
@@ -6147,7 +6142,6 @@ expand_builtin (tree exp, rtx target, rtx subtarget, enum machine_mode mode,
       break;
 
     CASE_INT_FN (BUILT_IN_PARITY):
-    case BUILT_IN_PARITYIMAX:
       target = expand_builtin_unop (target_mode, exp, target,
 				    subtarget, parity_optab);
       if (target)
@@ -8152,6 +8146,8 @@ fold_builtin_bitop (tree fndecl, tree arg)
 	  break;
 
 	CASE_INT_FN (BUILT_IN_CLRSB):
+	  if (width > 2 * HOST_BITS_PER_WIDE_INT)
+	    return NULL_TREE;
 	  if (width > HOST_BITS_PER_WIDE_INT
 	      && (hi & ((unsigned HOST_WIDE_INT) 1
 			<< (width - HOST_BITS_PER_WIDE_INT - 1))) != 0)
diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index a8e5f43..6506ae7 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -15606,6 +15606,8 @@ tree_call_nonnegative_warnv_p (tree type, tree fndecl,
 	CASE_INT_FN (BUILT_IN_FFS):
 	CASE_INT_FN (BUILT_IN_PARITY):
 	CASE_INT_FN (BUILT_IN_POPCOUNT):
+	CASE_INT_FN (BUILT_IN_CLZ):
+	CASE_INT_FN (BUILT_IN_CLRSB):
       case BUILT_IN_BSWAP32:
       case BUILT_IN_BSWAP64:
 	/* Always true.  */
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 7161536..2bc61c0 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2013-07-06  Jakub Jelinek  <jakub@redhat.com>
+
+	PR target/29776
+	* gcc.dg/tree-ssa/vrp89.c: New test.
+
 2013-07-06  Paolo Carlini  <paolo.carlini@oracle.com>
 
 	PR c++/28262
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp89.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp89.c
new file mode 100644
index 0000000..3e1d96e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp89.c
@@ -0,0 +1,57 @@
+/* PR target/29776 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-final { scan-tree-dump-not "link_error" "vrp1"} } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
+
+#define A(fn, arg, min, max) \
+  if (__builtin_##fn (arg) < min || __builtin_##fn (arg) > max) \
+    link_error ();
+#define B(fn, min, max) \
+  A (fn, a, min, max) A (fn##l, b, min, max) A (fn##ll, c, min, max)
+#define C(fn, min, sub) \
+  A (fn, a, min, ((int) sizeof (a) * __CHAR_BIT__ - sub)) \
+  A (fn##l, b, min, ((int) sizeof (b) * __CHAR_BIT__ - sub)) \
+  A (fn##ll, c, min, ((int) sizeof (c) * __CHAR_BIT__ - sub))
+#define D(fn, sub1, sub2) \
+  A (fn, a, ((int) sizeof (a) * __CHAR_BIT__ - sub1), \
+     ((int) sizeof (a) * __CHAR_BIT__ - sub2)) \
+  A (fn##l, b, ((int) sizeof (b) * __CHAR_BIT__ - sub1), \
+     ((int) sizeof (b) * __CHAR_BIT__ - sub2)) \
+  A (fn##ll, c, ((int) sizeof (c) * __CHAR_BIT__ - sub1), \
+     ((int) sizeof (c) * __CHAR_BIT__ - sub2))
+
+extern void link_error (void);
+
+unsigned int d;
+unsigned long e;
+unsigned long long f;
+
+void
+foo (unsigned int a, unsigned long b, unsigned long long c)
+{
+  B (parity, 0, 1)
+  C (ffs, 0, 0)
+  C (popcount, 0, 0)
+  C (clz, 0, 0)
+  C (ctz, -1, 0)
+  a &= 63;
+  b &= 63;
+  c &= 63;
+  B (ffs, 0, 6)
+  B (popcount, 0, 6)
+  a += 3; b += 3; c += 3;
+  B (ffs, 1, 7)
+  B (popcount, 1, 7)
+  a = 32U + (d & 1023U);
+  b = 32UL + (e & 1023UL);
+  c = 32ULL + (f & 1023ULL);
+  D (clz, 11, 6)
+  B (ctz, 0, 10)
+}
+
+void
+bar (int a, long b, long long c)
+{
+  C (clrsb, 0, 1)
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index ec7ef8f..ca9d8bd 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -3565,20 +3565,184 @@ extract_range_basic (value_range_t *vr, gimple stmt)
   bool sop = false;
   tree type = gimple_expr_type (stmt);
 
-  /* If the call is __builtin_constant_p and the argument is a
-     function parameter resolve it to false.  This avoids bogus
-     array bound warnings.
-     ???  We could do this as early as inlining is finished.  */
-  if (gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
-    {
-      tree arg = gimple_call_arg (stmt, 0);
-      if (TREE_CODE (arg) == SSA_NAME
-	  && SSA_NAME_IS_DEFAULT_DEF (arg)
-	  && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL)
-	set_value_range_to_null (vr, type);
-    }
-  else if (INTEGRAL_TYPE_P (type)
-	   && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
+  if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
+    {
+      tree fndecl = gimple_call_fndecl (stmt), arg;
+      int mini, maxi, zerov = 0, prec;
+
+      switch (DECL_FUNCTION_CODE (fndecl))
+	{
+	case BUILT_IN_CONSTANT_P:
+	  /* If the call is __builtin_constant_p and the argument is a
+	     function parameter resolve it to false.  This avoids bogus
+	     array bound warnings.
+	     ???  We could do this as early as inlining is finished.  */
+	  arg = gimple_call_arg (stmt, 0);
+	  if (TREE_CODE (arg) == SSA_NAME
+	      && SSA_NAME_IS_DEFAULT_DEF (arg)
+	      && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL)
+	    {
+	      set_value_range_to_null (vr, type);
+	      return;
+	    }
+	  break;
+	  /* Both __builtin_ffs* and __builtin_popcount return
+	     [0, prec].  */
+	CASE_INT_FN (BUILT_IN_FFS):
+	CASE_INT_FN (BUILT_IN_POPCOUNT):
+	  arg = gimple_call_arg (stmt, 0);
+	  prec = TYPE_PRECISION (TREE_TYPE (arg));
+	  mini = 0;
+	  maxi = prec;
+	  if (TREE_CODE (arg) == SSA_NAME)
+	    {
+	      value_range_t *vr0 = get_value_range (arg);
+	      /* If arg is non-zero, then ffs or popcount
+		 are non-zero.  */
+	      if (((vr0->type == VR_RANGE
+		    && integer_nonzerop (vr0->min))
+		   || (vr0->type == VR_ANTI_RANGE
+		       && integer_zerop (vr0->min)))
+		  && !TREE_OVERFLOW (vr0->min))
+		mini = 1;
+	      /* If some high bits are known to be zero,
+		 we can decrease the maximum.  */
+	      if (vr0->type == VR_RANGE
+		  && TREE_CODE (vr0->max) == INTEGER_CST
+		  && !TREE_OVERFLOW (vr0->max))
+		maxi = tree_floor_log2 (vr0->max) + 1;
+	    }
+	  goto bitop_builtin;
+	  /* __builtin_parity* returns [0, 1].  */
+	CASE_INT_FN (BUILT_IN_PARITY):
+	  mini = 0;
+	  maxi = 1;
+	  goto bitop_builtin;
+	  /* __builtin_c[lt]z* return [0, prec-1], except for
+	     when the argument is 0, but that is undefined behavior.
+	     On many targets where the CLZ RTL or optab value is defined
+	     for 0 the value is prec, so include that in the range
+	     by default.  */
+	CASE_INT_FN (BUILT_IN_CLZ):
+	  arg = gimple_call_arg (stmt, 0);
+	  prec = TYPE_PRECISION (TREE_TYPE (arg));
+	  mini = 0;
+	  maxi = prec;
+	  if (optab_handler (clz_optab, TYPE_MODE (TREE_TYPE (arg)))
+	      != CODE_FOR_nothing
+	      && CLZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (TREE_TYPE (arg)),
+					    zerov)
+	      /* Handle only the single common value.  */
+	      && zerov != prec)
+	    /* Magic value to give up, unless vr0 proves
+	       arg is non-zero.  */
+	    mini = -2;
+	  if (TREE_CODE (arg) == SSA_NAME)
+	    {
+	      value_range_t *vr0 = get_value_range (arg);
+	      /* From clz of VR_RANGE minimum we can compute
+		 result maximum.  */
+	      if (vr0->type == VR_RANGE
+		  && TREE_CODE (vr0->min) == INTEGER_CST
+		  && !TREE_OVERFLOW (vr0->min))
+		{
+		  maxi = prec - 1 - tree_floor_log2 (vr0->min);
+		  if (maxi != prec)
+		    mini = 0;
+		}
+	      else if (vr0->type == VR_ANTI_RANGE
+		       && integer_zerop (vr0->min)
+		       && !TREE_OVERFLOW (vr0->min))
+		{
+		  maxi = prec - 1;
+		  mini = 0;
+		}
+	      if (mini == -2)
+		break;
+	      /* From clz of VR_RANGE maximum we can compute
+		 result minimum.  */
+	      if (vr0->type == VR_RANGE
+		  && TREE_CODE (vr0->max) == INTEGER_CST
+		  && !TREE_OVERFLOW (vr0->max))
+		{
+		  mini = prec - 1 - tree_floor_log2 (vr0->max);
+		  if (mini == prec)
+		    break;
+		}
+	    }
+	  if (mini == -2)
+	    break;
+	  goto bitop_builtin;
+	  /* __builtin_ctz* return [0, prec-1], except for
+	     when the argument is 0, but that is undefined behavior.
+	     If there is a ctz optab for this mode and
+	     CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
+	     otherwise just assume 0 won't be seen.  */
+	CASE_INT_FN (BUILT_IN_CTZ):
+	  arg = gimple_call_arg (stmt, 0);
+	  prec = TYPE_PRECISION (TREE_TYPE (arg));
+	  mini = 0;
+	  maxi = prec - 1;
+	  if (optab_handler (ctz_optab, TYPE_MODE (TREE_TYPE (arg)))
+	      != CODE_FOR_nothing
+	      && CTZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (TREE_TYPE (arg)),
+					    zerov))
+	    {
+	      /* Handle only the two common values.  */
+	      if (zerov == -1)
+		mini = -1;
+	      else if (zerov == prec)
+		maxi = prec;
+	      else
+		/* Magic value to give up, unless vr0 proves
+		   arg is non-zero.  */
+		mini = -2;
+	    }
+	  if (TREE_CODE (arg) == SSA_NAME)
+	    {
+	      value_range_t *vr0 = get_value_range (arg);
+	      /* If arg is non-zero, then use [0, prec - 1].  */
+	      if (((vr0->type == VR_RANGE
+		    && integer_nonzerop (vr0->min))
+		   || (vr0->type == VR_ANTI_RANGE
+		       && integer_zerop (vr0->min)))
+		  && !TREE_OVERFLOW (vr0->min))
+		{
+		  mini = 0;
+		  maxi = prec - 1;
+		}
+	      /* If some high bits are known to be zero,
+		 we can decrease the result maximum.  */
+	      if (vr0->type == VR_RANGE
+		  && TREE_CODE (vr0->max) == INTEGER_CST
+		  && !TREE_OVERFLOW (vr0->max))
+		{
+		  maxi = tree_floor_log2 (vr0->max);
+		  /* For vr0 [0, 0] give up.  */
+		  if (maxi == -1)
+		    break;
+		}
+	    }
+	  if (mini == -2)
+	    break;
+	  goto bitop_builtin;
+	  /* __builtin_clrsb* returns [0, prec-1].  */
+	CASE_INT_FN (BUILT_IN_CLRSB):
+	  arg = gimple_call_arg (stmt, 0);
+	  prec = TYPE_PRECISION (TREE_TYPE (arg));
+	  mini = 0;
+	  maxi = prec - 1;
+	  goto bitop_builtin;
+	bitop_builtin:
+	  set_value_range (vr, VR_RANGE, build_int_cst (type, mini),
+			   build_int_cst (type, maxi), NULL);
+	  return;
+	default:
+	  break;
+	}
+    }
+  if (INTEGRAL_TYPE_P (type)
+      && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
     set_value_range_to_nonnegative (vr, type,
 				    sop || stmt_overflow_infinity (stmt));
   else if (vrp_stmt_computes_nonzero (stmt, &sop)
diff --git a/gcc/tree.h b/gcc/tree.h
index b444517..6297b49 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -322,7 +322,7 @@ extern const char * built_in_names[(int) END_BUILTINS];
 
 #define CASE_FLT_FN(FN) case FN: case FN##F: case FN##L
 #define CASE_FLT_FN_REENT(FN) case FN##_R: case FN##F_R: case FN##L_R
-#define CASE_INT_FN(FN) case FN: case FN##L: case FN##LL
+#define CASE_INT_FN(FN) case FN: case FN##L: case FN##LL: case FN##IMAX
 
 /* In an OMP_CLAUSE node.  */