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 <[email protected]>
Date: Thu, 21 Jul 2016 16:20:42 +0200
Subject: [PATCH] predict.c: merge multi-edges
gcc/testsuite/ChangeLog:
2016-07-21 Martin Liska <[email protected]>
* gcc.dg/predict-13.c: New test.
gcc/ChangeLog:
2016-07-21 Martin Liska <[email protected]>
* 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
