On Fri, 27 May 2016, Jan Hubicka wrote:
> Hi,
> this patch adds infrastructure to tree-ssa-loop-niter to record likely upper
> bounds.
> The basic idea is that it is easier to get likely bounds that 100% safe
> bounds or
> realistic estimates and the bound can be effectively used to trim down
> optimizations
> that are good idea only for large trip counts. This patch only updates the
> infrastructure. I have two followup patches. First turns current optimizers to
> use the bound (and adds testcase) and second enables loop peeling at -O3 and
> makes
> us to peel in cases where we would fully unroll if the loop bound was safe.
> This improves some benchmarks, like John the ripper.
>
> Currently likely upper bounds are derived in two cases
> 1) for arrays we can't prove to be non-trailing
> 2) for array accesses in conditional. I.e.
> int a[3];
> for (int i = 0; t(); i++)
> if (q())
> a[i]++;
> It is easy to add more cases, for example when the only unbounded loopback
> path contains
> unlikely edge.
>
> Bootstrapped/regtested x86_64-linux, OK?
likely_max_loop_iterations misses a function comment.
Ugh, one more widest_int in struct loop ... (oh well). Given
that (on x86_64) sizeof(widest_int) == 40 and sizeof(tree_int_cst) == 24
(ok, that's cheating, it's with just one HWI for the number) it looks
appealing to change the storage of these to 'tree' ... (as a followup,
using uint128_type_node or so or whatever largest integer type a
target supports). Another option is to add a GCed wide_int that we
can "allocate" - you can do this already by having a GTY HWI array
and length and using wi::from_buffer (). That way you'd avoid defining
any tree type.
Ok with the comment added.
Thanks,
Richard.
> Honza
>
> * 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.
> Index: cfgloop.c
> ===================================================================
> --- cfgloop.c (revision 236762)
> +++ cfgloop.c (working copy)
> @@ -1790,6 +1790,11 @@ record_niter_bound (struct loop *loop, c
> {
> 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, c
> 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, c
> && 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 *lo
> 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. */
> @@ -1899,6 +1935,40 @@ get_max_loop_iterations_int (struct loop
> return -1;
>
> if (!wi::fits_shwi_p (nit))
> + return -1;
> + hwi_nit = nit.to_shwi ();
> +
> + 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 ();
>
> Index: cfgloop.h
> ===================================================================
> --- cfgloop.h (revision 236762)
> +++ cfgloop.h (working copy)
> @@ -160,6 +160,8 @@ struct GTY ((chain_next ("%h.next"))) lo
> 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"))) lo
>
> 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. */
> Index: cfgloopmanip.c
> ===================================================================
> --- cfgloopmanip.c (revision 236762)
> +++ cfgloopmanip.c (working copy)
> @@ -1016,6 +1016,9 @@ copy_loop_info (struct loop *loop, struc
> 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;
> Index: loop-unroll.c
> ===================================================================
> --- loop-unroll.c (revision 236762)
> +++ loop-unroll.c (working copy)
> @@ -523,6 +523,11 @@ unroll_loop_constant_iterations (struct
> 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->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
> 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 l
> 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 l
> --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)
> Index: lto-streamer-in.c
> ===================================================================
> --- lto-streamer-in.c (revision 236762)
> +++ lto-streamer-in.c (working copy)
> @@ -835,6 +835,9 @@ input_cfg (struct lto_input_block *ib, s
> 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);
> Index: lto-streamer-out.c
> ===================================================================
> --- lto-streamer-out.c (revision 236762)
> +++ lto-streamer-out.c (working copy)
> @@ -1925,6 +1925,9 @@ output_cfg (struct output_block *ob, str
> 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);
> Index: tree-ssa-loop-ivcanon.c
> ===================================================================
> --- tree-ssa-loop-ivcanon.c (revision 236762)
> +++ tree-ssa-loop-ivcanon.c (working copy)
> @@ -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 (s
> 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
> Index: tree-ssa-loop-niter.c
> ===================================================================
> --- tree-ssa-loop-niter.c (revision 236762)
> +++ tree-ssa-loop-niter.c (working copy)
> @@ -2954,8 +2958,6 @@ record_estimate (struct loop *loop, tree
> 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
> /* 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,37 @@ max_loop_iterations_int (struct loop *lo
> return hwi_nit < 0 ? -1 : hwi_nit;
> }
>
> +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 +3902,7 @@ estimated_stmt_executions_int (struct lo
> 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. */
>
> @@ -3882,6 +3915,25 @@ max_stmt_executions (struct loop *loop,
> return false;
>
> nit_minus_one = *nit;
> +
> + *nit += 1;
> +
> + 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;
>
> Index: tree-ssa-loop-niter.h
> ===================================================================
> --- tree-ssa-loop-niter.h (revision 236762)
> +++ tree-ssa-loop-niter.h (working copy)
> @@ -35,9 +35,13 @@ extern bool estimated_loop_iterations (s
> 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 *);
>
>
--
Richard Biener <rguent...@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB
21284 (AG Nuernberg)
