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 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