Convert -Walloca pass to ranger.

gcc/ChangeLog:

	* gimple-ssa-warn-alloca.c (enum alloca_type): Remove
	ALLOCA_BOUND_UNKNOWN and ALLOCA_CAST_FROM_SIGNED.
	(warn_limit_specified_p): New.
	(alloca_call_type_by_arg): Remove.
	(cast_from_signed_p): Remove.
	(is_max): Remove.
	(alloca_call_type): Remove heuristics and replace with call into
	ranger.
	(pass_walloca::execute): Instantiate ranger.

gcc/testsuite/ChangeLog:

	* gcc.dg/Walloca-1.c: Adjust for ranger.
	* gcc.dg/Walloca-12.c: Same.
	* gcc.dg/Walloca-13.c: Same.
	* gcc.dg/Walloca-2.c: Same.
	* gcc.dg/Walloca-3.c: Same.
	* gcc.dg/Walloca-6.c: Same.
	* gcc.dg/Wvla-larger-than-2.c: Same.

1 files changed, 44 insertions, 307 deletions

diff --git a/gcc/gimple-ssa-warn-alloca.c b/gcc/gimple-ssa-warn-alloca.c
index 9e80e5d..33824a7 100644
--- a/gcc/gimple-ssa-warn-alloca.c
+++ b/gcc/gimple-ssa-warn-alloca.c
@@ -36,6 +36,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "calls.h"
 #include "cfgloop.h"
 #include "intl.h"
+#include "gimple-range.h"
 
 static unsigned HOST_WIDE_INT adjusted_warn_limit (bool);
 
@@ -99,12 +100,6 @@ enum alloca_type {
   // Alloca argument may be too large.
   ALLOCA_BOUND_MAYBE_LARGE,
 
-  // Alloca argument is bounded but of an indeterminate size.
-  ALLOCA_BOUND_UNKNOWN,
-
-  // Alloca argument was casted from a signed integer.
-  ALLOCA_CAST_FROM_SIGNED,
-
   // Alloca appears in a loop.
   ALLOCA_IN_LOOP,
 
@@ -135,6 +130,15 @@ public:
   }
 };
 
