Re: Loop-ch improvements, part 3

[Richard Biener <rguenther@suse.de>]

On Wed, 23 Aug 2023, Jan Hubicka wrote:

> > We seem to peel one iteration for no good reason.  The loop is
> > a do-while loop already.  The key is we see the first iteration
> > exit condition is known not taken and then:
> Hi,
> this is patch fixing wrong return value in should_duplicate_loop_header_p.
> Doing so uncovered suboptimal decisions on some jump threading testcases
> where we chose to stop duplicating just before basic block that has zero
> cost and duplicating so would be always a win.
> 
> This is because the heuristics trying to chose right point to duplicate
> all winning blocks and to get loop to be do_while did not account
> zero_cost blocks in all cases.  The patch simplifies the logic by
> simply remembering zero cost blocks and handling them last after
> the right stopping point is chosen.
> 
> Bootstrapped/regtested x86_64-linux, OK?

OK.

Thanks,
Richard.

> gcc/ChangeLog:
> 
> 	* tree-ssa-loop-ch.cc (enum ch_decision): Fix comment.
> 	(should_duplicate_loop_header_p): Fix return value for static exits.
> 	(ch_base::copy_headers): Improve handling of ch_possible_zero_cost.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.dg/tree-ssa/copy-headers-9.c: Update template.
> 
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c
> index b49d1fc9576..11ee29458a2 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-9.c
> @@ -13,7 +13,6 @@ void test (int m, int n)
>  	}
>  	while (i<10);
>  }
> -/* { dg-final { scan-tree-dump-times "Duplicating bb . is a win" 2 "ch2" } } */
> -/* { dg-final { scan-tree-dump-times "Duplicating bb . is a win. it has zero" 1 "ch2" } } */
> +/* { dg-final { scan-tree-dump-times "Duplicating bb . is a win" 1 "ch2" } } */
>  /* { dg-final { scan-tree-dump-times "Will duplicate bb" 2 "ch2" } } */
>  /* { dg-final { scan-tree-dump "is now do-while loop" "ch2" } } */
> diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc
> index 6cdb87a762f..461416e4086 100644
> --- a/gcc/tree-ssa-loop-ch.cc
> +++ b/gcc/tree-ssa-loop-ch.cc
> @@ -176,7 +176,7 @@ enum ch_decision
>    ch_impossible,
>    /* We can copy it if it enables wins.  */
>    ch_possible,
> -  /* We can "cop" it if it enables wins and doing
> +  /* We can "copy" it if it enables wins and doing
>       so will introduce no new code.  */
>    ch_possible_zero_cost,
>    /* We want to copy.  */
> @@ -464,7 +464,7 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
>       TODO: Even if duplication costs some size we may opt to do so in case
>       exit probability is significant enough (do partial peeling).  */
>    if (static_exit)
> -    return code_size_cost ? ch_possible_zero_cost : ch_win;
> +    return !code_size_cost ? ch_possible_zero_cost : ch_possible;
>  
>    /* We was not able to prove that conditional will be eliminated.  */
>    int insns = estimate_num_insns (last, &eni_size_weights);
> @@ -824,6 +824,7 @@ ch_base::copy_headers (function *fun)
>        int last_win_nheaders = 0;
>        bool last_win_invariant_exit = false;
>        ch_decision ret;
> +      auto_vec <ch_decision, 32> decision;
>        hash_set <edge> *invariant_exits = new hash_set <edge>;
>        hash_set <edge> *static_exits = new hash_set <edge>;
>        while ((ret = should_duplicate_loop_header_p (header, loop, ranger,
> @@ -833,6 +834,7 @@ ch_base::copy_headers (function *fun)
>  	     != ch_impossible)
>  	{
>  	  nheaders++;
> +	  decision.safe_push (ret);
>  	  if (ret >= ch_win)
>  	    {
>  	      last_win_nheaders = nheaders;
> @@ -841,20 +843,6 @@ ch_base::copy_headers (function *fun)
>  		fprintf (dump_file, "    Duplicating bb %i is a win\n",
>  			 header->index);
>  	    }
> -	  /* Duplicate BB if has zero cost but be sure it will not
> -	     imply duplication of other BBs.  */
> -	  else if (ret == ch_possible_zero_cost
> -		   && (last_win_nheaders == nheaders - 1
> -		       || (last_win_nheaders == nheaders - 2
> -			   && last_win_invariant_exit)))
> -	    {
> -	      last_win_nheaders = nheaders;
> -	      last_win_invariant_exit = false;
> -	      if (dump_file && (dump_flags & TDF_DETAILS))
> -		fprintf (dump_file,
> -			 "    Duplicating bb %i is a win; it has zero cost\n",
> -			 header->index);
> -	    }
>  	  else
>  	    if (dump_file && (dump_flags & TDF_DETAILS))
>  	      fprintf (dump_file, "    May duplicate bb %i\n", header->index);
> @@ -884,6 +872,16 @@ ch_base::copy_headers (function *fun)
>  	    fprintf (dump_file,
>  		     "    Duplicating header BB to obtain do-while loop\n");
>  	}
> +      /* "Duplicate" all BBs with zero cost following last basic blocks we
> +	 decided to copy.  */
> +      while (last_win_nheaders < (int)decision.length ()
> +	     && decision[last_win_nheaders] == ch_possible_zero_cost)
> +	{
> +	  if (dump_file && (dump_flags & TDF_DETAILS))
> +	    fprintf (dump_file,
> +		     "    Duplicating extra bb is a win; it has zero cost\n");
> +	  last_win_nheaders++;
> +	}
>  
>        if (last_win_nheaders)
>  	candidates.safe_push ({loop, last_win_nheaders,
> 

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