Message ID | 596c4483-864c-1d03-955c-69906171f037@suse.cz |
---|---|
State | New |
Headers | show |
Series | Improve profile handling in switch lowering. | expand |
PING^1 On 1/26/22 12:11, Martin Liška wrote: > Hello. > > Right now, switch lowering does not update basic_block::count values > so that they are uninitiliazed. Moreover, I've updated probability scaling > when a more complex expansion happens. There are still some situations where > the profile is a bit imprecise, but the patch improves rapidly the current situation. > > Patch can bootstrap on x86_64-linux-gnu and survives regression tests. > > Ready to be installed? > Thanks, > Martin > > PR tree-optimization/101301 > PR tree-optimization/103680 > > gcc/ChangeLog: > > * tree-switch-conversion.cc (bit_test_cluster::emit): > Handle correctly remaining probability. > (switch_decision_tree::try_switch_expansion): Fix BB's count > where a cluster expansion happens. > (switch_decision_tree::emit_cmp_and_jump_insns): Fill up also > BB count. > (switch_decision_tree::do_jump_if_equal): Likewise. > (switch_decision_tree::emit_case_nodes): Handle special case > for BT expansion which can also fallback to a default BB. > * tree-switch-conversion.h (cluster::cluster): Add > m_default_prob probability. > --- > gcc/tree-switch-conversion.cc | 51 ++++++++++++++++++++++++----------- > gcc/tree-switch-conversion.h | 8 +++++- > 2 files changed, 43 insertions(+), 16 deletions(-) > > diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc > index 670397c87e4..d6679e8dee3 100644 > --- a/gcc/tree-switch-conversion.cc > +++ b/gcc/tree-switch-conversion.cc > @@ -1538,10 +1538,12 @@ bit_test_cluster::emit (tree index_expr, tree index_type, > test[k].target_bb = n->m_case_bb; > test[k].label = n->m_case_label_expr; > test[k].bits = 0; > + test[k].prob = profile_probability::never (); > count++; > } > > test[k].bits += n->get_range (n->get_low (), n->get_high ()); > + test[k].prob += n->m_prob; > > lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval)); > if (n->get_high () == NULL_TREE) > @@ -1629,6 +1631,11 @@ bit_test_cluster::emit (tree index_expr, tree index_type, > /*simple=*/true, NULL_TREE, > /*before=*/true, GSI_SAME_STMT); > > + profile_probability subtree_prob = m_subtree_prob; > + profile_probability default_prob = m_default_prob; > + if (!default_prob.initialized_p ()) > + default_prob = m_subtree_prob.invert (); > + > if (m_handles_entire_switch && entry_test_needed) > { > tree range = int_const_binop (MINUS_EXPR, maxval, minval); > @@ -1639,9 +1646,10 @@ bit_test_cluster::emit (tree index_expr, tree index_type, > /*simple=*/true, NULL_TREE, > /*before=*/true, GSI_SAME_STMT); > tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); > + default_prob = default_prob.apply_scale (1, 2); > basic_block new_bb > = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb, > - profile_probability::unlikely ()); > + default_prob); > gsi = gsi_last_bb (new_bb); > } > > @@ -1662,14 +1670,12 @@ bit_test_cluster::emit (tree index_expr, tree index_type, > else > csui = tmp; > > - profile_probability prob = profile_probability::always (); > - > /* for each unique set of cases: > if (const & csui) goto target */ > for (k = 0; k < count; k++) > { > - prob = profile_probability::always ().apply_scale (test[k].bits, > - bt_range); > + profile_probability prob = test[k].prob / (subtree_prob + default_prob); > + subtree_prob -= test[k].prob; > bt_range -= test[k].bits; > tmp = wide_int_to_tree (word_type_node, test[k].mask); > tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); > @@ -1908,9 +1914,13 @@ switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters) > /* Emit cluster-specific switch handling. */ > for (unsigned i = 0; i < clusters.length (); i++) > if (clusters[i]->get_type () != SIMPLE_CASE) > - clusters[i]->emit (index_expr, index_type, > - gimple_switch_default_label (m_switch), > - m_default_bb, gimple_location (m_switch)); > + { > + edge e = single_pred_edge (clusters[i]->m_case_bb); > + e->dest->count = e->src->count.apply_probability (e->probability); > + clusters[i]->emit (index_expr, index_type, > + gimple_switch_default_label (m_switch), > + m_default_bb, gimple_location (m_switch)); > + } > } > > fix_phi_operands_for_edges (); > @@ -2162,6 +2172,7 @@ switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0, > edge false_edge = split_block (bb, cond); > false_edge->flags = EDGE_FALSE_VALUE; > false_edge->probability = prob.invert (); > + false_edge->dest->count = bb->count.apply_probability (prob.invert ()); > > edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); > true_edge->probability = prob; > @@ -2192,6 +2203,7 @@ switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1, > edge false_edge = split_block (bb, cond); > false_edge->flags = EDGE_FALSE_VALUE; > false_edge->probability = prob.invert (); > + false_edge->dest->count = bb->count.apply_probability (prob.invert ()); > > edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); > true_edge->probability = prob; > @@ -2227,7 +2239,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, > node->m_c->m_case_bb, p, loc); > /* Since this case is taken at this point, reduce its weight from > subtree_weight. */ > - node->m_c->m_subtree_prob -= p; > + node->m_c->m_subtree_prob -= node->m_c->m_prob; > > if (node->m_left != NULL && node->m_right != NULL) > { > @@ -2246,6 +2258,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, > / (node->m_c->m_subtree_prob + default_prob)); > bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (), > node->m_right->m_c->m_case_bb, p, loc); > + node->m_c->m_subtree_prob -= node->m_right->m_c->m_prob; > > p = (node->m_left->m_c->m_prob > / (node->m_c->m_subtree_prob + default_prob)); > @@ -2262,6 +2275,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, > p = ((node->m_right->m_c->m_subtree_prob > + default_prob.apply_scale (1, 2)) > / (node->m_c->m_subtree_prob + default_prob)); > + test_bb->count = bb->count.apply_probability (p); > bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), > GT_EXPR, test_bb, p, loc); > default_prob = default_prob.apply_scale (1, 2); > @@ -2348,21 +2362,28 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, > is the one to branch to. */ > if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE) > { > + bool is_bt = node->m_c->get_type () == BIT_TEST; > + int parts = is_bt ? 3 : 2; > + > /* Branch to a label where we will handle it later. */ > basic_block test_bb = split_edge (single_succ_edge (bb)); > redirect_edge_succ (single_pred_edge (test_bb), > single_succ_edge (bb)->dest); > > - > - profile_probability right_prob = profile_probability::never (); > - if (node->m_right) > - right_prob = node->m_right->m_c->m_subtree_prob; > - p = ((right_prob + default_prob.apply_scale (1, 2)) > + profile_probability right_prob = profile_probability::never (); > + if (node->m_right) > + right_prob = node->m_right->m_c->m_subtree_prob; > + p = ((right_prob + default_prob.apply_scale (1, parts)) > / (node->m_c->m_subtree_prob + default_prob)); > + test_bb->count = bb->count.apply_probability (p); > > bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), > GT_EXPR, test_bb, p, loc); > - default_prob = default_prob.apply_scale (1, 2); > + > + default_prob = default_prob.apply_scale (1, parts); > + node->m_c->m_subtree_prob -= right_prob; > + if (is_bt) > + node->m_c->m_default_prob = default_prob; > > /* Value belongs to this node or to the left-hand subtree. */ > p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob); > diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h > index e969c051a05..5f3f99353ba 100644 > --- a/gcc/tree-switch-conversion.h > +++ b/gcc/tree-switch-conversion.h > @@ -102,6 +102,10 @@ public: > /* Probability of reaching subtree rooted at this node. */ > profile_probability m_subtree_prob; > > + /* Probability of default case when reaching the node. > + It is used by bit-test right now. */ > + profile_probability m_default_prob; > + > protected: > /* Default constructor. */ > cluster () {} > @@ -110,7 +114,8 @@ protected: > cluster::cluster (tree case_label_expr, basic_block case_bb, > profile_probability prob, profile_probability subtree_prob): > m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob), > - m_subtree_prob (subtree_prob) > + m_subtree_prob (subtree_prob), > + m_default_prob (profile_probability::uninitialized ()) > { > } > > @@ -542,6 +547,7 @@ public: > basic_block target_bb; > tree label; > int bits; > + profile_probability prob; > > /* Comparison function for qsort to order bit tests by decreasing > probability of execution. */
PING^2 On 3/4/22 14:47, Martin Liška wrote: > PING^1 > > On 1/26/22 12:11, Martin Liška wrote: >> Hello. >> >> Right now, switch lowering does not update basic_block::count values >> so that they are uninitiliazed. Moreover, I've updated probability scaling >> when a more complex expansion happens. There are still some situations where >> the profile is a bit imprecise, but the patch improves rapidly the current situation. >> >> Patch can bootstrap on x86_64-linux-gnu and survives regression tests. >> >> Ready to be installed? >> Thanks, >> Martin >> >> PR tree-optimization/101301 >> PR tree-optimization/103680 >> >> gcc/ChangeLog: >> >> * tree-switch-conversion.cc (bit_test_cluster::emit): >> Handle correctly remaining probability. >> (switch_decision_tree::try_switch_expansion): Fix BB's count >> where a cluster expansion happens. >> (switch_decision_tree::emit_cmp_and_jump_insns): Fill up also >> BB count. >> (switch_decision_tree::do_jump_if_equal): Likewise. >> (switch_decision_tree::emit_case_nodes): Handle special case >> for BT expansion which can also fallback to a default BB. >> * tree-switch-conversion.h (cluster::cluster): Add >> m_default_prob probability. >> --- >> gcc/tree-switch-conversion.cc | 51 ++++++++++++++++++++++++----------- >> gcc/tree-switch-conversion.h | 8 +++++- >> 2 files changed, 43 insertions(+), 16 deletions(-) >> >> diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc >> index 670397c87e4..d6679e8dee3 100644 >> --- a/gcc/tree-switch-conversion.cc >> +++ b/gcc/tree-switch-conversion.cc >> @@ -1538,10 +1538,12 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >> test[k].target_bb = n->m_case_bb; >> test[k].label = n->m_case_label_expr; >> test[k].bits = 0; >> + test[k].prob = profile_probability::never (); >> count++; >> } >> >> test[k].bits += n->get_range (n->get_low (), n->get_high ()); >> + test[k].prob += n->m_prob; >> >> lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval)); >> if (n->get_high () == NULL_TREE) >> @@ -1629,6 +1631,11 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >> /*simple=*/true, NULL_TREE, >> /*before=*/true, GSI_SAME_STMT); >> >> + profile_probability subtree_prob = m_subtree_prob; >> + profile_probability default_prob = m_default_prob; >> + if (!default_prob.initialized_p ()) >> + default_prob = m_subtree_prob.invert (); >> + >> if (m_handles_entire_switch && entry_test_needed) >> { >> tree range = int_const_binop (MINUS_EXPR, maxval, minval); >> @@ -1639,9 +1646,10 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >> /*simple=*/true, NULL_TREE, >> /*before=*/true, GSI_SAME_STMT); >> tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); >> + default_prob = default_prob.apply_scale (1, 2); >> basic_block new_bb >> = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb, >> - profile_probability::unlikely ()); >> + default_prob); >> gsi = gsi_last_bb (new_bb); >> } >> >> @@ -1662,14 +1670,12 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >> else >> csui = tmp; >> >> - profile_probability prob = profile_probability::always (); >> - >> /* for each unique set of cases: >> if (const & csui) goto target */ >> for (k = 0; k < count; k++) >> { >> - prob = profile_probability::always ().apply_scale (test[k].bits, >> - bt_range); >> + profile_probability prob = test[k].prob / (subtree_prob + default_prob); >> + subtree_prob -= test[k].prob; >> bt_range -= test[k].bits; >> tmp = wide_int_to_tree (word_type_node, test[k].mask); >> tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); >> @@ -1908,9 +1914,13 @@ switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters) >> /* Emit cluster-specific switch handling. */ >> for (unsigned i = 0; i < clusters.length (); i++) >> if (clusters[i]->get_type () != SIMPLE_CASE) >> - clusters[i]->emit (index_expr, index_type, >> - gimple_switch_default_label (m_switch), >> - m_default_bb, gimple_location (m_switch)); >> + { >> + edge e = single_pred_edge (clusters[i]->m_case_bb); >> + e->dest->count = e->src->count.apply_probability (e->probability); >> + clusters[i]->emit (index_expr, index_type, >> + gimple_switch_default_label (m_switch), >> + m_default_bb, gimple_location (m_switch)); >> + } >> } >> >> fix_phi_operands_for_edges (); >> @@ -2162,6 +2172,7 @@ switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0, >> edge false_edge = split_block (bb, cond); >> false_edge->flags = EDGE_FALSE_VALUE; >> false_edge->probability = prob.invert (); >> + false_edge->dest->count = bb->count.apply_probability (prob.invert ()); >> >> edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); >> true_edge->probability = prob; >> @@ -2192,6 +2203,7 @@ switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1, >> edge false_edge = split_block (bb, cond); >> false_edge->flags = EDGE_FALSE_VALUE; >> false_edge->probability = prob.invert (); >> + false_edge->dest->count = bb->count.apply_probability (prob.invert ()); >> >> edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); >> true_edge->probability = prob; >> @@ -2227,7 +2239,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >> node->m_c->m_case_bb, p, loc); >> /* Since this case is taken at this point, reduce its weight from >> subtree_weight. */ >> - node->m_c->m_subtree_prob -= p; >> + node->m_c->m_subtree_prob -= node->m_c->m_prob; >> >> if (node->m_left != NULL && node->m_right != NULL) >> { >> @@ -2246,6 +2258,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >> / (node->m_c->m_subtree_prob + default_prob)); >> bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (), >> node->m_right->m_c->m_case_bb, p, loc); >> + node->m_c->m_subtree_prob -= node->m_right->m_c->m_prob; >> >> p = (node->m_left->m_c->m_prob >> / (node->m_c->m_subtree_prob + default_prob)); >> @@ -2262,6 +2275,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >> p = ((node->m_right->m_c->m_subtree_prob >> + default_prob.apply_scale (1, 2)) >> / (node->m_c->m_subtree_prob + default_prob)); >> + test_bb->count = bb->count.apply_probability (p); >> bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), >> GT_EXPR, test_bb, p, loc); >> default_prob = default_prob.apply_scale (1, 2); >> @@ -2348,21 +2362,28 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >> is the one to branch to. */ >> if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE) >> { >> + bool is_bt = node->m_c->get_type () == BIT_TEST; >> + int parts = is_bt ? 3 : 2; >> + >> /* Branch to a label where we will handle it later. */ >> basic_block test_bb = split_edge (single_succ_edge (bb)); >> redirect_edge_succ (single_pred_edge (test_bb), >> single_succ_edge (bb)->dest); >> >> - >> - profile_probability right_prob = profile_probability::never (); >> - if (node->m_right) >> - right_prob = node->m_right->m_c->m_subtree_prob; >> - p = ((right_prob + default_prob.apply_scale (1, 2)) >> + profile_probability right_prob = profile_probability::never (); >> + if (node->m_right) >> + right_prob = node->m_right->m_c->m_subtree_prob; >> + p = ((right_prob + default_prob.apply_scale (1, parts)) >> / (node->m_c->m_subtree_prob + default_prob)); >> + test_bb->count = bb->count.apply_probability (p); >> >> bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), >> GT_EXPR, test_bb, p, loc); >> - default_prob = default_prob.apply_scale (1, 2); >> + >> + default_prob = default_prob.apply_scale (1, parts); >> + node->m_c->m_subtree_prob -= right_prob; >> + if (is_bt) >> + node->m_c->m_default_prob = default_prob; >> >> /* Value belongs to this node or to the left-hand subtree. */ >> p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob); >> diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h >> index e969c051a05..5f3f99353ba 100644 >> --- a/gcc/tree-switch-conversion.h >> +++ b/gcc/tree-switch-conversion.h >> @@ -102,6 +102,10 @@ public: >> /* Probability of reaching subtree rooted at this node. */ >> profile_probability m_subtree_prob; >> >> + /* Probability of default case when reaching the node. >> + It is used by bit-test right now. */ >> + profile_probability m_default_prob; >> + >> protected: >> /* Default constructor. */ >> cluster () {} >> @@ -110,7 +114,8 @@ protected: >> cluster::cluster (tree case_label_expr, basic_block case_bb, >> profile_probability prob, profile_probability subtree_prob): >> m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob), >> - m_subtree_prob (subtree_prob) >> + m_subtree_prob (subtree_prob), >> + m_default_prob (profile_probability::uninitialized ()) >> { >> } >> >> @@ -542,6 +547,7 @@ public: >> basic_block target_bb; >> tree label; >> int bits; >> + profile_probability prob; >> >> /* Comparison function for qsort to order bit tests by decreasing >> probability of execution. */ >
PING^3 On 3/24/22 11:22, Martin Liška wrote: > PING^2 > > On 3/4/22 14:47, Martin Liška wrote: >> PING^1 >> >> On 1/26/22 12:11, Martin Liška wrote: >>> Hello. >>> >>> Right now, switch lowering does not update basic_block::count values >>> so that they are uninitiliazed. Moreover, I've updated probability scaling >>> when a more complex expansion happens. There are still some situations where >>> the profile is a bit imprecise, but the patch improves rapidly the current situation. >>> >>> Patch can bootstrap on x86_64-linux-gnu and survives regression tests. >>> >>> Ready to be installed? >>> Thanks, >>> Martin >>> >>> PR tree-optimization/101301 >>> PR tree-optimization/103680 >>> >>> gcc/ChangeLog: >>> >>> * tree-switch-conversion.cc (bit_test_cluster::emit): >>> Handle correctly remaining probability. >>> (switch_decision_tree::try_switch_expansion): Fix BB's count >>> where a cluster expansion happens. >>> (switch_decision_tree::emit_cmp_and_jump_insns): Fill up also >>> BB count. >>> (switch_decision_tree::do_jump_if_equal): Likewise. >>> (switch_decision_tree::emit_case_nodes): Handle special case >>> for BT expansion which can also fallback to a default BB. >>> * tree-switch-conversion.h (cluster::cluster): Add >>> m_default_prob probability. >>> --- >>> gcc/tree-switch-conversion.cc | 51 ++++++++++++++++++++++++----------- >>> gcc/tree-switch-conversion.h | 8 +++++- >>> 2 files changed, 43 insertions(+), 16 deletions(-) >>> >>> diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc >>> index 670397c87e4..d6679e8dee3 100644 >>> --- a/gcc/tree-switch-conversion.cc >>> +++ b/gcc/tree-switch-conversion.cc >>> @@ -1538,10 +1538,12 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >>> test[k].target_bb = n->m_case_bb; >>> test[k].label = n->m_case_label_expr; >>> test[k].bits = 0; >>> + test[k].prob = profile_probability::never (); >>> count++; >>> } >>> >>> test[k].bits += n->get_range (n->get_low (), n->get_high ()); >>> + test[k].prob += n->m_prob; >>> >>> lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval)); >>> if (n->get_high () == NULL_TREE) >>> @@ -1629,6 +1631,11 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >>> /*simple=*/true, NULL_TREE, >>> /*before=*/true, GSI_SAME_STMT); >>> >>> + profile_probability subtree_prob = m_subtree_prob; >>> + profile_probability default_prob = m_default_prob; >>> + if (!default_prob.initialized_p ()) >>> + default_prob = m_subtree_prob.invert (); >>> + >>> if (m_handles_entire_switch && entry_test_needed) >>> { >>> tree range = int_const_binop (MINUS_EXPR, maxval, minval); >>> @@ -1639,9 +1646,10 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >>> /*simple=*/true, NULL_TREE, >>> /*before=*/true, GSI_SAME_STMT); >>> tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); >>> + default_prob = default_prob.apply_scale (1, 2); >>> basic_block new_bb >>> = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb, >>> - profile_probability::unlikely ()); >>> + default_prob); >>> gsi = gsi_last_bb (new_bb); >>> } >>> >>> @@ -1662,14 +1670,12 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >>> else >>> csui = tmp; >>> >>> - profile_probability prob = profile_probability::always (); >>> - >>> /* for each unique set of cases: >>> if (const & csui) goto target */ >>> for (k = 0; k < count; k++) >>> { >>> - prob = profile_probability::always ().apply_scale (test[k].bits, >>> - bt_range); >>> + profile_probability prob = test[k].prob / (subtree_prob + default_prob); >>> + subtree_prob -= test[k].prob; >>> bt_range -= test[k].bits; >>> tmp = wide_int_to_tree (word_type_node, test[k].mask); >>> tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); >>> @@ -1908,9 +1914,13 @@ switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters) >>> /* Emit cluster-specific switch handling. */ >>> for (unsigned i = 0; i < clusters.length (); i++) >>> if (clusters[i]->get_type () != SIMPLE_CASE) >>> - clusters[i]->emit (index_expr, index_type, >>> - gimple_switch_default_label (m_switch), >>> - m_default_bb, gimple_location (m_switch)); >>> + { >>> + edge e = single_pred_edge (clusters[i]->m_case_bb); >>> + e->dest->count = e->src->count.apply_probability (e->probability); >>> + clusters[i]->emit (index_expr, index_type, >>> + gimple_switch_default_label (m_switch), >>> + m_default_bb, gimple_location (m_switch)); >>> + } >>> } >>> >>> fix_phi_operands_for_edges (); >>> @@ -2162,6 +2172,7 @@ switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0, >>> edge false_edge = split_block (bb, cond); >>> false_edge->flags = EDGE_FALSE_VALUE; >>> false_edge->probability = prob.invert (); >>> + false_edge->dest->count = bb->count.apply_probability (prob.invert ()); >>> >>> edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); >>> true_edge->probability = prob; >>> @@ -2192,6 +2203,7 @@ switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1, >>> edge false_edge = split_block (bb, cond); >>> false_edge->flags = EDGE_FALSE_VALUE; >>> false_edge->probability = prob.invert (); >>> + false_edge->dest->count = bb->count.apply_probability (prob.invert ()); >>> >>> edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); >>> true_edge->probability = prob; >>> @@ -2227,7 +2239,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >>> node->m_c->m_case_bb, p, loc); >>> /* Since this case is taken at this point, reduce its weight from >>> subtree_weight. */ >>> - node->m_c->m_subtree_prob -= p; >>> + node->m_c->m_subtree_prob -= node->m_c->m_prob; >>> >>> if (node->m_left != NULL && node->m_right != NULL) >>> { >>> @@ -2246,6 +2258,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >>> / (node->m_c->m_subtree_prob + default_prob)); >>> bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (), >>> node->m_right->m_c->m_case_bb, p, loc); >>> + node->m_c->m_subtree_prob -= node->m_right->m_c->m_prob; >>> >>> p = (node->m_left->m_c->m_prob >>> / (node->m_c->m_subtree_prob + default_prob)); >>> @@ -2262,6 +2275,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >>> p = ((node->m_right->m_c->m_subtree_prob >>> + default_prob.apply_scale (1, 2)) >>> / (node->m_c->m_subtree_prob + default_prob)); >>> + test_bb->count = bb->count.apply_probability (p); >>> bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), >>> GT_EXPR, test_bb, p, loc); >>> default_prob = default_prob.apply_scale (1, 2); >>> @@ -2348,21 +2362,28 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >>> is the one to branch to. */ >>> if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE) >>> { >>> + bool is_bt = node->m_c->get_type () == BIT_TEST; >>> + int parts = is_bt ? 3 : 2; >>> + >>> /* Branch to a label where we will handle it later. */ >>> basic_block test_bb = split_edge (single_succ_edge (bb)); >>> redirect_edge_succ (single_pred_edge (test_bb), >>> single_succ_edge (bb)->dest); >>> >>> - >>> - profile_probability right_prob = profile_probability::never (); >>> - if (node->m_right) >>> - right_prob = node->m_right->m_c->m_subtree_prob; >>> - p = ((right_prob + default_prob.apply_scale (1, 2)) >>> + profile_probability right_prob = profile_probability::never (); >>> + if (node->m_right) >>> + right_prob = node->m_right->m_c->m_subtree_prob; >>> + p = ((right_prob + default_prob.apply_scale (1, parts)) >>> / (node->m_c->m_subtree_prob + default_prob)); >>> + test_bb->count = bb->count.apply_probability (p); >>> >>> bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), >>> GT_EXPR, test_bb, p, loc); >>> - default_prob = default_prob.apply_scale (1, 2); >>> + >>> + default_prob = default_prob.apply_scale (1, parts); >>> + node->m_c->m_subtree_prob -= right_prob; >>> + if (is_bt) >>> + node->m_c->m_default_prob = default_prob; >>> >>> /* Value belongs to this node or to the left-hand subtree. */ >>> p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob); >>> diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h >>> index e969c051a05..5f3f99353ba 100644 >>> --- a/gcc/tree-switch-conversion.h >>> +++ b/gcc/tree-switch-conversion.h >>> @@ -102,6 +102,10 @@ public: >>> /* Probability of reaching subtree rooted at this node. */ >>> profile_probability m_subtree_prob; >>> >>> + /* Probability of default case when reaching the node. >>> + It is used by bit-test right now. */ >>> + profile_probability m_default_prob; >>> + >>> protected: >>> /* Default constructor. */ >>> cluster () {} >>> @@ -110,7 +114,8 @@ protected: >>> cluster::cluster (tree case_label_expr, basic_block case_bb, >>> profile_probability prob, profile_probability subtree_prob): >>> m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob), >>> - m_subtree_prob (subtree_prob) >>> + m_subtree_prob (subtree_prob), >>> + m_default_prob (profile_probability::uninitialized ()) >>> { >>> } >>> >>> @@ -542,6 +547,7 @@ public: >>> basic_block target_bb; >>> tree label; >>> int bits; >>> + profile_probability prob; >>> >>> /* Comparison function for qsort to order bit tests by decreasing >>> probability of execution. */ >> >
PING^4 On 4/7/22 16:00, Martin Liška wrote: > PING^3 > > On 3/24/22 11:22, Martin Liška wrote: >> PING^2 >> >> On 3/4/22 14:47, Martin Liška wrote: >>> PING^1 >>> >>> On 1/26/22 12:11, Martin Liška wrote: >>>> Hello. >>>> >>>> Right now, switch lowering does not update basic_block::count values >>>> so that they are uninitiliazed. Moreover, I've updated probability scaling >>>> when a more complex expansion happens. There are still some situations where >>>> the profile is a bit imprecise, but the patch improves rapidly the current situation. >>>> >>>> Patch can bootstrap on x86_64-linux-gnu and survives regression tests. >>>> >>>> Ready to be installed? >>>> Thanks, >>>> Martin >>>> >>>> PR tree-optimization/101301 >>>> PR tree-optimization/103680 >>>> >>>> gcc/ChangeLog: >>>> >>>> * tree-switch-conversion.cc (bit_test_cluster::emit): >>>> Handle correctly remaining probability. >>>> (switch_decision_tree::try_switch_expansion): Fix BB's count >>>> where a cluster expansion happens. >>>> (switch_decision_tree::emit_cmp_and_jump_insns): Fill up also >>>> BB count. >>>> (switch_decision_tree::do_jump_if_equal): Likewise. >>>> (switch_decision_tree::emit_case_nodes): Handle special case >>>> for BT expansion which can also fallback to a default BB. >>>> * tree-switch-conversion.h (cluster::cluster): Add >>>> m_default_prob probability. >>>> --- >>>> gcc/tree-switch-conversion.cc | 51 ++++++++++++++++++++++++----------- >>>> gcc/tree-switch-conversion.h | 8 +++++- >>>> 2 files changed, 43 insertions(+), 16 deletions(-) >>>> >>>> diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc >>>> index 670397c87e4..d6679e8dee3 100644 >>>> --- a/gcc/tree-switch-conversion.cc >>>> +++ b/gcc/tree-switch-conversion.cc >>>> @@ -1538,10 +1538,12 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >>>> test[k].target_bb = n->m_case_bb; >>>> test[k].label = n->m_case_label_expr; >>>> test[k].bits = 0; >>>> + test[k].prob = profile_probability::never (); >>>> count++; >>>> } >>>> >>>> test[k].bits += n->get_range (n->get_low (), n->get_high ()); >>>> + test[k].prob += n->m_prob; >>>> >>>> lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval)); >>>> if (n->get_high () == NULL_TREE) >>>> @@ -1629,6 +1631,11 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >>>> /*simple=*/true, NULL_TREE, >>>> /*before=*/true, GSI_SAME_STMT); >>>> >>>> + profile_probability subtree_prob = m_subtree_prob; >>>> + profile_probability default_prob = m_default_prob; >>>> + if (!default_prob.initialized_p ()) >>>> + default_prob = m_subtree_prob.invert (); >>>> + >>>> if (m_handles_entire_switch && entry_test_needed) >>>> { >>>> tree range = int_const_binop (MINUS_EXPR, maxval, minval); >>>> @@ -1639,9 +1646,10 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >>>> /*simple=*/true, NULL_TREE, >>>> /*before=*/true, GSI_SAME_STMT); >>>> tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); >>>> + default_prob = default_prob.apply_scale (1, 2); >>>> basic_block new_bb >>>> = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb, >>>> - profile_probability::unlikely ()); >>>> + default_prob); >>>> gsi = gsi_last_bb (new_bb); >>>> } >>>> >>>> @@ -1662,14 +1670,12 @@ bit_test_cluster::emit (tree index_expr, tree index_type, >>>> else >>>> csui = tmp; >>>> >>>> - profile_probability prob = profile_probability::always (); >>>> - >>>> /* for each unique set of cases: >>>> if (const & csui) goto target */ >>>> for (k = 0; k < count; k++) >>>> { >>>> - prob = profile_probability::always ().apply_scale (test[k].bits, >>>> - bt_range); >>>> + profile_probability prob = test[k].prob / (subtree_prob + default_prob); >>>> + subtree_prob -= test[k].prob; >>>> bt_range -= test[k].bits; >>>> tmp = wide_int_to_tree (word_type_node, test[k].mask); >>>> tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); >>>> @@ -1908,9 +1914,13 @@ switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters) >>>> /* Emit cluster-specific switch handling. */ >>>> for (unsigned i = 0; i < clusters.length (); i++) >>>> if (clusters[i]->get_type () != SIMPLE_CASE) >>>> - clusters[i]->emit (index_expr, index_type, >>>> - gimple_switch_default_label (m_switch), >>>> - m_default_bb, gimple_location (m_switch)); >>>> + { >>>> + edge e = single_pred_edge (clusters[i]->m_case_bb); >>>> + e->dest->count = e->src->count.apply_probability (e->probability); >>>> + clusters[i]->emit (index_expr, index_type, >>>> + gimple_switch_default_label (m_switch), >>>> + m_default_bb, gimple_location (m_switch)); >>>> + } >>>> } >>>> >>>> fix_phi_operands_for_edges (); >>>> @@ -2162,6 +2172,7 @@ switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0, >>>> edge false_edge = split_block (bb, cond); >>>> false_edge->flags = EDGE_FALSE_VALUE; >>>> false_edge->probability = prob.invert (); >>>> + false_edge->dest->count = bb->count.apply_probability (prob.invert ()); >>>> >>>> edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); >>>> true_edge->probability = prob; >>>> @@ -2192,6 +2203,7 @@ switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1, >>>> edge false_edge = split_block (bb, cond); >>>> false_edge->flags = EDGE_FALSE_VALUE; >>>> false_edge->probability = prob.invert (); >>>> + false_edge->dest->count = bb->count.apply_probability (prob.invert ()); >>>> >>>> edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); >>>> true_edge->probability = prob; >>>> @@ -2227,7 +2239,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >>>> node->m_c->m_case_bb, p, loc); >>>> /* Since this case is taken at this point, reduce its weight from >>>> subtree_weight. */ >>>> - node->m_c->m_subtree_prob -= p; >>>> + node->m_c->m_subtree_prob -= node->m_c->m_prob; >>>> >>>> if (node->m_left != NULL && node->m_right != NULL) >>>> { >>>> @@ -2246,6 +2258,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >>>> / (node->m_c->m_subtree_prob + default_prob)); >>>> bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (), >>>> node->m_right->m_c->m_case_bb, p, loc); >>>> + node->m_c->m_subtree_prob -= node->m_right->m_c->m_prob; >>>> >>>> p = (node->m_left->m_c->m_prob >>>> / (node->m_c->m_subtree_prob + default_prob)); >>>> @@ -2262,6 +2275,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >>>> p = ((node->m_right->m_c->m_subtree_prob >>>> + default_prob.apply_scale (1, 2)) >>>> / (node->m_c->m_subtree_prob + default_prob)); >>>> + test_bb->count = bb->count.apply_probability (p); >>>> bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), >>>> GT_EXPR, test_bb, p, loc); >>>> default_prob = default_prob.apply_scale (1, 2); >>>> @@ -2348,21 +2362,28 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, >>>> is the one to branch to. */ >>>> if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE) >>>> { >>>> + bool is_bt = node->m_c->get_type () == BIT_TEST; >>>> + int parts = is_bt ? 3 : 2; >>>> + >>>> /* Branch to a label where we will handle it later. */ >>>> basic_block test_bb = split_edge (single_succ_edge (bb)); >>>> redirect_edge_succ (single_pred_edge (test_bb), >>>> single_succ_edge (bb)->dest); >>>> >>>> - >>>> - profile_probability right_prob = profile_probability::never (); >>>> - if (node->m_right) >>>> - right_prob = node->m_right->m_c->m_subtree_prob; >>>> - p = ((right_prob + default_prob.apply_scale (1, 2)) >>>> + profile_probability right_prob = profile_probability::never (); >>>> + if (node->m_right) >>>> + right_prob = node->m_right->m_c->m_subtree_prob; >>>> + p = ((right_prob + default_prob.apply_scale (1, parts)) >>>> / (node->m_c->m_subtree_prob + default_prob)); >>>> + test_bb->count = bb->count.apply_probability (p); >>>> >>>> bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), >>>> GT_EXPR, test_bb, p, loc); >>>> - default_prob = default_prob.apply_scale (1, 2); >>>> + >>>> + default_prob = default_prob.apply_scale (1, parts); >>>> + node->m_c->m_subtree_prob -= right_prob; >>>> + if (is_bt) >>>> + node->m_c->m_default_prob = default_prob; >>>> >>>> /* Value belongs to this node or to the left-hand subtree. */ >>>> p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob); >>>> diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h >>>> index e969c051a05..5f3f99353ba 100644 >>>> --- a/gcc/tree-switch-conversion.h >>>> +++ b/gcc/tree-switch-conversion.h >>>> @@ -102,6 +102,10 @@ public: >>>> /* Probability of reaching subtree rooted at this node. */ >>>> profile_probability m_subtree_prob; >>>> >>>> + /* Probability of default case when reaching the node. >>>> + It is used by bit-test right now. */ >>>> + profile_probability m_default_prob; >>>> + >>>> protected: >>>> /* Default constructor. */ >>>> cluster () {} >>>> @@ -110,7 +114,8 @@ protected: >>>> cluster::cluster (tree case_label_expr, basic_block case_bb, >>>> profile_probability prob, profile_probability subtree_prob): >>>> m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob), >>>> - m_subtree_prob (subtree_prob) >>>> + m_subtree_prob (subtree_prob), >>>> + m_default_prob (profile_probability::uninitialized ()) >>>> { >>>> } >>>> >>>> @@ -542,6 +547,7 @@ public: >>>> basic_block target_bb; >>>> tree label; >>>> int bits; >>>> + profile_probability prob; >>>> >>>> /* Comparison function for qsort to order bit tests by decreasing >>>> probability of execution. */ >>> >> >
On 1/26/22 04:11, Martin Liška wrote: > Hello. > > Right now, switch lowering does not update basic_block::count values > so that they are uninitiliazed. Moreover, I've updated probability scaling > when a more complex expansion happens. There are still some situations > where > the profile is a bit imprecise, but the patch improves rapidly the > current situation. > > Patch can bootstrap on x86_64-linux-gnu and survives regression tests. > > Ready to be installed? > Thanks, > Martin > > PR tree-optimization/101301 > PR tree-optimization/103680 > > gcc/ChangeLog: > > * tree-switch-conversion.cc (bit_test_cluster::emit): > Handle correctly remaining probability. > (switch_decision_tree::try_switch_expansion): Fix BB's count > where a cluster expansion happens. > (switch_decision_tree::emit_cmp_and_jump_insns): Fill up also > BB count. > (switch_decision_tree::do_jump_if_equal): Likewise. > (switch_decision_tree::emit_case_nodes): Handle special case > for BT expansion which can also fallback to a default BB. > * tree-switch-conversion.h (cluster::cluster): Add > m_default_prob probability. Funny you just ping'd this patch. I've held it in my queue for months as I didn't see it get installed. As far as I'm concerned, you know the switch conversion bits better than anyone. If you think the patch significantly improves the profile handling for switch conversion, then I'd say go for it. Particularly since it seems to fix at least two known bugs. Keff
diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc index 670397c87e4..d6679e8dee3 100644 --- a/gcc/tree-switch-conversion.cc +++ b/gcc/tree-switch-conversion.cc @@ -1538,10 +1538,12 @@ bit_test_cluster::emit (tree index_expr, tree index_type, test[k].target_bb = n->m_case_bb; test[k].label = n->m_case_label_expr; test[k].bits = 0; + test[k].prob = profile_probability::never (); count++; } test[k].bits += n->get_range (n->get_low (), n->get_high ()); + test[k].prob += n->m_prob; lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval)); if (n->get_high () == NULL_TREE) @@ -1629,6 +1631,11 @@ bit_test_cluster::emit (tree index_expr, tree index_type, /*simple=*/true, NULL_TREE, /*before=*/true, GSI_SAME_STMT); + profile_probability subtree_prob = m_subtree_prob; + profile_probability default_prob = m_default_prob; + if (!default_prob.initialized_p ()) + default_prob = m_subtree_prob.invert (); + if (m_handles_entire_switch && entry_test_needed) { tree range = int_const_binop (MINUS_EXPR, maxval, minval); @@ -1639,9 +1646,10 @@ bit_test_cluster::emit (tree index_expr, tree index_type, /*simple=*/true, NULL_TREE, /*before=*/true, GSI_SAME_STMT); tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); + default_prob = default_prob.apply_scale (1, 2); basic_block new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb, - profile_probability::unlikely ()); + default_prob); gsi = gsi_last_bb (new_bb); } @@ -1662,14 +1670,12 @@ bit_test_cluster::emit (tree index_expr, tree index_type, else csui = tmp; - profile_probability prob = profile_probability::always (); - /* for each unique set of cases: if (const & csui) goto target */ for (k = 0; k < count; k++) { - prob = profile_probability::always ().apply_scale (test[k].bits, - bt_range); + profile_probability prob = test[k].prob / (subtree_prob + default_prob); + subtree_prob -= test[k].prob; bt_range -= test[k].bits; tmp = wide_int_to_tree (word_type_node, test[k].mask); tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); @@ -1908,9 +1914,13 @@ switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters) /* Emit cluster-specific switch handling. */ for (unsigned i = 0; i < clusters.length (); i++) if (clusters[i]->get_type () != SIMPLE_CASE) - clusters[i]->emit (index_expr, index_type, - gimple_switch_default_label (m_switch), - m_default_bb, gimple_location (m_switch)); + { + edge e = single_pred_edge (clusters[i]->m_case_bb); + e->dest->count = e->src->count.apply_probability (e->probability); + clusters[i]->emit (index_expr, index_type, + gimple_switch_default_label (m_switch), + m_default_bb, gimple_location (m_switch)); + } } fix_phi_operands_for_edges (); @@ -2162,6 +2172,7 @@ switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0, edge false_edge = split_block (bb, cond); false_edge->flags = EDGE_FALSE_VALUE; false_edge->probability = prob.invert (); + false_edge->dest->count = bb->count.apply_probability (prob.invert ()); edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); true_edge->probability = prob; @@ -2192,6 +2203,7 @@ switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1, edge false_edge = split_block (bb, cond); false_edge->flags = EDGE_FALSE_VALUE; false_edge->probability = prob.invert (); + false_edge->dest->count = bb->count.apply_probability (prob.invert ()); edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); true_edge->probability = prob; @@ -2227,7 +2239,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, node->m_c->m_case_bb, p, loc); /* Since this case is taken at this point, reduce its weight from subtree_weight. */ - node->m_c->m_subtree_prob -= p; + node->m_c->m_subtree_prob -= node->m_c->m_prob; if (node->m_left != NULL && node->m_right != NULL) { @@ -2246,6 +2258,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, / (node->m_c->m_subtree_prob + default_prob)); bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (), node->m_right->m_c->m_case_bb, p, loc); + node->m_c->m_subtree_prob -= node->m_right->m_c->m_prob; p = (node->m_left->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob)); @@ -2262,6 +2275,7 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, p = ((node->m_right->m_c->m_subtree_prob + default_prob.apply_scale (1, 2)) / (node->m_c->m_subtree_prob + default_prob)); + test_bb->count = bb->count.apply_probability (p); bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), GT_EXPR, test_bb, p, loc); default_prob = default_prob.apply_scale (1, 2); @@ -2348,21 +2362,28 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, is the one to branch to. */ if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE) { + bool is_bt = node->m_c->get_type () == BIT_TEST; + int parts = is_bt ? 3 : 2; + /* Branch to a label where we will handle it later. */ basic_block test_bb = split_edge (single_succ_edge (bb)); redirect_edge_succ (single_pred_edge (test_bb), single_succ_edge (bb)->dest); - - profile_probability right_prob = profile_probability::never (); - if (node->m_right) - right_prob = node->m_right->m_c->m_subtree_prob; - p = ((right_prob + default_prob.apply_scale (1, 2)) + profile_probability right_prob = profile_probability::never (); + if (node->m_right) + right_prob = node->m_right->m_c->m_subtree_prob; + p = ((right_prob + default_prob.apply_scale (1, parts)) / (node->m_c->m_subtree_prob + default_prob)); + test_bb->count = bb->count.apply_probability (p); bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), GT_EXPR, test_bb, p, loc); - default_prob = default_prob.apply_scale (1, 2); + + default_prob = default_prob.apply_scale (1, parts); + node->m_c->m_subtree_prob -= right_prob; + if (is_bt) + node->m_c->m_default_prob = default_prob; /* Value belongs to this node or to the left-hand subtree. */ p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob); diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h index e969c051a05..5f3f99353ba 100644 --- a/gcc/tree-switch-conversion.h +++ b/gcc/tree-switch-conversion.h @@ -102,6 +102,10 @@ public: /* Probability of reaching subtree rooted at this node. */ profile_probability m_subtree_prob; + /* Probability of default case when reaching the node. + It is used by bit-test right now. */ + profile_probability m_default_prob; + protected: /* Default constructor. */ cluster () {} @@ -110,7 +114,8 @@ protected: cluster::cluster (tree case_label_expr, basic_block case_bb, profile_probability prob, profile_probability subtree_prob): m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob), - m_subtree_prob (subtree_prob) + m_subtree_prob (subtree_prob), + m_default_prob (profile_probability::uninitialized ()) { } @@ -542,6 +547,7 @@ public: basic_block target_bb; tree label; int bits; + profile_probability prob; /* Comparison function for qsort to order bit tests by decreasing probability of execution. */