This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCHv3][PR 59521] Respect __builtin_expect in switch statements


Hello.

I'm sending updated version of the patch that is now built on
top of recent switch expansion changes.

Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

Ready to be installed?
Martin
>From 1e362576dacb8a601f3362e033a725c234f6bc7c Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Thu, 16 Aug 2018 14:16:01 +0200
Subject: [PATCH] Make __builtin_expect effective in switch statements
 (PR middle-end/59521).

gcc/ChangeLog:

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

  PR middle-end/59521
	* predict.c (set_even_probabilities): Add likely_edges
        argument and handle cases where we have precisely one
        likely edge.
	(combine_predictions_for_bb): Catch also likely_edges.
	(tree_predict_by_opcode): Handle gswitch statements.
	* tree-cfg.c (find_taken_edge_switch_expr): Remove
        const quantifier.
	(find_case_label_for_value): Likewise.
	* tree-cfg.h (find_case_label_for_value): New declaration.
	(find_taken_edge_switch_expr): Likewise.
	* tree-switch-conversion.c (switch_decision_tree::balance_case_nodes):
        Find pivot in decision tree based on probabily, not by number of
        nodes.

gcc/testsuite/ChangeLog:

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

  PR middle-end/59521
	* c-c++-common/pr59521-1.c: New test.
	* c-c++-common/pr59521-2.c: New test.
	* gcc.dg/tree-prof/pr59521-3.c: New test.
---
 gcc/predict.c                              | 96 +++++++++++++++++-----
 gcc/testsuite/c-c++-common/pr59521-1.c     | 15 ++++
 gcc/testsuite/c-c++-common/pr59521-2.c     | 15 ++++
 gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c | 34 ++++++++
 gcc/tree-cfg.c                             | 10 +--
 gcc/tree-cfg.h                             |  2 +
 gcc/tree-switch-conversion.c               | 45 +++++-----
 7 files changed, 168 insertions(+), 49 deletions(-)
 create mode 100644 gcc/testsuite/c-c++-common/pr59521-1.c
 create mode 100644 gcc/testsuite/c-c++-common/pr59521-2.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c

