[v2] tree-ssa-sink: Improve code sinking pass

  Hello All:

This patch improves code sinking pass to sink statements before call to reduce
register pressure.
Review comments are incorporated.

For example :

void bar();
int j;
void foo(int a, int b, int c, int d, int e, int f)
{
  int l;
  l = a + b + c + d +e + f;
  if (a != 5)
    {
      bar();
      j = l;
    }
}

Code Sinking does the following:

void bar();
int j;
void foo(int a, int b, int c, int d, int e, int f)
{
  int l;
  
  if (a != 5)
    {
      l = a + b + c + d +e + f;     
      bar();
      j = l;
    }
}

Bootstrapped 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-05-18  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>

gcc/ChangeLog:

	* tree-ssa-sink.cc (statement_sink_location): 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 |  15 ++
 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c |  19 +++
 gcc/tree-ssa-sink.cc                        | 160 ++++++++++++++++++--
 3 files changed, 183 insertions(+), 11 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 Fri, May 19, 2023 at 11:43 AM Ajit Agarwal <aagarwa1@linux.ibm.com> wrote:
>
> Hello All:
>
> This patch improves code sinking pass to sink statements before call to reduce
> register pressure.
> Review comments are incorporated.
>
> For example :
>
> void bar();
> int j;
> void foo(int a, int b, int c, int d, int e, int f)
> {
>   int l;
>   l = a + b + c + d +e + f;
>   if (a != 5)
>     {
>       bar();
>       j = l;
>     }
> }
>
> Code Sinking does the following:
>
> void bar();
> int j;
> void foo(int a, int b, int c, int d, int e, int f)
> {
>   int l;
>
>   if (a != 5)
>     {
>       l = a + b + c + d +e + f;
>       bar();
>       j = l;
>     }
> }
>
> Bootstrapped 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.

Saw this update too late but I think all comments still apply.

