* [PATCH] Improve profile handling in switch lowering.
@ 2022-01-26 11:11 Martin Liška
2022-03-04 13:47 ` Martin Liška
2022-11-28 17:38 ` Jeff Law
0 siblings, 2 replies; 6+ messages in thread
From: Martin Liška @ 2022-01-26 11:11 UTC (permalink / raw)
To: gcc-patches
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. */
--
2.34.1
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Improve profile handling in switch lowering.
2022-01-26 11:11 [PATCH] Improve profile handling in switch lowering Martin Liška
@ 2022-03-04 13:47 ` Martin Liška
2022-03-24 10:22 ` Martin Liška
2022-11-28 17:38 ` Jeff Law
1 sibling, 1 reply; 6+ messages in thread
From: Martin Liška @ 2022-03-04 13:47 UTC (permalink / raw)
To: gcc-patches; +Cc: Jan Hubicka
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. */
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Improve profile handling in switch lowering.
2022-03-04 13:47 ` Martin Liška
@ 2022-03-24 10:22 ` Martin Liška
2022-04-07 14:00 ` Martin Liška
0 siblings, 1 reply; 6+ messages in thread
From: Martin Liška @ 2022-03-24 10:22 UTC (permalink / raw)
To: gcc-patches; +Cc: Jan Hubicka
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. */
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Improve profile handling in switch lowering.
2022-03-24 10:22 ` Martin Liška
@ 2022-04-07 14:00 ` Martin Liška
2022-11-28 9:53 ` Martin Liška
0 siblings, 1 reply; 6+ messages in thread
From: Martin Liška @ 2022-04-07 14:00 UTC (permalink / raw)
To: gcc-patches; +Cc: Jan Hubicka
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. */
>>
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Improve profile handling in switch lowering.
2022-04-07 14:00 ` Martin Liška
@ 2022-11-28 9:53 ` Martin Liška
0 siblings, 0 replies; 6+ messages in thread
From: Martin Liška @ 2022-11-28 9:53 UTC (permalink / raw)
To: gcc-patches; +Cc: Jan Hubicka
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. */
>>>
>>
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Improve profile handling in switch lowering.
2022-01-26 11:11 [PATCH] Improve profile handling in switch lowering Martin Liška
2022-03-04 13:47 ` Martin Liška
@ 2022-11-28 17:38 ` Jeff Law
1 sibling, 0 replies; 6+ messages in thread
From: Jeff Law @ 2022-11-28 17:38 UTC (permalink / raw)
To: Martin Liška, gcc-patches
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
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2022-11-28 17:38 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-01-26 11:11 [PATCH] Improve profile handling in switch lowering Martin Liška
2022-03-04 13:47 ` Martin Liška
2022-03-24 10:22 ` Martin Liška
2022-04-07 14:00 ` Martin Liška
2022-11-28 9:53 ` Martin Liška
2022-11-28 17:38 ` Jeff Law
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).