[2/3] Fix probability for bit-tests.

Message ID 0e9a9eca4a3bf0330b45993953c42d8e9e1fb2cb.1534236816.git.mliska@suse.cz
State New
Headers show
Series
  • Improvements to switch expansion code
Related show

Commit Message

Martin Liška Aug. 3, 2018, 2:10 p.m.
The patch set even probability to bit test based on number of
cases which are handled on each edge.

gcc/ChangeLog:

2018-08-06  Martin Liska  <mliska@suse.cz>

	* tree-switch-conversion.c (bit_test_cluster::find_bit_tests):
        Add new argument to bit_test_cluster constructor.
	(bit_test_cluster::emit): Set bits really number of values
        handlel by a test.
	(bit_test_cluster::hoist_edge_and_branch_if_true): Add
        probability argument.
	* tree-switch-conversion.h (struct bit_test_cluster):
        Add m_handles_entire_switch.

gcc/testsuite/ChangeLog:

2018-08-06  Martin Liska  <mliska@suse.cz>

	* gcc.dg/tree-ssa/switch-2.c: New test.
---
 gcc/testsuite/gcc.dg/tree-ssa/switch-2.c | 25 +++++++++++++
 gcc/tree-switch-conversion.c             | 46 +++++++++++++++++-------
 gcc/tree-switch-conversion.h             | 12 +++++--
 3 files changed, 67 insertions(+), 16 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-2.c

Comments

Jeff Law Aug. 18, 2018, 5:19 a.m. | #1
On 08/03/2018 08:10 AM, marxin wrote:
> The patch set even probability to bit test based on number of

> cases which are handled on each edge.

> 

> gcc/ChangeLog:

> 

> 2018-08-06  Martin Liska  <mliska@suse.cz>

> 

> 	* tree-switch-conversion.c (bit_test_cluster::find_bit_tests):

>         Add new argument to bit_test_cluster constructor.

> 	(bit_test_cluster::emit): Set bits really number of values

>         handlel by a test.

> 	(bit_test_cluster::hoist_edge_and_branch_if_true): Add

>         probability argument.

> 	* tree-switch-conversion.h (struct bit_test_cluster):

>         Add m_handles_entire_switch.

> 

> gcc/testsuite/ChangeLog:

> 

> 2018-08-06  Martin Liska  <mliska@suse.cz>

> 

> 	* gcc.dg/tree-ssa/switch-2.c: New test.

OK
jeff

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-2.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-2.c
new file mode 100644
index 00000000000..710825dc257
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-2.c
@@ -0,0 +1,25 @@ 
+/* { dg-do compile { target { { x86_64-*-* aarch64-*-* ia64-*-* powerpc64-*-* } && lp64 } } } */
+/* { dg-options "-O2 -fdump-tree-switchlower1" } */
+
+int global;
+
+int foo (int x)
+{
+  switch (x) {
+    case 0:
+    case 10:
+      return 1;
+    case 20:
+    case 30:
+    case 62:
+      return 2;
+    case 1000:
+    case 1010:
+    case 1025 ... 1030:
+      return 1;
+    default:
+      return 0;
+  }
+}
+
+/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: BT:0-62 BT:1000-1030" "switchlower1" } } */
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index 0b5c93118f6..cd771438214 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -1282,12 +1282,16 @@  bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
     return clusters.copy ();
 
   /* Find and build the clusters.  */
-  for (int end = l;;)
+  for (unsigned end = l;;)
     {
       int start = min[end].m_start;
 
       if (is_beneficial (clusters, start, end - 1))
-	output.safe_push (new bit_test_cluster (clusters, start, end - 1));
+	{
+	  bool entire = start == 0 && end == clusters.length ();
+	  output.safe_push (new bit_test_cluster (clusters, start, end - 1,
+						  entire));
+	}
       else
 	for (int i = end - 1; i >=  start; i--)
 	  output.safe_push (clusters[i]);
@@ -1437,6 +1441,7 @@  bit_test_cluster::emit (tree index_expr, tree index_type,
   tree minval = get_low ();
   tree maxval = get_high ();
   tree range = int_const_binop (MINUS_EXPR, maxval, minval);
+  unsigned HOST_WIDE_INT bt_range = get_range (minval, maxval);
 
   /* Go through all case labels, and collect the case labels, profile
      counts, and other information we need to build the branch tests.  */
@@ -1455,11 +1460,11 @@  bit_test_cluster::emit (tree index_expr, tree index_type,
 	  test[k].mask = wi::zero (prec);
 	  test[k].target_bb = n->m_case_bb;
 	  test[k].label = n->m_case_label_expr;
-	  test[k].bits = 1;
+	  test[k].bits = 0;
 	  count++;
 	}
-      else
-	test[k].bits++;
+
+      test[k].bits += n->get_range (n->get_low (), n->get_high ());
 
       lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval));
       if (n->get_high () == NULL_TREE)
