This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Hi!

This PR is about a certain test FAILing on arm, because it scans for
"Invalid sum ..." message in the *.ira dump, but recent GCC versions have
that message in there; not introduced by IRA though, but all the way from
expansion.  We are expanding:
  <bb 2> [local count: 1073741825]:
  _1 = *x_3(D);
  if (_1 u>= 0.0)
    goto <bb 4>; [99.95%]
  else
    goto <bb 3>; [0.05%]

  <bb 3> [local count: 536864]:
  sqrtf (_1);
and do_compare_rtx_and_jump decides to split the single _1 u>= 0.0
comparison into two.  The expectation is that the basic block counts stay
the same, so if bb 3's count is 0.05% times bb 2's count, the probabilities
need to be computed on both jumps so that this is preserved.
We want to expand essentially to:
  <bb 2> [local count: 1073741825]:
...
  if (cond1)
    goto <bb 4>; [first_prob]
  else
    goto <bb 5>; [first_prob.invert ()]

  <bb 5>:
  if (cond2)
    goto <bb 4>; [prob]
  else
    goto <bb 3>; [prob.invert ()]

  <bb 3> [local count: 536864]:
  sqrtf (_1);
and compute first_prob and prob from the original prob such that the bb
counts match.  The code used to hardcode first_prob to 1% or 99% depending
on condition, and leave the second probability the original one.

That IMHO can't work and the Invalid sum message verifies that.  If we want
the first jump to hit 99times more often than the second one or vice versa,
I believe first_prob should be .99 * prob or .01 * prob respectively, and
the second probability then should be (0.01 * prob) / (1 - 0.99 * prob)
or (0.99 * prob) / (1 - 0.01 * prob) respectively.

With this change the Invalid sum message disappears.
predict-8.c testcase was apparently trying to match the hardcoded 0.99
probability rather than .99 * 65% emitted now.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

If this patch is right, I think do_jump_by_parts* are buggy similarly too,
there we emit prob or prob.invert () for all the N jumps we emit instead of
the original single conditional jump with probability prob.  I think we'd
need to decide what relative probabilities we want to use for the different
jumps, e.g. all have even relative likelyhood and then adjust the
probability of each branch and from what we compute the following
probabiliries similarly to this patch.

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

	PR tree-optimization/83081
	* dojump.c (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/dojump.c.jj	2018-01-03 10:19:55.000000000 +0100
+++ gcc/dojump.c	2018-01-19 17:07:25.238927314 +0100
@@ -1122,11 +1122,30 @@ do_compare_rtx_and_jump (rtx op0, rtx op
 	    {
 	      profile_probability first_prob = prob;
 	      if (first_code == UNORDERED)
-		first_prob = profile_probability::guessed_always ().apply_scale
-				 (1, 100);
+		{
+		  /* 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, but the first jump jumps
+		     much less often than the second jump.  */
+		  first_prob = prob.guessed ().apply_scale (1, 100);
+		  prob = (prob.guessed () - first_prob) / first_prob.invert ();
+		}
 	      else if (first_code == ORDERED)
-		first_prob = profile_probability::guessed_always ().apply_scale
-				 (99, 100);
+		{
+		  /* See above, except the first jump should jump much more
+		     often than the second one.  */
+		  first_prob = prob.guessed ().apply_scale (99, 100);
+		  prob = (prob.guessed () - first_prob) / first_prob.invert ();
+		}
+	      else
+		{
+		  first_prob = prob.guessed ().apply_scale (50, 100);
+		  prob = first_prob;
+		}
 	      if (and_them)
 		{
 		  rtx_code_label *dest_label;
--- gcc/testsuite/gcc.dg/predict-8.c.jj	2017-11-21 23:17:43.149093787 +0100
+++ gcc/testsuite/gcc.dg/predict-8.c	2018-01-19 22:24:09.949249810 +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 "64.[34]. .guessed" 2 "expand"} } */

	Jakub


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]