From 43aabfcfd4139e4c9e7b868199e09b97e66010bc Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Fri, 15 Jul 2016 09:04:57 +0000 Subject: [PATCH] tree-scalar-evolution.c (simple_iv_with_niters): New funcion. * tree-scalar-evolution.c (simple_iv_with_niters): New funcion. (derive_simple_iv_with_niters): New function. (simple_iv): Rewrite using simple_iv_with_niters. * tree-scalar-evolution.h (simple_iv_with_niters): New decl. * tree-ssa-loop-niter.c (number_of_iterations_exit_assumptions): New function. (number_of_iterations_exit): Rewrite using above function. * tree-ssa-loop-niter.h (number_of_iterations_exit_assumptions): New Decl. gcc/testsuite * gcc.dg/tree-ssa/loop-41.c: New test. From-SVN: r238367 --- gcc/ChangeLog | 12 ++++ gcc/testsuite/ChangeLog | 4 ++ gcc/testsuite/gcc.dg/tree-ssa/loop-41.c | 14 ++++ gcc/tree-scalar-evolution.c | 94 +++++++++++++++++++++++-- gcc/tree-scalar-evolution.h | 2 + gcc/tree-ssa-loop-niter.c | 94 ++++++++++++------------- gcc/tree-ssa-loop-niter.h | 3 + 7 files changed, 170 insertions(+), 53 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-41.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 624d4d63b8f..e9c1144ccf4 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,15 @@ +2016-07-15 Bin Cheng + + * tree-scalar-evolution.c (simple_iv_with_niters): New funcion. + (derive_simple_iv_with_niters): New function. + (simple_iv): Rewrite using simple_iv_with_niters. + * tree-scalar-evolution.h (simple_iv_with_niters): New decl. + * tree-ssa-loop-niter.c (number_of_iterations_exit_assumptions): New + function. + (number_of_iterations_exit): Rewrite using above function. + * tree-ssa-loop-niter.h (number_of_iterations_exit_assumptions): New + Decl. + 2016-07-15 Richard Biener * config/i386/i386.c (ix86_builtin_vectorization_cost): Adjust diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 885dbbf6a5e..f31c63eac79 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2016-07-15 Bin Cheng + + * gcc.dg/tree-ssa/loop-41.c: New test. + 2016-07-15 Bin Cheng PR tree-optimization/71347 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-41.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-41.c new file mode 100644 index 00000000000..52ba96849ac --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-41.c @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O1 -ftree-vrp -fdump-tree-vrp-alias" } */ + +signed char arr[240]; +void foo (void) +{ + + unsigned short i, length = 200; + + for (i = 1; (int)i < (length - 1); i++) + arr[i] = -1; +} + +/* { dg-final { scan-tree-dump-not "RANGE \\\[0, 65535\\\]" "vrp1" } } */ diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index ae5e9079328..d8ed84af495 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -3393,6 +3393,55 @@ iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step) return false; } +/* Given EV with form of "(type) {inner_base, inner_step}_loop", this + function tries to derive condition under which it can be simplified + into "{(type)inner_base, (type)inner_step}_loop". The condition is + the maximum number that inner iv can iterate. */ + +static tree +derive_simple_iv_with_niters (tree ev, tree *niters) +{ + if (!CONVERT_EXPR_P (ev)) + return ev; + + tree inner_ev = TREE_OPERAND (ev, 0); + if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC) + return ev; + + tree init = CHREC_LEFT (inner_ev); + tree step = CHREC_RIGHT (inner_ev); + if (TREE_CODE (init) != INTEGER_CST + || TREE_CODE (step) != INTEGER_CST || integer_zerop (step)) + return ev; + + tree type = TREE_TYPE (ev); + tree inner_type = TREE_TYPE (inner_ev); + if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type)) + return ev; + + /* Type conversion in "(type) {inner_base, inner_step}_loop" can be + folded only if inner iv won't overflow. We compute the maximum + number the inner iv can iterate before overflowing and return the + simplified affine iv. */ + tree delta; + init = fold_convert (type, init); + step = fold_convert (type, step); + ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step); + if (tree_int_cst_sign_bit (step)) + { + tree bound = lower_bound_in_type (inner_type, inner_type); + delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound)); + step = fold_build1 (NEGATE_EXPR, type, step); + } + else + { + tree bound = upper_bound_in_type (inner_type, inner_type); + delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init); + } + *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step); + return ev; +} + /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with respect to WRTO_LOOP and returns its base and step in IV if possible (see analyze_scalar_evolution_in_loop for more details on USE_LOOP @@ -3410,13 +3459,29 @@ iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step) not wrap by some other argument. Otherwise, this might introduce undefined behavior, and - for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step)) + i = iv->base; + for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step)) + + must be used instead. + + When IV_NITERS is not NULL, this function also checks case in which OP + is a conversion of an inner simple iv of below form: + + (outer_type){inner_base, inner_step}_loop. - must be used instead. */ + If type of inner iv has smaller precision than outer_type, it can't be + folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because + the inner iv could overflow/wrap. In this case, we derive a condition + under which the inner iv won't overflow/wrap and do the simplification. + The derived condition normally is the maximum number the inner iv can + iterate, and will be stored in IV_NITERS. This is useful in loop niter + analysis, to derive break conditions when a loop must terminate, when is + infinite. */ bool -simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, - affine_iv *iv, bool allow_nonconstant_step) +simple_iv_with_niters (struct loop *wrto_loop, struct loop *use_loop, + tree op, affine_iv *iv, tree *iv_niters, + bool allow_nonconstant_step) { enum tree_code code; tree type, ev, base, e, stop; @@ -3446,8 +3511,14 @@ simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, return true; } - if (TREE_CODE (ev) != POLYNOMIAL_CHREC - || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num) + /* If we can derive valid scalar evolution with assumptions. */ + if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC) + ev = derive_simple_iv_with_niters (ev, iv_niters); + + if (TREE_CODE (ev) != POLYNOMIAL_CHREC) + return false; + + if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num) return false; iv->step = CHREC_RIGHT (ev); @@ -3544,6 +3615,17 @@ simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, return true; } +/* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple + affine iv unconditionally. */ + +bool +simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, + affine_iv *iv, bool allow_nonconstant_step) +{ + return simple_iv_with_niters (wrto_loop, use_loop, op, iv, + NULL, allow_nonconstant_step); +} + /* Finalize the scalar evolution analysis. */ void diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h index 382d71751cc..a77e4525f6d 100644 --- a/gcc/tree-scalar-evolution.h +++ b/gcc/tree-scalar-evolution.h @@ -36,6 +36,8 @@ extern void gather_stats_on_scev_database (void); extern void final_value_replacement_loop (struct loop *); extern unsigned int scev_const_prop (void); extern bool expression_expensive_p (tree); +extern bool simple_iv_with_niters (struct loop *, struct loop *, tree, + struct affine_iv *, tree *, bool); extern bool simple_iv (struct loop *, struct loop *, tree, struct affine_iv *, bool); extern bool iv_can_overflow_p (struct loop *, tree, tree, tree); diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 182753cef3d..d96c03b3993 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -2176,20 +2176,17 @@ loop_only_exit_p (const struct loop *loop, const_edge exit) } /* Stores description of number of iterations of LOOP derived from - EXIT (an exit edge of the LOOP) in NITER. Returns true if some - useful information could be derived (and fields of NITER has - meaning described in comments at struct tree_niter_desc - declaration), false otherwise. If WARN is true and - -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use - potentially unsafe assumptions. + EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful + information could be derived (and fields of NITER have meaning described + in comments at struct tree_niter_desc declaration), false otherwise. When EVERY_ITERATION is true, only tests that are known to be executed - every iteration are considered (i.e. only test that alone bounds the loop). + every iteration are considered (i.e. only test that alone bounds the loop). */ bool -number_of_iterations_exit (struct loop *loop, edge exit, - struct tree_niter_desc *niter, - bool warn, bool every_iteration) +number_of_iterations_exit_assumptions (struct loop *loop, edge exit, + struct tree_niter_desc *niter, + bool every_iteration) { gimple *last; gcond *stmt; @@ -2241,9 +2238,16 @@ number_of_iterations_exit (struct loop *loop, edge exit, && !POINTER_TYPE_P (type)) return false; - if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false)) + tree iv0_niters = NULL_TREE; + if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt), + op0, &iv0, &iv0_niters, false)) return false; - if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false)) + tree iv1_niters = NULL_TREE; + if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt), + op1, &iv1, &iv1_niters, false)) + return false; + /* Give up on complicated case. */ + if (iv0_niters && iv1_niters) return false; /* We don't want to see undefined signed overflow warnings while @@ -2259,6 +2263,24 @@ number_of_iterations_exit (struct loop *loop, edge exit, return false; } + /* Incorporate additional assumption implied by control iv. */ + tree iv_niters = iv0_niters ? iv0_niters : iv1_niters; + if (iv_niters) + { + tree assumption = fold_build2 (LE_EXPR, boolean_type_node, niter->niter, + fold_convert (TREE_TYPE (niter->niter), + iv_niters)); + + if (!integer_nonzerop (assumption)) + niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + niter->assumptions, assumption); + + /* Refine upper bound if possible. */ + if (TREE_CODE (iv_niters) == INTEGER_CST + && niter->max > wi::to_widest (iv_niters)) + niter->max = wi::to_widest (iv_niters); + } + if (optimize >= 3) { niter->assumptions = simplify_using_outer_evolutions (loop, @@ -2281,44 +2303,22 @@ number_of_iterations_exit (struct loop *loop, edge exit, if (TREE_CODE (niter->niter) == INTEGER_CST) niter->max = wi::to_widest (niter->niter); - if (integer_onep (niter->assumptions)) - return true; - - /* With -funsafe-loop-optimizations we assume that nothing bad can happen. - But if we can prove that there is overflow or some other source of weird - behavior, ignore the loop even with -funsafe-loop-optimizations. */ - if (integer_zerop (niter->assumptions) || !single_exit (loop)) - return false; - - if (flag_unsafe_loop_optimizations) - niter->assumptions = boolean_true_node; + return (!integer_zerop (niter->assumptions)); +} - if (warn) - { - const char *wording; - location_t loc = gimple_location (stmt); - - /* We can provide a more specific warning if one of the operator is - constant and the other advances by +1 or -1. */ - if (!integer_zerop (iv1.step) - ? (integer_zerop (iv0.step) - && (integer_onep (iv1.step) || integer_all_onesp (iv1.step))) - : (integer_onep (iv0.step) || integer_all_onesp (iv0.step))) - wording = - flag_unsafe_loop_optimizations - ? N_("assuming that the loop is not infinite") - : N_("cannot optimize possibly infinite loops"); - else - wording = - flag_unsafe_loop_optimizations - ? N_("assuming that the loop counter does not overflow") - : N_("cannot optimize loop, the loop counter may overflow"); +/* Like number_of_iterations_exit, but return TRUE only if the niter + information holds unconditionally. */ - warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location, - OPT_Wunsafe_loop_optimizations, "%s", gettext (wording)); - } +bool +number_of_iterations_exit (struct loop *loop, edge exit, + struct tree_niter_desc *niter, + bool, bool every_iteration) +{ + if (!number_of_iterations_exit_assumptions (loop, exit, niter, + every_iteration)) + return false; - return flag_unsafe_loop_optimizations; + return (integer_nonzerop (niter->assumptions)); } /* Try to determine the number of iterations of LOOP. If we succeed, diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h index 1b5d111bc3e..1aea5801d00 100644 --- a/gcc/tree-ssa-loop-niter.h +++ b/gcc/tree-ssa-loop-niter.h @@ -27,6 +27,9 @@ extern bool loop_only_exit_p (const struct loop *, const_edge); extern bool number_of_iterations_exit (struct loop *, edge, struct tree_niter_desc *niter, bool, bool every_iteration = true); +extern bool number_of_iterations_exit_assumptions (struct loop *, edge, + struct tree_niter_desc *, + bool = true); extern tree find_loop_niter (struct loop *, edge *); extern bool finite_loop_p (struct loop *); extern tree loop_niter_by_eval (struct loop *, edge); -- 2.30.2