Hello Richard:
On 22/05/23 6:26 pm, Richard Biener wrote:
> On Thu, May 18, 2023 at 9:14 AM Ajit Agarwal <aagar...@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 <aagar...@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.
>> 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
>>