@@ -1516,14 +1521,20 @@  bit_test_cluster::emit (tree index_expr, tree index_type,
 				  /*simple=*/true, NULL_TREE,
 				  /*before=*/true, GSI_SAME_STMT);
 
-  /* if (idx > range) goto default */
-  range = force_gimple_operand_gsi (&gsi,
+  if (m_handles_entire_switch)
+    {
+      /* if (idx > range) goto default */
+      range
+	= force_gimple_operand_gsi (&gsi,
 				    fold_convert (unsigned_index_type, range),
 				    /*simple=*/true, NULL_TREE,
 				    /*before=*/true, GSI_SAME_STMT);
-  tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
-  basic_block new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb);
-  gsi = gsi_last_bb (new_bb);
+      tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
+      basic_block new_bb
+	= hoist_edge_and_branch_if_true (&gsi, tmp, default_bb,
+					 profile_probability::unlikely ());
+      gsi = gsi_last_bb (new_bb);
+    }
 
   /* csui = (1 << (word_mode) idx) */
   csui = make_ssa_name (word_type_node);
@@ -1536,17 +1547,23 @@  bit_test_cluster::emit (tree index_expr, tree index_type,
   gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
   update_stmt (shift_stmt);
 
+  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);
+      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);
       tmp = force_gimple_operand_gsi (&gsi, tmp,
 				      /*simple=*/true, NULL_TREE,
 				      /*before=*/true, GSI_SAME_STMT);
       tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
-      new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb);
+      basic_block new_bb
+	= hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb, prob);
       gsi = gsi_last_bb (new_bb);
     }
 
@@ -1554,7 +1571,8 @@  bit_test_cluster::emit (tree index_expr, tree index_type,
   gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
 
   /* If nothing matched, go to the default label.  */
-  make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
+  edge e = make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
+  e->probability = profile_probability::always ();
 }
 
 /* Split the basic block at the statement pointed to by GSIP, and insert
@@ -1574,7 +1592,8 @@  bit_test_cluster::emit (tree index_expr, tree index_type,
 
 basic_block
 bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
-						 tree cond, basic_block case_bb)
+						 tree cond, basic_block case_bb,
+						 profile_probability prob)
 {
   tree tmp;
   gcond *cond_stmt;
@@ -1582,6 +1601,7 @@  bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
   basic_block new_bb, split_bb = gsi_bb (*gsip);
 
   edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE);
+  e_true->probability = prob;
   gcc_assert (e_true->src == split_bb);
 
   tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index af2f47a07e6..726d54ad912 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -329,8 +329,10 @@  This transformation was contributed by Roger Sayle, see this e-mail:
 struct bit_test_cluster: public group_cluster
 {
   /* Constructor.  */
-  bit_test_cluster (vec<cluster *> &clusters, unsigned start, unsigned end)
-  :group_cluster (clusters, start, end)
+  bit_test_cluster (vec<cluster *> &clusters, unsigned start, unsigned end,
+		    bool handles_entire_switch)
+  :group_cluster (clusters, start, end),
+  m_handles_entire_switch (handles_entire_switch)
   {}
 
   cluster_type
@@ -396,7 +398,11 @@  struct bit_test_cluster: public group_cluster
    Returns the newly created basic block.  */
   static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
 						    tree cond,
-						    basic_block case_bb);
+						    basic_block case_bb,
+						    profile_probability prob);
+
+  /* True when the jump table handles an entire switch statement.  */
+  bool m_handles_entire_switch;
 
   /* Maximum number of different basic blocks that can be handled by
      a bit test.  */