From 1e3d54b4299c69b4e40205dd7d6cabc888b307c5 Mon Sep 17 00:00:00 2001
From: Jan Hubicka <jh@suse.cz>
Date: Tue, 5 Jul 2016 18:17:12 +0200
Subject: [PATCH] tree-scalar-evolution.c (iv_can_overflow_p): New function.

	* tree-scalar-evolution.c (iv_can_overflow_p): New function.
	(simple_iv): Use it.

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

From-SVN: r238012
---
 gcc/ChangeLog                           |  5 ++
 gcc/testsuite/ChangeLog                 |  4 ++
 gcc/testsuite/gcc.dg/tree-ssa/scev-14.c | 11 +++
 gcc/tree-scalar-evolution.c             | 89 +++++++++++++++++++++++++
 4 files changed, 109 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scev-14.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index bc4b4db8944..c7468666273 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,8 @@
+2016-07-05  Jan Hubicka  <jh@suse.cz>
+
+	* tree-scalar-evolution.c (iv_can_overflow_p): New function.
+	(simple_iv): Use it.
+
 2016-07-05  Jan Hubicka  <jh@suse.cz>
 
 	* tree-ssa-loop-niter.c (nowrap_type_p): Use ANY_INTEGRAL_TYPE_P.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index f86ee90ec5e..d57f9c3eede 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2016-07-05  Jan Hubicka  <jh@suse.cz>
+
+	* gcc.dg/tree-ssa/scev-14.c: new testcase.
+
 2016-07-05  David Malcolm  <dmalcolm@redhat.com>
 
 	PR c++/62314
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-14.c b/gcc/testsuite/gcc.dg/tree-ssa/scev-14.c
new file mode 100644
index 00000000000..43af7d3dab4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-14.c
@@ -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" } } */
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index 7c4c4336728..e51f0aaedc1 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -3309,6 +3309,91 @@ 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.  */
+  bool overflow = false;
+  nit = wi::add (nit, 1, SIGNED, &overflow);
+  if (overflow)
+    return true;
+
+  /* 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
@@ -3377,6 +3462,10 @@ simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
 
   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:
 
        (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
-- 
2.30.2