Re: [PATCH] Fix branch probability computation in do_compare_rtx_and_jump (PR tree-optimization/83081)

[Jakub Jelinek <jakub at redhat dot com>]

On Mon, Jan 22, 2018 at 02:43:50PM +0100, Jan Hubicka wrote:
> > But this looks incorrect, because that computes only the above c2 in
> > prob, not
> > second_prob.  It needs to be
> >   prob = cprob.invert () * prob / first_prob.invert ();
> > or
> >   prob *= cprob.invert () / first_prob.invert ();
> > or that
> >   prob = (prob - first_prob) / first_prob.invert ();
> > I had in the patch.  The last one looked to me like cheapest to compute.
> 
> Aha, I see.  Ok that makes sense to me now :)
> > 
> > > void profile_probability::split (profile_probability cprob,
> > > profile_probability *first_prob, profile_probability *second_prob)
> > 
> > This doesn't take prob as an argument, or should it be a method and take
> > prob as *this?  Couldn't it simply return first_prob and adjust itself,
> > so
> > profile_probability split (profile_probability cprob)
> > {
> >   profile_probability ret = *this * cprob;
> >   *this = (*this - prob) / ret.invert ();
> > // or *this = *this * cprob.invert () / ret.invert ();
> >   return ret;
> > }
> > ?
> 
> Yep, that is fine.

So like this if it passes bootstrap/regtest on {x86_64,i686}-linux?

Besides adding the new helper method and using it in the spots I've changed
plus the two you've mentioned, I had to do another fix - looking
at how TRUTH_ANDIF_EXPR is handled in dojump_1 and seeing Invalid sum
messages in predict-8.c's *.expand jump, I've realized that it also works
as is only for the discussed, i.e.
  if (x)
    goto t; // prob
transformed into:
  if (a)
    goto t; // first_prob
  if (b)
    goto t; // prob
but not for the case where and_them is true, where we have:
  if (c)
    goto dummy; // first_prob.invert ()
  if (d)
    goto t; // prob
dummy:
which needs to be handled similarly to the TRUTH_ANDIF_EXPR case.
At least when trying in gdb on predict-8.c various values of cprob
(1%, 15%, 50%, 62%, 98%) none of them generate the Invalid sum messages.

2018-01-22  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/83081
	* profile-count.h (profile_probability::split): New method.
	* dojump.c (do_jump_1) <case TRUTH_ANDIF_EXPR, case TRUTH_ORIF_EXPR>:
	Use profile_probability::split.
	(do_compare_rtx_and_jump): Fix adjustment of probabilities
	when splitting a single conditional jump into 2.

	* gcc.dg/predict-8.c: Adjust expected probability.

--- gcc/profile-count.h.jj	2018-01-19 19:41:52.910549618 +0100
+++ gcc/profile-count.h	2018-01-22 16:20:27.073096515 +0100
@@ -410,6 +410,19 @@ public:
       return *this;
     }
 
+  /* Split *THIS (ORIG) probability into 2 probabilities, such that
+     the returned one (FIRST) is *THIS * CPROB and *THIS is
+     adjusted (SECOND) so that FIRST + FIRST.invert () * SECOND
+     == ORIG.  */
+  profile_probability split (const profile_probability &cprob)
+    {
+      profile_probability ret = *this * cprob;
+      /* The following is equivalent to:
+	 *this = cprob.invert () * *this / ret.invert ();  */
+      *this = (*this - ret) / ret.invert ();
+      return ret;
+    }
+
   gcov_type apply (gcov_type val) const
     {
       if (*this == profile_probability::uninitialized ())
--- gcc/dojump.c.jj	2018-01-19 19:41:49.978548984 +0100
+++ gcc/dojump.c	2018-01-22 16:31:43.867185428 +0100
@@ -347,13 +347,11 @@ do_jump_1 (enum tree_code code, tree op0
         profile_probability op1_prob = profile_probability::uninitialized ();
         if (prob.initialized_p ())
           {
-            profile_probability false_prob = prob.invert ();
-            profile_probability op0_false_prob = false_prob.apply_scale (1, 2);
-	    profile_probability op1_false_prob = false_prob.apply_scale (1, 2)
-				/ op0_false_prob.invert ();
+	    op1_prob = prob.invert ();
+	    op0_prob = op1_prob.split (profile_probability::even ());
             /* Get the probability that each jump below is true.  */
-            op0_prob = op0_false_prob.invert ();
-            op1_prob = op1_false_prob.invert ();
+	    op0_prob = op0_prob.invert ();
+	    op1_prob = op1_prob.invert ();
           }
 	if (if_false_label == NULL)
           {
@@ -380,8 +378,8 @@ do_jump_1 (enum tree_code code, tree op0
         profile_probability op1_prob = profile_probability::uninitialized ();
         if (prob.initialized_p ())
           {
-            op0_prob = prob.apply_scale (1, 2);
-            op1_prob = prob.apply_scale (1, 2) / op0_prob.invert ();
+	    op1_prob = prob;
+	    op0_prob = op1_prob.split (profile_probability::even ());
 	  }
 	if (if_true_label == NULL)
 	  {
@@ -1120,16 +1118,27 @@ do_compare_rtx_and_jump (rtx op0, rtx op
 
 	  else
 	    {
-	      profile_probability first_prob = prob;
+	      profile_probability cprob
+		= profile_probability::guessed_always ();
 	      if (first_code == UNORDERED)
-		first_prob = profile_probability::guessed_always ().apply_scale
-				 (1, 100);
+		cprob = cprob.apply_scale (1, 100);
 	      else if (first_code == ORDERED)
-		first_prob = profile_probability::guessed_always ().apply_scale
-				 (99, 100);
+		cprob = cprob.apply_scale (99, 100);
+	      else
+		cprob = profile_probability::even ();
+	      /* We want to split:
+		 if (x) goto t; // prob;
+		 into
+		 if (a) goto t; // first_prob;
+		 if (b) goto t; // prob;
+		 such that the overall probability of jumping to t
+		 remains the same and first_prob is prob * cprob.  */
 	      if (and_them)
 		{
 		  rtx_code_label *dest_label;
+		  prob = prob.invert ();
+		  profile_probability first_prob = prob.split (cprob).invert ();
+		  prob = prob.invert ();
 		  /* If we only jump if true, just bypass the second jump.  */
 		  if (! if_false_label)
 		    {
@@ -1143,8 +1152,11 @@ do_compare_rtx_and_jump (rtx op0, rtx op
 					   size, dest_label, NULL, first_prob);
 		}
               else
-                do_compare_rtx_and_jump (op0, op1, first_code, unsignedp, mode,
-					 size, NULL, if_true_label, first_prob);
+		{
+		  profile_probability first_prob = prob.split (cprob);
+		  do_compare_rtx_and_jump (op0, op1, first_code, unsignedp, mode,
+					   size, NULL, if_true_label, first_prob);
+		}
 	    }
 	}
 
--- gcc/testsuite/gcc.dg/predict-8.c.jj	2017-10-12 20:51:33.192974887 +0200
+++ gcc/testsuite/gcc.dg/predict-8.c	2018-01-22 16:18:09.528071106 +0100
@@ -8,4 +8,4 @@ int foo(float a, float b) {
     return 2;
 }
 
-/* { dg-final { scan-rtl-dump-times "99.0. .guessed" 2 "expand"} } */
+/* { dg-final { scan-rtl-dump-times "65.\[34]. .guessed" 2 "expand"} } */

	Jakub