diff --git a/gcc/predict.c b/gcc/predict.c
index 8c8e79153fc..db1fe737cb4 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -831,7 +831,8 @@ unlikely_executed_bb_p (basic_block bb)
 
 static void
 set_even_probabilities (basic_block bb,
-			hash_set<edge> *unlikely_edges = NULL)
+			hash_set<edge> *unlikely_edges = NULL,
+			hash_set<edge_prediction *> *likely_edges = NULL)
 {
   unsigned nedges = 0, unlikely_count = 0;
   edge e = NULL;
@@ -843,7 +844,7 @@ set_even_probabilities (basic_block bb,
       all -= e->probability;
     else if (!unlikely_executed_edge_p (e))
       {
-        nedges ++;
+	nedges++;
         if (unlikely_edges != NULL && unlikely_edges->contains (e))
 	  {
 	    all -= profile_probability::very_unlikely ();
@@ -852,26 +853,54 @@ set_even_probabilities (basic_block bb,
       }
 
   /* Make the distribution even if all edges are unlikely.  */
+  unsigned likely_count = likely_edges ? likely_edges->elements () : 0;
   if (unlikely_count == nedges)
     {
       unlikely_edges = NULL;
       unlikely_count = 0;
     }
 
-  unsigned c = nedges - unlikely_count;
-
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    if (e->probability.initialized_p ())
-      ;
-    else if (!unlikely_executed_edge_p (e))
-      {
-	if (unlikely_edges != NULL && unlikely_edges->contains (e))
-	  e->probability = profile_probability::very_unlikely ();
+  /* If we have one likely edge, then use its probability and distribute
+     remaining probabilities as even.  */
+  if (likely_count == 1)
+    {
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	if (e->probability.initialized_p ())
+	  ;
+	else if (!unlikely_executed_edge_p (e))
+	  {
+	    edge_prediction *prediction = *likely_edges->begin ();
+	    int p = prediction->ep_probability;
+	    profile_probability prob
+	      = profile_probability::from_reg_br_prob_base (p);
+	    profile_probability remainder = prob.invert ();
+
+	    if (prediction->ep_edge == e)
+	      e->probability = prob;
+	    else
+	      e->probability = remainder.apply_scale (1, nedges - 1);
+	  }
 	else
-	  e->probability = all.apply_scale (1, c).guessed ();
-      }
-    else
-      e->probability = profile_probability::never ();
+	  e->probability = profile_probability::never ();
+    }
+  else
+    {
+      /* Make all unlikely edges unlikely and the rest will have even
+	 probability.  */
+      unsigned scale = nedges - unlikely_count;
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	if (e->probability.initialized_p ())
+	  ;
+	else if (!unlikely_executed_edge_p (e))
+	  {
+	    if (unlikely_edges != NULL && unlikely_edges->contains (e))
+	      e->probability = profile_probability::very_unlikely ();
+	    else
+	      e->probability = all.apply_scale (1, scale);
+	  }
+	else
+	  e->probability = profile_probability::never ();
+    }
 }
 
 /* Add REG_BR_PROB note to JUMP with PROB.  */
@@ -1175,6 +1204,7 @@ combine_predictions_for_bb (basic_block bb, bool dry_run)
   if (nedges != 2)
     {
       hash_set<edge> unlikely_edges (4);
+      hash_set<edge_prediction *> likely_edges (4);
 
       /* Identify all edges that have a probability close to very unlikely.
 	 Doing the approach for very unlikely doesn't worth for doing as
@@ -1182,11 +1212,16 @@ combine_predictions_for_bb (basic_block bb, bool dry_run)
       edge_prediction **preds = bb_predictions->get (bb);
       if (preds)
 	for (pred = *preds; pred; pred = pred->ep_next)
-	  if (pred->ep_probability <= PROB_VERY_UNLIKELY)
-	    unlikely_edges.add (pred->ep_edge);
+	  {
+	    if (pred->ep_probability <= PROB_VERY_UNLIKELY)
+	      unlikely_edges.add (pred->ep_edge);
+	    if (pred->ep_probability >= PROB_VERY_LIKELY
+		|| pred->ep_predictor == PRED_BUILTIN_EXPECT)
+	      likely_edges.add (pred);
+	  }
 
       if (!dry_run)
-	set_even_probabilities (bb, &unlikely_edges);
+	set_even_probabilities (bb, &unlikely_edges, &likely_edges);
       clear_bb_predictions (bb);
       if (dump_file)
 	{
@@ -2575,7 +2610,30 @@ tree_predict_by_opcode (basic_block bb)
   enum br_predictor predictor;
   HOST_WIDE_INT probability;
 
-  if (!stmt || gimple_code (stmt) != GIMPLE_COND)
+  if (!stmt)
+    return;
+
+  if (gswitch *sw = dyn_cast <gswitch *> (stmt))
+    {
+      tree index = gimple_switch_index (sw);
+      tree val = expr_expected_value (index, auto_bitmap (),
+				      &predictor, &probability);
+      if (val && TREE_CODE (val) == INTEGER_CST)
+	{
+	  edge e = find_taken_edge_switch_expr (sw, val);
+	  if (predictor == PRED_BUILTIN_EXPECT)
+	    {
+	      int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
+	      gcc_assert (percent >= 0 && percent <= 100);
+	      predict_edge (e, PRED_BUILTIN_EXPECT,
+			    HITRATE (percent));
+	    }
+	  else
+	    predict_edge_def (e, predictor, TAKEN);
+	}
+    }
+
+  if (gimple_code (stmt) != GIMPLE_COND)
     return;
   FOR_EACH_EDGE (then_edge, ei, bb->succs)
     if (then_edge->flags & EDGE_TRUE_VALUE)
diff --git a/gcc/testsuite/c-c++-common/pr59521-1.c b/gcc/testsuite/c-c++-common/pr59521-1.c
new file mode 100644
index 00000000000..32320b57052
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/pr59521-1.c
@@ -0,0 +1,15 @@
+/* { dg-options "-O2" } */
+/* { dg-do compile } */
+
+extern int puts (const char *);
+
+void
+f(int ch) {
+  switch (ch) {
+    case 3: puts("a"); break;
+    case 42: puts("e"); break;
+    case 333: puts("i"); break;
+  } 
+}
+
+/* { dg-final { scan-assembler "cmp.*42,.*cmp.*333,.*cmp.*3," { target i?86-*-* x86_64-*-* } } } */
diff --git a/gcc/testsuite/c-c++-common/pr59521-2.c b/gcc/testsuite/c-c++-common/pr59521-2.c
new file mode 100644
index 00000000000..3c48825b347
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/pr59521-2.c
@@ -0,0 +1,15 @@
+/* { dg-options "-O2" } */
+/* { dg-do compile } */
+
+extern int puts (const char *);
+
+void
+f(int ch) {
+  switch (__builtin_expect(ch, 333)) {
+    case 3: puts("a"); break;
+    case 42: puts("e"); break;
+    case 333: puts("i"); break;
+  } 
+}
+
+/* { dg-final { scan-assembler "cmp.*333,.*cmp.*3,.*cmp.*42," { target i?86-*-* x86_64-*-* } } } */
diff --git a/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c b/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c
new file mode 100644
index 00000000000..497643bed3d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c
@@ -0,0 +1,34 @@
+/* { dg-options "-O2 -save-temps" } */
+
+#include <stdio.h>
+
+__attribute__((noinline,noclone)) void
+sink(const char *s) {
+  asm("" :: "r"(s));
+}
+
+void
+foo(int ch) {
+  switch (ch) {
+    case 100: sink("100"); break;
+    case 10: sink("10"); break;
+    case 1: sink("1"); break;
+    } 
+}
+
+int main()
+{
+  for (int i = 0; i < 10000; i++)
+  {
+    int v;
+    if (i % 100 == 0)
+      v = 100;
+    else if(i % 10 == 0)
+      v = 10;
+    else
+      v = 1;
+    foo(v);
+  }
+}
+
+/* { dg-final-use-not-autofdo { scan-assembler "\nfoo:\n.*cmp.*1,.*cmp.*10,.*cmp.*100" { target i?86-*-* x86_64-*-* } } } */
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index b021fb0f97b..738e0e7fe7f 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -171,8 +171,6 @@ static bool gimple_can_merge_blocks_p (basic_block, basic_block);
 static void remove_bb (basic_block);
 static edge find_taken_edge_computed_goto (basic_block, tree);
 static edge find_taken_edge_cond_expr (const gcond *, tree);
-static edge find_taken_edge_switch_expr (const gswitch *, tree);
-static tree find_case_label_for_value (const gswitch *, tree);
 static void lower_phi_internal_fn ();
 
 void
@@ -2436,8 +2434,8 @@ find_taken_edge_cond_expr (const gcond *cond_stmt, tree val)
    If VAL is NULL_TREE, then the current value of SWITCH_STMT's index
    is used.  */
 
-static edge
-find_taken_edge_switch_expr (const gswitch *switch_stmt, tree val)
+edge
+find_taken_edge_switch_expr (gswitch *switch_stmt, tree val)
 {
   basic_block dest_bb;
   edge e;
@@ -2466,8 +2464,8 @@ find_taken_edge_switch_expr (const gswitch *switch_stmt, tree val)
    We can make optimal use here of the fact that the case labels are
    sorted: We can do a binary search for a case matching VAL.  */
 
-static tree
-find_case_label_for_value (const gswitch *switch_stmt, tree val)
+tree
+find_case_label_for_value (gswitch *switch_stmt, tree val)
 {
   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
   tree default_case = gimple_switch_default_label (switch_stmt);
diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h
index 349a9543168..10ec50e95fd 100644
--- a/gcc/tree-cfg.h
+++ b/gcc/tree-cfg.h
@@ -102,6 +102,8 @@ extern tree gimplify_build2 (gimple_stmt_iterator *, enum tree_code,
 extern tree gimplify_build1 (gimple_stmt_iterator *, enum tree_code,
 			     tree, tree);
 extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
+extern tree find_case_label_for_value (gswitch *switch_stmt, tree val);
+extern edge find_taken_edge_switch_expr (gswitch *switch_stmt, tree val);
 extern unsigned int execute_fixup_cfg (void);
 extern unsigned int split_critical_edges (void);
 extern basic_block insert_cond_bb (basic_block, gimple *, gimple *,
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index a31ff94b895..5e4876474f9 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -1921,6 +1921,7 @@ switch_decision_tree::balance_case_nodes (case_tree_node **head,
       int ranges = 0;
       case_tree_node **npp;
       case_tree_node *left;
+      profile_probability prob = profile_probability::never ();
 
       /* Count the number of entries on branch.  Also count the ranges.  */
 
@@ -1930,6 +1931,7 @@ switch_decision_tree::balance_case_nodes (case_tree_node **head,
 	    ranges++;
 
 	  i++;
+	  prob += np->m_c->m_prob;
 	  np = np->m_right;
 	}
 
@@ -1938,39 +1940,34 @@ switch_decision_tree::balance_case_nodes (case_tree_node **head,
 	  /* Split this list if it is long enough for that to help.  */
 	  npp = head;
 	  left = *npp;
+	  profile_probability pivot_prob = prob.apply_scale (1, 2);
 
-	  /* If there are just three nodes, split at the middle one.  */
-	  if (i == 3)
-	    npp = &(*npp)->m_right;
-	  else
+	  /* Find the place in the list that bisects the list's total cost,
+	     where ranges count as 2.  */
+	  while (1)
 	    {
-	      /* Find the place in the list that bisects the list's total cost,
-		 where ranges count as 2.
-		 Here I gets half the total cost.  */
-	      i = (i + ranges + 1) / 2;
-	      while (1)
-		{
-		  /* Skip nodes while their cost does not reach that amount.  */
-		  if (!tree_int_cst_equal ((*npp)->m_c->get_low (),
-					   (*npp)->m_c->get_high ()))
-		    i--;
-		  i--;
-		  if (i <= 0)
-		    break;
-		  npp = &(*npp)->m_right;
-		}
+	      /* Skip nodes while their probability does not reach
+		 that amount.  */
+	      prob -= (*npp)->m_c->m_prob;
+	      if (prob <= pivot_prob || ! (*npp)->m_right)
+		break;
+	      npp = &(*npp)->m_right;
 	    }
-	  *head = np = *npp;
-	  *npp = 0;
+
+	  np = *npp;
+ 	  *npp = 0;
+	  *head = np;
 	  np->m_parent = parent;
-	  np->m_left = left;
+	  np->m_left = left == np ? NULL : left;
 
 	  /* Optimize each of the two split parts.  */
 	  balance_case_nodes (&np->m_left, np);
 	  balance_case_nodes (&np->m_right, np);
 	  np->m_c->m_subtree_prob = np->m_c->m_prob;
-	  np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
-	  np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
+	  if (np->m_left)
+	    np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
+	  if (np->m_right)
+	    np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
 	}
       else
 	{
-- 
2.18.0


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]