Re: [PATCH] unswitch most profitable condition first

[Richard Biener <rguenther@suse.de>]

On Tue, 25 Oct 2022, Richard Biener wrote:

> When doing the loop unswitching re-org we promised to followup
> with improvements on the cost modeling.  The following makes sure we
> try to unswitch on the most profitable condition first.  As most profitable
> we pick the condition leading to the edge with the highest profile count.
> 
> Note the profile is only applied when picking the first unswitching
> opportunity since the profile counts are not updated with earlier
> unswitchings in mind.  Further opportunities are picked in DFS order.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> 
> Any comments?

I have now pushed this.

Richard.

> Thanks,
> Richard.
> 
> 	* tree-ssa-loop-unswitch.cc (unswitch_predicate::count): New.
> 	(unswitch_predicate::unswitch_predicate): Initialize count.
> 	(init_loop_unswitch_info): First collect candidates and
> 	determine the outermost loop to unswitch.
> 	(tree_ssa_unswitch_loops): First perform all guard hoisting,
> 	then perform unswitching on innermost loop predicates.
> 	(find_unswitching_predicates_for_bb): Keep track of the
> 	most profitable predicate to unswitch on.
> 	(tree_unswitch_single_loop): Unswitch given predicate if
> 	not NULL.
> ---
>  gcc/tree-ssa-loop-unswitch.cc | 66 ++++++++++++++++++++++++++++-------
>  1 file changed, 54 insertions(+), 12 deletions(-)
> 
> diff --git a/gcc/tree-ssa-loop-unswitch.cc b/gcc/tree-ssa-loop-unswitch.cc
> index 7d6781d1505..dfe75f52f12 100644
> --- a/gcc/tree-ssa-loop-unswitch.cc
> +++ b/gcc/tree-ssa-loop-unswitch.cc
> @@ -118,6 +118,7 @@ struct unswitch_predicate
>      if (!false_range.varying_p ()
>  	&& !false_range.undefined_p ())
>        false_range.invert ();
> +    count = e->count ();
>      num = predicates->length ();
>      predicates->safe_push (this);
>    }
> @@ -126,7 +127,8 @@ struct unswitch_predicate
>    unswitch_predicate (gcond *stmt)
>      : switch_p (false)
>    {
> -    if (EDGE_SUCC (gimple_bb (stmt), 0)->flags & EDGE_TRUE_VALUE)
> +    basic_block bb = gimple_bb (stmt);
> +    if (EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE)
>        edge_index = 0;
>      else
>        edge_index = 1;
> @@ -134,6 +136,7 @@ struct unswitch_predicate
>      tree rhs = gimple_cond_rhs (stmt);
>      enum tree_code code = gimple_cond_code (stmt);
>      condition = build2 (code, boolean_type_node, lhs, rhs);
> +    count = EDGE_SUCC (bb, 0)->count ().max (EDGE_SUCC (bb, 1)->count ());
>      if (irange::supports_p (TREE_TYPE (lhs)))
>        {
>  	auto range_op = range_op_handler (code, TREE_TYPE (lhs));
> @@ -180,6 +183,9 @@ struct unswitch_predicate
>    /* Index of the edge the predicate belongs to in the successor vector.  */
>    int edge_index;
>  
> +  /* The profile count of this predicate.  */
> +  profile_count count;
> +
>    /* Whether the predicate was created from a switch statement.  */
>    bool switch_p;
>  
> @@ -206,10 +212,14 @@ static class loop *tree_unswitch_loop (class loop *, edge, tree);
>  static bool tree_unswitch_single_loop (class loop *, dump_user_location_t,
>  				       predicate_vector &predicate_path,
>  				       unsigned loop_size, unsigned &budget,
> -				       int ignored_edge_flag, bitmap);
> +				       int ignored_edge_flag, bitmap,
> +				       unswitch_predicate * = NULL,
> +				       basic_block = NULL);
>  static void
>  find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
> -				    vec<unswitch_predicate *> &candidates);
> +				    vec<unswitch_predicate *> &candidates,
> +				    unswitch_predicate *&hottest,
> +				    basic_block &hottest_bb);
>  static bool tree_unswitch_outer_loop (class loop *);
>  static edge find_loop_guard (class loop *, vec<gimple *>&);
>  static bool empty_bb_without_guard_p (class loop *, basic_block,
> @@ -242,7 +252,8 @@ set_predicates_for_bb (basic_block bb, vec<unswitch_predicate *> predicates)
>     Return total number of instructions in the loop.  */
>  
>  static unsigned
> -init_loop_unswitch_info (class loop *loop)
> +init_loop_unswitch_info (class loop *loop, unswitch_predicate *&hottest,
> +			 basic_block &hottest_bb)
>  {
>    unsigned total_insns = 0;
>  
> @@ -259,13 +270,16 @@ init_loop_unswitch_info (class loop *loop)
>        total_insns += insns;
>      }
>  
> +  hottest = NULL;
> +  hottest_bb = NULL;
>    /* Find all unswitching candidates.  */
>    for (unsigned i = 0; i != loop->num_nodes; i++)
>      {
>        /* Find a bb to unswitch on.  */
>        vec<unswitch_predicate *> candidates;
>        candidates.create (1);
> -      find_unswitching_predicates_for_bb (bbs[i], loop, candidates);
> +      find_unswitching_predicates_for_bb (bbs[i], loop, candidates,
> +					  hottest, hottest_bb);
>        if (!candidates.is_empty ())
>  	set_predicates_for_bb (bbs[i], candidates);
>        else
> @@ -329,7 +343,10 @@ tree_ssa_unswitch_loops (function *fun)
>  	  unswitch_predicate::predicates = new vec<unswitch_predicate *> ();
>  
>  	  /* Unswitch innermost loop.  */
> -	  unsigned int loop_size = init_loop_unswitch_info (loop);
> +	  unswitch_predicate *hottest;
> +	  basic_block hottest_bb;
> +	  unsigned int loop_size = init_loop_unswitch_info (loop, hottest,
> +							    hottest_bb);
>  	  unsigned int budget = loop_size + param_max_unswitch_insns;
>  
>  	  predicate_vector predicate_path;
> @@ -338,7 +355,8 @@ tree_ssa_unswitch_loops (function *fun)
>  	  changed_unswitch
>  	    |= tree_unswitch_single_loop (loop, loc, predicate_path,
>  					  loop_size, budget,
> -					  ignored_edge_flag, handled);
> +					  ignored_edge_flag, handled,
> +					  hottest, hottest_bb);
>  	  predicate_path.release ();
>  
>  	  for (auto predlist : bb_predicates)
> @@ -449,7 +467,9 @@ is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
>  
>  static void
>  find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
> -				    vec<unswitch_predicate *> &candidates)
> +				    vec<unswitch_predicate *> &candidates,
> +				    unswitch_predicate *&hottest,
> +				    basic_block &hottest_bb)
>  {
>    gimple *last, *def;
>    tree use;
> @@ -489,6 +509,14 @@ find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
>  
>        unswitch_predicate *predicate = new unswitch_predicate (stmt);
>        candidates.safe_push (predicate);
> +      /* If we unswitch on this predicate we isolate both paths, so
> +	 pick the highest count for updating of the hottest predicate
> +	 to unswitch on first.  */
> +      if (!hottest || predicate->count > hottest->count)
> +	{
> +	  hottest = predicate;
> +	  hottest_bb = bb;
> +	}
>      }
>    else if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
>      {
> @@ -561,6 +589,11 @@ find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
>  					  edge_index, e,
>  					  edge_range[edge_index]);
>  	      candidates.safe_push (predicate);
> +	      if (!hottest || predicate->count > hottest->count)
> +		{
> +		  hottest = predicate;
> +		  hottest_bb = bb;
> +		}
>  	    }
>  	}
>      }
> @@ -888,13 +921,15 @@ evaluate_loop_insns_for_predicate (class loop *loop,
>  
>  /* Unswitch single LOOP.  PREDICATE_PATH contains so far used predicates
>     for unswitching.  BUDGET is number of instruction for which we can increase
> -   the loop and is updated when unswitching occurs.  */
> +   the loop and is updated when unswitching occurs.  If HOTTEST is not
> +   NULL then pick this candidate as the one to unswitch on.  */
>  
>  static bool
>  tree_unswitch_single_loop (class loop *loop, dump_user_location_t loc,
>  			   predicate_vector &predicate_path,
>  			   unsigned loop_size, unsigned &budget,
> -			   int ignored_edge_flag, bitmap handled)
> +			   int ignored_edge_flag, bitmap handled,
> +			   unswitch_predicate *hottest, basic_block hottest_bb)
>  {
>    class loop *nloop;
>    bool changed = false;
> @@ -939,8 +974,15 @@ tree_unswitch_single_loop (class loop *loop, dump_user_location_t loc,
>  	}
>        return false;
>      };
> -  /* Check predicates of reachable blocks.  */
> -  evaluate_bbs (loop, NULL, ignored_edge_flag, check_predicates);
> +
> +  if (hottest)
> +    {
> +      predicate = hottest;
> +      predicate_bb = hottest_bb;
> +    }
> +  else
> +    /* Check predicates of reachable blocks.  */
> +    evaluate_bbs (loop, NULL, ignored_edge_flag, check_predicates);
>  
>    if (predicate != NULL)
>      {
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
HRB 36809 (AG Nuernberg)