Re: Determine more IVs to be non-overflowing

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
this is updated version of patch. I finally convinced myself to read bit of
wide-int.h and learnt some new things, like that they exists in multiple
precisions.  I always tought of wide-int as wider version of HOST_WIDE_INT that
can hold all of target data types with not-so handy API because it lacks the
signed flag :)

The version bellow stay in type's precision and use the overflow flags.  If
step's range is positive it check that:

  step_max * nit <= type_max-base_max

in unsigned arithmetic (all values are positive). The right hand side can not
overflow (INT_MAX-INT_MIN is representable as unsigned int) and for left hand
side I use the unsigned mult with overflow check.

If step can be also negative I also check:

  step_min * (-nit) <= base_min-type_min

Clearly this path triggers only for signed types with defined overflow (as
otherwise nowrap_type returns true and iv_can_overflow_p is neve rused). It is
not very important right now. It will make more sense once ivopts is updated to
use no-wrap flag rather htan no-overflow and we will be able to have unsgined
IVs going down.

I also added sanity check that base's range is representable in the type's range.
This is only because some uses of IVs weems bit sloppy WRT nops and it may
cause the right hand side of the comparsion to underflow.

For loop infrastructure it would be very useful to have a helper which can
determine value range of an expression based on value range of individual
SSA_NAMEs in it.  Would that be easy to get out of tree-vrp?
  
Bootstrapped/regtested x86_64-linux, OK?

	* gcc.dg/tree-ssa/scev-14.c: new testcase.

	* tree-scalar-evolution.c (iv_can_overflow_p): New function.
	(simple_iv): Use it; use nowrap_type_p to check if type can overflow.
	* tree-ssa-loop-niter.c (nowrap_type_p): Use ANY_INTEGRAL_TYPE_P.
Index: testsuite/gcc.dg/tree-ssa/scev-14.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/scev-14.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/scev-14.c	(working copy)
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
+int a[100];
+void t(unsigned int n)
+{
+  unsigned int i;
+  for (i=0; i<n; i++)
+     a[i]++;
+}
+/* { dg-final { scan-tree-dump "Overflowness wrto loop niter:	No-overflow"  "ivopts" } } */
+/* { dg-final { scan-tree-dump-not "Overflowness wrto loop niter:	Overflow" "ivopts" } } */
Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c	(revision 237908)
+++ tree-scalar-evolution.c	(working copy)
@@ -3309,6 +3309,89 @@ scev_reset (void)
     }
 }
 
+/* Return true if the IV calculation in TYPE can overflow based on the knowledge
+   of the upper bound on the number of iterations of LOOP, the BASE and STEP
+   of IV.
+
+   We do not use information whether TYPE can overflow so it is safe to
+   use this test even for derived IVs not computed every iteration or
+   hypotetical IVs to be inserted into code.  */
+
+static bool
+iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
+{
+  widest_int nit;
+  wide_int base_min, base_max, step_min, step_max, type_min, type_max;
+  signop sgn = TYPE_SIGN (type);
+
+  if (integer_zerop (step))
+    return false;
+
+  if (TREE_CODE (base) == INTEGER_CST)
+    base_min = base_max = base;
+  else if (TREE_CODE (base) == SSA_NAME
+	   && INTEGRAL_TYPE_P (TREE_TYPE (base))
+	   && get_range_info (base, &base_min, &base_max) == VR_RANGE)
+    ;
+  else
+    return true;
+
+  if (TREE_CODE (step) == INTEGER_CST)
+    step_min = step_max = step;
+  else if (TREE_CODE (step) == SSA_NAME
+	   && INTEGRAL_TYPE_P (TREE_TYPE (step))
+	   && get_range_info (step, &step_min, &step_max) == VR_RANGE)
+    ;
+  else
+    return true;
+
+  if (!get_max_loop_iterations (loop, &nit))
+    return true;
+
+  type_min = wi::min_value (type);
+  type_max = wi::max_value (type);
+
+  /* Just sanity check that we don't see values out of the range of the type.
+     In this case the arithmetics bellow would overflow.  */
+  gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
+		       && wi::le_p (base_max, type_max, sgn));
+
+  /* Account the possible increment in the last ieration.  */
+  nit = nit + 1;
+
+  /* NIT is typeless and can exceed the precision of the type.  In this case
+     overflow is always possible, because we know STEP is non-zero.  */
+  if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
+    return true;
+  wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
+
+
+  /* If step can be positive, check that nit*step <= type_max-base.
+     This can be done by unsigned arithmetic and we only need to watch overflow
+     in the multiplication. The right hand side can always be represented in
+     the type.  */
+  if (sgn == UNSIGNED || !wi::neg_p (step_max))
+    {
+      bool overflow = false;
+      if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
+		     type_max - base_max)
+	  || overflow)
+	return true;
+    }
+  /* If step can be negative, check that nit*(-step) <= base_min-type_min.  */
+  if (sgn == SIGNED && wi::neg_p (step_min))
+    {
+      bool overflow = false, overflow2 = false;
+      if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
+		     nit2, UNSIGNED, &overflow),
+		     base_min - type_min)
+	  || overflow || overflow2)
+        return true;
+    }
+
+  return false;
+}
+
 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
    respect to WRTO_LOOP and returns its base and step in IV if possible
    (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
@@ -3375,8 +3458,12 @@ simple_iv (struct loop *wrto_loop, struc
   if (tree_contains_chrecs (iv->base, NULL))
     return false;
 
-  iv->no_overflow = (!folded_casts && ANY_INTEGRAL_TYPE_P (type)
-		     && TYPE_OVERFLOW_UNDEFINED (type));
+  iv->no_overflow = !folded_casts && nowrap_type_p (type);
+
+  if (!iv->no_overflow
+      && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
+    iv->no_overflow = true;
+
 
   /* Try to simplify iv base:
 
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c	(revision 237908)
+++ tree-ssa-loop-niter.c	(working copy)
@@ -4105,7 +4105,7 @@ n_of_executions_at_most (gimple *stmt,
 bool
 nowrap_type_p (tree type)
 {
-  if (INTEGRAL_TYPE_P (type)
+  if (ANY_INTEGRAL_TYPE_P (type)
       && TYPE_OVERFLOW_UNDEFINED (type))
     return true;