Fix merging of value predictors

  Hi,
expr_expected_value is doing some guesswork when it is merging two or more
independent value predictions either in PHI node or in binary operation.
Since we do not know how the predictions interact with each other, we can
not really merge the values precisely.

The previous logic merged the prediciton and picked the later predictor
(since predict.def is sorted by reliability). This however leads to troubles
with __builtin_expect_with_probability since it is special cased as a predictor
with custom probabilities.  If this predictor is downgraded to something else,
we ICE since we have prediction given by predictor that is not expected
to have customprobability.

This patch fixies it by inventing new predictors PRED_COMBINED_VALUE_PREDICTIONS
and PRED_COMBINED_VALUE_PREDICTIONS_PHI which also allows custom values but
are considered less reliable then __builtin_expect_with_probability (they
are combined by ds theory rather then by first match).  This is less likely
going to lead to very stupid decisions if combining does not work as expected.

I also updated the code to be bit more careful about merging values and do not
downgrade the precision when unnecesary (as tested by new testcases).

Bootstrapped/regtested x86_64-linux, will commit it tomorrow if there are
no complains.

2024-01-17  Jan Hubicka <jh@suse.cz>
	    Jakub Jelinek <jakub@redhat.com>

	PR tree-optimization/110852

gcc/ChangeLog:

	* predict.cc (expr_expected_value_1):
	(get_predictor_value):
	* predict.def (PRED_COMBINED_VALUE_PREDICTIONS):
	(PRED_COMBINED_VALUE_PREDICTIONS_PHI):

gcc/testsuite/ChangeLog:

	* gcc.dg/predict-18.c:
	* gcc.dg/predict-23.c: New test.
	* gcc.dg/tree-ssa/predict-1.c: New test.
	* gcc.dg/tree-ssa/predict-2.c: New test.
	* gcc.dg/tree-ssa/predict-3.c: New test.
  

On Wed, Jan 17, 2024 at 01:45:18PM +0100, Jan Hubicka wrote:
> Hi,
> expr_expected_value is doing some guesswork when it is merging two or more
> independent value predictions either in PHI node or in binary operation.
> Since we do not know how the predictions interact with each other, we can
> not really merge the values precisely.
> 
> The previous logic merged the prediciton and picked the later predictor
> (since predict.def is sorted by reliability). This however leads to troubles
> with __builtin_expect_with_probability since it is special cased as a predictor
> with custom probabilities.  If this predictor is downgraded to something else,
> we ICE since we have prediction given by predictor that is not expected
> to have customprobability.
> 
> This patch fixies it by inventing new predictors PRED_COMBINED_VALUE_PREDICTIONS
> and PRED_COMBINED_VALUE_PREDICTIONS_PHI which also allows custom values but
> are considered less reliable then __builtin_expect_with_probability (they
> are combined by ds theory rather then by first match).  This is less likely
> going to lead to very stupid decisions if combining does not work as expected.
> 
> I also updated the code to be bit more careful about merging values and do not
> downgrade the precision when unnecesary (as tested by new testcases).
> 
> Bootstrapped/regtested x86_64-linux, will commit it tomorrow if there are
> no complains.
> 
> 2024-01-17  Jan Hubicka <jh@suse.cz>
> 	    Jakub Jelinek <jakub@redhat.com>

2 spaces before < rather than 1.
> 
> 	PR tree-optimization/110852
> 
> gcc/ChangeLog:
> 
> 	* predict.cc (expr_expected_value_1):
> 	(get_predictor_value):
> 	* predict.def (PRED_COMBINED_VALUE_PREDICTIONS):
> 	(PRED_COMBINED_VALUE_PREDICTIONS_PHI):
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.dg/predict-18.c:

Please fill in what has changed, both for predict-18.c and predict.{cc,def}
changes.

> @@ -2613,24 +2658,40 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
>  	  if (!nop1)
>  	    nop1 = op1;
>  	 }
> +      /* We already checked if folding one of arguments to constant is good
> +	 enough.  Consequently failing to fold both means that we will not
> +	 succeed determinging the value.  */

s/determinging/determining/

Otherwise LGTM.

	Jakub
  

> 
> Please fill in what has changed, both for predict-18.c and predict.{cc,def}
> changes.

Sorry, I re-generated the patch after fixing some typos and forgot to
copy over the changelog.
> 
> > @@ -2613,24 +2658,40 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
> >  	  if (!nop1)
> >  	    nop1 = op1;
> >  	 }
> > +      /* We already checked if folding one of arguments to constant is good
> > +	 enough.  Consequently failing to fold both means that we will not
> > +	 succeed determinging the value.  */
> 
> s/determinging/determining/
Fixed.  I am re-testing the following and will commit if it succeeds (on
x86_64-linux)

