On Tue, May 30, 2023 at 7:06 AM Ajit Agarwal <[email protected]> wrote:
>
> Hello Richard:
>
> On 22/05/23 6:26 pm, Richard Biener wrote:
> > On Thu, May 18, 2023 at 9:14 AM Ajit Agarwal <[email protected]> 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 <[email protected]>
> >>
> >> 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?
> >> 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
> >>
