re PR tree-optimization/79721 (Scalar evolution introduces signed overflow)

2017-03-01  Richard Biener  <rguenther@suse.de>

	PR middle-end/79721
	* tree-chrec.c (chrec_evaluate): Perform computation of Newtons
	interpolating formula in wrapping arithmetic.
	(chrec_apply): Convert chrec_evaluate return value to wanted type.

	* gcc.dg/torture/pr79721.c: New testcase.

From-SVN: r245803

4 files changed, 50 insertions, 8 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 12ee03a..253eab3 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2017-03-01  Richard Biener  <rguenther@suse.de>
+
+	PR middle-end/79721
+	* tree-chrec.c (chrec_evaluate): Perform computation of Newtons
+	interpolating formula in wrapping arithmetic.
+	(chrec_apply): Convert chrec_evaluate return value to wanted type.
+
 2017-03-01  Jakub Jelinek  <jakub@redhat.com>
 
 	PR tree-optimization/79734
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 4cce675..7aac384 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2017-03-01  Richard Biener  <rguenther@suse.de>
+
+	PR middle-end/79721
+	* gcc.dg/torture/pr79721.c: New testcase.
+
 2017-03-01  Jakub Jelinek  <jakub@redhat.com>
 
 	PR c++/79746
diff --git a/gcc/testsuite/gcc.dg/torture/pr79721.c b/gcc/testsuite/gcc.dg/torture/pr79721.c
new file mode 100644
index 0000000..97d20ca
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr79721.c
@@ -0,0 +1,21 @@
+/* { dg-do run }  */
+/* { dg-require-effective-target int32plus } */
+/* We use -ftrapv so that when SCEV final value replacement introduces
+   undefined overflow we trap.  UBSAN inhibits final value replacement.  */
+/* { dg-additional-options "-ftrapv" } */
+
+int __attribute__((noclone,noinline))
+foo(int a, int b)
+{
+  int sum = 0;
+  for (int i = 0; i < 60000; i++)
+    sum += a + i * b;
+  return sum;
+}
+
+int main(int argc, char **argv)
+{
+  if (foo (-30000, 2) != 1799940000)
+    __builtin_abort ();
+  return 0;
+}
diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c
index e924962..80a1bbd2 100644
--- a/gcc/tree-chrec.c
+++ b/gcc/tree-chrec.c
@@ -536,7 +536,8 @@ tree_fold_binomial (tree type, tree n, unsigned int k)
 }
 
 /* Helper function.  Use the Newton's interpolating formula for
-   evaluating the value of the evolution function.  */
+   evaluating the value of the evolution function.
+   The result may be in an unsigned type of CHREC.  */
 
 static tree
 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
@@ -549,25 +550,33 @@ chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
 	 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
     chrec = CHREC_LEFT (chrec);
 
+  /* The formula associates the expression and thus we have to make
+     sure to not introduce undefined overflow.  */
+  tree ctype = type;
+  if (INTEGRAL_TYPE_P (type)
+      && ! TYPE_OVERFLOW_WRAPS (type))
+    ctype = unsigned_type_for (type);
+
   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
       && CHREC_VARIABLE (chrec) == var)
     {
       arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
       if (arg1 == chrec_dont_know)
 	return chrec_dont_know;
-      binomial_n_k = tree_fold_binomial (type, n, k);
+      binomial_n_k = tree_fold_binomial (ctype, n, k);
       if (!binomial_n_k)
 	return chrec_dont_know;
-      arg0 = fold_build2 (MULT_EXPR, type,
-			  CHREC_LEFT (chrec), binomial_n_k);
-      return chrec_fold_plus (type, arg0, arg1);
+      tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
+      arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
+      return chrec_fold_plus (ctype, arg0, arg1);
     }
 
-  binomial_n_k = tree_fold_binomial (type, n, k);
+  binomial_n_k = tree_fold_binomial (ctype, n, k);
   if (!binomial_n_k)
     return chrec_dont_know;
 
-  return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
+  return fold_build2 (MULT_EXPR, ctype,
+		      chrec_convert (ctype, chrec, NULL), binomial_n_k);
 }
 
 /* Evaluates "CHREC (X)" when the varying variable is VAR.
@@ -623,7 +632,7 @@ chrec_apply (unsigned var,
       else if (TREE_CODE (x) == INTEGER_CST
 	       && tree_int_cst_sgn (x) == 1)
 	/* testsuite/.../ssa-chrec-38.c.  */
-	res = chrec_evaluate (var, chrec, x, 0);
+	res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
       else
 	res = chrec_dont_know;
       break;