tree-optimization/100221 - improve DSE a bit
Commit Message
When facing multiple PHI defs and one feeding the other we can
postpone processing uses of one and thus can proceed.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
2022-05-20 Richard Biener <rguenther@suse.de>
PR tree-optimization/100221
* tree-ssa-dse.cc (contains_phi_arg): New function.
(dse_classify_store): Postpone PHI defs that feed another PHI in defs.
* gcc.dg/tree-ssa/ssa-dse-44.c: New testcase.
* gcc.dg/tree-ssa/ssa-dse-45.c: Likewise.
---
gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c | 19 +++++++++
gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c | 24 +++++++++++
gcc/tree-ssa-dse.cc | 46 +++++++++++++++++++---
3 files changed, 84 insertions(+), 5 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c
Comments
On Tue, 24 May 2022 at 11:50, Richard Biener via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> When facing multiple PHI defs and one feeding the other we can
> postpone processing uses of one and thus can proceed.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
>
> 2022-05-20 Richard Biener <rguenther@suse.de>
>
> PR tree-optimization/100221
> * tree-ssa-dse.cc (contains_phi_arg): New function.
> (dse_classify_store): Postpone PHI defs that feed another PHI in defs.
>
> * gcc.dg/tree-ssa/ssa-dse-44.c: New testcase.
> * gcc.dg/tree-ssa/ssa-dse-45.c: Likewise.
> ---
> gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c | 19 +++++++++
> gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c | 24 +++++++++++
> gcc/tree-ssa-dse.cc | 46 +++++++++++++++++++---
> 3 files changed, 84 insertions(+), 5 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c
> new file mode 100644
> index 00000000000..aaec41d7bdf
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c
> @@ -0,0 +1,19 @@
> +/* { dg-do link } */
> +/* { dg-options "-O -fdump-tree-dse1-details" } */
> +
> +extern void foo(void);
> +int a, b;
> +static int c;
> +int main()
> +{
> + if (c)
> + foo ();
> + int *g = &c;
> + int **h = &g;
> + int ***h1 = &h;
> + if (a)
> + while (b)
> + b = 0;
> +}
> +
> +/* { dg-final { scan-tree-dump "Deleted dead store: g = &c;" "dse1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c
> new file mode 100644
> index 00000000000..fd92d7b599a
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c
> @@ -0,0 +1,24 @@
> +/* { dg-do link } */
> +/* { dg-options "-O" } */
> +
> +extern void foo(void);
> +int a, b;
> +static int c;
> +static void f() {
> + while (a)
> + for (; b; b--)
> + ;
> +}
> +void i() {
> + if (c)
> + foo();
> + int *g = &c;
> + {
> + int **h[1] = {&g};
> + f();
> + }
> +}
> +int main() {
> + i();
> + return 0;
> +}
> diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc
> index 881a2d0f98d..ea50de789b1 100644
> --- a/gcc/tree-ssa-dse.cc
> +++ b/gcc/tree-ssa-dse.cc
> @@ -898,6 +898,17 @@ dse_optimize_redundant_stores (gimple *stmt)
> }
> }
>
> +/* Return whether PHI contains ARG as an argument. */
> +
> +static bool
> +contains_phi_arg (gphi *phi, tree arg)
> +{
> + for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
> + if (gimple_phi_arg_def (phi, i) == arg)
> + return true;
> + return false;
> +}
Hi Richard,
Just wondering if contains_phi_arg could be a more general purpose
utility function, and moved to gimple.cc
or tree-ssa.cc than be specific to tree-ssa-dse.cc ?
Thanks,
Prathamesh
> +
> /* A helper of dse_optimize_stmt.
> Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
> according to downstream uses and defs. Sets *BY_CLOBBER_P to true
> @@ -949,8 +960,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
> return DSE_STORE_LIVE;
>
> auto_vec<gimple *, 10> defs;
> - gimple *first_phi_def = NULL;
> - gimple *last_phi_def = NULL;
> + gphi *first_phi_def = NULL;
> + gphi *last_phi_def = NULL;
> FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
> {
> /* Limit stmt walking. */
> @@ -973,8 +984,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
> {
> defs.safe_push (use_stmt);
> if (!first_phi_def)
> - first_phi_def = use_stmt;
> - last_phi_def = use_stmt;
> + first_phi_def = as_a <gphi *> (use_stmt);
> + last_phi_def = as_a <gphi *> (use_stmt);
> }
> }
> /* If the statement is a use the store is not dead. */
> @@ -1046,6 +1057,7 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
> use_operand_p use_p;
> tree vdef = (gimple_code (def) == GIMPLE_PHI
> ? gimple_phi_result (def) : gimple_vdef (def));
> + gphi *phi_def;
> /* If the path to check starts with a kill we do not need to
> process it further.
> ??? With byte tracking we need only kill the bytes currently
> @@ -1079,7 +1091,31 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
> && bitmap_bit_p (visited,
> SSA_NAME_VERSION
> (PHI_RESULT (use_stmt))))))
> - defs.unordered_remove (i);
> + {
> + defs.unordered_remove (i);
> + if (def == first_phi_def)
> + first_phi_def = NULL;
> + else if (def == last_phi_def)
> + last_phi_def = NULL;
> + }
> + /* If def is a PHI and one of its arguments is another PHI node still
> + in consideration we can defer processing it. */
> + else if ((phi_def = dyn_cast <gphi *> (def))
> + && ((last_phi_def
> + && phi_def != last_phi_def
> + && contains_phi_arg (phi_def,
> + gimple_phi_result (last_phi_def)))
> + || (first_phi_def
> + && phi_def != first_phi_def
> + && contains_phi_arg
> + (phi_def, gimple_phi_result (first_phi_def)))))
> + {
> + defs.unordered_remove (i);
> + if (phi_def == first_phi_def)
> + first_phi_def = NULL;
> + else if (phi_def == last_phi_def)
> + last_phi_def = NULL;
> + }
> else
> ++i;
> }
> --
> 2.35.3
On Tue, 24 May 2022, Prathamesh Kulkarni wrote:
> On Tue, 24 May 2022 at 11:50, Richard Biener via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
> >
> > When facing multiple PHI defs and one feeding the other we can
> > postpone processing uses of one and thus can proceed.
> >
> > Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
> >
> > 2022-05-20 Richard Biener <rguenther@suse.de>
> >
> > PR tree-optimization/100221
> > * tree-ssa-dse.cc (contains_phi_arg): New function.
> > (dse_classify_store): Postpone PHI defs that feed another PHI in defs.
> >
> > * gcc.dg/tree-ssa/ssa-dse-44.c: New testcase.
> > * gcc.dg/tree-ssa/ssa-dse-45.c: Likewise.
> > ---
> > gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c | 19 +++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c | 24 +++++++++++
> > gcc/tree-ssa-dse.cc | 46 +++++++++++++++++++---
> > 3 files changed, 84 insertions(+), 5 deletions(-)
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c
> >
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c
> > new file mode 100644
> > index 00000000000..aaec41d7bdf
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c
> > @@ -0,0 +1,19 @@
> > +/* { dg-do link } */
> > +/* { dg-options "-O -fdump-tree-dse1-details" } */
> > +
> > +extern void foo(void);
> > +int a, b;
> > +static int c;
> > +int main()
> > +{
> > + if (c)
> > + foo ();
> > + int *g = &c;
> > + int **h = &g;
> > + int ***h1 = &h;
> > + if (a)
> > + while (b)
> > + b = 0;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump "Deleted dead store: g = &c;" "dse1" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c
> > new file mode 100644
> > index 00000000000..fd92d7b599a
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c
> > @@ -0,0 +1,24 @@
> > +/* { dg-do link } */
> > +/* { dg-options "-O" } */
> > +
> > +extern void foo(void);
> > +int a, b;
> > +static int c;
> > +static void f() {
> > + while (a)
> > + for (; b; b--)
> > + ;
> > +}
> > +void i() {
> > + if (c)
> > + foo();
> > + int *g = &c;
> > + {
> > + int **h[1] = {&g};
> > + f();
> > + }
> > +}
> > +int main() {
> > + i();
> > + return 0;
> > +}
> > diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc
> > index 881a2d0f98d..ea50de789b1 100644
> > --- a/gcc/tree-ssa-dse.cc
> > +++ b/gcc/tree-ssa-dse.cc
> > @@ -898,6 +898,17 @@ dse_optimize_redundant_stores (gimple *stmt)
> > }
> > }
> >
> > +/* Return whether PHI contains ARG as an argument. */
> > +
> > +static bool
> > +contains_phi_arg (gphi *phi, tree arg)
> > +{
> > + for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
> > + if (gimple_phi_arg_def (phi, i) == arg)
> > + return true;
> > + return false;
> > +}
> Hi Richard,
> Just wondering if contains_phi_arg could be a more general purpose
> utility function, and moved to gimple.cc
> or tree-ssa.cc than be specific to tree-ssa-dse.cc ?
The implementation doesn't work for all kind of 'arg' and I did not
want to make it more expensive than required (it's also a bit
gross to walk all args of course).
Richard.
> Thanks,
> Prathamesh
> > +
> > /* A helper of dse_optimize_stmt.
> > Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
> > according to downstream uses and defs. Sets *BY_CLOBBER_P to true
> > @@ -949,8 +960,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
> > return DSE_STORE_LIVE;
> >
> > auto_vec<gimple *, 10> defs;
> > - gimple *first_phi_def = NULL;
> > - gimple *last_phi_def = NULL;
> > + gphi *first_phi_def = NULL;
> > + gphi *last_phi_def = NULL;
> > FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
> > {
> > /* Limit stmt walking. */
> > @@ -973,8 +984,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
> > {
> > defs.safe_push (use_stmt);
> > if (!first_phi_def)
> > - first_phi_def = use_stmt;
> > - last_phi_def = use_stmt;
> > + first_phi_def = as_a <gphi *> (use_stmt);
> > + last_phi_def = as_a <gphi *> (use_stmt);
> > }
> > }
> > /* If the statement is a use the store is not dead. */
> > @@ -1046,6 +1057,7 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
> > use_operand_p use_p;
> > tree vdef = (gimple_code (def) == GIMPLE_PHI
> > ? gimple_phi_result (def) : gimple_vdef (def));
> > + gphi *phi_def;
> > /* If the path to check starts with a kill we do not need to
> > process it further.
> > ??? With byte tracking we need only kill the bytes currently
> > @@ -1079,7 +1091,31 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
> > && bitmap_bit_p (visited,
> > SSA_NAME_VERSION
> > (PHI_RESULT (use_stmt))))))
> > - defs.unordered_remove (i);
> > + {
> > + defs.unordered_remove (i);
> > + if (def == first_phi_def)
> > + first_phi_def = NULL;
> > + else if (def == last_phi_def)
> > + last_phi_def = NULL;
> > + }
> > + /* If def is a PHI and one of its arguments is another PHI node still
> > + in consideration we can defer processing it. */
> > + else if ((phi_def = dyn_cast <gphi *> (def))
> > + && ((last_phi_def
> > + && phi_def != last_phi_def
> > + && contains_phi_arg (phi_def,
> > + gimple_phi_result (last_phi_def)))
> > + || (first_phi_def
> > + && phi_def != first_phi_def
> > + && contains_phi_arg
> > + (phi_def, gimple_phi_result (first_phi_def)))))
> > + {
> > + defs.unordered_remove (i);
> > + if (phi_def == first_phi_def)
> > + first_phi_def = NULL;
> > + else if (phi_def == last_phi_def)
> > + last_phi_def = NULL;
> > + }
> > else
> > ++i;
> > }
> > --
> > 2.35.3
>
new file mode 100644
@@ -0,0 +1,19 @@
+/* { dg-do link } */
+/* { dg-options "-O -fdump-tree-dse1-details" } */
+
+extern void foo(void);
+int a, b;
+static int c;
+int main()
+{
+ if (c)
+ foo ();
+ int *g = &c;
+ int **h = &g;
+ int ***h1 = &h;
+ if (a)
+ while (b)
+ b = 0;
+}
+
+/* { dg-final { scan-tree-dump "Deleted dead store: g = &c;" "dse1" } } */
new file mode 100644
@@ -0,0 +1,24 @@
+/* { dg-do link } */
+/* { dg-options "-O" } */
+
+extern void foo(void);
+int a, b;
+static int c;
+static void f() {
+ while (a)
+ for (; b; b--)
+ ;
+}
+void i() {
+ if (c)
+ foo();
+ int *g = &c;
+ {
+ int **h[1] = {&g};
+ f();
+ }
+}
+int main() {
+ i();
+ return 0;
+}
@@ -898,6 +898,17 @@ dse_optimize_redundant_stores (gimple *stmt)
}
}
+/* Return whether PHI contains ARG as an argument. */
+
+static bool
+contains_phi_arg (gphi *phi, tree arg)
+{
+ for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
+ if (gimple_phi_arg_def (phi, i) == arg)
+ return true;
+ return false;
+}
+
/* A helper of dse_optimize_stmt.
Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
according to downstream uses and defs. Sets *BY_CLOBBER_P to true
@@ -949,8 +960,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
return DSE_STORE_LIVE;
auto_vec<gimple *, 10> defs;
- gimple *first_phi_def = NULL;
- gimple *last_phi_def = NULL;
+ gphi *first_phi_def = NULL;
+ gphi *last_phi_def = NULL;
FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
{
/* Limit stmt walking. */
@@ -973,8 +984,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
{
defs.safe_push (use_stmt);
if (!first_phi_def)
- first_phi_def = use_stmt;
- last_phi_def = use_stmt;
+ first_phi_def = as_a <gphi *> (use_stmt);
+ last_phi_def = as_a <gphi *> (use_stmt);
}
}
/* If the statement is a use the store is not dead. */
@@ -1046,6 +1057,7 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
use_operand_p use_p;
tree vdef = (gimple_code (def) == GIMPLE_PHI
? gimple_phi_result (def) : gimple_vdef (def));
+ gphi *phi_def;
/* If the path to check starts with a kill we do not need to
process it further.
??? With byte tracking we need only kill the bytes currently
@@ -1079,7 +1091,31 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
&& bitmap_bit_p (visited,
SSA_NAME_VERSION
(PHI_RESULT (use_stmt))))))
- defs.unordered_remove (i);
+ {
+ defs.unordered_remove (i);
+ if (def == first_phi_def)
+ first_phi_def = NULL;
+ else if (def == last_phi_def)
+ last_phi_def = NULL;
+ }
+ /* If def is a PHI and one of its arguments is another PHI node still
+ in consideration we can defer processing it. */
+ else if ((phi_def = dyn_cast <gphi *> (def))
+ && ((last_phi_def
+ && phi_def != last_phi_def
+ && contains_phi_arg (phi_def,
+ gimple_phi_result (last_phi_def)))
+ || (first_phi_def
+ && phi_def != first_phi_def
+ && contains_phi_arg
+ (phi_def, gimple_phi_result (first_phi_def)))))
+ {
+ defs.unordered_remove (i);
+ if (phi_def == first_phi_def)
+ first_phi_def = NULL;
+ else if (phi_def == last_phi_def)
+ last_phi_def = NULL;
+ }
else
++i;
}