2024-01-17  Jan Hubicka  <jh@suse.cz>
	    Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/110852

gcc/ChangeLog:

	* predict.cc (expr_expected_value_1): Fix profile merging of PHI and
	binary operations
	(get_predictor_value): Handle PRED_COMBINED_VALUE_PREDICTIONS and
	PRED_COMBINED_VALUE_PREDICTIONS_PHI
	* predict.def (PRED_COMBINED_VALUE_PREDICTIONS): New predictor.
	(PRED_COMBINED_VALUE_PREDICTIONS_PHI): New predictor.

gcc/testsuite/ChangeLog:

	* gcc.dg/predict-18.c: Update template to expect combined value predictor.
	* gcc.dg/predict-23.c: New test.
	* gcc.dg/tree-ssa/predict-1.c: New test.
	* gcc.dg/tree-ssa/predict-2.c: New test.
	* gcc.dg/tree-ssa/predict-3.c: New test.

diff --git a/gcc/predict.cc b/gcc/predict.cc
index 84cbe3ffc61..c1c48bf3df1 100644
--- a/gcc/predict.cc
+++ b/gcc/predict.cc
@@ -2404,44 +2404,78 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
       if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
 	return NULL;
 
-      if (gimple_code (def) == GIMPLE_PHI)
+      if (gphi *phi = dyn_cast <gphi *> (def))
 	{
 	  /* All the arguments of the PHI node must have the same constant
 	     length.  */
-	  int i, n = gimple_phi_num_args (def);
-	  tree val = NULL, new_val;
+	  int i, n = gimple_phi_num_args (phi);
+	  tree val = NULL;
+	  bool has_nonzero_edge = false;
+
+	  /* If we already proved that given edge is unlikely, we do not need
+	     to handle merging of the probabilities.  */
+	  for (i = 0; i < n && !has_nonzero_edge; i++)
+	    {
+	      tree arg = PHI_ARG_DEF (phi, i);
+	      if (arg == PHI_RESULT (phi))
+		continue;
+	      profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
+	      if (!cnt.initialized_p () || cnt.nonzero_p ())
+		has_nonzero_edge = true;
+	    }
 
 	  for (i = 0; i < n; i++)
 	    {
-	      tree arg = PHI_ARG_DEF (def, i);
+	      tree arg = PHI_ARG_DEF (phi, i);
 	      enum br_predictor predictor2;
 
-	      /* If this PHI has itself as an argument, we cannot
-		 determine the string length of this argument.  However,
-		 if we can find an expected constant value for the other
-		 PHI args then we can still be sure that this is
-		 likely a constant.  So be optimistic and just
-		 continue with the next argument.  */
-	      if (arg == PHI_RESULT (def))
+	      /* Skip self-referring parameters, since they does not change
+		 expected value.  */
+	      if (arg == PHI_RESULT (phi))
 		continue;
 
+	      /* Skip edges which we already predicted as executing
+		 zero times.  */
+	      if (has_nonzero_edge)
+		{
+		  profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
+		  if (cnt.initialized_p () && !cnt.nonzero_p ())
+		    continue;
+		}
 	      HOST_WIDE_INT probability2;
-	      new_val = expr_expected_value (arg, visited, &predictor2,
-					     &probability2);
+	      tree new_val = expr_expected_value (arg, visited, &predictor2,
+						  &probability2);
+	      /* If we know nothing about value, give up.  */
+	      if (!new_val)
+		return NULL;
 
-	      /* It is difficult to combine value predictors.  Simply assume
-		 that later predictor is weaker and take its prediction.  */
-	      if (*predictor < predictor2)
+	      /* If this is a first edge, trust its prediction.  */
+	      if (!val)
 		{
+		  val = new_val;
 		  *predictor = predictor2;
 		  *probability = probability2;
+		  continue;
 		}
-	      if (!new_val)
-		return NULL;
-	      if (!val)
-		val = new_val;
-	      else if (!operand_equal_p (val, new_val, false))
+	      /* If there are two different values, give up.  */
+	      if (!operand_equal_p (val, new_val, false))
 		return NULL;
+
+	      int p1 = get_predictor_value (*predictor, *probability);
+	      int p2 = get_predictor_value (predictor2, probability2);
+	      /* If both predictors agree, it does not matter from which
+		 edge we enter the basic block.  */
+	      if (*predictor == predictor2 && p1 == p2)
+		continue;
+	      /* The general case has no precise solution, since we do not
+		 know probabilities of incomming edges, yet.
+		 Still if value is predicted over all incomming edges, we
+		 can hope it will be indeed the case.  Conservatively
+		 downgrade prediction quality (so first match merging is not
+		 performed) and take least successful prediction.  */
+
+	      *predictor = PRED_COMBINED_VALUE_PREDICTIONS_PHI;
+	      *probability = MIN (p1, p2);
 	    }
 	  return val;
 	}
