[PATCH][PR 59521] Respect probabilities when expanding switch statement

[Yuri Gribov <tetra2005@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 661 bytes --]

Hi all,

Currently all cases in switch statement are treated as having equal
probabilities which causes suboptimal code as demonstrated in
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521 . This patch
modifies expander to select pivot point for decision tree so that
probabilities of cases on the left are roughly equal to probabilities
on the right.

Patch survives bootstrap and regtesting on x64 but has some issues:
* tests are fragile but I'm not sure how to make them better
* I haven't done any performance measurements - would these be needed?
I don't have access to SPEC these days, any other suggestions?

Patch is jointly authored with Martin.

-Y

[-- Attachment #2: pr59521-1.patch --]
[-- Type: application/octet-stream, Size: 14972 bytes --]

2017-06-29  Yury Gribov  <tetra2005@gmail.com>
	    Martin Liska  <marxin@gcc.gnu.org>

	PR middle-end/59521
gcc/
	* predict.c (set_even_probabilities): Handle case of a single
	likely edge.
	(combine_predictions_for_bb): Ditto.
	(tree_predict_by_opcode): Handle switch statements.
	* stmt.c (balance_case_nodes): Select pivot value based on
	probabilities.

gcc/testsuite/
	* 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.

diff -rupN gcc/gcc/predict.c gcc-59521/gcc/predict.c
--- gcc/gcc/predict.c	2017-07-07 09:47:43.000000000 +0200
+++ gcc-59521/gcc/predict.c	2017-07-16 07:15:08.000000000 +0200
@@ -836,7 +836,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;
   edge e = NULL;
@@ -844,29 +845,55 @@ set_even_probabilities (basic_block bb,
 
   FOR_EACH_EDGE (e, ei, bb->succs)
     if (!unlikely_executed_edge_p (e))
-      nedges ++;
+      nedges++;
 
   /* Make the distribution even if all edges are unlikely.  */
   unsigned unlikely_count = unlikely_edges ? unlikely_edges->elements () : 0;
+  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 (!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 (!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 = profile_probability::guessed_always ()
-				.apply_scale (1, c);
-      }
-    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 (!unlikely_executed_edge_p (e))
+	  {
+	    if (unlikely_edges != NULL && unlikely_edges->contains (e))
+	      e->probability = profile_probability::very_unlikely ();
+	    else
+	      e->probability = profile_probability::guessed_always ()
+				    .apply_scale (1, scale);
+	  }
+	else
+	  e->probability = profile_probability::never ();
+    }
 }
 
 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
@@ -1153,6 +1180,7 @@ combine_predictions_for_bb (basic_block 
   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
@@ -1160,11 +1188,16 @@ combine_predictions_for_bb (basic_block 
       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 (!bb->count.initialized_p () && !dry_run)
-	set_even_probabilities (bb, &unlikely_edges);
+	set_even_probabilities (bb, &unlikely_edges, &likely_edges);
       clear_bb_predictions (bb);
       if (dump_file)
 	{
@@ -2451,7 +2484,30 @@ tree_predict_by_opcode (basic_block bb)
   edge_iterator ei;
   enum br_predictor predictor;
 
-  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);
+      if (val && TREE_CODE (val) == INTEGER_CST)
+	{
+	  edge e = find_taken_edge_switch_expr (sw, bb, 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 -rupN gcc/gcc/stmt.c gcc-59521/gcc/stmt.c
--- gcc/gcc/stmt.c	2017-07-07 09:47:43.000000000 +0200
+++ gcc-59521/gcc/stmt.c	2017-07-16 07:15:22.000000000 +0200
@@ -1377,6 +1377,7 @@ balance_case_nodes (case_node_ptr *head,
       int ranges = 0;
       case_node_ptr *npp;
       case_node_ptr left;
+      profile_probability prob = profile_probability::never();
 
       /* Count the number of entries on branch.  Also count the ranges.  */
 
@@ -1386,6 +1387,7 @@ balance_case_nodes (case_node_ptr *head,
 	    ranges++;
 
 	  i++;
+	  prob += np->prob;
 	  np = np->right;
 	}
 
@@ -1394,38 +1396,35 @@ balance_case_nodes (case_node_ptr *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)->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)->low, (*npp)->high))
-		    i--;
-		  i--;
-		  if (i <= 0)
-		    break;
-		  npp = &(*npp)->right;
-		}
+	      /* Skip nodes while their probability does not reach
+		 that amount.  */
+	      if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
+		prob -= (*npp)->prob;
+	      prob -= (*npp)->prob;
+	      if (prob <= pivot_prob || ! (*npp)->right)
+		break;
+	      npp = &(*npp)->right;
 	    }
-	  *head = np = *npp;
+	  np = *npp;
 	  *npp = 0;
+	  *head = np;
 	  np->parent = parent;
-	  np->left = left;
+	  np->left = left == np ? NULL : left;
 
 	  /* Optimize each of the two split parts.  */
 	  balance_case_nodes (&np->left, np);
 	  balance_case_nodes (&np->right, np);
-          np->subtree_prob = np->prob;
-          np->subtree_prob += np->left->subtree_prob;
-          np->subtree_prob += np->right->subtree_prob;
+	  np->subtree_prob = np->prob;
+	  if (np->left)
+	    np->subtree_prob += np->left->subtree_prob;
+	  if (np->right)
+	    np->subtree_prob += np->right->subtree_prob;
 	}
       else
 	{
diff -rupN gcc/gcc/testsuite/c-c++-common/pr59521-1.c gcc-59521/gcc/testsuite/c-c++-common/pr59521-1.c
--- gcc/gcc/testsuite/c-c++-common/pr59521-1.c	1970-01-01 01:00:00.000000000 +0100
+++ gcc-59521/gcc/testsuite/c-c++-common/pr59521-1.c	2017-07-17 22:09:11.000000000 +0200
@@ -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 -rupN gcc/gcc/testsuite/c-c++-common/pr59521-2.c gcc-59521/gcc/testsuite/c-c++-common/pr59521-2.c
--- gcc/gcc/testsuite/c-c++-common/pr59521-2.c	1970-01-01 01:00:00.000000000 +0100
+++ gcc-59521/gcc/testsuite/c-c++-common/pr59521-2.c	2017-07-17 22:09:15.000000000 +0200
@@ -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 -rupN gcc/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c gcc-59521/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c
--- gcc/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c	1970-01-01 01:00:00.000000000 +0100
+++ gcc-59521/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c	2017-07-17 21:54:38.000000000 +0200
@@ -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 -rupN gcc/gcc/tree-cfg.c gcc-59521/gcc/tree-cfg.c
--- gcc/gcc/tree-cfg.c	2017-07-07 09:48:01.000000000 +0200
+++ gcc-59521/gcc/tree-cfg.c	2017-07-11 22:02:10.000000000 +0200
@@ -170,8 +170,6 @@ static bool gimple_can_merge_blocks_p (b
 static void remove_bb (basic_block);
 static edge find_taken_edge_computed_goto (basic_block, tree);
 static edge find_taken_edge_cond_expr (basic_block, tree);
-static edge find_taken_edge_switch_expr (gswitch *, basic_block, tree);
-static tree find_case_label_for_value (gswitch *, tree);
 static void lower_phi_internal_fn ();
 
 void
@@ -2311,73 +2309,6 @@ find_taken_edge_cond_expr (basic_block b
   return (integer_zerop (val) ? false_edge : true_edge);
 }
 
-/* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
-   statement, determine which edge will be taken out of the block.  Return
-   NULL if any edge may be taken.  */
-
-static edge
-find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
-			     tree val)
-{
-  basic_block dest_bb;
-  edge e;
-  tree taken_case;
-
-  if (gimple_switch_num_labels (switch_stmt) == 1)
-    taken_case = gimple_switch_default_label (switch_stmt);
-  else if (! val || TREE_CODE (val) != INTEGER_CST)
-    return NULL;
-  else
-    taken_case = find_case_label_for_value (switch_stmt, val);
-  dest_bb = label_to_block (CASE_LABEL (taken_case));
-
-  e = find_edge (bb, dest_bb);
-  gcc_assert (e);
-  return e;
-}
-
-
-/* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for 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 (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);
-
-  for (low = 0, high = n; high - low > 1; )
-    {
-      size_t i = (high + low) / 2;
-      tree t = gimple_switch_label (switch_stmt, i);
-      int cmp;
-
-      /* Cache the result of comparing CASE_LOW and val.  */
-      cmp = tree_int_cst_compare (CASE_LOW (t), val);
-
-      if (cmp > 0)
-	high = i;
-      else
-	low = i;
-
-      if (CASE_HIGH (t) == NULL)
-	{
-	  /* A singe-valued case label.  */
-	  if (cmp == 0)
-	    return t;
-	}
-      else
-	{
-	  /* A case range.  We can only handle integer ranges.  */
-	  if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
-	    return t;
-	}
-    }
-
-  return default_case;
-}
-
 
 /* Dump a basic block on stderr.  */
 
