Dne 2018-01-19 22:45, Jakub Jelinek napsal:
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.
OK, so if we end u with first_prob 1% we increase probability to
dispatch to bb 4 by little
bit that is acceptale noise, but when first_prob is 99% then we
obviously get it wrong.
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.
In new code bb4 is reached by first_prob + (1-first_prob)*second_prob
which should be equal to prob.
Say your choosen constant is to obtain first_prob=c*prob is c=0.99 and
you want to know c2 to obtain second_prob=c2*prob
You want the combined probability of branch
(c*prob)+(1-c*prob)*(prob*c2) to be the same prob
This should give c2=(1-c)/(1-c*prob) so
(c*prob)+(1-c*prob)*prob*(1-c)/(1-c*prob) cancels out to
c*prob+(1-c)*prob
that is
profile_probability cprob =
profile_probability::guessed_always ().apply_scale (1, 100);
first_prob = prob * cprob;
prob = cprob.inverse () / (first_prob).inverse ();
unless I missed something. No need to do .guessed conversion on prob.
It will be propagated
in as cprob which is already constructed as a guess.
I would say that there are multiple cases where we want to redistribute
probabilities so perhaps factor it out into a helper. Perhaps something
like
void profile_probability::split (profile_probability cprob,
profile_probability *first_prob, profile_probability *second_prob)
I would bet we already have something like that but don't see it.
Other cases seems to choose c as 1/2 that simplifies the formulate bit
it is also easy to get misunderstand such as in:
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 ();
So I would convert those into profile_probability::split
OK with this change.
Thanks for looking into this!
Honza
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 <ja...@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
