From a81e2c6240655f60a49c16e0d8bbfd2ba40bba51 Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Thu, 15 Nov 2018 03:44:49 +0000 Subject: [PATCH] re PR tree-optimization/84648 (Missed optimization : loop not removed.) PR tree-optimization/84648 * tree-ssa-loop-niter.c (adjust_cond_for_loop_until_wrap): New. (number_of_iterations_cond): Adjust exit cond for loop-until-wrap case by calling adjust_cond_for_loop_until_wrap. gcc/testsuite * gcc.dg/tree-ssa/pr84648.c: New test. * gcc.dg/pr68317.c: Add warning check on overflow. From-SVN: r266171 --- gcc/ChangeLog | 7 +++ gcc/testsuite/ChangeLog | 6 ++ gcc/testsuite/gcc.dg/pr68317.c | 2 +- gcc/testsuite/gcc.dg/tree-ssa/pr84648.c | 10 ++++ gcc/tree-ssa-loop-niter.c | 75 +++++++++++++++++++++---- 5 files changed, 89 insertions(+), 11 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr84648.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 143a4398336..aa1d0de9f95 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2018-11-15 Bin Cheng + + PR tree-optimization/84648 + * tree-ssa-loop-niter.c (adjust_cond_for_loop_until_wrap): New. + (number_of_iterations_cond): Adjust exit cond for loop-until-wrap case + by calling adjust_cond_for_loop_until_wrap. + 2018-11-15 Sandra Loosemore PR other/56334 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 9d52f14fc00..a5dfd90de49 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2018-11-15 Bin Cheng + + PR tree-optimization/84648 + * gcc.dg/tree-ssa/pr84648.c: New test. + * gcc.dg/pr68317.c: Add warning check on overflow. + 2018-11-14 Nathan Sidwell PR debug/88006 diff --git a/gcc/testsuite/gcc.dg/pr68317.c b/gcc/testsuite/gcc.dg/pr68317.c index 7b565639588..9ba6fb075e6 100644 --- a/gcc/testsuite/gcc.dg/pr68317.c +++ b/gcc/testsuite/gcc.dg/pr68317.c @@ -11,5 +11,5 @@ foo () for (index; index <= 10; index--) /* Result of the following multiply will overflow when converted to signed int. */ - bar ((0xcafe + index) * 0xdead); + bar ((0xcafe + index) * 0xdead); /* { dg-warning "iteration \[0-9\]+ invokes undefined behavior" } */ } diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr84648.c b/gcc/testsuite/gcc.dg/tree-ssa/pr84648.c new file mode 100644 index 00000000000..6ff5a07cd20 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr84648.c @@ -0,0 +1,10 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-cddce1-details" } */ + +int main() { + for (unsigned i = 0; i < (1u << 31); ++i) { + } + return 0; +} + +/* { dg-final { scan-tree-dump-times "Found loop 1 to be finite: upper bound found" 1 "cddce1" } } */ diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 9bcd66449fa..67a3d689463 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -1641,6 +1641,62 @@ dump_affine_iv (FILE *file, affine_iv *iv) } } +/* Given exit condition IV0 CODE IV1 in TYPE, this function adjusts + the condition for loop-until-wrap cases. For example: + (unsigned){8, -1}_loop < 10 => {0, 1} != 9 + 10 < (unsigned){0, max - 7}_loop => {0, 1} != 8 + Return true if condition is successfully adjusted. */ + +static bool +adjust_cond_for_loop_until_wrap (tree type, affine_iv *iv0, tree_code *code, + affine_iv *iv1) +{ + /* Only support simple cases for the moment. */ + if (TREE_CODE (iv0->base) != INTEGER_CST + || TREE_CODE (iv1->base) != INTEGER_CST) + return false; + + tree niter_type = unsigned_type_for (type), high, low; + /* Case: i-- < 10. */ + if (integer_zerop (iv1->step)) + { + /* TODO: Should handle case in which abs(step) != 1. */ + if (!integer_minus_onep (iv0->step)) + return false; + /* Give up on infinite loop. */ + if (*code == LE_EXPR + && tree_int_cst_equal (iv1->base, TYPE_MAX_VALUE (type))) + return false; + high = fold_build2 (PLUS_EXPR, niter_type, + fold_convert (niter_type, iv0->base), + build_int_cst (niter_type, 1)); + low = fold_convert (niter_type, TYPE_MIN_VALUE (type)); + } + else if (integer_zerop (iv0->step)) + { + /* TODO: Should handle case in which abs(step) != 1. */ + if (!integer_onep (iv1->step)) + return false; + /* Give up on infinite loop. */ + if (*code == LE_EXPR + && tree_int_cst_equal (iv0->base, TYPE_MIN_VALUE (type))) + return false; + high = fold_convert (niter_type, TYPE_MAX_VALUE (type)); + low = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, iv1->base), + build_int_cst (niter_type, 1)); + } + else + gcc_unreachable (); + + iv0->base = low; + iv0->step = fold_convert (niter_type, integer_one_node); + iv1->base = high; + iv1->step = build_int_cst (niter_type, 0); + *code = NE_EXPR; + return true; +} + /* Determine the number of iterations according to condition (for staying inside loop) which compares two induction variables using comparison operator CODE. The induction variable on left side of the comparison @@ -1764,16 +1820,6 @@ number_of_iterations_cond (struct loop *loop, if (integer_zerop (iv0->step) && integer_zerop (iv1->step)) return false; - /* Ignore loops of while (i-- < 10) type. */ - if (code != NE_EXPR) - { - if (iv0->step && tree_int_cst_sign_bit (iv0->step)) - return false; - - if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step)) - return false; - } - /* If the loop exits immediately, there is nothing to do. */ tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base); if (tem && integer_zerop (tem)) @@ -1783,6 +1829,15 @@ number_of_iterations_cond (struct loop *loop, return true; } + /* Handle special case loops: while (i-- < 10) and while (10 < i++) by + adjusting iv0, iv1 and code. */ + if (code != NE_EXPR + && (tree_int_cst_sign_bit (iv0->step) + || (!integer_zerop (iv1->step) + && !tree_int_cst_sign_bit (iv1->step))) + && !adjust_cond_for_loop_until_wrap (type, iv0, &code, iv1)) + return false; + /* OK, now we know we have a senseful loop. Handle several cases, depending on what comparison operator is used. */ bound_difference (loop, iv1->base, iv0->base, &bnds); -- 2.30.2