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]

Re: [PATCH] predict.c: merge multi-edges


On 07/22/2016 12:53 PM, Segher Boessenkool wrote:
> Hi Martin,
> 
> On Fri, Jul 22, 2016 at 10:17:51AM +0200, Martin Liška wrote:
>>  /* We can not predict the probabilities of outgoing edges of bb.  Set them
>> -   evenly and hope for the best.  */
>> +   evenly and hope for the best.  If UNLIKELY_EDGES is not null, distribute
>> +   evel probability for all edges not mentioned in the set.  These edges
>> +   are given PROB_VERY_UNLIKELY probability.  */
> 
> Typo ("evel");

Hello Segher.

The typo is fixed.

> 
>> +  unsigned unlikely_count = unlikely_edges ? unlikely_edges->elements () : 0;
>> +
>>    FOR_EACH_EDGE (e, ei, bb->succs)
>>      if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
>>        nedges ++;
>> +
>> +  unsigned c = nedges - unlikely_count;
> 
> What prevents c from becoming 0?  The sum of outgoing edge probabilities
> will be very small then (unless there are very many such noreturn edges,
> then the sum is too big, instead).

You are right, I'm sending second version where I set even probabilities
in case of all edges are PROB_VERY_UNLIKELY. However, I was unable to come
up with a test-case for that:

int main(int argc, char **argv)
{
  switch (argc)
    {
    case 1:
      __builtin_unreachable();
    case 4:
      __builtin_unreachable();
    default:
      __builtin_unreachable();
    }

  return 10;
}

No predictors are set as 'has_return_edges' == false in tree_bb_level_predictions.

I'm going to re-trigger tests for the patch.

Martin

> 
>>    FOR_EACH_EDGE (e, ei, bb->succs)
>>      if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
>> -      e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
>> +      {
>> +	if (unlikely_edges != NULL && unlikely_edges->contains (e))
>> +	  e->probability = PROB_VERY_UNLIKELY;
>> +	else
>> +	  e->probability = (REG_BR_PROB_BASE + c / 2) / c;
>> +      }
>>      else
>>        e->probability = 0;
>>  }
> 
> Even in the normal case, the sum of probabilities will not be almost 1
> this way (almost REG_BR_PROB_BASE), but somewhat bigger.
> 
> 
> Segher
> 

>From f746848bec44877173bbe9ea3b04bdabe947119c Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Thu, 21 Jul 2016 16:20:42 +0200
Subject: [PATCH] predict.c: merge multi-edges

gcc/testsuite/ChangeLog:

2016-07-21  Martin Liska  <mliska@suse.cz>

	* gcc.dg/predict-13.c: New test.

gcc/ChangeLog:

2016-07-21  Martin Liska  <mliska@suse.cz>

	* predict.c (set_even_probabilities): Handle unlikely edges.
	(combine_predictions_for_bb): Likewise.
---
 gcc/predict.c                     | 73 +++++++++++++++++++++++++++++++++------
 gcc/testsuite/gcc.dg/predict-13.c | 24 +++++++++++++
 2 files changed, 87 insertions(+), 10 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/predict-13.c

diff --git a/gcc/predict.c b/gcc/predict.c
index 7fbd404..ca320cd 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -785,9 +785,13 @@ dump_prediction (FILE *file, enum br_predictor predictor, int probability,
 }
 
 /* We can not predict the probabilities of outgoing edges of bb.  Set them
-   evenly and hope for the best.  */
+   evenly and hope for the best.  If UNLIKELY_EDGES is not null, distribute
+   even probability for all edges not mentioned in the set.  These edges
+   are given PROB_VERY_UNLIKELY probability.  */
+
 static void
-set_even_probabilities (basic_block bb)
+set_even_probabilities (basic_block bb,
+			hash_set<edge> *unlikely_edges = NULL)
 {
   int nedges = 0;
   edge e;
@@ -796,9 +800,25 @@ set_even_probabilities (basic_block bb)
   FOR_EACH_EDGE (e, ei, bb->succs)
     if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
       nedges ++;
+
+  /* Make the distribution even if all edges are unlikely.  */
+  unsigned unlikely_count = unlikely_edges ? unlikely_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->flags & (EDGE_EH | EDGE_FAKE)))
-      e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
+      {
+	if (unlikely_edges != NULL && unlikely_edges->contains (e))
+	  e->probability = PROB_VERY_UNLIKELY;
+	else
+	  e->probability = (REG_BR_PROB_BASE + c / 2) / c;
+      }
     else
       e->probability = 0;
 }
@@ -1068,18 +1088,51 @@ combine_predictions_for_bb (basic_block bb, bool dry_run)
 
   /* When there is no successor or only one choice, prediction is easy.
 
-     We are lazy for now and predict only basic blocks with two outgoing
-     edges.  It is possible to predict generic case too, but we have to
-     ignore first match heuristics and do more involved combining.  Implement
-     this later.  */
+     When we have a basic block with more than 2 successors, the situation
+     is more complicated as DS theory cannot be used literally.
+     More precisely, let's assume we predicted edge e1 with probability p1,
+     thus: m1({b1}) = p1.  As we're going to combine more than 2 edges, we
+     need to find probability of e.g. m1({b2}), which we don't know.
+     The only approximation is to equally distribute 1-p1 to all edges
+     different from b1.
+
+     According to numbers we've got from SPEC2006 benchark, there's only
+     one interesting reliable predictor (noreturn call), which can be
+     handled with a bit easier approach.  */
   if (nedges != 2)
     {
+      hash_set<edge> unlikely_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
+	 there's no such probability in SPEC2006 benchmark.  */
+      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 (!bb->count && !dry_run)
-	set_even_probabilities (bb);
+	set_even_probabilities (bb, &unlikely_edges);
       clear_bb_predictions (bb);
       if (dump_file)
-	fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
-		 nedges, bb->index);
+	{
+	  fprintf (dump_file, "Predictions for bb %i\n", bb->index);
+	  if (unlikely_edges.elements () == 0)
+	    fprintf (dump_file,
+		     "%i edges in bb %i predicted to even probabilities\n",
+		     nedges, bb->index);
+	  else
+	    {
+	      fprintf (dump_file,
+		       "%i edges in bb %i predicted with some unlikely edges\n",
+		       nedges, bb->index);
+	      FOR_EACH_EDGE (e, ei, bb->succs)
+		if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
+		  dump_prediction (dump_file, PRED_COMBINED, e->probability,
+		   bb, REASON_NONE, e);
+	    }
+	}
       return;
     }
 
diff --git a/gcc/testsuite/gcc.dg/predict-13.c b/gcc/testsuite/gcc.dg/predict-13.c
new file mode 100644
index 0000000..df82b7e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-13.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+int main(int argc, char **argv)
+{
+  switch (argc)
+    {
+    case 1:
+      return 1;
+    case 2:
+      return 2;
+    case 3:
+      __builtin_unreachable();
+    case 4:
+      __builtin_unreachable();
+    default:
+      return 5;
+    }
+
+  return 10;
+}
+
+/* { dg-final { scan-tree-dump-times "combined heuristics of edge\[^:\]*: 33.3%" 3 "profile_estimate"} } */
+/* { dg-final { scan-tree-dump-times "combined heuristics of edge\[^:\]*: 0.0%" 2 "profile_estimate"} } */
-- 
2.9.0


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