Re: [PATCH] tree-optimization/33315 - common stores during sinking
On Wed, 13 May 2020, Martin Sebor wrote:
> On 5/13/20 2:20 AM, Richard Biener wrote:
> >
> > This implements commoning of stores to a common successor in
> > a simple ad-hoc way. I've decided to put it into the code sinking
> > pass since, well, it sinks stores. It's still separate since
> > it does not really sink code into less executed places.
> >
> > It's ad-hoc since it does not perform any dataflow or alias analysis
> > but simply only considers trailing stores in a block, iteratively
> > though. If the stores are from different values a PHI node is
> > inserted to merge them. gcc.dg/tree-ssa/split-path-7.c shows
> > that path splitting will eventually undo this very transform,
> > I've decided to not bother with it and simply disable sinking for
> > the particular testcase.
> >
> > Doing this transform is good for code size when the stores are
> > from constants, once we have to insert PHIs the situation becomes
> > less clear but it's a transform we do elsewhere as well
> > (cselim for one), and reversing the transform should be easy.
> >
> > Bootstrap / regtest running on x86_64-unknown-linux-gnu.
> >
> > Any comments?
>
> Rather than adding the new code to sink_code_in_bb I would suggest
> to consider adding either all of it or just the while loop (to reduce
> block nesting) into a few function and call it from sink_code_in_bb.
>
> I'd expect it to improve readability (sink_code_in_bb is a fairly
> small by GCC standards, only 100 lines long, but with the new code
> it would grow to over 250). It might also make it easier to move
> the code later as suggested in the comments.
>
> Other than that, should the new code update the pass stats counter?
Reasonable. I've added a new counter for this.
Bootstrap / regtest running on x86_64-unknown-linux-gnu.
Richard.
Subject: [PATCH] tree-optimization/33315 - common stores during sinking
This implements commoning of stores to a common successor in
a simple ad-hoc way. I've decided to put it into the code sinking
pass since, well, it sinks stores. It's still separate since
it does not really sink code into less executed places.
It's ad-hoc since it does not perform any dataflow or alias analysis
but simply only considers trailing stores in a block, iteratively
though. If the stores are from different values a PHI node is
inserted to merge them. gcc.dg/tree-ssa/split-path-7.c shows
that path splitting will eventually undo this very transform,
I've decided to not bother with it and simply disable sinking for
the particular testcase.
Doing this transform is good for code size when the stores are
from constants, once we have to insert PHIs the situation becomes
less clear but it's a transform we do elsewhere as well
(cselim for one), and reversing the transform should be easy.
2020-05-14 Richard Biener
PR tree-optimization/33315
* tree-ssa-sink.c: Include tree-eh.h.
(sink_stats): Add commoned member.
(sink_common_stores_to_bb): New function implementing store
commoning by sinking to the successor.
(sink_code_in_bb): Call it, pass down TODO_cleanup_cfg returned.
(pass_sink_code::execute): Likewise. Record commoned stores
in statistics.
* gcc.dg/tree-ssa/ssa-sink-13.c: New testcase.
* gcc.dg/tree-ssa/ssa-sink-14.c: Likewise.
* gcc.dg/tree-ssa/split-path-7.c: Disable sinking.
---
gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c | 25
gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-14.c | 17 +++
gcc/tree-ssa-sink.c | 185 ++-
4 files changed, 224 insertions(+), 5 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-14.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
b/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
index 3d6186b34d9..a5df75c9b72 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fsplit-paths -fno-tree-cselim
-fdump-tree-split-paths-details -w" } */
+/* { dg-options "-O2 -fsplit-paths -fno-tree-cselim -fno-tree-sink
-fdump-tree-split-paths-details -w" } */
struct _reent
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
new file mode 100644
index 000..a65ba35d4ba
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
@@ -0,0 +1,25 @@
+/* PR33315 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sink" } */
+
+int num;
+int a[20];
+
+void test ()
+{
+ int i;
+ int *ptr;
+ ptr = & a[0];
+ i = num;
+ if ( i == 1) *(ptr+0) = 0;
Re: [PATCH] tree-optimization/33315 - common stores during sinking
On 5/13/20 2:20 AM, Richard Biener wrote:
This implements commoning of stores to a common successor in
a simple ad-hoc way. I've decided to put it into the code sinking
pass since, well, it sinks stores. It's still separate since
it does not really sink code into less executed places.
It's ad-hoc since it does not perform any dataflow or alias analysis
but simply only considers trailing stores in a block, iteratively
though. If the stores are from different values a PHI node is
inserted to merge them. gcc.dg/tree-ssa/split-path-7.c shows
that path splitting will eventually undo this very transform,
I've decided to not bother with it and simply disable sinking for
the particular testcase.
Doing this transform is good for code size when the stores are
from constants, once we have to insert PHIs the situation becomes
less clear but it's a transform we do elsewhere as well
(cselim for one), and reversing the transform should be easy.
Bootstrap / regtest running on x86_64-unknown-linux-gnu.
Any comments?
Rather than adding the new code to sink_code_in_bb I would suggest
to consider adding either all of it or just the while loop (to reduce
block nesting) into a few function and call it from sink_code_in_bb.
I'd expect it to improve readability (sink_code_in_bb is a fairly
small by GCC standards, only 100 lines long, but with the new code
it would grow to over 250). It might also make it easier to move
the code later as suggested in the comments.
Other than that, should the new code update the pass stats counter?
Martin
2020-05-13 Richard Biener
PR tree-optimization/33315
* tree-ssa-sink.c: Include tree-eh.h.
(sink_code_in_bb): Return TODO_cleanup_cfg if we commonized
and sunk stores. Implement store commoning by sinking to
the successor.
* gcc.dg/tree-ssa/ssa-sink-13.c: New testcase.
* gcc.dg/tree-ssa/ssa-sink-14.c: Likewise.
* gcc.dg/tree-ssa/split-path-7.c: Disable sinking.
---
gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c | 25
gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-14.c | 17 +++
gcc/tree-ssa-sink.c | 168 ++-
4 files changed, 207 insertions(+), 5 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-14.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
b/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
index 3d6186b34d9..a5df75c9b72 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fsplit-paths -fno-tree-cselim -fdump-tree-split-paths-details
-w" } */
+/* { dg-options "-O2 -fsplit-paths -fno-tree-cselim -fno-tree-sink
-fdump-tree-split-paths-details -w" } */
struct _reent
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
new file mode 100644
index 000..a65ba35d4ba
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
@@ -0,0 +1,25 @@
+/* PR33315 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sink" } */
+
+int num;
+int a[20];
+
+void test ()
+{
+ int i;
+ int *ptr;
+ ptr = & a[0];
+ i = num;
+ if ( i == 1) *(ptr+0) = 0;
+ if ( i != 1) *(ptr+0) = 0;
+ if ( i == 2) *(ptr+1) = 0;
+ if ( i != 2) *(ptr+1) = 0;
+ if ( i == 3) *(ptr+2) = 0;
+ if ( i != 3) *(ptr+2) = 0;
+}
+
+/* We should sink/merge all stores and end up with a single BB. */
+
+/* { dg-final { scan-tree-dump-times "MEM\[^\n\r\]* = 0;" 3 "sink" } } */
+/* { dg-final { scan-tree-dump-times "
/* TODO:
1. Sinking store only using scalar promotion (IE without moving the RHS):
@@ -469,7 +470,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
/* Perform code sinking on BB */
-static void
+static unsigned
sink_code_in_bb (basic_block bb)
{
basic_block son;
@@ -477,6 +478,163 @@ sink_code_in_bb (basic_block bb)
edge_iterator ei;
edge e;
bool last = true;
+ unsigned todo = 0;
+
+ /* Very simplistic code to sink common stores from the predecessor through
+ our virtual PHI. We do this before sinking stmts from BB as it might
+ expose sinking opportunities of the merged stores.
+ Once we have partial dead code elimination through sth like SSU-PRE this
+ should be moved there. */
+ gphi *phi;
+ if (EDGE_COUNT (bb->preds) > 1
+ && (phi = get_virtual_phi (bb)))
+{
+ /* Repeat until no more common stores are found. */
+ while (1)
+ {
+ gimple *first_store = NULL;
+ auto_vec vdefs;
+
+ /* Search for common stores defined by all virtual PHI args.
+??? Common stores not present in all predecessors could
+be handled by inserting a forwarder to sink to. Generally
+this involves deciding
[PATCH] tree-optimization/33315 - common stores during sinking
This implements commoning of stores to a common successor in
a simple ad-hoc way. I've decided to put it into the code sinking
pass since, well, it sinks stores. It's still separate since
it does not really sink code into less executed places.
It's ad-hoc since it does not perform any dataflow or alias analysis
but simply only considers trailing stores in a block, iteratively
though. If the stores are from different values a PHI node is
inserted to merge them. gcc.dg/tree-ssa/split-path-7.c shows
that path splitting will eventually undo this very transform,
I've decided to not bother with it and simply disable sinking for
the particular testcase.
Doing this transform is good for code size when the stores are
from constants, once we have to insert PHIs the situation becomes
less clear but it's a transform we do elsewhere as well
(cselim for one), and reversing the transform should be easy.
Bootstrap / regtest running on x86_64-unknown-linux-gnu.
Any comments?
2020-05-13 Richard Biener
PR tree-optimization/33315
* tree-ssa-sink.c: Include tree-eh.h.
(sink_code_in_bb): Return TODO_cleanup_cfg if we commonized
and sunk stores. Implement store commoning by sinking to
the successor.
* gcc.dg/tree-ssa/ssa-sink-13.c: New testcase.
* gcc.dg/tree-ssa/ssa-sink-14.c: Likewise.
* gcc.dg/tree-ssa/split-path-7.c: Disable sinking.
---
gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c | 25
gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-14.c | 17 +++
gcc/tree-ssa-sink.c | 168 ++-
4 files changed, 207 insertions(+), 5 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-14.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
b/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
index 3d6186b34d9..a5df75c9b72 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fsplit-paths -fno-tree-cselim
-fdump-tree-split-paths-details -w" } */
+/* { dg-options "-O2 -fsplit-paths -fno-tree-cselim -fno-tree-sink
-fdump-tree-split-paths-details -w" } */
struct _reent
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
new file mode 100644
index 000..a65ba35d4ba
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c
@@ -0,0 +1,25 @@
+/* PR33315 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sink" } */
+
+int num;
+int a[20];
+
+void test ()
+{
+ int i;
+ int *ptr;
+ ptr = & a[0];
+ i = num;
+ if ( i == 1) *(ptr+0) = 0;
+ if ( i != 1) *(ptr+0) = 0;
+ if ( i == 2) *(ptr+1) = 0;
+ if ( i != 2) *(ptr+1) = 0;
+ if ( i == 3) *(ptr+2) = 0;
+ if ( i != 3) *(ptr+2) = 0;
+}
+
+/* We should sink/merge all stores and end up with a single BB. */
+
+/* { dg-final { scan-tree-dump-times "MEM\[^\n\r\]* = 0;" 3 "sink" } } */
+/* { dg-final { scan-tree-dump-times "preds) > 1
+ && (phi = get_virtual_phi (bb)))
+{
+ /* Repeat until no more common stores are found. */
+ while (1)
+ {
+ gimple *first_store = NULL;
+ auto_vec vdefs;
+
+ /* Search for common stores defined by all virtual PHI args.
+??? Common stores not present in all predecessors could
+be handled by inserting a forwarder to sink to. Generally
+this involves deciding which stores to do this for if
+multiple common stores are present for different sets of
+predecessors. See PR11832 for an interesting case. */
+ for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
+ {
+ tree arg = gimple_phi_arg_def (phi, i);
+ gimple *def = SSA_NAME_DEF_STMT (arg);
+ if (! is_gimple_assign (def)
+ || stmt_can_throw_internal (cfun, def))
+ {
+ /* ??? We could handle some cascading with the def being
+another PHI. We'd have to insert multiple PHIs for
+the rhs then though (if they are not all equal). */
+ first_store = NULL;
+ break;
+ }
+ /* ??? Do not try to do anything fancy with aliasing, thus
+do not sink across non-aliased loads (or even stores,
+so different store order will make the sinking fail). */
+ bool all_uses_on_phi = true;
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ FOR_EACH_IMM_USE_FAST (use_p, iter, arg)
+ if (USE_STMT (use_p) != phi)
+ {
+ all_uses_on_phi = false;
+ break;
+ }
+ if (! all_uses_on_phi)
+ {
+