+/* Return TRUE if the user specified a limit for either VLAs or ALLOCAs.  */
+
+static bool
+warn_limit_specified_p (bool is_vla)
+{
+  unsigned HOST_WIDE_INT max = is_vla ? warn_vla_limit : warn_alloca_limit;
+  return max != HOST_WIDE_INT_MAX;
+}
+
 /* Return the value of the argument N to -Walloca-larger-than= or
    -Wvla-larger-than= adjusted for the target data model so that
    when N == HOST_WIDE_INT_MAX, the adjusted value is set to
@@ -158,183 +162,15 @@ adjusted_warn_limit (bool idx)
   return limits[idx];
 }
 
-
-// NOTE: When we get better range info, this entire function becomes
-// irrelevant, as it should be possible to get range info for an SSA
-// name at any point in the program.
-//
-// We have a few heuristics up our sleeve to determine if a call to
-// alloca() is within bounds.  Try them out and return the type of
-// alloca call with its assumed limit (if applicable).
-//
-// Given a known argument (ARG) to alloca() and an EDGE (E)
-// calculating said argument, verify that the last statement in the BB
-// in E->SRC is a gate comparing ARG to an acceptable bound for
-// alloca().  See examples below.
-//
-// If set, ARG_CASTED is the possible unsigned argument to which ARG
-// was casted to.  This is to handle cases where the controlling
-// predicate is looking at a casted value, not the argument itself.
-//    arg_casted = (size_t) arg;
-//    if (arg_casted < N)
-//      goto bb3;
-//    else
-//      goto bb5;
-//
-// MAX_SIZE is WARN_ALLOCA= adjusted for VLAs.  It is the maximum size
-// in bytes we allow for arg.
-
-static class alloca_type_and_limit
-alloca_call_type_by_arg (tree arg, tree arg_casted, edge e,
-			 unsigned HOST_WIDE_INT max_size)
-{
-  basic_block bb = e->src;
-  gimple_stmt_iterator gsi = gsi_last_bb (bb);
-  gimple *last = gsi_stmt (gsi);
-
-  const offset_int maxobjsize = tree_to_shwi (max_object_size ());
-
-  /* When MAX_SIZE is greater than or equal to PTRDIFF_MAX treat
-     allocations that aren't visibly constrained as OK, otherwise
-     report them as (potentially) unbounded.  */
-  alloca_type unbounded_result = (max_size < maxobjsize.to_uhwi ()
-				  ? ALLOCA_UNBOUNDED : ALLOCA_OK);
-
-  if (!last || gimple_code (last) != GIMPLE_COND)
-    {
-      return alloca_type_and_limit (unbounded_result);
-    }
-
-  enum tree_code cond_code = gimple_cond_code (last);
-  if (e->flags & EDGE_TRUE_VALUE)
-    ;
-  else if (e->flags & EDGE_FALSE_VALUE)
-    cond_code = invert_tree_comparison (cond_code, false);
-  else
-      return alloca_type_and_limit (unbounded_result);
-
-  // Check for:
-  //   if (ARG .COND. N)
-  //     goto <bb 3>;
-  //   else
-  //     goto <bb 4>;
-  //   <bb 3>:
-  //   alloca(ARG);
-  if ((cond_code == LE_EXPR
-       || cond_code == LT_EXPR
-       || cond_code == GT_EXPR
-       || cond_code == GE_EXPR)
-      && (gimple_cond_lhs (last) == arg
-	  || gimple_cond_lhs (last) == arg_casted))
-    {
-      if (TREE_CODE (gimple_cond_rhs (last)) == INTEGER_CST)
-	{
-	  tree rhs = gimple_cond_rhs (last);
-	  int tst = wi::cmpu (wi::to_widest (rhs), max_size);
-	  if ((cond_code == LT_EXPR && tst == -1)
-	      || (cond_code == LE_EXPR && (tst == -1 || tst == 0)))
-	    return alloca_type_and_limit (ALLOCA_OK);
-	  else
-	    {
-	      // Let's not get too specific as to how large the limit
-	      // may be.  Someone's clearly an idiot when things
-	      // degrade into "if (N > Y) alloca(N)".
-	      if (cond_code == GT_EXPR || cond_code == GE_EXPR)
-		rhs = integer_zero_node;
-	      return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
-					    wi::to_wide (rhs));
-	    }
-	}
-      else
-	{
-	  /* Analogous to ALLOCA_UNBOUNDED, when MAX_SIZE is greater
-	     than or equal to PTRDIFF_MAX, treat allocations with
-	     an unknown bound as OK.  */
-	  alloca_type unknown_result
-	    = (max_size < maxobjsize.to_uhwi ()
-	       ? ALLOCA_BOUND_UNKNOWN : ALLOCA_OK);
-	  return alloca_type_and_limit (unknown_result);
-	}
-    }
-
-  // Similarly, but check for a comparison with an unknown LIMIT.
-  //   if (LIMIT .COND. ARG)
-  //     alloca(arg);
-  //
-  //   Where LIMIT has a bound of unknown range.
-  //
-  // Note: All conditions of the form (ARG .COND. XXXX) where covered
-  // by the previous check above, so we only need to look for (LIMIT
-  // .COND. ARG) here.
-  tree limit = gimple_cond_lhs (last);
-  if ((gimple_cond_rhs (last) == arg
-       || gimple_cond_rhs (last) == arg_casted)
-      && TREE_CODE (limit) == SSA_NAME)
-    {
-      wide_int min, max;
-      value_range_kind range_type = get_range_info (limit, &min, &max);
-
-      if (range_type == VR_UNDEFINED || range_type == VR_VARYING)
-	return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN);
-
-      // ?? It looks like the above `if' is unnecessary, as we never
-      // get any VR_RANGE or VR_ANTI_RANGE here.  If we had a range
-      // for LIMIT, I suppose we would have taken care of it in
-      // alloca_call_type(), or handled above where we handle (ARG .COND. N).
-      //
-      // If this ever triggers, we should probably figure out why and
-      // handle it, though it is likely to be just an ALLOCA_UNBOUNDED.
-      return alloca_type_and_limit (unbounded_result);
-    }
-
-  return alloca_type_and_limit (unbounded_result);
-}
-
-// Return TRUE if SSA's definition is a cast from a signed type.
-// If so, set *INVALID_CASTED_TYPE to the signed type.
-
-static bool
-cast_from_signed_p (tree ssa, tree *invalid_casted_type)
-{
-  gimple *def = SSA_NAME_DEF_STMT (ssa);
-  if (def
-      && !gimple_nop_p (def)
-      && gimple_assign_cast_p (def)
-      && !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def))))
-    {
-      *invalid_casted_type = TREE_TYPE (gimple_assign_rhs1 (def));
-      return true;
-    }
-  return false;
-}
-
-// Return TRUE if X has a maximum range of MAX, basically covering the
-// entire domain, in which case it's no range at all.
-
-static bool
-is_max (tree x, wide_int max)
-{
-  return wi::max_value (TREE_TYPE (x)) == max;
-}
-
 // Analyze the alloca call in STMT and return the alloca type with its
 // corresponding limit (if applicable).  IS_VLA is set if the alloca
 // call was created by the gimplifier for a VLA.
