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

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

[Yuri Gribov]

[-- 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.  */
 

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

[Jan Hubicka]

> 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?

I think we could just check if daily testers shows some regressions after
patch is comitted. It seems right think to do.
> 
> Patch is jointly authored with Martin.

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.

I have made some changes to this fuction to fix other PR. So you may need
to update the patch.  What exactly is set_even_probabilities and 
combine_predictions_for_bb shooting for?

@@ -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)

I think this change can go in separately and is OK
(along with a testcase that checks that tree profile is right).

I will look into the RTL bits next.

Honza

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

[Yuri Gribov]

On Tue, Jul 18, 2017 at 8:45 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> 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?
>
> I think we could just check if daily testers shows some regressions after
> patch is comitted. It seems right think to do.

You mean gcc.opensuse.org? Makes sense.

>> Patch is jointly authored with Martin.
>
> 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.
>
> I have made some changes to this fuction to fix other PR. So you may need
> to update the patch.

Will do.

> What exactly is set_even_probabilities and combine_predictions_for_bb shooting for?

combine_predictions_for_bb calculates final probability for edges of
if-else or switch statements.

For if-elses this is done by combining values computed by different
predictors using Dempster-Shafer theory.  For switch statement DS is
not used, mainly because we do not have heuristics for predicting
which case will be taken (paper by Larus concluded that using if-else
heuristics does not give good results).

So until this patch we just used set_even_probabilities. The name of
this function is misleading, in addition to setting even probabilities
it can also understand that some edges are very unlikely and set
unlikely probs for those.  With patch it now also understands that one
edge is very likely.

> @@ -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)
>
> I think this change can go in separately and is OK
> (along with a testcase that checks that tree profile is right).

Ok.

> I will look into the RTL bits next.
>
> Honza

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

[Steven Bosscher]

On Tue, Jul 18, 2017 at 9:04 AM, Yuri Gribov wrote:
> 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.

Hi Yuri,

Can you come up with test cases that don't scan the assembly output?
Ideally the test case should check a dump file that is as close as
possible to the code transformation, in this case the dump from
pass_expand.

Ciao!
Steven

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

[Yuri Gribov]

On Thu, Jul 20, 2017 at 8:41 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Tue, Jul 18, 2017 at 9:04 AM, Yuri Gribov wrote:
>> 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.
>
> Hi Yuri,
>
> Can you come up with test cases that don't scan the assembly output?
> Ideally the test case should check a dump file that is as close as
> possible to the code transformation, in this case the dump from
> pass_expand.

