[v2] tree-ssa-sink: Improve code sinking pass
Checks
Commit Message
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
Comments
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
>
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */
@@ -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;