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 <mli...@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 <mli...@suse.cz>
* gcc.dg/predict-13.c: New test.
gcc/ChangeLog:
2016-07-21 Martin Liska <mli...@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
