* [PATCH V11] : tree-ssa-sink: Improve code sinking pass
@ 2023-10-30 12:10 Ajit Agarwal
2023-11-16 9:58 ` Richard Biener
0 siblings, 1 reply; 3+ messages in thread
From: Ajit Agarwal @ 2023-10-30 12:10 UTC (permalink / raw)
To: gcc-patches, Richard Biener; +Cc: Jeff Law, Segher Boessenkool, Peter Bergner
Hello Richard:
Currently, code sinking will sink code at the use points with loop having same
nesting depth. The following patch improves code sinking by placing the sunk
code in immediate dominator with same loop nest depth.
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
Currently, code sinking will sink code at the use points with loop having same
nesting depth. The following patch improves code sinking by placing the sunk
code in immediate dominator with same loop nest depth.
2023-10-30 Ajit Kumar Agarwal <aagarwa1@linux.ibm.com>
gcc/ChangeLog:
PR tree-optimization/81953
* tree-ssa-sink.cc (statement_sink_location): Move statements with
same loop nest depth.
(select_best_block): Add heuristics to select the best blocks in the
immediate dominato for same loop nest depthr.
gcc/testsuite/ChangeLog:
PR tree-optimization/81953
* gcc.dg/tree-ssa/ssa-sink-21.c: New test.
* gcc.dg/tree-ssa/ssa-sink-22.c: New test.
---
gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 15 +++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c | 19 +++++++++++++++++++
gcc/tree-ssa-sink.cc | 21 ++++++++++++++-------
3 files changed, 48 insertions(+), 7 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c
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..d3b79ca5803
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -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 {l_12\s+=\s+_4\s+\+\s+f_11\(D\);\n\s+bar\s+\(\)} sink1 } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c
new file mode 100644
index 00000000000..84e7938c54f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { 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 {l_13\s+=\s+_4\s+\+\s+f_12\(D\);\n\s+bar\s+\(\)} sink1 } } */
diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
index a360c5cdd6e..0b823b81309 100644
--- a/gcc/tree-ssa-sink.cc
+++ b/gcc/tree-ssa-sink.cc
@@ -176,6 +176,9 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
tree, return the best basic block between them (inclusive) to place
statements.
+ The best basic block should be an immediate dominator of
+ best basic block if we've moved to same loop nest.
+
We want the most control dependent block in the shallowest loop nest.
If the resulting block is in a shallower loop nest, then use it. Else
@@ -201,14 +204,13 @@ select_best_block (basic_block early_bb,
{
/* If we've moved into a lower loop nest, then that becomes
our best block. */
- if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
+ if (bb_loop_depth (temp_bb) <= bb_loop_depth (best_bb))
best_bb = temp_bb;
/* Walk up the dominator tree, hopefully we'll find a shallower
loop nest. */
temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
}
-
/* Placing a statement before a setjmp-like function would be invalid
(it cannot be reevaluated when execution follows an abnormal edge).
If we selected a block with abnormal predecessors, just punt. */
@@ -250,7 +252,14 @@ select_best_block (basic_block 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;
+ {
+ /* Avoid sinking to immediate dominator if the statement to be moved
+ has memory operand and same loop nest. */
+ if (best_bb != late_bb && gimple_vuse (stmt))
+ return late_bb;
+
+ return best_bb;
+ }
/* No better block found, so return EARLY_BB, which happens to be the
statement's original block. */
@@ -430,6 +439,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
continue;
break;
}
+
use = USE_STMT (one_use);
if (gimple_code (use) != GIMPLE_PHI)
@@ -439,10 +449,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
if (sinkbb == frombb)
return false;
- if (sinkbb == gimple_bb (use))
- *togsi = gsi_for_stmt (use);
- else
- *togsi = gsi_after_labels (sinkbb);
+ *togsi = gsi_after_labels (sinkbb);
return true;
}
--
2.39.3
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH V11] : tree-ssa-sink: Improve code sinking pass
2023-10-30 12:10 [PATCH V11] : tree-ssa-sink: Improve code sinking pass Ajit Agarwal
@ 2023-11-16 9:58 ` Richard Biener
2023-11-17 7:27 ` Ajit Agarwal
0 siblings, 1 reply; 3+ messages in thread
From: Richard Biener @ 2023-11-16 9:58 UTC (permalink / raw)
To: Ajit Agarwal; +Cc: gcc-patches, Jeff Law, Segher Boessenkool, Peter Bergner
On Mon, Oct 30, 2023 at 1:10 PM Ajit Agarwal <aagarwa1@linux.ibm.com> wrote:
>
> Hello Richard:
>
> Currently, code sinking will sink code at the use points with loop having same
> nesting depth. The following patch improves code sinking by placing the sunk
> code in immediate dominator with same loop nest depth.
>
> 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
>
> Currently, code sinking will sink code at the use points with loop having same
> nesting depth. The following patch improves code sinking by placing the sunk
> code in immediate dominator with same loop nest depth.
>
> 2023-10-30 Ajit Kumar Agarwal <aagarwa1@linux.ibm.com>
>
> gcc/ChangeLog:
>
> PR tree-optimization/81953
> * tree-ssa-sink.cc (statement_sink_location): Move statements with
> same loop nest depth.
> (select_best_block): Add heuristics to select the best blocks in the
> immediate dominato for same loop nest depthr.
>
> gcc/testsuite/ChangeLog:
>
> PR tree-optimization/81953
> * gcc.dg/tree-ssa/ssa-sink-21.c: New test.
> * gcc.dg/tree-ssa/ssa-sink-22.c: New test.
> ---
> gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 15 +++++++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c | 19 +++++++++++++++++++
> gcc/tree-ssa-sink.cc | 21 ++++++++++++++-------
> 3 files changed, 48 insertions(+), 7 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c
>
> 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..d3b79ca5803
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
> @@ -0,0 +1,15 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -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 {l_12\s+=\s+_4\s+\+\s+f_11\(D\);\n\s+bar\s+\(\)} sink1 } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c
> new file mode 100644
> index 00000000000..84e7938c54f
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c
> @@ -0,0 +1,19 @@
> +/* { dg-do compile } */
> +/* { 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 {l_13\s+=\s+_4\s+\+\s+f_12\(D\);\n\s+bar\s+\(\)} sink1 } } */
> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
> index a360c5cdd6e..0b823b81309 100644
> --- a/gcc/tree-ssa-sink.cc
> +++ b/gcc/tree-ssa-sink.cc
> @@ -176,6 +176,9 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
> tree, return the best basic block between them (inclusive) to place
> statements.
>
> + The best basic block should be an immediate dominator of
> + best basic block if we've moved to same loop nest.
> +
> We want the most control dependent block in the shallowest loop nest.
>
> If the resulting block is in a shallower loop nest, then use it. Else
> @@ -201,14 +204,13 @@ select_best_block (basic_block early_bb,
> {
> /* If we've moved into a lower loop nest, then that becomes
> our best block. */
> - if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
> + if (bb_loop_depth (temp_bb) <= bb_loop_depth (best_bb))
This will now only ever sink stmts out of loops but never do traditional
sinking into conditional executed blocks within the same loop.
That's clearly not what the code is intended to do.
Richard.
> best_bb = temp_bb;
>
> /* Walk up the dominator tree, hopefully we'll find a shallower
> loop nest. */
> temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
> }
> -
> /* Placing a statement before a setjmp-like function would be invalid
> (it cannot be reevaluated when execution follows an abnormal edge).
> If we selected a block with abnormal predecessors, just punt. */
> @@ -250,7 +252,14 @@ select_best_block (basic_block 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;
> + {
> + /* Avoid sinking to immediate dominator if the statement to be moved
> + has memory operand and same loop nest. */
> + if (best_bb != late_bb && gimple_vuse (stmt))
> + return late_bb;
> +
> + return best_bb;
> + }
>
> /* No better block found, so return EARLY_BB, which happens to be the
> statement's original block. */
> @@ -430,6 +439,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
> continue;
> break;
> }
> +
> use = USE_STMT (one_use);
>
> if (gimple_code (use) != GIMPLE_PHI)
> @@ -439,10 +449,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
> if (sinkbb == frombb)
> return false;
>
> - if (sinkbb == gimple_bb (use))
> - *togsi = gsi_for_stmt (use);
> - else
> - *togsi = gsi_after_labels (sinkbb);
> + *togsi = gsi_after_labels (sinkbb);
>
> return true;
> }
> --
> 2.39.3
>
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH V11] : tree-ssa-sink: Improve code sinking pass
2023-11-16 9:58 ` Richard Biener
@ 2023-11-17 7:27 ` Ajit Agarwal
0 siblings, 0 replies; 3+ messages in thread
From: Ajit Agarwal @ 2023-11-17 7:27 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches, Jeff Law, Segher Boessenkool, Peter Bergner
Hello Richard:
On 16/11/23 3:28 pm, Richard Biener wrote:
> On Mon, Oct 30, 2023 at 1:10 PM Ajit Agarwal <aagarwa1@linux.ibm.com> wrote:
>>
>> Hello Richard:
>>
>> Currently, code sinking will sink code at the use points with loop having same
>> nesting depth. The following patch improves code sinking by placing the sunk
>> code in immediate dominator with same loop nest depth.
>>
>> 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
>>
>> Currently, code sinking will sink code at the use points with loop having same
>> nesting depth. The following patch improves code sinking by placing the sunk
>> code in immediate dominator with same loop nest depth.
>>
>> 2023-10-30 Ajit Kumar Agarwal <aagarwa1@linux.ibm.com>
>>
>> gcc/ChangeLog:
>>
>> PR tree-optimization/81953
>> * tree-ssa-sink.cc (statement_sink_location): Move statements with
>> same loop nest depth.
>> (select_best_block): Add heuristics to select the best blocks in the
>> immediate dominato for same loop nest depthr.
>>
>> gcc/testsuite/ChangeLog:
>>
>> PR tree-optimization/81953
>> * gcc.dg/tree-ssa/ssa-sink-21.c: New test.
>> * gcc.dg/tree-ssa/ssa-sink-22.c: New test.
>> ---
>> gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 15 +++++++++++++++
>> gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c | 19 +++++++++++++++++++
>> gcc/tree-ssa-sink.cc | 21 ++++++++++++++-------
>> 3 files changed, 48 insertions(+), 7 deletions(-)
>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c
>>
>> 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..d3b79ca5803
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
>> @@ -0,0 +1,15 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -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 {l_12\s+=\s+_4\s+\+\s+f_11\(D\);\n\s+bar\s+\(\)} sink1 } } */
>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c
>> new file mode 100644
>> index 00000000000..84e7938c54f
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c
>> @@ -0,0 +1,19 @@
>> +/* { dg-do compile } */
>> +/* { 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 {l_13\s+=\s+_4\s+\+\s+f_12\(D\);\n\s+bar\s+\(\)} sink1 } } */
>> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
>> index a360c5cdd6e..0b823b81309 100644
>> --- a/gcc/tree-ssa-sink.cc
>> +++ b/gcc/tree-ssa-sink.cc
>> @@ -176,6 +176,9 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
>> tree, return the best basic block between them (inclusive) to place
>> statements.
>>
>> + The best basic block should be an immediate dominator of
>> + best basic block if we've moved to same loop nest.
>> +
>> We want the most control dependent block in the shallowest loop nest.
>>
>> If the resulting block is in a shallower loop nest, then use it. Else
>> @@ -201,14 +204,13 @@ select_best_block (basic_block early_bb,
>> {
>> /* If we've moved into a lower loop nest, then that becomes
>> our best block. */
>> - if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
>> + if (bb_loop_depth (temp_bb) <= bb_loop_depth (best_bb))
>
> This will now only ever sink stmts out of loops but never do traditional
> sinking into conditional executed blocks within the same loop.
>
> That's clearly not what the code is intended to do.
>
Incorporated in V12 of the patch. Ok for trunk?
Thanks & Regards
Ajit
> Richard.
>
>> best_bb = temp_bb;
>>
>> /* Walk up the dominator tree, hopefully we'll find a shallower
>> loop nest. */
>> temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
>> }
>> -
>> /* Placing a statement before a setjmp-like function would be invalid
>> (it cannot be reevaluated when execution follows an abnormal edge).
>> If we selected a block with abnormal predecessors, just punt. */
>> @@ -250,7 +252,14 @@ select_best_block (basic_block 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;
>> + {
>> + /* Avoid sinking to immediate dominator if the statement to be moved
>> + has memory operand and same loop nest. */
>> + if (best_bb != late_bb && gimple_vuse (stmt))
>> + return late_bb;
>> +
>> + return best_bb;
>> + }
>>
>> /* No better block found, so return EARLY_BB, which happens to be the
>> statement's original block. */
>> @@ -430,6 +439,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
>> continue;
>> break;
>> }
>> +
>> use = USE_STMT (one_use);
>>
>> if (gimple_code (use) != GIMPLE_PHI)
>> @@ -439,10 +449,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
>> if (sinkbb == frombb)
>> return false;
>>
>> - if (sinkbb == gimple_bb (use))
>> - *togsi = gsi_for_stmt (use);
>> - else
>> - *togsi = gsi_after_labels (sinkbb);
>> + *togsi = gsi_after_labels (sinkbb);
>>
>> return true;
>> }
>> --
>> 2.39.3
>>
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-11-17 7:27 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-10-30 12:10 [PATCH V11] : tree-ssa-sink: Improve code sinking pass Ajit Agarwal
2023-11-16 9:58 ` Richard Biener
2023-11-17 7:27 ` Ajit Agarwal
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).