tree-ssa-sink: Improve code sinking pass.

  Hello All:

This patch improves code sinking pass to sink the blocks before calls
in the use blocks or immediate dominator blocks that reduces register pressure.

Bootstrapped and regtested on powerpc64-linux-gnu.

Thanks & Regards
Ajit

	tree-ssa-sink: Improve code sinking pass.

	Code Sinking sinks the blocks after call. This increases
	register pressure for callee-saved registers. Improves
	code sinking before call in the use blocks or immediate
	dominator of use blocks.

	2023-04-16  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>

gcc/ChangeLog:

	* tree-ssa-sink.cc (statement_sink_location): Modifed to
	move statements before calls.
	(block_call_p): New function.
	(def_use_same_block): New function.
	(select_best_block): Add heuristics to select the best
	blocks in the immediate post dominator.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/ssa-sink-20.c: New testcase.
	* gcc.dg/tree-ssa/ssa-sink-21.c: New testcase.
---
 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c |  16 +++
 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c |  20 +++
 gcc/tree-ssa-sink.cc                        | 134 +++++++++++++++++++-
 3 files changed, 164 insertions(+), 6 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
  

On 4/16/23 07:20, Ajit Agarwal wrote:
> Hello All:
> 
> This patch improves code sinking pass to sink the blocks before calls
> in the use blocks or immediate dominator blocks that reduces register pressure.
> 
> Bootstrapped and regtested on powerpc64-linux-gnu.
> 
> Thanks & Regards
> Ajit
> 
> 	tree-ssa-sink: Improve code sinking pass.
> 
> 	Code Sinking sinks the blocks after call. This increases
> 	register pressure for callee-saved registers. Improves
> 	code sinking before call in the use blocks or immediate
> 	dominator of use blocks.
> 
> 	2023-04-16  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>
> 
> gcc/ChangeLog:
> 
> 	* tree-ssa-sink.cc (statement_sink_location): Modifed to
> 	move statements before calls.
> 	(block_call_p): New function.
> 	(def_use_same_block): New function.
> 	(select_best_block): Add heuristics to select the best
> 	blocks in the immediate post dominator.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.dg/tree-ssa/ssa-sink-20.c: New testcase.
> 	* gcc.dg/tree-ssa/ssa-sink-21.c: New testcase.
> ---

>   
> +/* Check def and use stmts are in same block.  */
A better function comment would be
/* Return TRUE if all the immediate uses of the defs in
    USE occur in the same block as USE, FALSE otherwise.  */

I would also strongly suggest you change "use" to something else.  This 
function is walking over uses and defs, so calling the incoming argument 
"use" is going to make it excessively hard to write clean comments for 
this function.  Something as simple as "stmt" would be considerably better.



