[Patch][RFC?] Re-guess probability when unswitch hoists a condition before the loop [PR126664]
Tobias Burnus <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
This is for https://gcc.gnu.org/PR126664 where an invariant condition in
a loop is estimated to have 0% and 100% edge probabilities. One can argue
about the 0% vs. 1000% in the loop, but, in any case, after hoisting the
condition, the probability is surely wrong as 41% and 59% are expected.
The 0% leads to count 0, which prevents vectorization; with vectorization,
the mentioned code in the PR runs, respectively, 9 or 40 times faster on
an AMD GPU with OpenMP and OpenACC offloading. (cf. PR)
* * *
For the question about the 100% and 0% see Richard's comment in the PR
in general and, additionally, his question whether the following is
a bug - fix by:
update_profile (epath, EDGE_SUCC (rd->dup_blocks[count], 0),
- path_out_count, path_out_count);
+ path_in_count, path_out_count);
* * *
Back to the attached patch:
The patch is based on the assumption that the probability can be
different when moved outside of the loop - and just re-guesses it
makes sense, which yields the expected 41% and 59% edge probabilities.
Is the patch OK – or at least like the right approach?
[At least for now, i.e. if it turned out that with other fixes,
it is no longer needed, then it could be still reverted.]
And: Any suggestion how to create a testcase for it?
I could package the testcase from the PR and check in the 'unswitch'
tree dump for the following:
if (l_params$hphb_187 < 0.0)
goto <bb 17>; [0.00%]
else
goto <bb 36>; [100.00%]
But not with 0% and 100% but with a probability between 10% and
90% for either edge. - Any better idea?
Tobias
unswitch.diff
(text/x-patch, 4.9 KB)
Re-guess probability when unswitch hoists a condition before the loop [PR126664] In the testcase in PR126664, the edge probabilities associated with the if condition were 0% and 100%. The condition was loop invariant and the 'unswitch' pass hoisted it before the loop and created two loop variants. However, the flow that lead to the 0% vs. 100% no longer holds after hoisting and the 0% lead to a 0 count that hampered vectorization and a severe performance penality. The solution taken in this commit is to re-guess the branch probability - which is now the expected 41% and 59%. gcc/ChangeLog: PR tree-optimization/126664 * cfgloopmanip.cc (lv_adjust_loop_entry_edge): If THEN_PROB or ELSE_PROB is uninitialized, get the probability by calling tree_guess_outgoing_edge_probabilities. (loop_version): If THEN_PROB or ELSE_PROB are uninitialized, scale by associated edge probability. * tree-ssa-loop-unswitch.cc (tree_unswitch_loop): Pass an uninitialized probability to loop_version. Co-authored-by: Arsen Arsenović <[email protected]> gcc/cfgloopmanip.cc | 36 +++++++++++++++++++++++++++++++----- gcc/tree-ssa-loop-unswitch.cc | 11 +++++------ 2 files changed, 36 insertions(+), 11 deletions(-) diff --git a/gcc/cfgloopmanip.cc b/gcc/cfgloopmanip.cc index f7551d5f30d..32ef907024f 100644 --- a/gcc/cfgloopmanip.cc +++ b/gcc/cfgloopmanip.cc @@ -1828,7 +1828,8 @@ force_single_succ_latches (void) THEN_PROB is the probability of then branch of the condition. ELSE_PROB is the probability of else branch. Note that they may be both REG_BR_PROB_BASE when condition is IFN_LOOP_VECTORIZED or - IFN_LOOP_DIST_ALIAS. */ + IFN_LOOP_DIST_ALIAS. If either probability is uninitialized, the + edge probabilities are guessed. */ static basic_block lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head, @@ -1852,8 +1853,20 @@ lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head, e = single_succ_edge (new_head); e1 = make_edge (new_head, first_head, current_ir_type () == IR_GIMPLE ? EDGE_TRUE_VALUE : 0); - e1->probability = then_prob; - e->probability = else_prob; + + if (!then_prob.initialized_p () || !else_prob.initialized_p ()) + { + edge e2; + edge_iterator ei; + FOR_EACH_EDGE (e2, ei, new_head->succs) + e2->probability = profile_probability::uninitialized (); + tree_guess_outgoing_edge_probabilities (new_head); + } + else + { + e1->probability = then_prob; + e->probability = else_prob; + } set_immediate_dominator (CDI_DOMINATORS, first_head, new_head); set_immediate_dominator (CDI_DOMINATORS, second_head, new_head); @@ -1880,6 +1893,9 @@ lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head, is the ratio by that the frequencies in the original loop should be scaled. ELSE_SCALE is the ratio by that the frequencies in the new loop should be scaled. + If THEN_PROB or ELSE_PROB are uninitialized, the edge probabilities + are guessed. If THEN_SCALE or ELSE_SCALE are uninitialized, the + scaling is based on the edge probability. If PLACE_AFTER is true, we place the new loop after LOOP in the instruction stream, otherwise it is placed before LOOP. */ @@ -1952,8 +1968,18 @@ loop_version (class loop *loop, add_bb_to_loop (cond_bb, outer); /* 4) Scale the original loop and new loop frequency. */ - scale_loop_frequencies (loop, then_scale); - scale_loop_frequencies (nloop, else_scale); + if (then_scale.initialized_p () && else_scale.initialized_p ()) + { + scale_loop_frequencies (loop, then_scale); + scale_loop_frequencies (nloop, else_scale); + } + else + { + edge te = EDGE_SUCC (cond_bb, 0); + edge ee = EDGE_SUCC (cond_bb, 1); + scale_loop_frequencies (loop, te->probability); + scale_loop_frequencies (nloop, ee->probability); + } update_dominators_in_loop (loop); update_dominators_in_loop (nloop); diff --git a/gcc/tree-ssa-loop-unswitch.cc b/gcc/tree-ssa-loop-unswitch.cc index a34c5385c7c..5dab8328f7c 100644 --- a/gcc/tree-ssa-loop-unswitch.cc +++ b/gcc/tree-ssa-loop-unswitch.cc @@ -1094,12 +1094,11 @@ tree_unswitch_loop (class loop *loop, edge edge_true, tree cond) gcc_assert (flow_bb_inside_loop_p (loop, edge_true->src)); gcc_assert (EDGE_COUNT (edge_true->src->succs) >= 2); - profile_probability prob_true = edge_true->probability; - return loop_version (loop, unshare_expr (cond), - NULL, prob_true, - prob_true.invert (), - prob_true, prob_true.invert (), - false); + /* Let loop_version re-guess the probability of the condition as hoisting + might have changed the probability. */ + profile_probability prob_uninit = profile_probability::uninitialized (); + return loop_version (loop, unshare_expr (cond), NULL, prob_uninit, + prob_uninit, prob_uninit, prob_uninit, false); } /* Unswitch outer loops by hoisting invariant guard on