Make tree_expr_nonnegative_warnv_p recurse into SSA names

The upcoming patch to move sqrt and cbrt simplifications to match.pd
caused a regression because the (abs @0)->@0 simplification didn't
trigger for:

        (abs (convert (abs X)))

The simplification is based on tree_expr_nonnegative_p, which at
the moment just gives up if it sees an SSA_NAME.

This patch makes tree_expr_nonnegative_p recurse into SSA name
definitions, but limits the depth of recursion to a small number
for the reason mentioned in the comment (adapted from an existing
comment in gimple_val_nonnegative_real_p).  The patch reuses code
in tree-vrp.c, moving it to gimple-fold.c.  It also replaces calls
to gimple_val_nonnegative_real_p with calls to tree_expr_nonnegative_p.

A knock-on effect is that we can now prove _i_589 < 0 is false in
sequences like:

      i_1917 = ASSERT_EXPR <i_1075, i_1075 == 0>;
      _i_589 = (const int) i_1917;
      _i_1507 = ASSERT_EXPR <_i_589, _i_589 < 0>;

This defeats an assert in tree-vrp.c that ASSERT_EXPR conditions
are never known to be false.  Previously the assert only ever used
local knowledge and so would be limited to cases like x != x for
integer x.  Now that we use global knowledge it's possible to prove
the assertion condition is false in blocks that are in practice
unreachable.  The patch therefore removes the assert.

Bootstrapped & regression-tested on x86_64-linux-gnu.  I didn't write
a specific test because this is already covered by the testsuite if
the follow-on patch is also applied.

gcc/
	* params.def (PARAM_MAX_SSA_NAME_QUERY_DEPTH): New param.
	* doc/invoke.texi (--param max-ssa-name-query-depth): Document.
	* fold-const.h (tree_unary_nonnegative_warnv_p)
	(tree_single_nonnegative_warnv_p, tree_call_nonnegative_warnv_p)
	(tree_expr_nonnegative_warnv_p): Add depth parameters.
	* fold-const.c: Include gimple-fold.h and params.h.
	(tree_ssa_name_nonnegative_warnv_p): New function.
	(tree_unary_nonnegative_warnv_p, tree_binary_nonnegative_warnv_p)
	(tree_single_nonnegative_warnv_p, tree_call_nonnegative_warnv_p)
	(tree_invalid_nonnegative_warnv_p, tree_expr_nonnegative_warnv_p):
	Add a depth parameter and increment it for recursive calls to
	tree_expr_nonnegative_warnv_p.  Use tree_ssa_name_nonnegative_warnv_p
	to handle SSA names.
	* gimple-fold.h (gimple_val_nonnegative_real_p): Delete.
	(gimple_stmt_nonnegative_warnv_p): Declare.
	* tree-vrp.c (remove_range_assertions): Remove assert that condition
	cannot be proven false.
	(gimple_assign_nonnegative_warnv_p, gimple_call_nonnegative_warnv_p)
	(gimple_stmt_nonnegative_warnv_p): Move to...
	* gimple-fold.c: ...here.  Add depth parameters and pass them
	down to the tree routines.  Accept statements that aren't
	assignments or calls but just return false for them.
	(gimple_val_nonnegative_real_p): Delete.
	* tree-ssa-math-opts.c (gimple_expand_builtin_pow): Use
	tree_expr_nonnegative_p instead of gimple_val_nonnegative_real_p.
	Check HONOR_NANs first.

From-SVN: r228614

1 files changed, 84 insertions, 87 deletions

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 2851a29..5d8822f 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -77,6 +77,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "cgraph.h"
 #include "generic-match.h"
 #include "optabs-query.h"
+#include "gimple-fold.h"
+#include "params.h"
 
 #ifndef LOAD_EXTEND_OP
 #define LOAD_EXTEND_OP(M) UNKNOWN
@@ -12749,6 +12751,12 @@ multiple_of_p (tree type, const_tree top, const_tree bottom)
     }
 }
 
+#define tree_expr_nonnegative_warnv_p(X, Y) \
+  _Pragma ("GCC error \"Use RECURSE for recursive calls\"") 0
+
+#define RECURSE(X) \
+  ((tree_expr_nonnegative_warnv_p) (X, strict_overflow_p, depth + 1))
+
 /* Return true if CODE or TYPE is known to be non-negative. */
 
 static bool
