[PATCH] Improve predictions for hot and cold labels ([[likely]], [[unlikely]]).

[Martin Liška <mliska at suse dot cz>]

Hi.

This patch is a reaction to Jason's commit where he introduced new C++ attributes.
First I would like to align cold/hot to __builtin_expect, so I adjusted probability
and made the predictors first match predictors.

Second I fixed how we consider the predictors in switch statements, so that
we can correctly predict situation in predict-3.

Honza is fine with the patch, I'll install it later if there are no objections.
Survives tests and bootstrap on xc86_64-linux-gnu.

Martin

gcc/ChangeLog:

2018-11-29  Martin Liska  <mliska@suse.cz>

	* predict.c (set_even_probabilities): Include also
	unlikely_count in calculation.
	(combine_predictions_for_bb): Consider also HOT and
	COLD labels predictions.
	* predict.def (PRED_HOT_LABEL): Move it just after
	__builtin_expect_with_probability predictor.
	(PRED_COLD_LABEL): Likewise.

gcc/testsuite/ChangeLog:

2018-11-29  Martin Liska  <mliska@suse.cz>

	* g++.dg/predict-2.C: New test.
	* g++.dg/predict-3.C: New test.
	* g++.dg/predict-4.C: New test.
	* gcc.dg/tree-ssa/attr-hotcold-2.c: Adjust test-case.
---
 gcc/predict.c                                  | 15 ++++++++++++---
 gcc/predict.def                                | 15 ++++++++-------
 gcc/testsuite/g++.dg/predict-2.C               | 16 ++++++++++++++++
 gcc/testsuite/g++.dg/predict-3.C               | 17 +++++++++++++++++
 gcc/testsuite/g++.dg/predict-4.C               | 17 +++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c |  4 ++--
 6 files changed, 72 insertions(+), 12 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/predict-2.C
 create mode 100644 gcc/testsuite/g++.dg/predict-3.C
 create mode 100644 gcc/testsuite/g++.dg/predict-4.C


diff --git a/gcc/predict.c b/gcc/predict.c
index 5ad252c2d39..81dbb67da4e 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -878,11 +878,18 @@ set_even_probabilities (basic_block bb,
 	    profile_probability prob
 	      = profile_probability::from_reg_br_prob_base (p);
 	    profile_probability remainder = prob.invert ();
+	    remainder -= profile_probability::very_unlikely ()
+	      .apply_scale (unlikely_count, 1);
+	    int count = nedges - unlikely_count - 1;
+	    gcc_assert (count >= 0);
+	    profile_probability even = remainder.apply_scale (1, count);
 
 	    if (prediction->ep_edge == e)
 	      e->probability = prob;
+	    else if (unlikely_edges != NULL && unlikely_edges->contains (e))
+	      e->probability = profile_probability::very_unlikely ();
 	    else
-	      e->probability = remainder.apply_scale (1, nedges - 1);
+	      e->probability = even;
 	  }
 	else
 	  e->probability = profile_probability::never ();
@@ -1217,10 +1224,12 @@ combine_predictions_for_bb (basic_block bb, bool dry_run)
       if (preds)
 	for (pred = *preds; pred; pred = pred->ep_next)
 	  {
-	    if (pred->ep_probability <= PROB_VERY_UNLIKELY)
+	    if (pred->ep_probability <= PROB_VERY_UNLIKELY
+		|| pred->ep_predictor == PRED_COLD_LABEL)
 	      unlikely_edges.add (pred->ep_edge);
 	    if (pred->ep_probability >= PROB_VERY_LIKELY
-		|| pred->ep_predictor == PRED_BUILTIN_EXPECT)
+		|| pred->ep_predictor == PRED_BUILTIN_EXPECT
+		|| pred->ep_predictor == PRED_HOT_LABEL)
 	      likely_edges.add (pred);
 	  }
 
diff --git a/gcc/predict.def b/gcc/predict.def
index e2a56f95955..27d0e4dc6f9 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -78,6 +78,14 @@ DEF_PREDICTOR (PRED_BUILTIN_EXPECT_WITH_PROBABILITY,
 	       "__builtin_expect_with_probability", PROB_UNINITIALIZED,
 	       PRED_FLAG_FIRST_MATCH)
 
