From e3a8f1fa88d6d87444489c5cf8100aeb09bfb179 Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Mon, 8 Oct 2012 20:09:41 +0200 Subject: [PATCH] loop-unswitch.c (unswitch_single_loop): Use estimated_loop_iterations_int to prevent unswitching when... * loop-unswitch.c (unswitch_single_loop): Use estimated_loop_iterations_int to prevent unswitching when loop is known to not roll. * tree-ssa-loop-niter.c (estimated_loop_iterations): Do not segfault when SCEV is not initialized. (max_loop_iterations): Likewise. * tree-ssa-loop-unswitch.c (tree_ssa_unswitch_loops): Use estimated_loop_iterations_int to prevent unswithcing when loop is known to not roll. * tree-scalar-evolution.c (scev_initialized_p): New function. * tree-scalar-evolution.h (scev_initialized_p): Likewise. * loop-unroll.c (decide_peel_once_rolling): Use max_loop_iterations_int. (unroll_loop_constant_iterations): Update nb_iterations_upper_bound and nb_iterations_estimate. (decide_unroll_runtime_iterations): Use estimated_loop_iterations or max_loop_iterations; (unroll_loop_runtime_iterations): fix profile updating. (decide_peel_simple): Use estimated_loop_iterations and max_loop_iterations. (decide_unroll_stupid): Use estimated_loop_iterations ad max_loop_iterations. * loop-doloop.c (doloop_modify): Use max_loop_iterations_int. (doloop_optimize): Likewise. * loop-iv.c (iv_number_of_iterations): Use record_niter_bound. (find_simple_exit): Likewise. * cfgloop.h (struct niter_desc): Remove niter_max. From-SVN: r192219 --- gcc/ChangeLog | 30 ++++++++++++++++ gcc/cfgloop.h | 3 -- gcc/loop-doloop.c | 27 ++++++++++---- gcc/loop-iv.c | 29 ++++++++-------- gcc/loop-unroll.c | 83 ++++++++++++++++++++++++++++++++++---------- gcc/loop-unswitch.c | 4 ++- gcc/tree-scalar-evolution.c | 8 +++++ gcc/tree-scalar-evolution.h | 1 + gcc/tree-ssa-loop-niter.c | 23 ++++++++++-- gcc/tree-ssa-loop-unswitch.c | 11 ++++++ 10 files changed, 173 insertions(+), 46 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b7e0a64be80..ba74c1bbc1f 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,33 @@ +2012-10-08 Jan Hubicka + + * loop-unswitch.c (unswitch_single_loop): Use + estimated_loop_iterations_int to prevent unswitching when loop + is known to not roll. + * tree-ssa-loop-niter.c (estimated_loop_iterations): Do not segfault + when SCEV is not initialized. + (max_loop_iterations): Likewise. + * tree-ssa-loop-unswitch.c (tree_ssa_unswitch_loops): Use + estimated_loop_iterations_int to prevent unswithcing when + loop is known to not roll. + * tree-scalar-evolution.c (scev_initialized_p): New function. + * tree-scalar-evolution.h (scev_initialized_p): Likewise. + * loop-unroll.c (decide_peel_once_rolling): Use + max_loop_iterations_int. + (unroll_loop_constant_iterations): Update + nb_iterations_upper_bound and nb_iterations_estimate. + (decide_unroll_runtime_iterations): Use + estimated_loop_iterations or max_loop_iterations; + (unroll_loop_runtime_iterations): fix profile updating. + (decide_peel_simple): Use estimated_loop_iterations + and max_loop_iterations. + (decide_unroll_stupid): Use estimated_loop_iterations + ad max_loop_iterations. + * loop-doloop.c (doloop_modify): Use max_loop_iterations_int. + (doloop_optimize): Likewise. + * loop-iv.c (iv_number_of_iterations): Use record_niter_bound. + (find_simple_exit): Likewise. + * cfgloop.h (struct niter_desc): Remove niter_max. + 2012-10-08 Marek Polacek PR debug/54831 diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index e0a370f32bf..9d7b784174d 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -386,9 +386,6 @@ struct niter_desc /* Number of iterations if constant. */ unsigned HOST_WIDEST_INT niter; - /* Upper bound on the number of iterations. */ - unsigned HOST_WIDEST_INT niter_max; - /* Assumptions under that the rest of the information is valid. */ rtx assumptions; diff --git a/gcc/loop-doloop.c b/gcc/loop-doloop.c index 39e6ca92734..8dcfea5bba8 100644 --- a/gcc/loop-doloop.c +++ b/gcc/loop-doloop.c @@ -410,6 +410,7 @@ doloop_modify (struct loop *loop, struct niter_desc *desc, basic_block loop_end = desc->out_edge->src; enum machine_mode mode; rtx true_prob_val; + double_int iterations; jump_insn = BB_END (loop_end); @@ -460,9 +461,10 @@ doloop_modify (struct loop *loop, struct niter_desc *desc, /* Determine if the iteration counter will be non-negative. Note that the maximum value loaded is iterations_max - 1. */ - if (desc->niter_max - <= ((unsigned HOST_WIDEST_INT) 1 - << (GET_MODE_PRECISION (mode) - 1))) + if (max_loop_iterations (loop, &iterations) + && (iterations.ule (double_int_one.llshift + (GET_MODE_PRECISION (mode) - 1, + GET_MODE_PRECISION (mode))))) nonneg = 1; break; @@ -548,9 +550,17 @@ doloop_modify (struct loop *loop, struct niter_desc *desc, { rtx init; unsigned level = get_loop_level (loop) + 1; + double_int iter; + rtx iter_rtx; + + if (!max_loop_iterations (loop, &iter) + || !iter.fits_shwi ()) + iter_rtx = const0_rtx; + else + iter_rtx = GEN_INT (iter.to_shwi()); init = gen_doloop_begin (counter_reg, desc->const_iter ? desc->niter_expr : const0_rtx, - GEN_INT (desc->niter_max), + iter_rtx, GEN_INT (level)); if (init) { @@ -608,6 +618,7 @@ doloop_optimize (struct loop *loop) struct niter_desc *desc; unsigned word_mode_size; unsigned HOST_WIDE_INT word_mode_max; + double_int iter; if (dump_file) fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num); @@ -658,7 +669,11 @@ doloop_optimize (struct loop *loop) count = copy_rtx (desc->niter_expr); iterations = desc->const_iter ? desc->niter_expr : const0_rtx; - iterations_max = GEN_INT (desc->niter_max); + if (!max_loop_iterations (loop, &iter) + || !iter.fits_shwi ()) + iterations_max = const0_rtx; + else + iterations_max = GEN_INT (iter.to_shwi()); level = get_loop_level (loop) + 1; /* Generate looping insn. If the pattern FAILs then give up trying @@ -678,7 +693,7 @@ doloop_optimize (struct loop *loop) computed, we must be sure that the number of iterations fits into the new mode. */ && (word_mode_size >= GET_MODE_PRECISION (mode) - || desc->niter_max <= word_mode_max)) + || iter.ule (double_int::from_shwi (word_mode_max)))) { if (word_mode_size > GET_MODE_PRECISION (mode)) { diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c index e5c72596a32..658f20360f7 100644 --- a/gcc/loop-iv.c +++ b/gcc/loop-iv.c @@ -2294,10 +2294,6 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, desc->const_iter = false; desc->niter_expr = NULL_RTX; - desc->niter_max = 0; - if (loop->any_upper_bound - && loop->nb_iterations_upper_bound.fits_uhwi ()) - desc->niter_max = loop->nb_iterations_upper_bound.low; cond = GET_CODE (condition); gcc_assert (COMPARISON_P (condition)); @@ -2567,9 +2563,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, ? iv0.base : mode_mmin); max = (up - down) / inc + 1; - if (!desc->niter_max - || max < desc->niter_max) - desc->niter_max = max; + record_niter_bound (loop, double_int::from_shwi (max), + false, true); if (iv0.step == const0_rtx) { @@ -2780,14 +2775,16 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr); desc->const_iter = true; - desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode); + desc->niter = val & GET_MODE_MASK (desc->mode); + record_niter_bound (loop, double_int::from_shwi (desc->niter), + false, true); } else { max = determine_max_iter (loop, desc, old_niter); - if (!desc->niter_max - || max < desc->niter_max) - desc->niter_max = max; + gcc_assert (max); + record_niter_bound (loop, double_int::from_shwi (max), + false, true); /* simplify_using_initial_values does a copy propagation on the registers in the expression for the number of iterations. This prolongs life @@ -2812,7 +2809,8 @@ zero_iter_simplify: zero_iter: desc->const_iter = true; desc->niter = 0; - desc->niter_max = 0; + record_niter_bound (loop, double_int_zero, + true, true); desc->noloop_assumptions = NULL_RTX; desc->niter_expr = const0_rtx; return; @@ -2946,9 +2944,10 @@ find_simple_exit (struct loop *loop, struct niter_desc *desc) print_rtl (dump_file, desc->niter_expr); fprintf (dump_file, "\n"); - fprintf (dump_file, " upper bound: "); - fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max); - fprintf (dump_file, "\n"); + fprintf (dump_file, " upper bound: %li\n", + (long)max_loop_iterations_int (loop)); + fprintf (dump_file, " realistic bound: %li\n", + (long)estimated_loop_iterations_int (loop)); } else fprintf (dump_file, "Loop %d is not simple.\n", loop->num); diff --git a/gcc/loop-unroll.c b/gcc/loop-unroll.c index a09192597dd..b9ac22b8255 100644 --- a/gcc/loop-unroll.c +++ b/gcc/loop-unroll.c @@ -341,7 +341,8 @@ decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED) || desc->assumptions || desc->infinite || !desc->const_iter - || desc->niter != 0) + || (desc->niter != 0 + && max_loop_iterations_int (loop) != 0)) { if (dump_file) fprintf (dump_file, @@ -695,7 +696,13 @@ unroll_loop_constant_iterations (struct loop *loop) desc->noloop_assumptions = NULL_RTX; desc->niter -= exit_mod; - desc->niter_max -= exit_mod; + loop->nb_iterations_upper_bound -= double_int::from_uhwi (exit_mod); + if (loop->any_estimate + && double_int::from_uhwi (exit_mod).ule + (loop->nb_iterations_estimate)) + loop->nb_iterations_estimate -= double_int::from_uhwi (exit_mod); + else + loop->any_estimate = false; } SET_BIT (wont_exit, 1); @@ -733,7 +740,12 @@ unroll_loop_constant_iterations (struct loop *loop) apply_opt_in_copies (opt_info, exit_mod + 1, false, false); desc->niter -= exit_mod + 1; - desc->niter_max -= exit_mod + 1; + if (loop->any_estimate + && double_int::from_uhwi (exit_mod + 1).ule + (loop->nb_iterations_estimate)) + loop->nb_iterations_estimate -= double_int::from_uhwi (exit_mod + 1); + else + loop->any_estimate = false; desc->noloop_assumptions = NULL_RTX; SET_BIT (wont_exit, 0); @@ -782,7 +794,15 @@ unroll_loop_constant_iterations (struct loop *loop) } desc->niter /= max_unroll + 1; - desc->niter_max /= max_unroll + 1; + loop->nb_iterations_upper_bound + = loop->nb_iterations_upper_bound.udiv (double_int::from_uhwi (exit_mod + + 1), + FLOOR_DIV_EXPR); + if (loop->any_estimate) + loop->nb_iterations_estimate + = loop->nb_iterations_estimate.udiv (double_int::from_uhwi (exit_mod + + 1), + FLOOR_DIV_EXPR); desc->niter_expr = GEN_INT (desc->niter); /* Remove the edges. */ @@ -803,6 +823,7 @@ decide_unroll_runtime_iterations (struct loop *loop, int flags) { unsigned nunroll, nunroll_by_av, i; struct niter_desc *desc; + double_int iterations; if (!(flags & UAP_UNROLL)) { @@ -856,9 +877,10 @@ decide_unroll_runtime_iterations (struct loop *loop, int flags) } /* If we have profile feedback, check whether the loop rolls. */ - if ((loop->header->count - && expected_loop_iterations (loop) < 2 * nunroll) - || desc->niter_max < 2 * nunroll) + if ((estimated_loop_iterations (loop, &iterations) + || max_loop_iterations (loop, &iterations)) + && iterations.fits_shwi () + && iterations.to_shwi () <= 2 * nunroll) { if (dump_file) fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n"); @@ -1092,6 +1114,7 @@ unroll_loop_runtime_iterations (struct loop *loop) single_pred_edge (swtch)->probability = REG_BR_PROB_BASE - p; e = make_edge (swtch, preheader, single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP); + e->count = RDIV (preheader->count * REG_BR_PROB_BASE, p); e->probability = p; } @@ -1111,6 +1134,7 @@ unroll_loop_runtime_iterations (struct loop *loop) single_succ_edge (swtch)->probability = REG_BR_PROB_BASE - p; e = make_edge (swtch, preheader, single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP); + e->count = RDIV (preheader->count * REG_BR_PROB_BASE, p); e->probability = p; } @@ -1172,13 +1196,26 @@ unroll_loop_runtime_iterations (struct loop *loop) desc->niter_expr = simplify_gen_binary (UDIV, desc->mode, old_niter, GEN_INT (max_unroll + 1)); - desc->niter_max /= max_unroll + 1; + loop->nb_iterations_upper_bound + = loop->nb_iterations_upper_bound.udiv (double_int::from_uhwi (max_unroll + + 1), + FLOOR_DIV_EXPR); + if (loop->any_estimate) + loop->nb_iterations_estimate + = loop->nb_iterations_estimate.udiv (double_int::from_uhwi (max_unroll + + 1), + FLOOR_DIV_EXPR); if (exit_at_end) { desc->niter_expr = simplify_gen_binary (MINUS, desc->mode, desc->niter_expr, const1_rtx); desc->noloop_assumptions = NULL_RTX; - desc->niter_max--; + --loop->nb_iterations_upper_bound; + if (loop->any_estimate + && loop->nb_iterations_estimate != double_int_zero) + --loop->nb_iterations_estimate; + else + loop->any_estimate = false; } if (dump_file) @@ -1196,6 +1233,7 @@ decide_peel_simple (struct loop *loop, int flags) { unsigned npeel; struct niter_desc *desc; + double_int iterations; if (!(flags & UAP_PEEL)) { @@ -1239,23 +1277,30 @@ decide_peel_simple (struct loop *loop, int flags) return; } - if (loop->header->count) + /* If we have realistic estimate on number of iterations, use it. */ + if (estimated_loop_iterations (loop, &iterations)) { - unsigned niter = expected_loop_iterations (loop); - if (niter + 1 > npeel) + if (!iterations.fits_shwi () + || iterations.to_shwi () + 1 > npeel) { if (dump_file) { fprintf (dump_file, ";; Not peeling loop, rolls too much ("); fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, - (HOST_WIDEST_INT) (niter + 1)); + (HOST_WIDEST_INT) (iterations.to_shwi () + 1)); fprintf (dump_file, " iterations > %d [maximum peelings])\n", npeel); } return; } - npeel = niter + 1; - } + npeel = iterations.to_shwi () + 1; + } + /* If we have small enough bound on iterations, we can still peel (completely + unroll). */ + else if (max_loop_iterations (loop, &iterations) + && iterations.fits_shwi () + && iterations.to_shwi () + 1 <= npeel) + npeel = iterations.to_shwi () + 1; else { /* For now we have no good heuristics to decide whether loop peeling @@ -1349,6 +1394,7 @@ decide_unroll_stupid (struct loop *loop, int flags) { unsigned nunroll, nunroll_by_av, i; struct niter_desc *desc; + double_int iterations; if (!(flags & UAP_UNROLL_ALL)) { @@ -1401,9 +1447,10 @@ decide_unroll_stupid (struct loop *loop, int flags) } /* If we have profile feedback, check whether the loop rolls. */ - if ((loop->header->count - && expected_loop_iterations (loop) < 2 * nunroll) - || desc->niter_max < 2 * nunroll) + if ((estimated_loop_iterations (loop, &iterations) + || max_loop_iterations (loop, &iterations)) + && iterations.fits_shwi () + && iterations.to_shwi () <= 2 * nunroll) { if (dump_file) fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n"); diff --git a/gcc/loop-unswitch.c b/gcc/loop-unswitch.c index a9089a66cdf..4107048de01 100644 --- a/gcc/loop-unswitch.c +++ b/gcc/loop-unswitch.c @@ -257,6 +257,7 @@ unswitch_single_loop (struct loop *loop, rtx cond_checked, int num) rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn; int repeat; edge e; + HOST_WIDE_INT iterations; /* Do not unswitch too much. */ if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) @@ -299,7 +300,8 @@ unswitch_single_loop (struct loop *loop, rtx cond_checked, int num) } /* Nor if the loop usually does not roll. */ - if (expected_loop_iterations (loop) < 1) + iterations = estimated_loop_iterations_int (loop); + if (iterations >= 0 && iterations <= 1) { if (dump_file) fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n"); diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index d88bb1aa861..325654bac1b 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -3124,6 +3124,14 @@ scev_initialize (void) } } +/* Return true if SCEV is initialized. */ + +bool +scev_initialized_p (void) +{ + return scalar_evolution_info != NULL; +} + /* Cleans up the information cached by the scalar evolutions analysis in the hash table. */ diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h index dd1bdfc3404..3e52c57e393 100644 --- a/gcc/tree-scalar-evolution.h +++ b/gcc/tree-scalar-evolution.h @@ -27,6 +27,7 @@ extern tree number_of_exit_cond_executions (struct loop *); extern gimple get_loop_exit_condition (const struct loop *); extern void scev_initialize (void); +extern bool scev_initialized_p (void); extern void scev_reset (void); extern void scev_reset_htab (void); extern void scev_finalize (void); diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 84ae6104490..cdcdb5c5ad8 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -3012,9 +3012,23 @@ estimate_numbers_of_iterations_loop (struct loop *loop) bool estimated_loop_iterations (struct loop *loop, double_int *nit) { - estimate_numbers_of_iterations_loop (loop); + /* When SCEV information is available, try to update loop iterations + estimate. Otherwise just return whatever we recorded earlier. */ + if (scev_initialized_p ()) + estimate_numbers_of_iterations_loop (loop); + + /* Even if the bound is not recorded, possibly we can derrive one from + profile. */ if (!loop->any_estimate) - return false; + { + if (loop->header->count) + { + *nit = gcov_type_to_double_int + (expected_loop_iterations_unbounded (loop) + 1); + return true; + } + return false; + } *nit = loop->nb_iterations_estimate; return true; @@ -3027,7 +3041,10 @@ estimated_loop_iterations (struct loop *loop, double_int *nit) bool max_loop_iterations (struct loop *loop, double_int *nit) { - estimate_numbers_of_iterations_loop (loop); + /* When SCEV information is available, try to update loop iterations + estimate. Otherwise just return whatever we recorded earlier. */ + if (scev_initialized_p ()) + estimate_numbers_of_iterations_loop (loop); if (!loop->any_upper_bound) return false; diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c index eaf41e7d6ce..b24f3d74dce 100644 --- a/gcc/tree-ssa-loop-unswitch.c +++ b/gcc/tree-ssa-loop-unswitch.c @@ -78,6 +78,7 @@ tree_ssa_unswitch_loops (void) loop_iterator li; struct loop *loop; bool changed = false; + HOST_WIDE_INT iterations; /* Go through inner loops (only original ones). */ FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) @@ -102,6 +103,16 @@ tree_ssa_unswitch_loops (void) continue; } + /* If the loop is not expected to iterate, there is no need + for unswitching. */ + iterations = estimated_loop_iterations_int (loop); + if (iterations >= 0 && iterations <= 1) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ";; Not unswitching, loop is not expected to iterate\n"); + continue; + } + changed |= tree_unswitch_single_loop (loop, 0); } -- 2.11.4.GIT