@@ -12765,11 +12773,11 @@ tree_simple_nonnegative_warnv_p (enum tree_code code, tree type)
 /* Return true if (CODE OP0) is known to be non-negative.  If the return
    value is based on the assumption that signed overflow is undefined,
    set *STRICT_OVERFLOW_P to true; otherwise, don't change
-   *STRICT_OVERFLOW_P.  */
+   *STRICT_OVERFLOW_P.  DEPTH is the current nesting depth of the query.  */
 
 bool
 tree_unary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
-				bool *strict_overflow_p)
+				bool *strict_overflow_p, int depth)
 {
   if (TYPE_UNSIGNED (type))
     return true;
@@ -12791,8 +12799,7 @@ tree_unary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
     case NON_LVALUE_EXPR:
     case FLOAT_EXPR:
     case FIX_TRUNC_EXPR:
-      return tree_expr_nonnegative_warnv_p (op0,
-					    strict_overflow_p);
+      return RECURSE (op0);
 
     CASE_CONVERT:
       {
@@ -12802,21 +12809,18 @@ tree_unary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
 	if (TREE_CODE (outer_type) == REAL_TYPE)
 	  {
 	    if (TREE_CODE (inner_type) == REAL_TYPE)
-	      return tree_expr_nonnegative_warnv_p (op0,
-						    strict_overflow_p);
+	      return RECURSE (op0);
 	    if (INTEGRAL_TYPE_P (inner_type))
 	      {
 		if (TYPE_UNSIGNED (inner_type))
 		  return true;
-		return tree_expr_nonnegative_warnv_p (op0,
-						      strict_overflow_p);
+		return RECURSE (op0);
 	      }
 	  }
 	else if (INTEGRAL_TYPE_P (outer_type))
 	  {
 	    if (TREE_CODE (inner_type) == REAL_TYPE)
-	      return tree_expr_nonnegative_warnv_p (op0,
-						    strict_overflow_p);
+	      return RECURSE (op0);
 	    if (INTEGRAL_TYPE_P (inner_type))
 	      return TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type)
 		      && TYPE_UNSIGNED (inner_type);
@@ -12835,11 +12839,12 @@ tree_unary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
 /* Return true if (CODE OP0 OP1) is known to be non-negative.  If the return
    value is based on the assumption that signed overflow is undefined,
    set *STRICT_OVERFLOW_P to true; otherwise, don't change
-   *STRICT_OVERFLOW_P.  */
+   *STRICT_OVERFLOW_P.  DEPTH is the current nesting depth of the query.  */
 
 bool
 tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
-				      tree op1, bool *strict_overflow_p)
+				 tree op1, bool *strict_overflow_p,
+				 int depth)
 {
   if (TYPE_UNSIGNED (type))
     return true;
@@ -12849,10 +12854,7 @@ tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
     case POINTER_PLUS_EXPR:
     case PLUS_EXPR:
       if (FLOAT_TYPE_P (type))
-	return (tree_expr_nonnegative_warnv_p (op0,
-					       strict_overflow_p)
-		&& tree_expr_nonnegative_warnv_p (op1,
-						  strict_overflow_p));
+	return RECURSE (op0) && RECURSE (op1);
 
       /* zero_extend(x) + zero_extend(y) is non-negative if x and y are
 	 both unsigned and at least 2 bits shorter than the result.  */
@@ -12878,8 +12880,7 @@ tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
 	  /* x * x is always non-negative for floating point x
 	     or without overflow.  */
 	  if (operand_equal_p (op0, op1, 0)
-	      || (tree_expr_nonnegative_warnv_p (op0, strict_overflow_p)
-		  && tree_expr_nonnegative_warnv_p (op1, strict_overflow_p)))
+	      || (RECURSE (op0) && RECURSE (op1)))
 	    {
 	      if (ANY_INTEGRAL_TYPE_P (type)
 		  && TYPE_OVERFLOW_UNDEFINED (type))
@@ -12928,10 +12929,7 @@ tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
 
     case BIT_AND_EXPR:
     case MAX_EXPR:
-      return (tree_expr_nonnegative_warnv_p (op0,
-					     strict_overflow_p)
-	      || tree_expr_nonnegative_warnv_p (op1,
-						strict_overflow_p));
+      return RECURSE (op0) || RECURSE (op1);
 
     case BIT_IOR_EXPR:
     case BIT_XOR_EXPR:
@@ -12941,17 +12939,14 @@ tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
     case CEIL_DIV_EXPR:
     case FLOOR_DIV_EXPR:
     case ROUND_DIV_EXPR:
-      return (tree_expr_nonnegative_warnv_p (op0,
-					     strict_overflow_p)
-	      && tree_expr_nonnegative_warnv_p (op1,
-						strict_overflow_p));
+      return RECURSE (op0) && RECURSE (op1);
 
     case TRUNC_MOD_EXPR:
     case CEIL_MOD_EXPR:
     case FLOOR_MOD_EXPR:
     case ROUND_MOD_EXPR:
-      return tree_expr_nonnegative_warnv_p (op0,
-					    strict_overflow_p);
+      return RECURSE (op0);
+
     default:
       return tree_simple_nonnegative_warnv_p (code, type);
     }
