[1/3] Fix probabilities for jump table (PR tree-optimization/86702).

Message ID f201efd0569588279576f4a2e1fd0b4be34dfd1f.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, 12:58 p.m.
The patch set even probability to jump tables based on number of
cases which are handled on each edge.

gcc/ChangeLog:

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

        PR tree-optimization/86702
	* tree-switch-conversion.c (jump_table_cluster::emit):
        Make probabilities even for values in jump table
        according to number of cases handled.
	(switch_decision_tree::compute_cases_per_edge): Pass
        argument to reset_out_edges_aux function.
	(switch_decision_tree::analyze_switch_statement): Likewise.
	* tree-switch-conversion.h (switch_decision_tree::reset_out_edges_aux):
        Make it static.
---
 gcc/tree-switch-conversion.c | 40 ++++++++++++++++++++++++++++++++++--
 gcc/tree-switch-conversion.h | 11 +++++-----
 2 files changed, 43 insertions(+), 8 deletions(-)

Comments

Jeff Law Aug. 18, 2018, 5:17 a.m. | #1
On 08/03/2018 06:58 AM, marxin wrote:
> The patch set even probability to jump tables based on number of

> cases which are handled on each edge.

> 

> gcc/ChangeLog:

> 

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

> 

>         PR tree-optimization/86702

> 	* tree-switch-conversion.c (jump_table_cluster::emit):

>         Make probabilities even for values in jump table

>         according to number of cases handled.

> 	(switch_decision_tree::compute_cases_per_edge): Pass

>         argument to reset_out_edges_aux function.

> 	(switch_decision_tree::analyze_switch_statement): Likewise.

> 	* tree-switch-conversion.h (switch_decision_tree::reset_out_edges_aux):

>         Make it static.

> ---

>  gcc/tree-switch-conversion.c | 40 ++++++++++++++++++++++++++++++++++--

>  gcc/tree-switch-conversion.h | 11 +++++-----

>  2 files changed, 43 insertions(+), 8 deletions(-)

> 

OK.
jeff

Patch

diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index 492cd365a30..0b5c93118f6 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -1064,6 +1064,9 @@  void
 jump_table_cluster::emit (tree index_expr, tree,
 			  tree default_label_expr, basic_block default_bb)
 {
+  unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
+  unsigned HOST_WIDE_INT nondefault_range = 0;
+
   /* For jump table we just emit a new gswitch statement that will
      be latter lowered to jump table.  */
   auto_vec <tree> labels;
@@ -1080,6 +1083,39 @@  jump_table_cluster::emit (tree index_expr, tree,
 				    unshare_expr (default_label_expr), labels);
   gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb);
   gsi_insert_after (&gsi, s, GSI_NEW_STMT);
+
+  /* Set up even probabilities for all cases.  */
+  for (unsigned i = 0; i < m_cases.length (); i++)
+    {
+      simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
+      edge case_edge = find_edge (m_case_bb, sc->m_case_bb);
+      unsigned HOST_WIDE_INT case_range
+	= sc->get_range (sc->get_low (), sc->get_high ());
+      nondefault_range += case_range;
+
+      /* case_edge->aux is number of values in a jump-table that are covered
+	 by the case_edge.  */
+      case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + case_range);
+    }
+
+  edge default_edge = gimple_switch_default_edge (s);
+  default_edge->probability = profile_probability::never ();
+
+  for (unsigned i = 0; i < m_cases.length (); i++)
+    {
+      simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
+      edge case_edge = find_edge (m_case_bb, sc->m_case_bb);
+      case_edge->probability
+	= profile_probability::always ().apply_scale ((intptr_t)case_edge->aux,
+						      range);
+    }
+
+  /* Number of non-default values is probability of default edge.  */
+  default_edge->probability
+    += profile_probability::always ().apply_scale (nondefault_range,
+						   range).invert ();
+
+  switch_decision_tree::reset_out_edges_aux (s);
 }
 
 /* Find jump tables of given CLUSTERS, where all members of the vector
@@ -1571,7 +1607,7 @@  bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
 void
 switch_decision_tree::compute_cases_per_edge ()
 {
-  reset_out_edges_aux ();
+  reset_out_edges_aux (m_switch);
   int ncases = gimple_switch_num_labels (m_switch);
   for (int i = ncases - 1; i >= 1; --i)
     {
@@ -1614,7 +1650,7 @@  switch_decision_tree::analyze_switch_statement ()
       m_case_bbs.quick_push (case_edge->dest);
     }
 
-  reset_out_edges_aux ();
+  reset_out_edges_aux (m_switch);
 
   /* Find jump table clusters.  */
   vec<cluster *> output = jump_table_cluster::find_jump_tables (clusters);
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index 4beac785f05..af2f47a07e6 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -513,10 +513,6 @@  struct switch_decision_tree
   /* Attempt to expand CLUSTERS as a decision tree.  Return true when
      expanded.  */
   bool try_switch_expansion (vec<cluster *> &clusters);
-
-  /* Reset the aux field of all outgoing edges of switch basic block.  */
-  inline void reset_out_edges_aux ();
-
   /* Compute the number of case labels that correspond to each outgoing edge of
      switch statement.  Record this information in the aux field of the edge.
      */
@@ -576,6 +572,9 @@  struct switch_decision_tree
 					      basic_block label_bb,
 					      profile_probability prob);
 
+  /* Reset the aux field of all outgoing edges of switch basic block.  */
+  static inline void reset_out_edges_aux (gswitch *swtch);
+
   /* Switch statement.  */
   gswitch *m_switch;
 
@@ -838,9 +837,9 @@  struct switch_conversion
 };
 
 void
-switch_decision_tree::reset_out_edges_aux ()
+switch_decision_tree::reset_out_edges_aux (gswitch *swtch)
 {
-  basic_block bb = gimple_bb (m_switch);
+  basic_block bb = gimple_bb (swtch);
   edge e;
   edge_iterator ei;
   FOR_EACH_EDGE (e, ei, bb->succs)