On Tue, Oct 5, 2021 at 3:39 PM Richard Sandiford via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> In g:62acc72a957b5614 I'd stopped the unroller from using
> an epilogue loop in cases where the iteration count was
> known to be a multiple of the unroll factor. The epilogue
> and non-epilogue cases still shared this (preexisting) code
> to update the edge frequencies:
>
> basic_block exit_bb = single_pred (loop->latch);
> new_exit = find_edge (exit_bb, rest);
> new_exit->probability = profile_probability::always ()
> .apply_scale (1, new_est_niter + 1);
> [etc]
>
> But of course (in hindsight) that only makes sense for the
> epilogue case, where we've already moved the main loop's exit edge
> to be a sibling of the latch edge. For the non-epilogue case,
> the exit edge stays (and needs to stay) in its original position.
>
> I don't really understand what the code is trying to do for
> the epilogue case. It has:
>
> /* Ensure that the frequencies in the loop match the new estimated
> number of iterations, and change the probability of the new
> exit edge. */
>
> profile_count freq_h = loop->header->count;
> profile_count freq_e = (loop_preheader_edge (loop))->count ();
> if (freq_h.nonzero_p ())
> {
> ...
> scale_loop_frequencies (loop, freq_e.probability_in (freq_h));
> }
>
> Here, freq_e.probability_in (freq_h) is freq_e / freq_h, so for the
> header block, this has the effect of:
>
> new header count = freq_h * (freq_e / freq_h)
>
> i.e. we say that the header executes exactly as often as the
> preheader edge, which would only make sense if the loop never
> iterates. Also, after setting the probability of the nonexit edge
> (correctly) to new_est_niter / (new_est_niter + 1), the code does:
>
> scale_bbs_frequencies (&loop->latch, 1, prob);
>
> for this new probability. I think that only makes sense if the
> nonexit edge was previously unconditional (100%). But the code
> carefully preserved the probability of the original exit edge
> when creating the new one.
>
> All I'm trying to do here though is fix the mess I created
> and get the probabilities right for the non-epilogue case.
> Things are simpler there since we don't have to worry about
> loop versioning. Hopefully the comments explain the approach.
>
> The function's current interface implies that it can cope with
> multiple exit edges and that the function only needs the iteration
> count relative to one of those edges in order to work correctly.
> In practice that's not the case: it assumes there is exactly one
> exit edge and all current callers also ensure that the exit test
> dominates the latch. I think the function is easier to follow
> if we remove the implied generality.
>
> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install?
OK.
Thanks,
Richard.
> Richard
>
>
> gcc/
> PR tree-optimization/102385
> * predict.h (change_edge_frequency): Declare.
> * predict.c (change_edge_frequency): New function.
> * tree-ssa-loop-manip.h (tree_transform_and_unroll_loop): Remove
> edge argument.
> (tree_unroll_loop): Likewise.
> * gimple-loop-jam.c (tree_loop_unroll_and_jam): Update accordingly.
> * tree-predcom.c (pcom_worker::tree_predictive_commoning_loop):
> Likewise.
> * tree-ssa-loop-manip.c (tree_unroll_loop): Likewise.
> (tree_transform_and_unroll_loop): Likewise. Use single_dom_exit
> to retrieve the exit edges. Make all the old profile update code
> conditional on !single_loop_p -- the case it was written for --
> and use a different approach for the single-loop case.
>
> gcc/testsuite/
> * testsuite/gcc.dg/pr102385.c: New test.
> ---
> gcc/gimple-loop-jam.c | 3 +-
> gcc/predict.c | 37 +++++++++++
> gcc/predict.h | 1 +
> gcc/testsuite/gcc.dg/pr102385.c | 14 ++++
> gcc/tree-predcom.c | 3 +-
> gcc/tree-ssa-loop-manip.c | 111 ++++++++++++++++++++++++--------
> gcc/tree-ssa-loop-manip.h | 5 +-
> gcc/tree-ssa-loop-prefetch.c | 3 +-
> 8 files changed, 140 insertions(+), 37 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/pr102385.c
>
> diff --git a/gcc/predict.h b/gcc/predict.h
> index 8860cafa31c..4df51bd615c 100644
> --- a/gcc/predict.h
> +++ b/gcc/predict.h
> @@ -100,6 +100,7 @@ extern void rebuild_frequencies (void);
> extern void report_predictor_hitrates (void);
> extern void force_edge_cold (edge, bool);
> extern void propagate_unlikely_bbs_forward (void);
> +extern void change_edge_frequency (edge, profile_probability);
>
> extern void add_reg_br_prob_note (rtx_insn *, profile_probability);
>
> diff --git a/gcc/predict.c b/gcc/predict.c
> index d9c7249831e..68b11135680 100644
> --- a/gcc/predict.c
> +++ b/gcc/predict.c
> @@ -4481,6 +4481,43 @@ force_edge_cold (edge e, bool impossible)
> }
> }
>
> +/* Change E's probability to NEW_E_PROB, redistributing the probabilities
> + of other outgoing edges proportionally.
> +
> + Note that this function does not change the profile counts of any
> + basic blocks. The caller must do that instead, using whatever
> + information it has about the region that needs updating. */
> +
> +void
> +change_edge_frequency (edge e, profile_probability new_e_prob)
> +{
> + profile_probability old_e_prob = e->probability;
> + profile_probability old_other_prob = old_e_prob.invert ();
> + profile_probability new_other_prob = new_e_prob.invert ();
> +
> + e->probability = new_e_prob;
> + profile_probability cumulative_prob = new_e_prob;
> +
> + unsigned int num_other = EDGE_COUNT (e->src->succs) - 1;
> + edge other_e;
> + edge_iterator ei;
> + FOR_EACH_EDGE (other_e, ei, e->src->succs)
> + if (other_e != e)
> + {
> + num_other -= 1;
> + if (num_other == 0)
> + /* Ensure that the probabilities add up to 1 without
> + rounding error. */
> + other_e->probability = cumulative_prob.invert ();
> + else
> + {
> + other_e->probability /= old_other_prob;
> + other_e->probability *= new_other_prob;
> + cumulative_prob += other_e->probability;
> + }
> + }
> +}
> +
> #if CHECKING_P
>
> namespace selftest {
> diff --git a/gcc/tree-ssa-loop-manip.h b/gcc/tree-ssa-loop-manip.h
> index 86fc118b6be..5e2d7fa11a4 100644
> --- a/gcc/tree-ssa-loop-manip.h
> +++ b/gcc/tree-ssa-loop-manip.h
> @@ -50,10 +50,9 @@ extern bool can_unroll_loop_p (class loop *loop, unsigned
> factor,
> class tree_niter_desc *niter);
> extern gcov_type niter_for_unrolled_loop (class loop *, unsigned);
> extern void tree_transform_and_unroll_loop (class loop *, unsigned,
> - edge, class tree_niter_desc *,
> + tree_niter_desc *,
> transform_callback, void *);
> -extern void tree_unroll_loop (class loop *, unsigned,
> - edge, class tree_niter_desc *);
> +extern void tree_unroll_loop (class loop *, unsigned, tree_niter_desc *);
> extern tree canonicalize_loop_ivs (class loop *, tree *, bool);
> extern unsigned int loop_invariant_motion_in_fun (function *, bool);
>
> diff --git a/gcc/tree-predcom.c b/gcc/tree-predcom.c
> index 6b195d1914f..8f1cf4d44a2 100644
> --- a/gcc/tree-predcom.c
> +++ b/gcc/tree-predcom.c
> @@ -3397,8 +3397,7 @@ pcom_worker::tree_predictive_commoning_loop (bool
> allow_unroll_p)
> the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
> replace_phis_by_defined_names (m_chains);
>
> - edge exit = single_dom_exit (m_loop);
> - tree_transform_and_unroll_loop (m_loop, unroll_factor, exit, &desc,
> + tree_transform_and_unroll_loop (m_loop, unroll_factor, &desc,
> execute_pred_commoning_cbck, &dta);
> eliminate_temp_copies (m_loop, tmp_vars);
> }
> diff --git a/gcc/gimple-loop-jam.c b/gcc/gimple-loop-jam.c
> index d212e391489..611d3805304 100644
> --- a/gcc/gimple-loop-jam.c
> +++ b/gcc/gimple-loop-jam.c
> @@ -587,8 +587,7 @@ tree_loop_unroll_and_jam (void)
> "applying unroll and jam with factor %d\n",
> unroll_factor);
> initialize_original_copy_tables ();
> - tree_unroll_loop (outer, unroll_factor, single_dom_exit (outer),
> - &desc);
> + tree_unroll_loop (outer, unroll_factor, &desc);
> free_original_copy_tables ();
> fuse_loops (outer->inner);
> todo |= TODO_cleanup_cfg;
> diff --git a/gcc/tree-ssa-loop-prefetch.c b/gcc/tree-ssa-loop-prefetch.c
> index 85977e23245..04b2b33c1ba 100644
> --- a/gcc/tree-ssa-loop-prefetch.c
> +++ b/gcc/tree-ssa-loop-prefetch.c
> @@ -1962,8 +1962,7 @@ loop_prefetch_arrays (class loop *loop)
> iterations so that we do not issue superfluous prefetches. */
> if (unroll_factor != 1)
> {
> - tree_unroll_loop (loop, unroll_factor,
> - single_dom_exit (loop), &desc);
> + tree_unroll_loop (loop, unroll_factor, &desc);
> unrolled = true;
> }
>
> diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
> index c7a2f67b129..2d576bfa391 100644
> --- a/gcc/tree-ssa-loop-manip.c
> +++ b/gcc/tree-ssa-loop-manip.c
> @@ -1182,8 +1182,9 @@ niter_for_unrolled_loop (class loop *loop, unsigned
> factor)
> return new_est_niter;
> }
>
> -/* Unroll LOOP FACTOR times. DESC describes number of iterations of LOOP.
> - EXIT is the exit of the loop to that DESC corresponds.
> +/* Unroll LOOP FACTOR times. LOOP is known to have a single exit edge
> + whose source block dominates the latch. DESC describes the number of
> + iterations of LOOP.
>
> If N is number of iterations of the loop and MAY_BE_ZERO is the condition
> under that loop exits in the first iteration even if N != 0,
> @@ -1241,7 +1242,7 @@ niter_for_unrolled_loop (class loop *loop, unsigned
> factor)
>
> void
> tree_transform_and_unroll_loop (class loop *loop, unsigned factor,
> - edge exit, class tree_niter_desc *desc,
> + class tree_niter_desc *desc,
> transform_callback transform,
> void *data)
> {
> @@ -1265,10 +1266,11 @@ tree_transform_and_unroll_loop (class loop *loop,
> unsigned factor,
>
> gcond *exit_if = nullptr;
> class loop *new_loop = nullptr;
> - basic_block rest;
> edge new_exit;
> if (!single_loop_p)
> {
> + edge exit = single_dom_exit (loop);
> +
> /* The values for scales should keep profile consistent, and somewhat
> close to correct.
>
> @@ -1291,7 +1293,7 @@ tree_transform_and_unroll_loop (class loop *loop,
> unsigned factor,
>
> /* Prepare the cfg and update the phi nodes. Move the loop exit to the
> loop latch (and make its condition dummy, for the moment). */
> - rest = loop_preheader_edge (new_loop)->src;
> + basic_block rest = loop_preheader_edge (new_loop)->src;
> edge precond_edge = single_pred_edge (rest);
> split_edge (loop_latch_edge (loop));
> basic_block exit_bb = single_pred (loop->latch);
> @@ -1373,10 +1375,7 @@ tree_transform_and_unroll_loop (class loop *loop,
> unsigned factor,
> remove_path (exit);
> }
> else
> - {
> - new_exit = exit;
> - rest = exit->dest;
> - }
> + new_exit = single_dom_exit (loop);
>
> /* Transform the loop. */
> if (transform)
> @@ -1401,6 +1400,7 @@ tree_transform_and_unroll_loop (class loop *loop,
> unsigned factor,
> }
> update_ssa (TODO_update_ssa);
>
> + new_exit = single_dom_exit (loop);
> if (!single_loop_p)
> {
> /* Ensure that the frequencies in the loop match the new estimated
> @@ -1417,29 +1417,24 @@ tree_transform_and_unroll_loop (class loop *loop,
> unsigned factor,
> freq_e = freq_e.force_nonzero ();
> scale_loop_frequencies (loop, freq_e.probability_in (freq_h));
> }
> - }
>
> - basic_block exit_bb = single_pred (loop->latch);
> - new_exit = find_edge (exit_bb, rest);
> - new_exit->probability = profile_probability::always ()
> - .apply_scale (1, new_est_niter + 1);
> + basic_block rest = new_exit->dest;
> + new_exit->probability = profile_probability::always ()
> + .apply_scale (1, new_est_niter + 1);
>
> - if (!single_loop_p)
> - rest->count += new_exit->count ();
> + rest->count += new_exit->count ();
>
> - edge new_nonexit = single_pred_edge (loop->latch);
> - profile_probability prob = new_nonexit->probability;
> - new_nonexit->probability = new_exit->probability.invert ();
> - prob = new_nonexit->probability / prob;
> - if (prob.initialized_p ())
> - scale_bbs_frequencies (&loop->latch, 1, prob);
> + edge new_nonexit = single_pred_edge (loop->latch);
> + profile_probability prob = new_nonexit->probability;
> + new_nonexit->probability = new_exit->probability.invert ();
> + prob = new_nonexit->probability / prob;
> + if (prob.initialized_p ())
> + scale_bbs_frequencies (&loop->latch, 1, prob);
>
> - if (!single_loop_p)
> - {
> /* Finally create the new counter for number of iterations and add
> the new exit instruction. */
> tree ctr_before, ctr_after;
> - gimple_stmt_iterator bsi = gsi_last_nondebug_bb (exit_bb);
> + gimple_stmt_iterator bsi = gsi_last_nondebug_bb (new_exit->src);
> exit_if = as_a <gcond *> (gsi_stmt (bsi));
> create_iv (exit_base, exit_step, NULL_TREE, loop,
> &bsi, false, &ctr_before, &ctr_after);
> @@ -1448,6 +1443,67 @@ tree_transform_and_unroll_loop (class loop *loop,
> unsigned factor,
> gimple_cond_set_rhs (exit_if, exit_bound);
> update_stmt (exit_if);
> }
> + else
> + {
> + /* gimple_duplicate_loop_to_header_edge has adjusted the loop body's
> + original profile counts in line with the unroll factor. However,
> + the old counts might not have been consistent with the old
> + iteration count.
> +
> + Therefore, if the iteration count is known exactly, make sure that
> the
> + profile counts of the loop header (and any other blocks that might be
> + executed in the final iteration) are consistent with the combination
> + of (a) the incoming profile count and (b) the new iteration count.
> */
> + profile_count in_count = loop_preheader_edge (loop)->count ();
> + profile_count old_header_count = loop->header->count;
> + if (in_count.nonzero_p ()
> + && old_header_count.nonzero_p ()
> + && TREE_CODE (desc->niter) == INTEGER_CST)
> + {
> + /* The + 1 converts latch counts to iteration counts. */
> + profile_count new_header_count
> + = (in_count.apply_scale (new_est_niter + 1, 1));
> + basic_block *body = get_loop_body (loop);
> + scale_bbs_frequencies_profile_count (body, loop->num_nodes,
> + new_header_count,
> + old_header_count);
> + free (body);
> + }
> +
> + /* gimple_duplicate_loop_to_header_edge discarded FACTOR - 1
> + exit edges and adjusted the loop body's profile counts for the
> + new probabilities of the remaining non-exit edges. However,
> + the remaining exit edge still has the same probability as it
> + did before, even though it is now more likely.
> +
> + Therefore, all blocks executed after a failed exit test now have
> + a profile count that is too high, and the sum of the profile counts
> + for the header's incoming edges is greater than the profile count
> + of the header itself.
> +
> + Adjust the profile counts of all code in the loop body after
> + the exit test so that the sum of the counts on entry to the
> + header agree. */
> + profile_count old_latch_count = loop_latch_edge (loop)->count ();
> + profile_count new_latch_count = loop->header->count - in_count;
> + if (old_latch_count.nonzero_p () && new_latch_count.nonzero_p ())
> + scale_dominated_blocks_in_loop (loop, new_exit->src, new_latch_count,
> + old_latch_count);
> +
> + /* Set the probability of the exit edge based on NEW_EST_NITER
> + (which estimates latch counts rather than iteration counts).
> + Update the probabilities of other edges to match.
> +
> + If the profile counts are large enough to give the required
> + precision, the updates above will have made
> +
> + e->dest->count / e->src->count ~= new e->probability
> +
> + for every outgoing edge e of NEW_EXIT->src. */
> + profile_probability new_exit_prob = profile_probability::always ()
> + .apply_scale (1, new_est_niter + 1);
> + change_edge_frequency (new_exit, new_exit_prob);
> + }
>
> checking_verify_flow_info ();
> checking_verify_loop_structure ();
> @@ -1461,10 +1517,9 @@ tree_transform_and_unroll_loop (class loop *loop,
> unsigned factor,
>
> void
> tree_unroll_loop (class loop *loop, unsigned factor,
> - edge exit, class tree_niter_desc *desc)
> + class tree_niter_desc *desc)
> {
> - tree_transform_and_unroll_loop (loop, factor, exit, desc,
> - NULL, NULL);
> + tree_transform_and_unroll_loop (loop, factor, desc, NULL, NULL);
> }
>
> /* Rewrite the phi node at position PSI in function of the main
> diff --git a/gcc/testsuite/gcc.dg/pr102385.c b/gcc/testsuite/gcc.dg/pr102385.c
> new file mode 100644
> index 00000000000..1339540c722
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr102385.c
> @@ -0,0 +1,14 @@
> +/* { dg-options "-Wall -Wextra -O2 -fno-toplevel-reorder -fno-tree-ch
> -fno-tree-dce -fno-tree-dominator-opts -fno-tree-dse -fno-tree-loop-ivcanon
> -fpredictive-commoning" } */
> +
> +short a, b;
> +int c[9];
> +void(d)() {}
> +void e() {
> + a = 0;
> + for (; a <= 4; a++) {
> + short *f = &b;
> + c[a] || (*f = 0);
> + d(c[a + 2]);
> + }
> +}
> +int main() {return 0;}
