| Message ID | 20180119214556.GY2063@tucnak |
|---|---|
| State | New |
| Headers | show |
| Series | Fix branch probability computation in do_compare_rtx_and_jump (PR tree-optimization/83081) | expand |
On 19 January 2018 at 22:45, Jakub Jelinek <jakub@redhat.com> wrote: > 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? > Hi, Did you notice any performance impact? Thanks, Christophe > 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
On Mon, Jan 22, 2018 at 01:11:34PM +0100, Christophe Lyon wrote: > On 19 January 2018 at 22:45, Jakub Jelinek <jakub@redhat.com> wrote: > > 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? > > > Hi, > > Did you notice any performance impact? Haven't been looking for that, this is a bugfix, the current code is broken. It changes (fixes) probabilities of some edges, sure, so it could affect something both ways. Jakub
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 <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
On Mon, Jan 22, 2018 at 01:52:11PM +0100, Jan Hubicka wrote: > 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; Yes, if we want it to be done with arbitrary cprob, we can do it the above way and move the latter into the helper. > prob = cprob.inverse () / (first_prob).inverse (); 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. > 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; } ? > > 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 (); Or profile_probability op1_false_prob = op0_false_prob / op0_false_prob.invert (); Jakub
Dne 2018-01-22 14:29, Jakub Jelinek napsal: > On Mon, Jan 22, 2018 at 01:52:11PM +0100, Jan Hubicka wrote: >> 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; > > Yes, if we want it to be done with arbitrary cprob, we can do it the > above > way and move the latter into the helper. > >> prob = cprob.inverse () / (first_prob).inverse (); > > 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. >> >> 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 (); > > Or profile_probability op1_false_prob = op0_false_prob / > op0_false_prob.invert (); I would use the splitting function here so once someone decides to change the weights the code will not produce corrupt profile. Thanks, Honza > > Jakub
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
Dne 2018-01-22 16:57, Jakub Jelinek napsal: > 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. */ To make documentation clear, i would include the pseudocode with conditionals and individual probabilities. It is bit non-obvious transformation and it would be nice to reduce level of apparent magicness in profiling code :) OK, Honza > + 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
On Mon, Jan 22, 2018 at 06:44:17PM +0100, Jan Hubicka wrote: > > + /* 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. */ > > To make documentation clear, i would include the pseudocode with > conditionals and individual > probabilities. > It is bit non-obvious transformation and it would be nice to reduce level of > apparent > magicness in profiling code :) So like this? 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,30 @@ 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. This is useful e.g. when splitting a conditional + branch like: + if (cond) + goto lab; // ORIG probability + into + if (cond1) + goto lab; // FIRST = ORIG * CPROB probability + if (cond2) + goto lab; // SECOND probability + such that the overall probability of jumping to lab remains + the same. CPROB gives the relative probability between the + branches. */ + 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
Dne 2018-01-22 19:36, Jakub Jelinek napsal: > On Mon, Jan 22, 2018 at 06:44:17PM +0100, Jan Hubicka wrote: >> > + /* 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. */ >> >> To make documentation clear, i would include the pseudocode with >> conditionals and individual >> probabilities. >> It is bit non-obvious transformation and it would be nice to reduce >> level of >> apparent >> magicness in profiling code :) > > So like this? > > 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. Looks great. Thanks a lot! Honza > > --- 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,30 @@ 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. This is useful e.g. when splitting a conditional > + branch like: > + if (cond) > + goto lab; // ORIG probability > + into > + if (cond1) > + goto lab; // FIRST = ORIG * CPROB probability > + if (cond2) > + goto lab; // SECOND probability > + such that the overall probability of jumping to lab remains > + the same. CPROB gives the relative probability between the > + branches. */ > + 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
--- 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"} } */
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. Jakub