+/* Branches to hot labels are likely.  */
+DEF_PREDICTOR (PRED_HOT_LABEL, "hot label", HITRATE (90),
+	       PRED_FLAG_FIRST_MATCH)
+
+/* Branches to cold labels are extremely unlikely.  */
+DEF_PREDICTOR (PRED_COLD_LABEL, "cold label", HITRATE (90),
+	       PRED_FLAG_FIRST_MATCH)
+
 /* Use number of loop iterations guessed by the contents of the loop.  */
 DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations",
 	       PROB_UNINITIALIZED, PRED_FLAG_FIRST_MATCH)
@@ -171,13 +179,6 @@ DEF_PREDICTOR (PRED_LOOP_GUARD, "loop guard", HITRATE (73), 0)
 DEF_PREDICTOR (PRED_LOOP_GUARD_WITH_RECURSION, "loop guard with recursion",
 	       HITRATE (85), 0)
 
-/* Branches to hot labels are likely.  */
-DEF_PREDICTOR (PRED_HOT_LABEL, "hot label", HITRATE (85), 0)
-
-/* Branches to cold labels are extremely unlikely.  */
-DEF_PREDICTOR (PRED_COLD_LABEL, "cold label", PROB_VERY_LIKELY,
-	       PRED_FLAG_FIRST_MATCH)
-
 /* The following predictors are used in Fortran. */
 
 /* Branch leading to an integer overflow are extremely unlikely.  */
diff --git a/gcc/testsuite/g++.dg/predict-2.C b/gcc/testsuite/g++.dg/predict-2.C
new file mode 100644
index 00000000000..1e0ac1d2c48
--- /dev/null
+++ b/gcc/testsuite/g++.dg/predict-2.C
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate -std=c++11" } */
+
+int a, b, c;
+
+void
+bar()
+{
+  if (a == 123)
+    [[likely]] c = 5;
+  else
+    c = 5;
+}
+
+/* { dg-final { scan-tree-dump "first match heuristics: 90.00%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "hot label heuristics of edge .*->.*: 90.00%" "profile_estimate"} } */
diff --git a/gcc/testsuite/g++.dg/predict-3.C b/gcc/testsuite/g++.dg/predict-3.C
new file mode 100644
index 00000000000..cf3373861b9
--- /dev/null
+++ b/gcc/testsuite/g++.dg/predict-3.C
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate -std=c++11" } */
+
+int a, b, c;
+
+void
+bar ()
+{
+  switch (a)
+  {
+    case 3: __builtin_puts("a"); break;
+    case 42: __builtin_puts("e"); break;
+    [[likely]] case 333: __builtin_puts("i"); break;
+  } 
+}
+
+/* { dg-final { scan-tree-dump "default.*3.33%.*case 3.*3.33%.*case 42.*3.33%.*case 333.*90.00%" "profile_estimate"} } */
diff --git a/gcc/testsuite/g++.dg/predict-4.C b/gcc/testsuite/g++.dg/predict-4.C
new file mode 100644
index 00000000000..ab40b48a340
--- /dev/null
+++ b/gcc/testsuite/g++.dg/predict-4.C
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate -std=c++11" } */
+
+int a, b, c;
+
+void
+bar ()
+{
+  switch (a)
+  {
+    case 3: __builtin_puts("a"); break;
+    [[unlikely]] case 42: __builtin_puts("e"); break;
+    [[likely]] case 333: __builtin_puts("i"); break;
+  } 
+}
+
+/* { dg-final { scan-tree-dump "default.*4.98%.*case 3.*4.98%.*case 42.*0.05%.*case 333.*90.00%" "profile_estimate"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c b/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
index 17526113d4b..3206d7d5e09 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
@@ -19,9 +19,9 @@ void f(int x, int y)
 
 /* { dg-final { scan-tree-dump-times "hot label heuristics" 1 "profile_estimate" } } */
 /* { dg-final { scan-tree-dump-times "cold label heuristics" 1 "profile_estimate" } } */
-/* { dg-final { scan-tree-dump-times "combined heuristics: 0\\\..*" 1 "profile_estimate" } } */
+/* { dg-final { scan-tree-dump-times "combined heuristics: 10.00%" 1 "profile_estimate" } } */
 
 /* Note: we're attempting to match some number > 6000, i.e. > 60%.
    The exact number ought to be tweekable without having to juggle
    the testcase around too much.  */
-/* { dg-final { scan-tree-dump-times "combined heuristics: \[6-9\]\[0-9\]\\\..*" 1 "profile_estimate" } } */
+/* { dg-final { scan-tree-dump-times "combined heuristics: 90.00%" 1 "profile_estimate" } } */