From 105e29c5cf8729021614b152328bcfe054bed64d Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Fri, 27 May 2016 14:10:34 +0200 Subject: [PATCH] cfgloop.c (record_niter_bound): Record likely upper bounds. * cfgloop.c (record_niter_bound): Record likely upper bounds. (likely_max_stmt_executions_int, get_likely_max_loop_iterations, get_likely_max_loop_iterations_int): New. * cfgloop.h (struct loop): Add nb_iterations_likely_upper_bound, any_likely_upper_bound. (get_likely_max_loop_iterations_int, get_likely_max_loop_iterations): Declare. * cfgloopmanip.c (copy_loop_info): Copy likely upper bounds. * loop-unroll.c (unroll_loop_constant_iterations): Update likely upper bound. (unroll_loop_constant_iterations): Likewise. (unroll_loop_runtime_iterations): Likewise. * lto-streamer-in.c (input_cfg): Stream likely upper bounds. * lto-streamer-out.c (output_cfg): Likewise. * tree-ssa-loop-ivcanon.c (try_peel_loop): Update likely upper bounds. (canonicalize_loop_induction_variables): Dump likely upper bounds. * tree-ssa-loop-niter.c (record_estimate): Record likely upper bounds. (likely_max_loop_iterations): New. (likely_max_loop_iterations_int): New. (likely_max_stmt_executions): New. * tree-ssa-loop-niter.h (likely_max_loop_iterations, likely_max_loop_iterations_int, likely_max_stmt_executions_int, likely_max_stmt_executions): Declare. From-SVN: r236816 --- gcc/ChangeLog | 27 ++++++++++++++ gcc/cfgloop.c | 70 +++++++++++++++++++++++++++++++++++++ gcc/cfgloop.h | 5 +++ gcc/cfgloopmanip.c | 3 ++ gcc/loop-unroll.c | 21 +++++++++++ gcc/lto-streamer-in.c | 3 ++ gcc/lto-streamer-out.c | 3 ++ gcc/tree-ssa-loop-ivcanon.c | 8 +++++ gcc/tree-ssa-loop-niter.c | 66 +++++++++++++++++++++++++++++++--- gcc/tree-ssa-loop-niter.h | 4 +++ 10 files changed, 205 insertions(+), 5 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 14ba165d82c..eb34a284658 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,30 @@ +2016-05-27 Jan Hubicka + + * cfgloop.c (record_niter_bound): Record likely upper bounds. + (likely_max_stmt_executions_int, get_likely_max_loop_iterations, + get_likely_max_loop_iterations_int): New. + * cfgloop.h (struct loop): Add nb_iterations_likely_upper_bound, + any_likely_upper_bound. + (get_likely_max_loop_iterations_int, get_likely_max_loop_iterations): + Declare. + * cfgloopmanip.c (copy_loop_info): Copy likely upper bounds. + * loop-unroll.c (unroll_loop_constant_iterations): Update likely + upper bound. + (unroll_loop_constant_iterations): Likewise. + (unroll_loop_runtime_iterations): Likewise. + * lto-streamer-in.c (input_cfg): Stream likely upper bounds. + * lto-streamer-out.c (output_cfg): Likewise. + * tree-ssa-loop-ivcanon.c (try_peel_loop): Update likely upper + bounds. + (canonicalize_loop_induction_variables): Dump likely upper bounds. + * tree-ssa-loop-niter.c (record_estimate): Record likely upper bounds. + (likely_max_loop_iterations): New. + (likely_max_loop_iterations_int): New. + (likely_max_stmt_executions): New. + * tree-ssa-loop-niter.h (likely_max_loop_iterations, + likely_max_loop_iterations_int, likely_max_stmt_executions_int, + likely_max_stmt_executions): Declare. + 2016-05-27 Marek Polacek PR middle-end/71308 diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 02234173b08..27ccfb226c9 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -1790,6 +1790,11 @@ record_niter_bound (struct loop *loop, const widest_int &i_bound, { loop->any_upper_bound = true; loop->nb_iterations_upper_bound = i_bound; + if (!loop->any_likely_upper_bound) + { + loop->any_likely_upper_bound = true; + loop->nb_iterations_likely_upper_bound = i_bound; + } } if (realistic && (!loop->any_estimate @@ -1798,6 +1803,13 @@ record_niter_bound (struct loop *loop, const widest_int &i_bound, loop->any_estimate = true; loop->nb_iterations_estimate = i_bound; } + if (!realistic + && (!loop->any_likely_upper_bound + || wi::ltu_p (i_bound, loop->nb_iterations_likely_upper_bound))) + { + loop->any_likely_upper_bound = true; + loop->nb_iterations_likely_upper_bound = i_bound; + } /* If an upper bound is smaller than the realistic estimate of the number of iterations, use the upper bound instead. */ @@ -1806,6 +1818,11 @@ record_niter_bound (struct loop *loop, const widest_int &i_bound, && wi::ltu_p (loop->nb_iterations_upper_bound, loop->nb_iterations_estimate)) loop->nb_iterations_estimate = loop->nb_iterations_upper_bound; + if (loop->any_upper_bound + && loop->any_likely_upper_bound + && wi::ltu_p (loop->nb_iterations_upper_bound, + loop->nb_iterations_likely_upper_bound)) + loop->nb_iterations_likely_upper_bound = loop->nb_iterations_upper_bound; } /* Similar to get_estimated_loop_iterations, but returns the estimate only @@ -1847,6 +1864,25 @@ max_stmt_executions_int (struct loop *loop) return snit < 0 ? -1 : snit; } +/* Returns an likely upper bound on the number of executions of statements + in the LOOP. For statements before the loop exit, this exceeds + the number of execution of the latch by one. */ + +HOST_WIDE_INT +likely_max_stmt_executions_int (struct loop *loop) +{ + HOST_WIDE_INT nit = get_likely_max_loop_iterations_int (loop); + HOST_WIDE_INT snit; + + if (nit == -1) + return -1; + + snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1); + + /* If the computation overflows, return -1. */ + return snit < 0 ? -1 : snit; +} + /* Sets NIT to the estimated number of executions of the latch of the LOOP. If we have no reliable estimate, the function returns false, otherwise returns true. */ @@ -1905,6 +1941,40 @@ get_max_loop_iterations_int (struct loop *loop) return hwi_nit < 0 ? -1 : hwi_nit; } +/* Sets NIT to an upper bound for the maximum number of executions of the + latch of the LOOP. If we have no reliable estimate, the function returns + false, otherwise returns true. */ + +bool +get_likely_max_loop_iterations (struct loop *loop, widest_int *nit) +{ + if (!loop->any_likely_upper_bound) + return false; + + *nit = loop->nb_iterations_likely_upper_bound; + return true; +} + +/* Similar to get_max_loop_iterations, but returns the estimate only + if it fits to HOST_WIDE_INT. If this is not the case, or the estimate + on the number of iterations of LOOP could not be derived, returns -1. */ + +HOST_WIDE_INT +get_likely_max_loop_iterations_int (struct loop *loop) +{ + widest_int nit; + HOST_WIDE_INT hwi_nit; + + if (!get_likely_max_loop_iterations (loop, &nit)) + return -1; + + if (!wi::fits_shwi_p (nit)) + return -1; + hwi_nit = nit.to_shwi (); + + return hwi_nit < 0 ? -1 : hwi_nit; +} + /* Returns the loop depth of the loop BB belongs to. */ int diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 173fda84ba4..aba2988c99e 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -160,6 +160,8 @@ struct GTY ((chain_next ("%h.next"))) loop { valid if any_upper_bound is true. */ widest_int nb_iterations_upper_bound; + widest_int nb_iterations_likely_upper_bound; + /* An integer giving an estimate on nb_iterations. Unlike nb_iterations_upper_bound, there is no guarantee that it is at least nb_iterations. */ @@ -167,6 +169,7 @@ struct GTY ((chain_next ("%h.next"))) loop { bool any_upper_bound; bool any_estimate; + bool any_likely_upper_bound; /* True if the loop can be parallel. */ bool can_be_parallel; @@ -776,8 +779,10 @@ loop_outermost (struct loop *loop) extern void record_niter_bound (struct loop *, const widest_int &, bool, bool); extern HOST_WIDE_INT get_estimated_loop_iterations_int (struct loop *); extern HOST_WIDE_INT get_max_loop_iterations_int (struct loop *); +extern HOST_WIDE_INT get_likely_max_loop_iterations_int (struct loop *); extern bool get_estimated_loop_iterations (struct loop *loop, widest_int *nit); extern bool get_max_loop_iterations (struct loop *loop, widest_int *nit); +extern bool get_likely_max_loop_iterations (struct loop *loop, widest_int *nit); extern int bb_loop_depth (const_basic_block); /* Converts VAL to widest_int. */ diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 2bffb80e284..707a130d26a 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -1016,6 +1016,9 @@ copy_loop_info (struct loop *loop, struct loop *target) gcc_checking_assert (!target->any_upper_bound && !target->any_estimate); target->any_upper_bound = loop->any_upper_bound; target->nb_iterations_upper_bound = loop->nb_iterations_upper_bound; + target->any_likely_upper_bound = loop->any_likely_upper_bound; + target->nb_iterations_likely_upper_bound + = loop->nb_iterations_likely_upper_bound; target->any_estimate = loop->any_estimate; target->nb_iterations_estimate = loop->nb_iterations_estimate; target->estimate_state = loop->estimate_state; diff --git a/gcc/loop-unroll.c b/gcc/loop-unroll.c index 4d26e2f7cd1..97735a89e58 100644 --- a/gcc/loop-unroll.c +++ b/gcc/loop-unroll.c @@ -523,6 +523,11 @@ unroll_loop_constant_iterations (struct loop *loop) loop->nb_iterations_estimate -= exit_mod; else loop->any_estimate = false; + if (loop->any_likely_upper_bound + && wi::leu_p (exit_mod, loop->nb_iterations_likely_upper_bound)) + loop->nb_iterations_likely_upper_bound -= exit_mod; + else + loop->any_likely_upper_bound = false; } bitmap_set_bit (wont_exit, 1); @@ -566,6 +571,11 @@ unroll_loop_constant_iterations (struct loop *loop) loop->nb_iterations_estimate -= exit_mod + 1; else loop->any_estimate = false; + if (loop->any_likely_upper_bound + && wi::leu_p (exit_mod + 1, loop->nb_iterations_likely_upper_bound)) + loop->nb_iterations_likely_upper_bound -= exit_mod + 1; + else + loop->any_likely_upper_bound = false; desc->noloop_assumptions = NULL_RTX; bitmap_set_bit (wont_exit, 0); @@ -619,6 +629,9 @@ unroll_loop_constant_iterations (struct loop *loop) if (loop->any_estimate) loop->nb_iterations_estimate = wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1); + if (loop->any_likely_upper_bound) + loop->nb_iterations_likely_upper_bound + = wi::udiv_trunc (loop->nb_iterations_likely_upper_bound, max_unroll + 1); desc->niter_expr = GEN_INT (desc->niter); /* Remove the edges. */ @@ -1059,6 +1072,9 @@ unroll_loop_runtime_iterations (struct loop *loop) if (loop->any_estimate) loop->nb_iterations_estimate = wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1); + if (loop->any_likely_upper_bound) + loop->nb_iterations_likely_upper_bound + = wi::udiv_trunc (loop->nb_iterations_likely_upper_bound, max_unroll + 1); if (exit_at_end) { desc->niter_expr = @@ -1070,6 +1086,11 @@ unroll_loop_runtime_iterations (struct loop *loop) --loop->nb_iterations_estimate; else loop->any_estimate = false; + if (loop->any_likely_upper_bound + && loop->nb_iterations_likely_upper_bound != 0) + --loop->nb_iterations_likely_upper_bound; + else + loop->any_likely_upper_bound = false; } if (dump_file) diff --git a/gcc/lto-streamer-in.c b/gcc/lto-streamer-in.c index 3a353cd0437..00db94eac6b 100644 --- a/gcc/lto-streamer-in.c +++ b/gcc/lto-streamer-in.c @@ -835,6 +835,9 @@ input_cfg (struct lto_input_block *ib, struct data_in *data_in, loop->any_upper_bound = streamer_read_hwi (ib); if (loop->any_upper_bound) loop->nb_iterations_upper_bound = streamer_read_wi (ib); + loop->any_likely_upper_bound = streamer_read_hwi (ib); + if (loop->any_likely_upper_bound) + loop->nb_iterations_likely_upper_bound = streamer_read_wi (ib); loop->any_estimate = streamer_read_hwi (ib); if (loop->any_estimate) loop->nb_iterations_estimate = streamer_read_wi (ib); diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c index 35e58fd24cc..ed6f7482dbd 100644 --- a/gcc/lto-streamer-out.c +++ b/gcc/lto-streamer-out.c @@ -1925,6 +1925,9 @@ output_cfg (struct output_block *ob, struct function *fn) streamer_write_hwi (ob, loop->any_upper_bound); if (loop->any_upper_bound) streamer_write_wi (ob, loop->nb_iterations_upper_bound); + streamer_write_hwi (ob, loop->any_likely_upper_bound); + if (loop->any_likely_upper_bound) + streamer_write_wi (ob, loop->nb_iterations_likely_upper_bound); streamer_write_hwi (ob, loop->any_estimate); if (loop->any_estimate) streamer_write_wi (ob, loop->nb_iterations_estimate); diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c index e8f67953231..de447f40e78 100644 --- a/gcc/tree-ssa-loop-ivcanon.c +++ b/gcc/tree-ssa-loop-ivcanon.c @@ -1036,6 +1036,8 @@ try_peel_loop (struct loop *loop, } if (loop->any_upper_bound) loop->nb_iterations_upper_bound -= npeel; + if (loop->any_likely_upper_bound) + loop->nb_iterations_likely_upper_bound -= npeel; loop->nb_iterations_estimate = 0; /* Make sure to mark loop cold so we do not try to peel it more. */ scale_loop_profile (loop, 1, 0); @@ -1107,6 +1109,12 @@ canonicalize_loop_induction_variables (struct loop *loop, fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num, (int)maxiter); } + if (dump_file && (dump_flags & TDF_DETAILS) + && likely_max_loop_iterations_int (loop) >= 0) + { + fprintf (dump_file, "Loop likely %d iterates at most %i times.\n", loop->num, + (int)likely_max_loop_iterations_int (loop)); + } /* Remove exits that are known to be never taken based on loop bound. Needs to be called after compilation of max_loop_iterations_int that diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 5afc9b3fdf0..e38d2466bb4 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -2289,7 +2289,11 @@ number_of_iterations_exit (struct loop *loop, edge exit, /* If NITER has simplified into a constant, update MAX. */ if (TREE_CODE (niter->niter) == INTEGER_CST) - niter->max = wi::to_widest (niter->niter); + { + niter->max = wi::to_widest (niter->niter); + record_niter_bound (loop, niter->max, loop_only_exit_p (loop, exit), + true); + } if (integer_onep (niter->assumptions)) return true; @@ -2954,8 +2958,6 @@ record_estimate (struct loop *loop, tree bound, const widest_int &i_bound, realistic = false; else gcc_checking_assert (i_bound == wi::to_widest (bound)); - if (!upper && !realistic) - return; /* If we have a guaranteed upper bound, record it in the appropriate list, unless this is an !is_exit bound (i.e. undefined behavior in @@ -2977,7 +2979,7 @@ record_estimate (struct loop *loop, tree bound, const widest_int &i_bound, /* If statement is executed on every path to the loop latch, we can directly infer the upper bound on the # of iterations of the loop. */ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt))) - return; + upper = false; /* Update the number of iteration estimates according to the bound. If at_stmt is an exit then the loop latch is executed at most BOUND times, @@ -3850,6 +3852,41 @@ max_loop_iterations_int (struct loop *loop) return hwi_nit < 0 ? -1 : hwi_nit; } +/* Sets NIT to an likely upper bound for the maximum number of executions of the + latch of the LOOP. If we have no reliable estimate, the function returns + false, otherwise returns true. */ + +bool +likely_max_loop_iterations (struct loop *loop, widest_int *nit) +{ + /* 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); + + return get_likely_max_loop_iterations (loop, nit); +} + +/* Similar to max_loop_iterations, but returns the estimate only + if it fits to HOST_WIDE_INT. If this is not the case, or the estimate + on the number of iterations of LOOP could not be derived, returns -1. */ + +HOST_WIDE_INT +likely_max_loop_iterations_int (struct loop *loop) +{ + widest_int nit; + HOST_WIDE_INT hwi_nit; + + if (!likely_max_loop_iterations (loop, &nit)) + return -1; + + if (!wi::fits_shwi_p (nit)) + return -1; + hwi_nit = nit.to_shwi (); + + return hwi_nit < 0 ? -1 : hwi_nit; +} + /* Returns an estimate for the number of executions of statements in the LOOP. For statements before the loop exit, this exceeds the number of execution of the latch by one. */ @@ -3869,7 +3906,7 @@ estimated_stmt_executions_int (struct loop *loop) return snit < 0 ? -1 : snit; } -/* Sets NIT to the estimated maximum number of executions of the latch of the +/* Sets NIT to the maximum number of executions of the latch of the LOOP, plus one. If we have no reliable estimate, the function returns false, otherwise returns true. */ @@ -3888,6 +3925,25 @@ max_stmt_executions (struct loop *loop, widest_int *nit) return wi::gtu_p (*nit, nit_minus_one); } +/* Sets NIT to the estimated maximum number of executions of the latch of the + LOOP, plus one. If we have no likely estimate, the function returns + false, otherwise returns true. */ + +bool +likely_max_stmt_executions (struct loop *loop, widest_int *nit) +{ + widest_int nit_minus_one; + + if (!likely_max_loop_iterations (loop, nit)) + return false; + + nit_minus_one = *nit; + + *nit += 1; + + return wi::gtu_p (*nit, nit_minus_one); +} + /* Sets NIT to the estimated number of executions of the latch of the LOOP, plus one. If we have no reliable estimate, the function returns false, otherwise returns true. */ diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h index 84ff0aea11c..1b5d111bc3e 100644 --- a/gcc/tree-ssa-loop-niter.h +++ b/gcc/tree-ssa-loop-niter.h @@ -35,9 +35,13 @@ extern bool estimated_loop_iterations (struct loop *, widest_int *); extern HOST_WIDE_INT estimated_loop_iterations_int (struct loop *); extern bool max_loop_iterations (struct loop *, widest_int *); extern HOST_WIDE_INT max_loop_iterations_int (struct loop *); +extern bool likely_max_loop_iterations (struct loop *, widest_int *); +extern HOST_WIDE_INT likely_max_loop_iterations_int (struct loop *); extern HOST_WIDE_INT max_stmt_executions_int (struct loop *); +extern HOST_WIDE_INT likely_max_stmt_executions_int (struct loop *); extern HOST_WIDE_INT estimated_stmt_executions_int (struct loop *); extern bool max_stmt_executions (struct loop *, widest_int *); +extern bool likely_max_stmt_executions (struct loop *, widest_int *); extern bool estimated_stmt_executions (struct loop *, widest_int *); extern void estimate_numbers_of_iterations (void); extern bool stmt_dominates_stmt_p (gimple *, gimple *); -- 2.30.2