> +
> +bool
> +def_use_same_block (gimple *use)
> +{
> +  use_operand_p use_p;
> +  def_operand_p def_p;
> +  imm_use_iterator imm_iter;
> +  ssa_op_iter iter;
> +
> +  FOR_EACH_SSA_DEF_OPERAND (def_p, use, iter, SSA_OP_DEF)
> +    {
> +      FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
> +	{
> +	  if (is_gimple_debug (USE_STMT (use_p)))
> +	    continue;
> +
> +	  if (use_p
> +	      && (gimple_bb(USE_STMT (use_p)) == gimple_bb (use)))
Minor whitespace problems.  Make sure to include a space between the 
function name you are calling and the open parenthesis for the 
arguments.  ie gimple_bb (USE_STMT (use_p)).

It also seems like you're not checking all the uses, just one of them? 
Is that what you intended?  If so, then my suggested function comment is 
wrong and needs further adjustment.  This highlights how important it is 
to have a good function comment.


> +/* Check if the block has only calls.  */
This comment doesn't match the code.  It appears that you can have both 
calls and conditional branches.  Please update the function comment 
appropriately.  You should also describe the arguments and return value 
in the function comment (see my suggestion above as an example for how 
to describe the function arguments and return value.

Based on the code it looks like you're requiring a the block to contain 
only two real statements.  A call followed by a conditional.


> +
> +bool
> +block_call_p (basic_block bb)
> +{
> +  int i = 0;
> +  bool is_call = false;
> +  gimple_stmt_iterator gsi = gsi_last_bb (bb);
> +  gimple *last_stmt = gsi_stmt (gsi);
ISTM there is likely a function that will give you the last statement in 
the function.

> +
> +  if (last_stmt && gimple_code (last_stmt) == GIMPLE_COND)
> +    {
> +      if (!gsi_end_p (gsi))
> +	gsi_prev (&gsi);
> +
> +       for (; !gsi_end_p (gsi);)
> +	 {
> +	   gimple *stmt = gsi_stmt (gsi);
> +
> +	   if (is_gimple_debug (stmt))
> +	     return false;
Definitely incorrect as this can cause the decisions we make for 
optimization to change based on the existence of debug statements.


> +
> +	   if (is_gimple_call (stmt))
> +	     is_call = true;
> +	   else
> +	     return false;
ISTM that this might be better/clearer.  Once you've seen a call, if you 
see another, you can just return immediately.  It also seems like if I 
ever has a value other than 0/1, then you can return false immediately.

   if (is_gimple_call (stmt))
     {
       /* We have already seen a call.  */
       if (is_call)
	return false;
       is_call = true;
       continue;
     }

> +
> +	   if (!gsi_end_p (gsi))
> +	     gsi_prev (&gsi);
> +
> +	    ++i;
Isn't this going to cause this routine to return false if it has (for 
example) one or more labels followed by a CALL, then a conditional?


Overall I think the logic in here needs a bit of work.


> @@ -190,7 +254,8 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
>   static basic_block
>   select_best_block (basic_block early_bb,
>   		   basic_block late_bb,
> -		   gimple *stmt)
> +		   gimple *stmt,
> +		   gimple *use = 0)
Rather than use a default value, just fix the callers.  There's only 3 
and you already fixed one :-)  And if you're going to initialize a 
pointer, use NULL rather than 0.




>   {
>     basic_block best_bb = late_bb;
>     basic_block temp_bb = late_bb;
> @@ -230,7 +295,28 @@ select_best_block (basic_block early_bb,
>         if (threshold > 100)
>   	threshold = 100;
>       }
> +  if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
> +      && !(best_bb->count * 100 >= early_bb->count * threshold))
Isn't this condition the same as the one immediately following?  Note 
how there's a nice comment before the next one indicating what the 
heuristic is?  That's the kind of thing we want for every decision we 
make in this function.   In fact, I think there's a comment describing 
every block selection in this function.



> +    {
> +      basic_block new_best_bb = get_immediate_dominator (CDI_DOMINATORS, best_bb);
> +
> +      if (new_best_bb && use
> +	  && (new_best_bb != best_bb)
> +	  && (new_best_bb != early_bb)
> +	  && !is_gimple_call (stmt)
> +	  && gsi_end_p (gsi_start_phis (new_best_bb))
> +	  && (gimple_bb (use) != early_bb)
> +	  && !is_gimple_call (use)
> +	  && dominated_by_p (CDI_POST_DOMINATORS, new_best_bb, gimple_bb(use))
> +	  && dominated_by_p (CDI_DOMINATORS, new_best_bb, early_bb)
> +	  && block_call_p (new_best_bb))
So in english, what property are you checking for in this series of tests?


>   
>   	  if (sinkbb == frombb)
>   	    return false;
>   
> -	  if (sinkbb == gimple_bb (use))
> -	    *togsi = gsi_for_stmt (use);
> -	  else
> -	    *togsi = gsi_after_labels (sinkbb);
> +	   gimple *def_stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def_p));
[ ... ]
So, there's no comments in this code describing what you're looking for 
or why.

There are numerous comments in this file to help guide you with what you 
should be adding as comments.  The key is to make it so that someone not 
real familiar with this code/file should be able to read the comments 
and have a general understanding of what a hunk of code is doing and why.

What kind of testing have you done to make sure this doesn't change the 
sinking behavior for codes other than the case you're trying to improve. 
  RIght now I can't convince myself that your patch isn't going to have 
unintended consequences from a code generation standpoint.


Jeff