Improve profile handling in switch lowering.
Commit Message
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(-)
Comments
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
@@ -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);
@@ -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. */