@@ -12960,13 +12955,32 @@ tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0,
   return false;
 }
 
+/* Return true if SSA name T is known to be non-negative.  If the return
+   value is based on the assumption that signed overflow is undefined,
+   set *STRICT_OVERFLOW_P to true; otherwise, don't change
+   *STRICT_OVERFLOW_P.  DEPTH is the current nesting depth of the query.  */
+
+static bool
+tree_ssa_name_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth)
+{
+  /* Limit the depth of recursion to avoid quadratic behavior.
+     This is expected to catch almost all occurrences in practice.
+     If this code misses important cases that unbounded recursion
+     would not, passes that need this information could be revised
+     to provide it through dataflow propagation.  */
+  if (depth < PARAM_VALUE (PARAM_MAX_SSA_NAME_QUERY_DEPTH))
+    return gimple_stmt_nonnegative_warnv_p (SSA_NAME_DEF_STMT (t),
+					    strict_overflow_p, depth);
+  return tree_simple_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t));
+}
+
 /* Return true if T is known to be non-negative.  If the return
    value is based on the assumption that signed overflow is undefined,
    set *STRICT_OVERFLOW_P to true; otherwise, don't change
-   *STRICT_OVERFLOW_P.  */
+   *STRICT_OVERFLOW_P.  DEPTH is the current nesting depth of the query.  */
 
 bool
-tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p)
+tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth)
 {
   if (TYPE_UNSIGNED (TREE_TYPE (t)))
     return true;
@@ -12983,26 +12997,24 @@ tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p)
       return ! FIXED_VALUE_NEGATIVE (TREE_FIXED_CST (t));
 
     case COND_EXPR:
-      return (tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 1),
-					     strict_overflow_p)
-	      && tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 2),
-						strict_overflow_p));
+      return RECURSE (TREE_OPERAND (t, 1)) && RECURSE (TREE_OPERAND (t, 2));
+
+    case SSA_NAME:
+      return tree_ssa_name_nonnegative_warnv_p (t, strict_overflow_p, depth);
+
     default:
-      return tree_simple_nonnegative_warnv_p (TREE_CODE (t),
-						   TREE_TYPE (t));
+      return tree_simple_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t));
     }
-  /* We don't know sign of `t', so be conservative and return false.  */
-  return false;
 }
 
 /* Return true if T is known to be non-negative.  If the return
    value is based on the assumption that signed overflow is undefined,
    set *STRICT_OVERFLOW_P to true; otherwise, don't change
-   *STRICT_OVERFLOW_P.  */
+   *STRICT_OVERFLOW_P.  DEPTH is the current nesting depth of the query.  */
 
 bool
