Re: [PATCH] Improve profile handling in switch lowering.

2022-11-28 Thread Jeff Law via 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

Re: [PATCH] Improve profile handling in switch lowering.

2022-11-28 Thread Martin Liška 

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 (, 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 
)
    /* 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,

Re: [PATCH] Improve profile handling in switch lowering.

2022-04-07 Thread Martin Liška 

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 (, 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 
)
    /* 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;

Re: [PATCH] Improve profile handling in switch lowering.

2022-03-24 Thread Martin Liška 

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 (, 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 
)
    /* 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 @@

Re: [PATCH] Improve profile handling in switch lowering.

2022-03-04 Thread Martin Liška 

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 (, 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 
)
    /* 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

[PATCH] Improve profile handling in switch lowering.

2022-01-26 Thread Martin Liška 

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 (, 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 
)
   /* 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