Re: [PATCH v2 1/4] Fix loop split incorrect count and probability

[Jan Hubicka <hubicka@kam.mff.cuni.cz>]

> As discussed yesterday, for loop of form
> 
> for (...)
>   if (cond)
>     cond = something();
>   else
>     something2
> 
> Split as
> 

Say "if (cond)" has probability p, then individual statements scale as
follows:

  loop1:
p    for (...)
p      if (true)
1        cond = something();
1        if (!cond)
x          break
0      else
0        something2 ();
     
     loop2:
1-p  for (...)
1-p    if (false)
0        cond = something();
1      else
1        something2 ();

Block with x has same count as preheader of the loop.

Your patch does
  loop1:
p    for (...)
p      if (true)
p        cond = something();
p        if (!cond)
x          break
p      else
p        something2 ();
     
     loop2:
1-p  for (...)
1-p    if (false)
1-p      cond = something();
1-p    else
1-p      something2 ();

One does not need set 0 correctly (blocks will be removed), but it would
be nice to avoid dropping 1s down. Looking at this, things will go well
with your change if we are guaranteed that something() and something2()
is always 1 bb becuase block merging happening after turning condiitonal
to constant will remove the misupdated count. Your profile scales after merging
is:
  loop1:
p    for (...)
1        cond = something();
1        if (!cond)
x          break
     
     loop2:
1-p  for (...)
1       something2 ();

assuming that profile was sane and frequency of something() is
p*frequency of the conditional and similarly for something2().
This is why you see final profile correct.  So if we split only loops
with one BB then/else arms, the patch is OK with comment explaining
this.

Also I wonder, do we correctly duplicate&update known bounds on
iteration counts attached to the loop struccture?

Honza
> 
> If "if (cond)" has probability p, you want to scale loop1 by p
> and loop2 by 1-p as your patch does, but you need to exclude the basic
> blocks guarded by the condition.
> 
> One way is to break out loop_version and implement it inline, other
> option (perhaps leading to less code duplication) is to add argument listing
> basic blocks that should not be scaled, which would be set to both arms
> of the if.
> 
> Are there other profile patches of your I should look at?
> Honza
> >  	gcc_assert (loop2);
> >  
> > @@ -1486,10 +1490,10 @@ do_split_loop_on_cond (struct loop *loop1, edge invar_branch)
> >    initialize_original_copy_tables ();
> >  
> >    struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL,
> > -				     profile_probability::always (),
> > -				     profile_probability::never (),
> > -				     profile_probability::always (),
> > -				     profile_probability::always (),
> > +				     invar_branch->probability.invert (),
> > +				     invar_branch->probability,
> > +				     invar_branch->probability.invert (),
> > +				     invar_branch->probability,
> >  				     true);
> >    if (!loop2)
> >      {
> > @@ -1530,6 +1534,9 @@ do_split_loop_on_cond (struct loop *loop1, edge invar_branch)
> >    to_loop1->flags |= true_invar ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE;
> >    to_loop2->flags |= true_invar ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE;
> >  
> > +  to_loop1->probability = invar_branch->probability.invert ();
> > +  to_loop2->probability = invar_branch->probability;
> > +
> >    /* Due to introduction of a control flow edge from loop1 latch to loop2
> >       pre-header, we should update PHIs in loop2 to reflect this connection
> >       between loop1 and loop2.  */
> > -- 
> > 2.27.0.90.geebb51ba8c
> >