Determine more IVs to be non-overflowing

[Jan Hubicka]

Hi,
i sent the email before, but it seems it never left my machine. Sorry for
possible duplicates.  This is updated version which does not overflow (by
capping nit), but still using widest_int for the calculatoins. It seems more
readable to do so than using wi:add/wi:mult/wi:lt and overflow checks, but
i can definitly update the patch to do it, too.

Bootstrapped/regtested x86_64-linux, OK?

Honza

	* tree-scalar-evolution.h (iv_can_overflow_p): Declare.
	* tree-scalar-evolution.c (iv_can_overflow_p): New funcition.
	(simple_iv): Use it.
	* tree-ssa-loop-niter.c (nowrap_type_p): Use ANY_INTEGRAL_TYPE_P

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

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 237856)
+++ tree-scalar-evolution.c	(working copy)
@@ -280,6 +280,7 @@ along with GCC; see the file COPYING3.
 #include "params.h"
 #include "tree-ssa-propagate.h"
 #include "gimple-fold.h"
+#include "print-tree.h"
 
 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
 static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
@@ -3309,6 +3310,60 @@ 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.  */
+
+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);
+  signop base_sgn = TYPE_SIGN (TREE_TYPE (base));
+  signop step_sgn = TYPE_SIGN (TREE_TYPE (step));
+
+  if (step == 0)
+    return false;
+
+  if (TREE_CODE (base) == INTEGER_CST)
+    base_min = base_max = base;
+  else if (TREE_CODE (base) == SSA_NAME && !POINTER_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 && !POINTER_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);
+  /* Watch overflow.  */
+  if ((widest_int)1 << TYPE_PRECISION (type) < nit)
+    return true;
+  if ((widest_int::from (base_max, base_sgn)
+       + widest_int::from (step_max, step_sgn) * (nit + 1))
+       > widest_int::from (type_max, sgn)
+      || (widest_int::from (type_min, sgn)
+	  > (widest_int::from (base_min, base_sgn)
+	     + widest_int::from (step_min, step_sgn) * (nit + 1))))
+    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 +3430,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-scalar-evolution.h
===================================================================
--- tree-scalar-evolution.h	(revision 237856)
+++ tree-scalar-evolution.h	(working copy)
@@ -38,6 +38,7 @@ extern unsigned int scev_const_prop (voi
 extern bool expression_expensive_p (tree);
 extern bool simple_iv (struct loop *, struct loop *, tree, struct affine_iv *,
 		       bool);
+extern bool iv_can_overflow_p (struct loop *, tree, tree, tree);
 extern tree compute_overall_effect_of_inner_loop (struct loop *, tree);
 
 /* Returns the basic block preceding LOOP, or the CFG entry block when
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c	(revision 237856)
+++ 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;