[gcc(refs/users/marxin/heads/switch-lowering-fix-profile)] Improve profile probability for BT.

[gcc(refs/users/marxin/heads/switch-lowering-fix-profile)] Improve profile probability for BT.

[Martin Liska]

https://gcc.gnu.org/g:8aaa359d4d14ac59be69f027c95eff333b292604

commit 8aaa359d4d14ac59be69f027c95eff333b292604
Author: Martin Liska <mliska@suse.cz>
Date:   Tue Jan 25 16:58:17 2022 +0100

    Improve profile probability for BT.

Diff:
---
 gcc/tree-switch-conversion.cc | 23 +++++++++++++++++------
 gcc/tree-switch-conversion.h  |  8 +++++++-
 2 files changed, 24 insertions(+), 7 deletions(-)

diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc
index 4d90e820c08..57eb92936c9 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);
@@ -2233,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)
 	{
@@ -2252,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));
@@ -2369,7 +2376,11 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
 
 	  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);
+	  node->m_c->m_subtree_prob -= right_prob;
+	  if (node->m_c->get_type () == BIT_TEST)
+	    node->m_c->m_default_prob = profile_probability::never ();
 
 	  /* 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.  */