-//
-// If the alloca call may be too large because of a cast from a signed
-// type to an unsigned type, set *INVALID_CASTED_TYPE to the
-// problematic signed type.
 
 static class alloca_type_and_limit
-alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
+alloca_call_type (range_query &query, gimple *stmt, bool is_vla)
 {
   gcc_assert (gimple_alloca_call_p (stmt));
-  bool tentative_cast_from_signed = false;
   tree len = gimple_call_arg (stmt, 0);
-  tree len_casted = NULL;
-  wide_int min, max;
-  edge_iterator ei;
-  edge e;
 
   gcc_assert (!is_vla || warn_vla_limit >= 0);
   gcc_assert (is_vla || warn_alloca_limit >= 0);
@@ -361,118 +197,9 @@ alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
       return alloca_type_and_limit (ALLOCA_OK);
     }
 
-  // Check the range info if available.
-  if (TREE_CODE (len) == SSA_NAME)
-    {
-      value_range_kind range_type = get_range_info (len, &min, &max);
-      if (range_type == VR_RANGE)
-	{
-	  if (wi::leu_p (max, max_size))
-	    return alloca_type_and_limit (ALLOCA_OK);
-	  else
-	    {
-	      // A cast may have created a range we don't care
-	      // about.  For instance, a cast from 16-bit to
-	      // 32-bit creates a range of 0..65535, even if there
-	      // is not really a determinable range in the
-	      // underlying code.  In this case, look through the
-	      // cast at the original argument, and fall through
-	      // to look at other alternatives.
-	      //
-	      // We only look at through the cast when its from
-	      // unsigned to unsigned, otherwise we may risk
-	      // looking at SIGNED_INT < N, which is clearly not
-	      // what we want.  In this case, we'd be interested
-	      // in a VR_RANGE of [0..N].
-	      //
-	      // Note: None of this is perfect, and should all go
-	      // away with better range information.  But it gets
-	      // most of the cases.
-	      gimple *def = SSA_NAME_DEF_STMT (len);
-	      if (gimple_assign_cast_p (def))
-		{
-		  tree rhs1 = gimple_assign_rhs1 (def);
-		  tree rhs1type = TREE_TYPE (rhs1);
-
-		  // Bail if the argument type is not valid.
-		  if (!INTEGRAL_TYPE_P (rhs1type))
-		    return alloca_type_and_limit (ALLOCA_OK);
-
-		  if (TYPE_UNSIGNED (rhs1type))
-		    {
-		      len_casted = rhs1;
-		      range_type = get_range_info (len_casted, &min, &max);
-		    }
-		}
-	      // An unknown range or a range of the entire domain is
-	      // really no range at all.
-	      if (range_type == VR_VARYING
-		  || (!len_casted && is_max (len, max))
-		  || (len_casted && is_max (len_casted, max)))
-		{
-		  // Fall through.
-		}
-	      else if (range_type == VR_ANTI_RANGE)
-		return alloca_type_and_limit (ALLOCA_UNBOUNDED);
-
-	      if (range_type != VR_VARYING)
-		{
-		  const offset_int maxobjsize
-		    = wi::to_offset (max_object_size ());
-		  alloca_type result = (max_size < maxobjsize
-					? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK);
-		  return alloca_type_and_limit (result, max);
-		}
-	    }
-	}
-      else if (range_type == VR_ANTI_RANGE)
-	{
-	  // There may be some wrapping around going on.  Catch it
-	  // with this heuristic.  Hopefully, this VR_ANTI_RANGE
-	  // nonsense will go away, and we won't have to catch the
-	  // sign conversion problems with this crap.
-	  //
-	  // This is here to catch things like:
-	  // void foo(signed int n) {
-	  //   if (n < 100)
-	  //     alloca(n);
-	  //   ...
-	  // }
-	  if (cast_from_signed_p (len, invalid_casted_type))
-	    {
-	      // Unfortunately this also triggers:
-	      //
-	      // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah;
-	      // if (n < 100)
-	      //   alloca(n);
-	      //
-	      // ...which is clearly bounded.  So, double check that
-	      // the paths leading up to the size definitely don't
-	      // have a bound.
-	      tentative_cast_from_signed = true;
-	    }
-	}
-      // No easily determined range and try other things.
-    }
-
-  // If we couldn't find anything, try a few heuristics for things we
-  // can easily determine.  Check these misc cases but only accept
-  // them if all predecessors have a known bound.
-  class alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK);
-  FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
-    {
-      gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted)));
-      ret = alloca_call_type_by_arg (len, len_casted, e, max_size);
-      if (ret.type != ALLOCA_OK)
-	break;
-    }
-
-  if (ret.type != ALLOCA_OK && tentative_cast_from_signed)
-    ret = alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED);
-
+  struct alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK);
   // If we have a declared maximum size, we can take it into account.