@@ -2585,6 +2619,10 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
       tree res;
       tree nop0 = op0;
       tree nop1 = op1;
+
+      /* First handle situation where single op is enough to determine final
+	 value.  In this case we can do better job by avoiding the prediction
+	 merging.  */
       if (TREE_CODE (op0) != INTEGER_CST)
 	{
 	  /* See if expected value of op0 is good enough to determine the result.  */
@@ -2592,12 +2630,18 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
 	  if (nop0
 	      && (res = fold_build2 (code, type, nop0, op1)) != NULL
 	      && TREE_CODE (res) == INTEGER_CST)
+	    /* We are now getting conservative probability.  Consider for
+	       example:
+	          op0 * op1
+	       If op0 is 0 with probability p, then we will ignore the
+	       posibility that op0 != 0 and op1 == 0.  It does not seem to be
+	       worthwhile to downgrade prediciton quality for this.  */
 	    return res;
 	  if (!nop0)
 	    nop0 = op0;
 	 }
-      enum br_predictor predictor2;
-      HOST_WIDE_INT probability2;
+      enum br_predictor predictor2 = PRED_UNCONDITIONAL;
+      HOST_WIDE_INT probability2 = -1;
       if (TREE_CODE (op1) != INTEGER_CST)
 	{
 	  /* See if expected value of op1 is good enough to determine the result.  */
@@ -2606,6 +2650,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
 	      && (res = fold_build2 (code, type, op0, nop1)) != NULL
 	      && TREE_CODE (res) == INTEGER_CST)
 	    {
+	      /* Similarly as above we now get conservative probability.  */
 	      *predictor = predictor2;
 	      *probability = probability2;
 	      return res;
@@ -2613,24 +2658,40 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
 	  if (!nop1)
 	    nop1 = op1;
 	 }
+      /* We already checked if folding one of arguments to constant is good
+	 enough.  Consequently failing to fold both means that we will not
+	 succeed determining the value.  */
       if (nop0 == op0 || nop1 == op1)
 	return NULL;
       /* Finally see if we have two known values.  */
       res = fold_build2 (code, type, nop0, nop1);
-      if (TREE_CODE (res) == INTEGER_CST
-	  && TREE_CODE (nop0) == INTEGER_CST
-	  && TREE_CODE (nop1) == INTEGER_CST)
+      if (TREE_CODE (res) == INTEGER_CST)
 	{
-	  /* Combine binary predictions.  */
-	  if (*probability != -1 || probability2 != -1)
+	  HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
+	  HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
+
+	  /* If one of predictions is sure, such as PRED_UNCONDITIONAL, we
+	     can ignore it.  */
+	  if (p2 == PROB_ALWAYS)
+	    return res;
+	  if (p1 == PROB_ALWAYS)
 	    {
-	      HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
-	      HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
-	      *probability = RDIV (p1 * p2, REG_BR_PROB_BASE);
+	      *predictor = predictor2;
+	      *probability = probability2;
+	      return res;
 	    }
-
-	  if (predictor2 < *predictor)
-	    *predictor = predictor2;
+	  /* Combine binary predictions.
+	     Since we do not know about independence of predictors, we
+	     can not determine value precisely.  */
+	  *probability = RDIV (p1 * p2, REG_BR_PROB_BASE);
+	  /* If we no longer track useful information, give up.  */
+	  if (!*probability)
+	    return NULL;
+	  /* Otherwise mark that prediction is a result of combining
+	     different heuristics, since we do not want it to participate
+	     in first match merging.  It is no longer reliable since
+	     we do not know if the probabilities are indpenendet.  */
+	  *predictor = PRED_COMBINED_VALUE_PREDICTIONS;
 
 	  return res;
 	}
@@ -2690,6 +2751,8 @@ get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
     {
     case PRED_BUILTIN_EXPECT:
     case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
+    case PRED_COMBINED_VALUE_PREDICTIONS_PHI:
+    case PRED_COMBINED_VALUE_PREDICTIONS:
       gcc_assert (probability != -1);
       return probability;
     default:
diff --git a/gcc/predict.def b/gcc/predict.def
index 10cd73a9026..0b567842361 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -94,6 +94,16 @@ DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations",
 DEF_PREDICTOR (PRED_LOOP_ITERATIONS_MAX, "guessed loop iterations",
 	       PROB_UNINITIALIZED, PRED_FLAG_FIRST_MATCH)
 
+/* Prediction which is an outcome of combining multiple value predictions.  */
+DEF_PREDICTOR (PRED_COMBINED_VALUE_PREDICTIONS,
+	       "combined value predictions", PROB_UNINITIALIZED, 0)
+
+/* Prediction which is an outcome of combining multiple value predictions
+   on PHI statement (this is less accurate since we do not know reverse
+   edge probabilities at that time).  */
+DEF_PREDICTOR (PRED_COMBINED_VALUE_PREDICTIONS_PHI,
+	       "combined value predictions", PROB_UNINITIALIZED, 0)
+
 /* Branch containing goto is probably not taken.  */
 DEF_PREDICTOR (PRED_CONTINUE, "continue", HITRATE (67), 0)
 
diff --git a/gcc/testsuite/gcc.dg/predict-18.c b/gcc/testsuite/gcc.dg/predict-18.c
index 073e742d849..718eaf33c39 100644
--- a/gcc/testsuite/gcc.dg/predict-18.c
+++ b/gcc/testsuite/gcc.dg/predict-18.c
@@ -33,9 +33,9 @@ void foo (int a, int b)
     global++;
 }
 
