Re: [PATCH v1] tree-ssa-sink: Improve code sinking pass.

[Richard Biener <richard.guenther@gmail.com>]

On Tue, May 30, 2023 at 9:35 AM Ajit Agarwal <aagarwa1@linux.ibm.com> wrote:
>
> Hello Richard:
>
> On 30/05/23 12:34 pm, Richard Biener wrote:
> > On Tue, May 30, 2023 at 7:06 AM Ajit Agarwal <aagarwa1@linux.ibm.com> wrote:
> >>
> >> Hello Richard:
> >>
> >> On 22/05/23 6:26 pm, Richard Biener wrote:
> >>> On Thu, May 18, 2023 at 9:14 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.
> >>>>
> >>>> 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-05-18  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                        | 159 ++++++++++++++++++--
> >>>>  3 files changed, 185 insertions(+), 10 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..716bc1f9257
> >>>> --- /dev/null
> >>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
> >>>> @@ -0,0 +1,16 @@
> >>>> +/* { dg-do compile } */
> >>>> +/* { dg-options "-O2 -fdump-tree-sink -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" } } */
> >>>
> >>> this doesn't verify the place we sink to?
> >>>
> >>
> >> I am not sure how to verify the place we sink to with dg-final.
> >
> > I think dejagnu supports matching multi-line regexps so I suggest
> > to scan for the sunk expr RHS to be followed by the call?
> >
>
> You meant to use dg-begin-multiline-output and dg-end-multiline-output.

I was referring to uses like that in gcc.dg/debug/dwarf2/pr41445-6.c

> Thanks & Regards
> Ajit
> >>>> 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..ff41e2ea8ae
> >>>> --- /dev/null
> >>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
> >>>> @@ -0,0 +1,20 @@
> >>>> +/* { dg-do compile } */
> >>>> +/* { dg-options "-O2 -fdump-tree-sink-stats -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" } } */
> >>>
> >>> likewise.  So both tests already pass before the patch?
> >>>
> >>>> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
> >>>> index 87b1d40c174..76556e7795b 100644
> >>>> --- a/gcc/tree-ssa-sink.cc
> >>>> +++ b/gcc/tree-ssa-sink.cc
> >>>> @@ -171,6 +171,72 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
> >>>>    return commondom;
> >>>>  }
> >>>>
> >>>> +/* Return TRUE if immediate uses of the defs in
> >>>> +   USE occur in the same block as USE, FALSE otherwise.  */
> >>>> +
> >>>> +bool
> >>>> +def_use_same_block (gimple *stmt)
> >>>> +{
> >>>> +  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, stmt, 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
> >>>
> >>> use_p is never null
> >>>
> >>>> +             && (gimple_bb (USE_STMT (use_p)) == gimple_bb (stmt)))
> >>>> +           return true;
> >>>
> >>> the function behavior is obviously odd ...
> >>>
> >>>> +       }
> >>>> +     }
> >>>> +  return false;
> >>>> +}
> >>>> +
> >>>> +/* Return TRUE if the block has only calls, 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;
> >>>
> >>> Likewise.  Do you want to check whether a block has
> >>> a single stmt and that is a call and that is followed by
> >>> a condition?  It looks like a very convoluted way to write this.
> >>>
> >>>> +
> >>>> +          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 +256,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)
> >>>
> >>> please update the function comment
> >>>
> >>>>  {
> >>>>    basic_block best_bb = late_bb;
> >>>>    basic_block temp_bb = late_bb;
> >>>> @@ -230,14 +297,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;
> >>>
> >>> given the odd implementation of the predicates this matches very very
> >>> specific cases.
> >>>
> >>> Consider
> >>>
> >>>  if (..)
> >>>   {
> >>>     foo();
> >>>     bar();
> >>>     ... = l;
> >>>   }
> >>>
> >>> and C++ where foo and bar might throw.  You then likely want to sink
> >>> before foo ().
> >>>
> >>> What's the reason to only consider blocks with exactly 'call; cond;' ?
> >>>
> >>>> +
> >>>> +         return new_best_bb;
> >>>> +       }
> >>>> +       return best_bb;
> >>>> +    }
> >>>>
> >>>>    /* No better block found, so return EARLY_BB, which happens to be the
> >>>>       statement's original block.  */
> >>>> @@ -439,7 +539,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 +556,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);
> >>>
> >>> This is very convoluted.  I think that in the end you want to compute (once) the
> >>> position of the first call in each block.  Since we're waking the CFG backwards
> >>> in post-dominator order this information can be gathered during this walk.
> >>> This would determine the location to sink to iff the use stmt is dominated by
> >>> this location (you can for example use gimple_uid to mark stmts before it).
> >>>
> >>> The alternative is to simply always sink to the start of blocks even for the
> >>> use stmt block in case that has a call before the use (but you still need to
> >>> efficiently compute that).
> >>>
> >>
> >> Incorporated the above comments and sent a separate patch.
> >>
> >> Thanks & Regards
> >> Ajit
> >>
> >>> Richard.
> >>>
> >>>>
> >>>>           return true;
> >>>>         }
> >>>> @@ -480,7 +619,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
> >>>>