[PATCH] Fix PR79721

[Richard Biener <rguenther at suse dot de>]

The following fixes final value replacement introducing undefined 
overflow.  The issue is in how we compute Newtons interpolating
formula which really needs to be done in a type that has well-defined
overflow behavior.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Eventually the hack in value-replacement to rewrite stuff to unsigned
arithmetic can go away after this but this is for GCC 8.

Richard.

2017-02-28  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.

Index: gcc/tree-chrec.c
===================================================================
*** gcc/tree-chrec.c	(revision 245772)
--- gcc/tree-chrec.c	(working copy)
*************** tree_fold_binomial (tree type, tree n, u
*** 536,542 ****
  }
  
  /* Helper function.  Use the Newton's interpolating formula for
!    evaluating the value of the evolution function.  */
  
  static tree
  chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
--- 536,543 ----
  }
  
  /* Helper function.  Use the Newton's interpolating formula for
!    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)
*************** chrec_evaluate (unsigned var, tree chrec
*** 549,573 ****
  	 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
      chrec = CHREC_LEFT (chrec);
  
    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);
        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);
      }
  
!   binomial_n_k = tree_fold_binomial (type, n, k);
    if (!binomial_n_k)
      return chrec_dont_know;
  
!   return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
  }
  
  /* Evaluates "CHREC (X)" when the varying variable is VAR.
--- 550,582 ----
  	 && 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 (ctype, n, k);
        if (!binomial_n_k)
  	return chrec_dont_know;
!       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 (ctype, n, k);
    if (!binomial_n_k)
      return chrec_dont_know;
  
!   return fold_build2 (MULT_EXPR, ctype,
! 		      chrec_convert (ctype, chrec, NULL), binomial_n_k);
  }
  
  /* Evaluates "CHREC (X)" when the varying variable is VAR.
*************** chrec_apply (unsigned var,
*** 623,629 ****
        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);
        else
  	res = chrec_dont_know;
        break;
--- 632,638 ----
        else if (TREE_CODE (x) == INTEGER_CST
  	       && tree_int_cst_sgn (x) == 1)
  	/* testsuite/.../ssa-chrec-38.c.  */
! 	res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
        else
  	res = chrec_dont_know;
        break;
Index: gcc/testsuite/gcc.dg/torture/pr79721.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr79721.c	(nonexistent)
--- gcc/testsuite/gcc.dg/torture/pr79721.c	(working copy)
***************
*** 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;
+ }