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 <rguent...@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; + }