Sure, can do (it won't help much about test fragility though).

-Y

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

[Jan Hubicka]

Hello,
sorry for not responding for a while.  Martin Liska has patch to move switch
expansion to gimple level that will likely simplify the code combinatoin.

> 
> combine_predictions_for_bb calculates final probability for edges of
> if-else or switch statements.
> 
> For if-elses this is done by combining values computed by different
> predictors using Dempster-Shafer theory.  For switch statement DS is
> not used, mainly because we do not have heuristics for predicting
> which case will be taken (paper by Larus concluded that using if-else
> heuristics does not give good results).
> 
> So until this patch we just used set_even_probabilities. The name of
> this function is misleading, in addition to setting even probabilities
> it can also understand that some edges are very unlikely and set
> unlikely probs for those.  With patch it now also understands that one
> edge is very likely.

I am not sure that the conclusion of Ball&Larus paper applies to us here.
In addition to usual if-then-else heuristics we have those based on walk
of CFG (such as ones predicting paths to unlikely calls) and those should
work well on switch statements. 

We discussed adding predictor combining code for BBs with more than 2
successors. Martin, do you have some code for that?

I guess teaching even propbabilities about likely edges also works, but
perhaps doing more general prediction combining would be cleaner...

Honza

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

[Martin Liška]

On 08/02/2017 11:53 AM, Jan Hubicka wrote:
> Hello,
> sorry for not responding for a while.  Martin Liska has patch to move switch
> expansion to gimple level that will likely simplify the code combinatoin.

Hello.

Yep, will land today to gcc-patches mailing list.

> 
>>
>> combine_predictions_for_bb calculates final probability for edges of
>> if-else or switch statements.
>>
>> For if-elses this is done by combining values computed by different
>> predictors using Dempster-Shafer theory.  For switch statement DS is
>> not used, mainly because we do not have heuristics for predicting
>> which case will be taken (paper by Larus concluded that using if-else
>> heuristics does not give good results).
>>
>> So until this patch we just used set_even_probabilities. The name of
>> this function is misleading, in addition to setting even probabilities
>> it can also understand that some edges are very unlikely and set
>> unlikely probs for those.  With patch it now also understands that one
>> edge is very likely.
> 
> I am not sure that the conclusion of Ball&Larus paper applies to us here.
> In addition to usual if-then-else heuristics we have those based on walk
> of CFG (such as ones predicting paths to unlikely calls) and those should
> work well on switch statements. 
> 
> We discussed adding predictor combining code for BBs with more than 2
> successors. Martin, do you have some code for that?

This has been discussed and we decided to reject that as we're unable to
apply DS theory as we can't evaluate what probability has a predictor for
edges different from the edge which it can evaluate. Note that with 2 edges
and probability x, one can calculate probability of the second edge
simply by 1 - x. That's not doable if one has > 2 edges. That was reason
why I decided to use DF theory for such situations and wrote just simple
handling of very {un,}likely probabilities.

Maybe I overlooked something in understanding of DF theory?

Martin 

> 
> I guess teaching even propbabilities about likely edges also works, but
> perhaps doing more general prediction combining would be cleaner...
> 
> Honza
> 

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

[Martin Liška]

On 08/02/2017 12:52 PM, Yury Gribov wrote:
> On Wed, Aug 2, 2017 at 11:42 AM, Martin Liška <mliska@suse.cz <mailto:mliska@suse.cz>> wrote:
> 
>     On 08/02/2017 11:53 AM, Jan Hubicka wrote:
>     > Hello,
>     > sorry for not responding for a while.  Martin Liska has patch to move switch
>     > expansion to gimple level that will likely simplify the code combinatoin.
> 
>     Hello.
> 
>     Yep, will land today to gcc-patches mailing list.
> 
>     >
>     >>
>     >> combine_predictions_for_bb calculates final probability for edges of
>     >> if-else or switch statements.
>     >>
>     >> For if-elses this is done by combining values computed by different
>     >> predictors using Dempster-Shafer theory.  For switch statement DS is
>     >> not used, mainly because we do not have heuristics for predicting
>     >> which case will be taken (paper by Larus concluded that using if-else
>     >> heuristics does not give good results).
>     >>
>     >> So until this patch we just used set_even_probabilities. The name of
>     >> this function is misleading, in addition to setting even probabilities
>     >> it can also understand that some edges are very unlikely and set
>     >> unlikely probs for those.  With patch it now also understands that one
>     >> edge is very likely.
>     >
>     > I am not sure that the conclusion of Ball&Larus paper applies to us here.
>     > In addition to usual if-then-else heuristics we have those based on walk
>     > of CFG (such as ones predicting paths to unlikely calls) and those should
>     > work well on switch statements.
>     >
>     > We discussed adding predictor combining code for BBs with more than 2
>     > successors. Martin, do you have some code for that?
> 
>     This has been discussed and we decided to reject that as we're unable to
>     apply DS theory as we can't evaluate what probability has a predictor for
>     edges different from the edge which it can evaluate. Note that with 2 edges
>     and probability x, one can calculate probability of the second edge
>     simply by 1 - x. That's not doable if one has > 2 edges.
> 
> 
> Did you consider splitting 1 - x equally among alternatives?

That's quite obvious simplification. I'll take a look one more time what was problematic
there.

Thanks,
Martin

>  
> 
>     That was reason
>     why I decided to use DF theory for such situations and wrote just simple
>     handling of very {un,}likely probabilities.
> 
>     Maybe I overlooked something in understanding of DF theory?
> 
>     Martin
> 
>     >
>     > I guess teaching even propbabilities about likely edges also works, but
>     > perhaps doing more general prediction combining would be cleaner...
>     >
>     > Honza
>     >
> 
>