> 2023-05-18  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>
>
> gcc/ChangeLog:
>
>         * tree-ssa-sink.cc (statement_sink_location): 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 |  15 ++
>  gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c |  19 +++
>  gcc/tree-ssa-sink.cc                        | 160 ++++++++++++++++++--
>  3 files changed, 183 insertions(+), 11 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
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
> new file mode 100644
> index 00000000000..69fa6d32e7c
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
> @@ -0,0 +1,15 @@
> +/* { dg-options "-O2 -fdump-tree-optimized -fdump-tree-sink-stats" } */
> +
> +void bar();
> +int j;
> +void foo(int a, int b, int c, int d, int e, int f)
> +{
> +  int l;
> +  l = a + b + c + d +e + f;
> +  if (a != 5)
> +    {
> +      bar();
> +      j = l;
> +    }
> +}
> +/* { dg-final { scan-tree-dump-times "Sunk statements: 5" 1 "sink" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
> new file mode 100644
> index 00000000000..b34959c8a4d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
> @@ -0,0 +1,19 @@
> +/* { dg-options "-O2 -fdump-tree-sink-stats" } */
> +
> +void bar();
> +int j, x;
> +void foo(int a, int b, int c, int d, int e, int f)
> +{
> +  int l;
> +  l = a + b + c + d +e + f;
> +  if (a != 5)
> +    {
> +      bar();
> +      if (b != 3)
> +        x = 3;
> +      else
> +        x = 5;
> +      j = l;
> +    }
> +}
> +/* { dg-final { scan-tree-dump-times "Sunk statements: 5" 1 "sink" } } */
> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
> index b1ba7a2ad6c..091aa90d289 100644
> --- a/gcc/tree-ssa-sink.cc
> +++ b/gcc/tree-ssa-sink.cc
> @@ -171,6 +171,71 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
>    return commondom;
>  }
>
> +/* Return TRUE if immediate uses of the defs in
> +   STMT occur in the same block as STMT, FALSE otherwise.  */
> +
> +bool
> +def_use_same_block (gimple *stmt)
> +{
> +  use_operand_p use;
> +  def_operand_p def;
> +  imm_use_iterator imm_iter;
> +  ssa_op_iter iter;
> +
> +  FOR_EACH_SSA_DEF_OPERAND (def, stmt, iter, SSA_OP_DEF)
> +    {
> +      FOR_EACH_IMM_USE_FAST (use, imm_iter, DEF_FROM_PTR (def))
> +       {
> +         if (is_gimple_debug (USE_STMT (use)))
> +           continue;
> +
> +         if (use && (gimple_bb (USE_STMT (use)) == gimple_bb (stmt)))
> +           return true;
> +       }
> +     }
> +  return false;
> +}
> +
> +/* Return TRUE if the block has only one call statement, FALSE otherwise. */
> +
> +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);
> +
> +  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);
> +
> +          /* We have already seen a call.  */
> +          if (is_call)
> +            return false;
> +
> +          if (is_gimple_call (stmt))
> +            is_call = true;
> +          else
> +            return false;
> +
> +          if (!gsi_end_p (gsi))
> +            gsi_prev (&gsi);
> +
> +           ++i;
> +       }
> +     }
> +  if (is_call && i == 1)
> +    return true;
> +
> +  return false;
> +}
> +
>  /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
>     tree, return the best basic block between them (inclusive) to place
>     statements.
> @@ -190,7 +255,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)
>  {
>    basic_block best_bb = late_bb;
>    basic_block temp_bb = late_bb;
> @@ -230,14 +296,47 @@ select_best_block (basic_block early_bb,
>        if (threshold > 100)
>         threshold = 100;
>      }
> -
>    /* If BEST_BB is at the same nesting level, then require it to have
>       significantly lower execution frequency to avoid gratuitous movement.  */
>    if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
>        /* If result of comparsion is unknown, prefer EARLY_BB.
>          Thus use !(...>=..) rather than (...<...)  */
>        && !(best_bb->count * 100 >= early_bb->count * threshold))
> -    return best_bb;
> +    {
> +      basic_block new_best_bb = get_immediate_dominator (CDI_DOMINATORS, best_bb);
> +      /* Return best_bb if def and use are in same block otherwise new_best_bb.
> +
> +        Things to consider:
> +
> +          new_best_bb is not equal to best_bb and early_bb.
> +
> +          stmt is not call.
> +
> +          new_best_bb doesnt have any phis.
> +
> +          use basic block is not equal to early_bb.
> +
> +          use basic block post dominates to new_best_bb.
> +
> +          new_best_bb dominates early_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))
> +       {
> +         if (def_use_same_block (use))
> +           return best_bb;
> +
> +         return new_best_bb;
> +       }
> +       return best_bb;
> +    }
>
>    /* No better block found, so return EARLY_BB, which happens to be the
>       statement's original block.  */
> @@ -382,7 +481,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
>         {
>           /* Do not sink loads from hard registers.  */
>           if (gimple_assign_single_p (stmt)
> -             && VAR_P (gimple_assign_rhs1 (stmt))
> +             && TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL
>               && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
>             return false;
>
> @@ -439,7 +538,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
>        if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
>         return false;
>
> -      commondom = select_best_block (frombb, commondom, stmt);
> +      commondom = select_best_block (frombb, commondom, stmt, NULL);
>
>        if (commondom == frombb)
>         return false;
> @@ -456,19 +555,58 @@ statement_sink_location (gimple *stmt, basic_block frombb,
>             continue;
>           break;
>         }
> +
>        use = USE_STMT (one_use);
>
>        if (gimple_code (use) != GIMPLE_PHI)
>         {
> -         sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
> +         sinkbb = select_best_block (frombb, gimple_bb (use), stmt, use);
>
>           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));
> +
> +          if ((gimple_bb (def_stmt) == gimple_bb (use))
> +               && (gimple_bb (use) != sinkbb))
> +            sinkbb = gimple_bb (use);
> +
> +           if (sinkbb == gimple_bb (use))
> +             {
> +               gimple_stmt_iterator gsi = gsi_last_bb (sinkbb);
> +               gimple *def_stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def_p));
> +               gimple *last_stmt = gsi_stmt (gsi);
> +
> +               /* Update sinking point as stmt before call if the sinking block
> +                  has only calls. Otherwise update sinking point as the use
> +                  stmt.  */
> +               if (gsi_stmt (gsi) == use
> +                   && !is_gimple_call (last_stmt)
> +                   && gimple_code (last_stmt) != GIMPLE_SWITCH
> +                   && gimple_code (last_stmt) != GIMPLE_COND
> +                   && gimple_code (last_stmt) != GIMPLE_GOTO
> +                   && (!gimple_vdef (use) || !def_use_same_block (def_stmt)))
> +                 {
> +                   if (!gsi_end_p (gsi))
> +                     gsi_prev (&gsi);
> +
> +                   gimple *stmt = gsi_stmt (gsi);
> +
> +                   if (!gsi_end_p (gsi))
> +                     gsi_prev (&gsi);
> +
> +                   if (gsi_end_p (gsi) && stmt && is_gimple_call (stmt)
> +                       && gsi_end_p (gsi_start_phis (sinkbb))
> +                       && !is_gimple_call (def_stmt))
> +                     *togsi = gsi_for_stmt (stmt);
> +                   else
> +                     *togsi = gsi_for_stmt (use);
> +                  }
> +               else
> +                 *togsi = gsi_for_stmt(use);
> +              }
> +            else
> +               *togsi = gsi_after_labels (sinkbb);
>
>           return true;
>         }
> @@ -480,7 +618,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
>    if (!sinkbb)
>      return false;
>
> -  sinkbb = select_best_block (frombb, sinkbb, stmt);
> +  sinkbb = select_best_block (frombb, sinkbb, stmt, NULL);
>    if (!sinkbb || sinkbb == frombb)
>      return false;
>
> --
> 2.31.1
>