On Thu, Dec 10, 2020 at 12:50:02PM +0100, Eric Botcazou wrote: > prob.split adjusts prob so this needs to be reflected in the comment (maybe > "adjusted prob" or the formula if it is simple). Otherwise looks good to me.
Actually I went back to drawing board and the patch wasn't correct. Let's discuss the probabilities in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98212#c4 for !and_them it looks all correct, so for bar we split if (a != b) goto t; // prob 90% goto f; into: if (a unord b) goto t; // first_prob = prob * cprob = 90% * 1% = 0.9% if (a ltgt b) goto t; // adjusted prob = (prob - first_prob) / (1 - first_prob) = (90% - 0.9%) / (1 - 0.9%) = 89.909% and for qux we split if (a != b) goto t; // prob 10% goto f; into: if (a unord b) goto t; // first_prob = prob * cprob = 10% * 1% = 0.1% if (a ltgt b) goto t; // adjusted prob = (prob - first_prob) / (1 - first_prob) = (10% - 0.1%) / (1 - 0.1%) = 9.910% Now, the and_them cases should be probability wise exactly the same if we swap the f and t labels, because baz if (a == b) goto t; // prob 90% goto f; is equivalent to: if (a != b) goto f; // prob 10% goto t; which is in qux. This means we could expand baz as: if (a unord b) goto f; // 0.1% if (a ltgt b) goto f; // 9.910% goto t; But we don't expand it exactly that way, but instead (as the comment says) as: if (a ord b) ; else goto f; // first_prob as probability of ; if (a uneq b) goto t; // adjusted prob goto f; So, first_prob.invert () should be 0.1% and adjusted prob should be 1 - 9.910%. Thus, the right thing is 4 inverts: prob = prob.invert (); // baz is equivalent to qux with swap(t, f) and thus inverted original prob first_prob = prob.split (cprob.invert ()).invert (); // cprob.invert because by doing if (cond) ; else goto f; we effectively invert the condition // the second invert because first_prob is probability of ; rather than goto f prob = prob.invert (); // lastly because adjusted prob we want is // probability of goto t;, while the one from corresponding !and_them case // would be if (...) goto f; goto t; 2020-12-10 Jakub Jelinek <ja...@redhat.com> PR rtl-optimization/98212 * dojump.c (do_compare_rtx_and_jump): Change computation of first_prob for and_them. Add comment explaining and_them case. * gcc.dg/predict-8.c: Adjust expected probability. --- gcc/dojump.c.jj 2020-12-10 12:30:50.677948803 +0100 +++ gcc/dojump.c 2020-12-10 13:17:30.568082332 +0100 @@ -1138,19 +1138,38 @@ do_compare_rtx_and_jump (rtx op0, rtx op cprob = cprob.apply_scale (99, 100); else cprob = profile_probability::even (); - /* We want to split: + /* For and_them we want to split: if (x) goto t; // prob; + goto f; into - if (a) goto t; // first_prob; - if (b) goto t; // prob; + if (a) ; else goto f; // first_prob for ; + // 1 - first_prob for goto f; + if (b) goto t; // adjusted prob; + goto f; such that the overall probability of jumping to t - remains the same and first_prob is prob * cprob. */ + remains the same. The and_them case should be + probability-wise equivalent to the !and_them case with + f and t swapped and also the conditions inverted, i.e. + if (!a) goto f; + if (!b) goto f; + goto t; + where the overall probability of jumping to f is + 1 - prob (thus the first prob.invert () below). + cprob.invert () is because the a condition is inverted, + so if it was originally ORDERED, !a is UNORDERED and + thus should be relative 1% rather than 99%. + The invert () on assignment to first_prob is because + first_prob represents the probability of fallthru, + rather than goto f. And the last prob.invert () is + because the adjusted prob represents the probability of + jumping to t rather than to f. */ if (and_them) { rtx_code_label *dest_label; - prob = prob.invert (); - profile_probability first_prob = prob.split (cprob).invert (); - prob = prob.invert (); + prob = prob.invert (); + profile_probability first_prob + = prob.split (cprob.invert ()).invert (); + prob = prob.invert (); /* If we only jump if true, just bypass the second jump. */ if (! if_false_label) { @@ -1163,6 +1182,15 @@ do_compare_rtx_and_jump (rtx op0, rtx op do_compare_rtx_and_jump (op0, op1, first_code, unsignedp, mode, size, dest_label, NULL, first_prob); } + /* For !and_them we want to split: + if (x) goto t; // prob; + goto f; + into + if (a) goto t; // first_prob; + if (b) goto t; // adjusted prob; + goto f; + such that the overall probability of jumping to t + remains the same and first_prob is prob * cprob. */ else { profile_probability first_prob = prob.split (cprob); --- gcc/testsuite/gcc.dg/predict-8.c.jj 2020-12-10 12:30:50.677948803 +0100 +++ gcc/testsuite/gcc.dg/predict-8.c 2020-12-10 12:31:06.639772968 +0100 @@ -8,4 +8,4 @@ int foo(float a, float b) { return 2; } -/* { dg-final { scan-rtl-dump-times "65.\[34]. .guessed" 2 "expand"} } */ +/* { dg-final { scan-rtl-dump-times "99.\[678]. .guessed" 2 "expand"} } */ Jakub