diff mbox series

Improve profile handling in switch lowering.

Message ID 596c4483-864c-1d03-955c-69906171f037@suse.cz
State New
Headers show
Series Improve profile handling in switch lowering. | expand

Commit Message

Martin Liška Jan. 26, 2022, 11:11 a.m. UTC
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

Martin Liška March 4, 2022, 1:47 p.m. UTC | #1
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.  */
Martin Liška March 24, 2022, 10:22 a.m. UTC | #2
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.  */
>
Martin Liška April 7, 2022, 2 p.m. UTC | #3
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.  */
>>
>
diff mbox series

Patch

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.  */