[PATCH] tree-optimization/112344 - wrong final value replacement

[PATCH] tree-optimization/112344 - wrong final value replacement

[Richard Biener]

When performing final value replacement chrec_apply that's used to
compute the overall effect of niters to a CHREC doesn't consider that
the overall increment of { -2147483648, +, 2 } doesn't fit in
a signed integer when the loop iterates until the value of the IV
of 20.  The following fixes this mistake, carrying out the multiply
and add in an unsigned type instead, avoiding undefined overflow
and thus later miscompilation by path range analysis.

Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.

	PR tree-optimization/112344
	* tree-chrec.cc (chrec_apply): Perform the overall increment
	calculation and increment in an unsigned type.

	* gcc.dg/torture/pr112344.c: New testcase.
---
 gcc/testsuite/gcc.dg/torture/pr112344.c | 20 ++++++++++++++++
 gcc/tree-chrec.cc                       | 32 ++++++++++++++++---------
 2 files changed, 41 insertions(+), 11 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/torture/pr112344.c

diff --git a/gcc/testsuite/gcc.dg/torture/pr112344.c b/gcc/testsuite/gcc.dg/torture/pr112344.c
new file mode 100644
index 00000000000..c52d2c8304b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr112344.c
@@ -0,0 +1,20 @@
+/* { dg-do run } */
+/* { dg-require-effective-target int32plus } */
+
+int
+main ()
+{
+  long long b = 2036854775807LL;
+  signed char c = 3;
+  short d = 0;
+  int e = -2147483647 - 1, f;
+  for (f = 0; f < 7; f++)
+    while (e < 20)
+      {
+	e += 2;
+	d = c -= b;
+      }
+  if (d != 13)
+    __builtin_abort ();
+  return 0;
+}
diff --git a/gcc/tree-chrec.cc b/gcc/tree-chrec.cc
index 2f67581591a..f4ba130ba20 100644
--- a/gcc/tree-chrec.cc
+++ b/gcc/tree-chrec.cc
@@ -613,32 +613,42 @@ chrec_apply (unsigned var,
       if (evolution_function_is_affine_p (chrec))
 	{
 	  tree chrecr = CHREC_RIGHT (chrec);
+	  tree chrecl = CHREC_LEFT (chrec);
 	  if (CHREC_VARIABLE (chrec) != var)
-	    res = build_polynomial_chrec
-	      (CHREC_VARIABLE (chrec),
-	       chrec_apply (var, CHREC_LEFT (chrec), x),
-	       chrec_apply (var, chrecr, x));
+	    res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
+					  chrec_apply (var, chrecl, x),
+					  chrec_apply (var, chrecr, x));
 
-	  /* "{a, +, b} (x)"  ->  "a + b*x".  */
-	  else if (operand_equal_p (CHREC_LEFT (chrec), chrecr)
+	  /* "{a, +, a}" (x-1) -> "a*x".  */
+	  else if (operand_equal_p (chrecl, chrecr)
 		   && TREE_CODE (x) == PLUS_EXPR
 		   && integer_all_onesp (TREE_OPERAND (x, 1))
 		   && !POINTER_TYPE_P (type)
 		   && TYPE_PRECISION (TREE_TYPE (x))
 		      >= TYPE_PRECISION (type))
 	    {
-	      /* We know the number of iterations can't be negative.
-		 So {a, +, a} (x-1) -> "a*x".  */
+	      /* We know the number of iterations can't be negative.  */
 	      res = build_int_cst (TREE_TYPE (x), 1);
 	      res = chrec_fold_plus (TREE_TYPE (x), x, res);
 	      res = chrec_convert_rhs (type, res, NULL);
 	      res = chrec_fold_multiply (type, chrecr, res);
 	    }
+	  /* "{a, +, b} (x)"  ->  "a + b*x".  */
 	  else
 	    {
-	      res = chrec_convert_rhs (TREE_TYPE (chrecr), x, NULL);
-	      res = chrec_fold_multiply (TREE_TYPE (chrecr), chrecr, res);
-	      res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
+	      /* The overall increment might not fit in a signed type so
+		 use an unsigned computation to get at the final value
+		 and avoid undefined signed overflow.  */
+	      tree utype = TREE_TYPE (chrecr);
+	      if (INTEGRAL_TYPE_P (utype) && !TYPE_OVERFLOW_WRAPS (utype))
+		utype = unsigned_type_for (TREE_TYPE (chrecr));
+	      res = chrec_convert_rhs (utype, x, NULL);
+	      res = chrec_fold_multiply (utype,
+					 chrec_convert (utype, chrecr, NULL),
+					 res);
+	      res = chrec_fold_plus (utype,
+				     chrec_convert (utype, chrecl, NULL), res);
+	      res = chrec_convert (type, res, NULL);
 	    }
 	}
       else if (TREE_CODE (x) == INTEGER_CST
-- 
2.35.3