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]

[PATCH] predict.c: merge multi-edges


Hi.

Following patch enhances prediction for basic blocks with >2 successor edges.
Currently, even probability is set and the patch considers unlikely edges, where
even probability is set for the remaining edges.

I run SPEC2006 benchmark, where aforementioned BBs have following predictor distribution:
    48   loop guard with recursion
    127   continue
    196   null return
    203   loop exit with recursion
    284   negative return
    455   recursive call
    659   extra loop exit
    664   noreturn call
    956   loop exit
   1088   const return
   2110   loop guard
  10557   early return (on trees)
  40765   call

I would not make much sense to do a more sophisticated predictor merging because
majority of predictors are not so much strong (reliable). Thus considering just
'noreturn call' (unlikely) worth for handling.

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

Ready to be installed?
Martin
>From f572b283801d99e251f95b960cbd444968b3a73d 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                     | 66 +++++++++++++++++++++++++++++++++------
 gcc/testsuite/gcc.dg/predict-13.c | 24 ++++++++++++++
 2 files changed, 80 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..41b87dd 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -785,20 +785,33 @@ 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
+   evel 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;
   edge_iterator ei;
 
+  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;
   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 +1081,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]