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

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

> On Wed, 27 Oct 2021, Jan Hubicka wrote:
> 
> > > 
> > > gcc/ChangeLog:
> > > 
> > > 	* tree-ssa-loop-split.c (split_loop): Fix incorrect probability.
> > > 	(do_split_loop_on_cond): Likewise.
> > > ---
> > >  gcc/tree-ssa-loop-split.c | 25 ++++++++++++++++---------
> > >  1 file changed, 16 insertions(+), 9 deletions(-)
> > > 
> > > diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c
> > > index 3f6ad046623..d30782888f3 100644
> > > --- a/gcc/tree-ssa-loop-split.c
> > > +++ b/gcc/tree-ssa-loop-split.c
> > > @@ -575,7 +575,11 @@ split_loop (class loop *loop1)
> > >  					    stmts2);
> > >  	tree cond = build2 (guard_code, boolean_type_node, guard_init, border);
> > >  	if (!initial_true)
> > > -	  cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond); 
> > > +	  cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
> > > +
> > > +	edge true_edge = EDGE_SUCC (bbs[i], 0)->flags & EDGE_TRUE_VALUE
> > > +			   ? EDGE_SUCC (bbs[i], 0)
> > > +			   : EDGE_SUCC (bbs[i], 1);
> > >  
> > >  	/* Now version the loop, placing loop2 after loop1 connecting
> > >  	   them, and fix up SSA form for that.  */
> > > @@ -583,10 +587,10 @@ split_loop (class loop *loop1)
> > >  	basic_block cond_bb;
> > >  
> > >  	class loop *loop2 = loop_version (loop1, cond, &cond_bb,
> > > -					   profile_probability::always (),
> > > -					   profile_probability::always (),
> > > -					   profile_probability::always (),
> > > -					   profile_probability::always (),
> > > +					   true_edge->probability,
> > > +					   true_edge->probability.invert (),
> > > +					   true_edge->probability,
> > > +					   true_edge->probability.invert (),
> > >  					   true);
> > 
> > As discussed yesterday, for loop of form
> > 
> > for (...)
> >   if (cond)
> >     cond = something();
> >   else
> >     something2
> > 
> > Split as
> 
> Note that you are missing to conditionalize loop1 execution
> on 'cond' (not sure if that makes a difference).
You are right - forgot to mention that.

Entry conditional makes no difference on scaling stmts inside loop but
affects its header and expected trip count. We however need to set up
probability of this conditional (and preheader count if it exists)
There is no general way to read the probability of this initial
conditional from cfg profile.  So I guess we are stuck with guessing
some arbitrary value. I guess common case is that cond is true first
iteration tough and often we can easily see that fromo PHI node
initializing the test variable.

Other thing that changes is expected number of iterations of the split
loops, so we may want to update the exit conditinal probability
accordingly...

Honza
> 
> > loop1:
> if (cond)
> > for (...)
> >   if (true)
> >     cond = something();
> >     if (!cond)
> >       break
> >   else
> >     something2 ();
> > 
> > loop2:
> > for (...)
> >   if (false)
> >     cond = something();
> >   else
> >     something2 ();
> > 
> > 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
> > > 
> > 
> 
> -- 
> Richard Biener <rguenther@suse.de>
> SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
> Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)