From 0100ae430272feaa208b02c32e52d530cd9c8644 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Wed, 1 Mar 2017 08:54:29 +0000 Subject: [PATCH] re PR tree-optimization/79721 (Scalar evolution introduces signed overflow) 2017-03-01 Richard Biener 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 --- gcc/ChangeLog | 7 +++++++ gcc/testsuite/ChangeLog | 5 +++++ gcc/testsuite/gcc.dg/torture/pr79721.c | 21 +++++++++++++++++++++ gcc/tree-chrec.c | 25 +++++++++++++++++-------- 4 files changed, 50 insertions(+), 8 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/pr79721.c 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 + + 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 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 + + PR middle-end/79721 + * gcc.dg/torture/pr79721.c: New testcase. + 2017-03-01 Jakub Jelinek 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; -- 2.7.4