-  if (ret.type != ALLOCA_OK
-      && gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
+  if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
     {
       tree arg = gimple_call_arg (stmt, 2);
       if (compare_tree_int (arg, max_size) <= 0)
@@ -485,9 +212,37 @@ alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
 				? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK);
 	  ret = alloca_type_and_limit (result, wi::to_wide (arg));
 	}
+      return ret;
+    }
+
+  // If the user specified a limit, use it.
+  int_range_max r;
+  if (warn_limit_specified_p (is_vla)
+      && TREE_CODE (len) == SSA_NAME
+      && query.range_of_expr (r, len, stmt)
+      && !r.varying_p ())
+    {
+      // The invalid bits are anything outside of [0, MAX_SIZE].
+      static int_range<2> invalid_range (build_int_cst (size_type_node, 0),
+					 build_int_cst (size_type_node,
+							max_size),
+					 VR_ANTI_RANGE);
+
+      r.intersect (invalid_range);
+      if (r.undefined_p ())
+	return alloca_type_and_limit (ALLOCA_OK);
+
+      return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
+				    wi::to_wide (integer_zero_node));
     }
 
-  return ret;
+  const offset_int maxobjsize = tree_to_shwi (max_object_size ());
+  /* When MAX_SIZE is greater than or equal to PTRDIFF_MAX treat
+     allocations that aren't visibly constrained as OK, otherwise
+     report them as (potentially) unbounded.  */
+  alloca_type unbounded_result = (max_size < maxobjsize.to_uhwi ()
+				  ? ALLOCA_UNBOUNDED : ALLOCA_OK);
+  return alloca_type_and_limit (unbounded_result);
 }
 
 // Return TRUE if STMT is in a loop, otherwise return FALSE.
@@ -503,6 +258,7 @@ in_loop_p (gimple *stmt)
 unsigned int
 pass_walloca::execute (function *fun)
 {
+  gimple_ranger ranger;
   basic_block bb;
   FOR_EACH_BB_FN (bb, fun)
     {
@@ -535,9 +291,8 @@ pass_walloca::execute (function *fun)
 	  else if (warn_alloca_limit < 0)
 	    continue;
 
-	  tree invalid_casted_type = NULL;
 	  class alloca_type_and_limit t
-	    = alloca_call_type (stmt, is_vla, &invalid_casted_type);
+	    = alloca_call_type (ranger, stmt, is_vla);
 
 	  unsigned HOST_WIDE_INT adjusted_alloca_limit
 	    = adjusted_warn_limit (false);
@@ -599,13 +354,6 @@ pass_walloca::execute (function *fun)
 		  }
 	      }
 	      break;
-	    case ALLOCA_BOUND_UNKNOWN:
-	      warning_at (loc, wcode,
-			  (is_vla
-			   ? G_("%Gvariable-length array bound is unknown")
-			   : G_("%G%<alloca%> bound is unknown")),
-			  stmt);
-	      break;
 	    case ALLOCA_UNBOUNDED:
 	      warning_at (loc, wcode,
 			  (is_vla
@@ -618,17 +366,6 @@ pass_walloca::execute (function *fun)
 	      warning_at (loc, wcode,
 			  "%Guse of %<alloca%> within a loop", stmt);
 	      break;
-	    case ALLOCA_CAST_FROM_SIGNED:
-	      gcc_assert (invalid_casted_type != NULL_TREE);
-	      warning_at (loc, wcode,
-			  (is_vla
-			   ? G_("%Gargument to variable-length array "
-				"may be too large due to "
-				"conversion from %qT to %qT")
-			   : G_("%Gargument to %<alloca%> may be too large "
-				"due to conversion from %qT to %qT")),
-			  stmt, invalid_casted_type, size_type_node);
-	      break;
 	    case ALLOCA_ARG_IS_ZERO:
 	      warning_at (loc, wcode,
 			  (is_vla