-tree_call_nonnegative_warnv_p (tree type, tree fndecl,
-			       tree arg0, tree arg1, bool *strict_overflow_p)
+tree_call_nonnegative_warnv_p (tree type, tree fndecl, tree arg0, tree arg1,
+			       bool *strict_overflow_p, int depth)
 {
   if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
     switch (DECL_FUNCTION_CODE (fndecl))
@@ -13033,8 +13045,7 @@ tree_call_nonnegative_warnv_p (tree type, tree fndecl,
 	/* sqrt(-0.0) is -0.0.  */
 	if (!HONOR_SIGNED_ZEROS (element_mode (type)))
 	  return true;
-	return tree_expr_nonnegative_warnv_p (arg0,
-					      strict_overflow_p);
+	return RECURSE (arg0);
 
 	CASE_FLT_FN (BUILT_IN_ASINH):
 	CASE_FLT_FN (BUILT_IN_ATAN):
@@ -13072,27 +13083,19 @@ tree_call_nonnegative_warnv_p (tree type, tree fndecl,
 	CASE_FLT_FN (BUILT_IN_TANH):
 	CASE_FLT_FN (BUILT_IN_TRUNC):
 	/* True if the 1st argument is nonnegative.  */
-	return tree_expr_nonnegative_warnv_p (arg0,
-					      strict_overflow_p);
+	return RECURSE (arg0);
 
 	CASE_FLT_FN (BUILT_IN_FMAX):
 	/* True if the 1st OR 2nd arguments are nonnegative.  */
-	return (tree_expr_nonnegative_warnv_p (arg0,
-					       strict_overflow_p)
-		|| (tree_expr_nonnegative_warnv_p (arg1,
-						   strict_overflow_p)));
+	return RECURSE (arg0) || RECURSE (arg1);
 
 	CASE_FLT_FN (BUILT_IN_FMIN):
 	/* True if the 1st AND 2nd arguments are nonnegative.  */
-	return (tree_expr_nonnegative_warnv_p (arg0,
-					       strict_overflow_p)
-		&& (tree_expr_nonnegative_warnv_p (arg1,
-						   strict_overflow_p)));
+	return RECURSE (arg0) && RECURSE (arg1);
 
 	CASE_FLT_FN (BUILT_IN_COPYSIGN):
 	/* True if the 2nd argument is nonnegative.  */
-	return tree_expr_nonnegative_warnv_p (arg1,
-					      strict_overflow_p);
+	return RECURSE (arg1);
 
 	CASE_FLT_FN (BUILT_IN_POWI):
 	/* True if the 1st argument is nonnegative or the second
@@ -13100,8 +13103,7 @@ tree_call_nonnegative_warnv_p (tree type, tree fndecl,
 	if (TREE_CODE (arg1) == INTEGER_CST
 	    && (TREE_INT_CST_LOW (arg1) & 1) == 0)
 	  return true;
-	return tree_expr_nonnegative_warnv_p (arg0,
-					      strict_overflow_p);
+	return RECURSE (arg0);
 
 	CASE_FLT_FN (BUILT_IN_POW):
 	/* True if the 1st argument is nonnegative or the second
@@ -13121,23 +13123,21 @@ tree_call_nonnegative_warnv_p (tree type, tree fndecl,
 		  return true;
 	      }
 	  }
-	return tree_expr_nonnegative_warnv_p (arg0,
-					      strict_overflow_p);
+	return RECURSE (arg0);
 
       default:
 	break;
       }
-  return tree_simple_nonnegative_warnv_p (CALL_EXPR,
-					  type);
+  return tree_simple_nonnegative_warnv_p (CALL_EXPR, type);
 }
 
 /* Return true if T is known to be non-negative.  If the return
    value is based on the assumption that signed overflow is undefined,
    set *STRICT_OVERFLOW_P to true; otherwise, don't change
-   *STRICT_OVERFLOW_P.  */
+   *STRICT_OVERFLOW_P.  DEPTH is the current nesting depth of the query.  */
 
 static bool
-tree_invalid_nonnegative_warnv_p (tree t, bool *strict_overflow_p)
+tree_invalid_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth)
 {
   enum tree_code code = TREE_CODE (t);
   if (TYPE_UNSIGNED (TREE_TYPE (t)))
@@ -13153,7 +13153,7 @@ tree_invalid_nonnegative_warnv_p (tree t, bool *strict_overflow_p)
 	/* If the initializer is non-void, then it's a normal expression
 	   that will be assigned to the slot.  */
 	if (!VOID_TYPE_P (t))
-	  return tree_expr_nonnegative_warnv_p (t, strict_overflow_p);
+	  return RECURSE (t);
 
 	/* Otherwise, the initializer sets the slot in some way.  One common
 	   way is an assignment statement at the end of the initializer.  */
@@ -13171,8 +13171,7 @@ tree_invalid_nonnegative_warnv_p (tree t, bool *strict_overflow_p)
 	  }
 	if (TREE_CODE (t) == MODIFY_EXPR
 	    && TREE_OPERAND (t, 0) == temp)
-	  return tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 1),
-						strict_overflow_p);
+	  return RECURSE (TREE_OPERAND (t, 1));
 
 	return false;
       }