@@ -9339,6 +9270,72 @@ gt_pch_nx (edge_def *e, gt_pointer_opera
   op (&(block), cookie);
 }
 
+/* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
+   statement, determine which edge will be taken out of the block.  Return
+   NULL if any edge may be taken.  */
+
+edge
+find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
+			     tree val)
+{
+  basic_block dest_bb;
+  edge e;
+  tree taken_case;
+
+  if (gimple_switch_num_labels (switch_stmt) == 1)
+    taken_case = gimple_switch_default_label (switch_stmt);
+  else if (! val || TREE_CODE (val) != INTEGER_CST)
+    return NULL;
+  else
+    taken_case = find_case_label_for_value (switch_stmt, val);
+  dest_bb = label_to_block (CASE_LABEL (taken_case));
+
+  e = find_edge (bb, dest_bb);
+  gcc_assert (e);
+  return e;
+}
+
+/* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for 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.  */
+
+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);
+
+  for (low = 0, high = n; high - low > 1; )
+    {
+      size_t i = (high + low) / 2;
+      tree t = gimple_switch_label (switch_stmt, i);
+      int cmp;
+
+      /* Cache the result of comparing CASE_LOW and val.  */
+      cmp = tree_int_cst_compare (CASE_LOW (t), val);
+
+      if (cmp > 0)
+	high = i;
+      else
+	low = i;
+
+      if (CASE_HIGH (t) == NULL)
+	{
+	  /* A singe-valued case label.  */
+	  if (cmp == 0)
+	    return t;
+	}
+      else
+	{
+	  /* A case range.  We can only handle integer ranges.  */
+	  if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
+	    return t;
+	}
+    }
+
+  return default_case;
+}
+
 #if CHECKING_P
 
 namespace selftest {
diff -rupN gcc/gcc/tree-cfg.h gcc-59521/gcc/tree-cfg.h
--- gcc/gcc/tree-cfg.h	2017-07-07 09:48:01.000000000 +0200
+++ gcc-59521/gcc/tree-cfg.h	2017-07-11 22:02:10.000000000 +0200
@@ -108,6 +108,9 @@ extern basic_block insert_cond_bb (basic
 extern bool gimple_find_sub_bbs (gimple_seq, gimple_stmt_iterator *);
 extern bool extract_true_false_controlled_edges (basic_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,
+					 basic_block bb, tree val);
 
 /* Return true if the LHS of a call should be removed.  */