-/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 54.00%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "combined value predictions heuristics of edge .*->.*: 54.00%" "profile_estimate"} } */
 /* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 77.70%" "profile_estimate"} } */
-/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 98.96%" "profile_estimate"} } */
-/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 71.99%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "combined value predictions heuristics of edge .*->.*: 98.96%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "combined value predictions heuristics of edge .*->.*: 71.99%" "profile_estimate"} } */
 /* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 40.00%" "profile_estimate"} } */
 /* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 35.01%" "profile_estimate"} } */
diff --git a/gcc/testsuite/gcc.dg/predict-23.c b/gcc/testsuite/gcc.dg/predict-23.c
new file mode 100644
index 00000000000..7700bb34a07
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-23.c
@@ -0,0 +1,11 @@
+/* PR tree-optimization/110852 */
+/* { dg-options "-O1 -fno-tree-fre" } */
+
+unsigned i, j;
+
+unsigned
+foo (void)
+{
+  unsigned u = __builtin_expect (i, 0);
+  return 4 - (u < (j || i));
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/predict-1.c b/gcc/testsuite/gcc.dg/tree-ssa/predict-1.c
new file mode 100644
index 00000000000..1824643d75d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/predict-1.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+int test2();
+int
+test (int a, int b)
+{
+	if (__builtin_expect_with_probability (a, 0, 0.4)/__builtin_expect_with_probability (b, 5, 0.2))
+		test2();
+}
+/* { dg-final { scan-tree-dump-times "first match heuristics: 60.00" 1 "profile_estimate"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/predict-2.c b/gcc/testsuite/gcc.dg/tree-ssa/predict-2.c
new file mode 100644
index 00000000000..80c84f1b235
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/predict-2.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+int test2();
+int
+test (int a, int b)
+{
+	if (__builtin_expect_with_probability (a, 0, 0.8)+__builtin_expect_with_probability (b, 5, 0.9) == 5)
+		test2();
+}
+/* Combining two predictions together can not be done precisely, so check that result is DS theory.  */
+/* { dg-final { scan-tree-dump-times "combined value predictions heuristics of edge .->.: 72.00" 1 "profile_estimate"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/predict-3.c b/gcc/testsuite/gcc.dg/tree-ssa/predict-3.c
new file mode 100644
index 00000000000..9da58861854
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/predict-3.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+int test2();
+int
+test (int p, int a, int b, int c)
+{
+	int d;
+	if (p)
+	   d = __builtin_expect_with_probability (a, 0, 0.8) * b;
+	else
+	   d = __builtin_expect_with_probability (a, 0, 0.8) * c;
+	if (d)
+		test2();
+}
+/* { dg-final { scan-tree-dump-times "first match heuristics: 20.00" 1 "profile_estimate"} } */
  

On 17 January 2024 14:20:49 CET, Jan Hubicka <hubicka@ucw.cz> wrote:

>--- a/gcc/predict.def
>+++ b/gcc/predict.def
>@@ -94,6 +94,16 @@ DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations",
> DEF_PREDICTOR (PRED_LOOP_ITERATIONS_MAX, "guessed loop iterations",
> 	       PROB_UNINITIALIZED, PRED_FLAG_FIRST_MATCH)
> 
>+/* Prediction which is an outcome of combining multiple value predictions.  */
>+DEF_PREDICTOR (PRED_COMBINED_VALUE_PREDICTIONS,
>+	       "combined value predictions", PROB_UNINITIALIZED, 0)
>+
>+/* Prediction which is an outcome of combining multiple value predictions
>+   on PHI statement (this is less accurate since we do not know reverse
>+   edge probabilities at that time).  */
>+DEF_PREDICTOR (PRED_COMBINED_VALUE_PREDICTIONS_PHI,
>+	       "combined value predictions", PROB_UNINITIALIZED, 0)
>+

Do you want to add "phi" somewhere to the latter (to distinguish them in the dumps)?

thanks