@@ -13186,35 +13185,33 @@ tree_invalid_nonnegative_warnv_p (tree t, bool *strict_overflow_p)
 					      get_callee_fndecl (t),
 					      arg0,
 					      arg1,
-					      strict_overflow_p);
+					      strict_overflow_p, depth);
       }
     case COMPOUND_EXPR:
     case MODIFY_EXPR:
-      return tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 1),
-					    strict_overflow_p);
+      return RECURSE (TREE_OPERAND (t, 1));
+
     case BIND_EXPR:
-      return tree_expr_nonnegative_warnv_p (expr_last (TREE_OPERAND (t, 1)),
-					    strict_overflow_p);
+      return RECURSE (expr_last (TREE_OPERAND (t, 1)));
+
     case SAVE_EXPR:
-      return tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 0),
-					    strict_overflow_p);
+      return RECURSE (TREE_OPERAND (t, 0));
 
     default:
-      return tree_simple_nonnegative_warnv_p (TREE_CODE (t),
-						   TREE_TYPE (t));
+      return tree_simple_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t));
     }
-
-  /* We don't know sign of `t', so be conservative and return false.  */
-  return false;
 }
 
+#undef RECURSE
+#undef tree_expr_nonnegative_warnv_p
+
 /* Return true if T is known to be non-negative.  If the return
    value is based on the assumption that signed overflow is undefined,
    set *STRICT_OVERFLOW_P to true; otherwise, don't change
-   *STRICT_OVERFLOW_P.  */
+   *STRICT_OVERFLOW_P.  DEPTH is the current nesting depth of the query.  */
 
 bool
-tree_expr_nonnegative_warnv_p (tree t, bool *strict_overflow_p)
+tree_expr_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth)
 {
   enum tree_code code;
   if (t == error_mark_node)
@@ -13229,18 +13226,18 @@ tree_expr_nonnegative_warnv_p (tree t, bool *strict_overflow_p)
 					      TREE_TYPE (t),
 					      TREE_OPERAND (t, 0),
 					      TREE_OPERAND (t, 1),
-					      strict_overflow_p);
+					      strict_overflow_p, depth);
 
     case tcc_unary:
       return tree_unary_nonnegative_warnv_p (TREE_CODE (t),
 					     TREE_TYPE (t),
 					     TREE_OPERAND (t, 0),
-					     strict_overflow_p);
+					     strict_overflow_p, depth);
 
     case tcc_constant:
     case tcc_declaration:
     case tcc_reference:
-      return tree_single_nonnegative_warnv_p (t, strict_overflow_p);
+      return tree_single_nonnegative_warnv_p (t, strict_overflow_p, depth);
 
     default:
       break;
@@ -13255,12 +13252,12 @@ tree_expr_nonnegative_warnv_p (tree t, bool *strict_overflow_p)
 					      TREE_TYPE (t),
 					      TREE_OPERAND (t, 0),
 					      TREE_OPERAND (t, 1),
-					      strict_overflow_p);
+					      strict_overflow_p, depth);
     case TRUTH_NOT_EXPR:
       return tree_unary_nonnegative_warnv_p (TREE_CODE (t),
 					     TREE_TYPE (t),
 					     TREE_OPERAND (t, 0),
-					     strict_overflow_p);
+					     strict_overflow_p, depth);
 
     case COND_EXPR:
     case CONSTRUCTOR:
@@ -13269,10 +13266,10 @@ tree_expr_nonnegative_warnv_p (tree t, bool *strict_overflow_p)
     case ADDR_EXPR:
     case WITH_SIZE_EXPR:
     case SSA_NAME:
-      return tree_single_nonnegative_warnv_p (t, strict_overflow_p);
+      return tree_single_nonnegative_warnv_p (t, strict_overflow_p, depth);
 
     default:
-      return tree_invalid_nonnegative_warnv_p (t, strict_overflow_p);
+      return tree_invalid_nonnegative_warnv_p (t, strict_overflow_p, depth);
     }
 }