On Wed, 16 May 2018, Richard Biener wrote:
> On Tue, 15 May 2018, Richard Biener wrote:
>
> > On Tue, 15 May 2018, Richard Biener wrote:
> >
> > > On Tue, 15 May 2018, Richard Biener wrote:
> > >
> > > > On Tue, 15 May 2018, Richard Biener wrote:
> > > >
> > > > > On Tue, 15 May 2018, Richard Biener wrote:
> > > > >
> > > > > > On Mon, 14 May 2018, Kugan Vivekanandarajah wrote:
> > > > > >
> > > > > > > Hi,
> > > > > > >
> > > > > > > Attached patch handles PR63185 when we reach PHI with temp !=
> > > > > > > NULLL.
> > > > > > > We could see the PHI and if there isn't any uses for PHI that is
> > > > > > > interesting, we could ignore that ?
> > > > > > >
> > > > > > > Bootstrapped and regression tested on x86_64-linux-gnu.
> > > > > > > Is this OK?
> > > > > >
> > > > > > No, as Jeff said we can't do it this way.
> > > > > >
> > > > > > If we end up with multiple VDEFs in the walk of defvar immediate
> > > > > > uses we know we are dealing with a CFG fork. We can't really
> > > > > > ignore any of the paths but we have to
> > > > > >
> > > > > > a) find the merge point (and the associated VDEF)
> > > > > > b) verify for each each chain of VDEFs with associated VUSEs
> > > > > > up to that merge VDEF that we have no uses of the to classify
> > > > > > store and collect (partial) kills
> > > > > > c) intersect kill info and continue walking from the merge point
> > > > > >
> > > > > > in b) there's the optional possibility to find sinking opportunities
> > > > > > in case we have kills on some paths but uses on others. This is why
> > > > > > DSE should be really merged with (store) sinking.
> > > > > >
> > > > > > So if we want to enhance DSEs handling of branches then we need
> > > > > > to refactor the simple dse_classify_store function. Let me take
> > > > > > an attempt at this today.
> > > > >
> > > > > First (baby) step is the following - it arranges to collect the
> > > > > defs we need to continue walking from and implements trivial
> > > > > reduction by stopping at (full) kills. This allows us to handle
> > > > > the new testcase (which was already handled in the very late DSE
> > > > > pass with the help of sinking the store).
> > > > >
> > > > > I took the opportunity to kill the use_stmt parameter of
> > > > > dse_classify_store as the only user is only looking for whether
> > > > > the kills were all clobbers which I added a new parameter for.
> > > > >
> > > > > I didn't adjust the byte-tracking case fully (I'm not fully
> > > > > understanding
> > > > > the code in the case of a use and I'm not sure whether it's worth
> > > > > doing the def reduction with byte-tracking).
> > > > >
> > > > > Your testcase can be handled by reducing the PHI and the call def
> > > > > by seeing that the only use of a candidate def is another def
> > > > > we have already processed. Not sure if worth special-casing though,
> > > > > I'd rather have a go at "recursing". That will be the next
> > > > > patch.
> > > > >
> > > > > Bootstrap & regtest running on x86_64-unknown-linux-gnu.
> > > >
> > > > Applied.
> > > >
> > > > Another intermediate one below, fixing the byte-tracking for
> > > > stmt with uses. This also re-does the PHI handling by simply
> > > > avoiding recursion by means of a visited bitmap and stopping
> > > > at the DSE classify stmt when re-visiting it instead of failing.
> > > > This covers Pratamesh loop case for which I added ssa-dse-33.c.
> > > > For the do-while loop this still runs into the inability to
> > > > handle two defs to walk from.
> > > >
> > > > Bootstrap & regtest running on x86_64-unknown-linux-gnu.
> > >
> > > Ok, loop handling doesn't work in general since we run into the
> > > issue that SSA form across the backedge is not representing the
> > > same values. Consider
> > >
> > > <bb 3>
> > > # .MEM_22 = PHI <.MEM_12(D)(2), .MEM_13(4)>
> > > # n_20 = PHI <0(2), n_7(4)>
> > > # .MEM_13 = VDEF <.MEM_22>
> > > bytes[n_20] = _4;
> > > if (n_20 > 7)
> > > goto <bb 5>;
> > >
> > > <bb 4>
> > > n_7 = n_20 + 1;
> > > # .MEM_15 = VDEF <.MEM_13>
> > > bytes[n_20] = _5;
> > > goto <bb 3>;
> > >
> > > then when classifying the store in bb4, visiting the PHI node
> > > gets us to the store in bb3 which appears to be killing.
> > >
> > > if (gimple_code (temp) == GIMPLE_PHI)
> > > - defvar = PHI_RESULT (temp);
> > > + {
> > > + /* If we visit this PHI by following a backedge then reset
> > > + any info in ref that may refer to SSA names which we'd need
> > > + to PHI translate. */
> > > + if (gimple_bb (temp) == gimple_bb (stmt)
> > > + || dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt),
> > > + gimple_bb (temp)))
> > > + /* ??? ref->ref may not refer to SSA names or it may only
> > > + refer to SSA names that are invariant with respect to the
> > > + loop represented by this PHI node. */
> > > + ref->ref = NULL_TREE;
> > > + defvar = PHI_RESULT (temp);
> > > + bitmap_set_bit (visited, SSA_NAME_VERSION (defvar));
> > > + }
> > >
> > > should be a workable solution for that. I'm checking that, but
> > > eventually you can think of other things that might prevent us from
> > > handling backedges. Note the current code tries to allow
> > > looking across loops but not handle backedges of loops the
> > > original stmt belongs to.
> >
> > Just to mention before I leave for the day I think I've identified
> > a latent issue where I just fail to produce a testcase right now
> > which is that non-return exits from a function are not reliably
> > visited given they do not all have virtual operands, like
> > for example resx. Thus consider
> >
> > void foo (int *p, int x)
> > {
> > *p = 0;
> > if (x)
> > resx;
> > *p = 1;
> > return;
> > }
> >
> > where we will never visit any stmts on the resx path and thus think
> > the *p = 0 store is dead (all with current trunk of course).
> >
> > Will continue to dig tomorrow.
>
> PR85803.
>
> I am currently re-testing the following on x86_64-unknown-linux-gnu
> with --param dse-max-alias-queries-per-store=100000 in BOOT_CFLAGS.
>
> I'll refrain from doing the separate-walks-for-each-def thing
> but will try to fix PR85757 by pattern matching the
> def-has-single-virtual-use-that-is-another-def-in-the-vector case
> in which case we can remove it from further processing.
After committing I am now testing that fix for PR85757
on x86_64-unknown-linux-gnu.
Richard.
2018-05-16 Richard Biener <rguent...@suse.de>
PR tree-optimization/85757
* tree-ssa-dse.c (dse_classify_store): Record a PHI def and
remove defs that only feed that PHI from further processing.
* gcc.dg/tree-ssa/ssa-dse-34.c: New testcase.
>From bf8054a966485ba32b1b25ab287312eaf4b763d8 Mon Sep 17 00:00:00 2001
From: Richard Guenther <rguent...@suse.de>
Date: Wed, 16 May 2018 13:50:18 +0200
Subject: [PATCH 3/4] dse#3
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-34.c
b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-34.c
new file mode 100644
index 00000000000..3016dfecd38
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-34.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-dse1-details" } */
+
+void f(int n, char *p0, char *p1, char *p2, char *o)
+{
+ int t0, t1;
+ __builtin_memcpy(&t0, p0, 1);
+ __builtin_memcpy(&t1, p1, 1);
+ if (n==3)
+ __builtin_memcpy(o+2, p2, 1);
+ __builtin_memcpy(o+0, &t0, 1);
+ __builtin_memcpy(o+1, &t1, 1);
+}
+
+/* { dg-final { scan-tree-dump-times "Deleted dead store" 2 "dse1" } } */
diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
index 32a25b9eb1e..589cfef5df5 100644
--- a/gcc/tree-ssa-dse.c
+++ b/gcc/tree-ssa-dse.c
@@ -577,6 +577,7 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
else
defvar = gimple_vdef (temp);
auto_vec<gimple *, 10> defs;
+ gimple *phi_def = NULL;
FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
{
/* Limit stmt walking. */
@@ -600,7 +601,10 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
processing. */
if (!bitmap_bit_p (visited,
SSA_NAME_VERSION (PHI_RESULT (use_stmt))))
- defs.safe_push (use_stmt);
+ {
+ defs.safe_push (use_stmt);
+ phi_def = use_stmt;
+ }
}
/* If the statement is a use the store is not dead. */
else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
@@ -657,15 +661,31 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
return DSE_STORE_DEAD;
}
- /* Process defs and remove paths starting with a kill from further
- processing. */
+ /* Process defs and remove those we need not process further. */
for (unsigned i = 0; i < defs.length (); ++i)
- if (stmt_kills_ref_p (defs[i], ref))
- {
- if (by_clobber_p && !gimple_clobber_p (defs[i]))
- *by_clobber_p = false;
+ {
+ gimple *def = defs[i];
+ gimple *use_stmt;
+ use_operand_p use_p;
+ /* 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
+ live. */
+ if (stmt_kills_ref_p (def, ref))
+ {
+ if (by_clobber_p && !gimple_clobber_p (def))
+ *by_clobber_p = false;
+ defs.unordered_remove (i);
+ }
+ /* In addition to kills we can remove defs whose only use
+ is another def in defs. That can only ever be PHIs of which
+ we track a single for simplicity reasons (we fail for multiple
+ PHIs anyways). */
+ else if (gimple_code (def) != GIMPLE_PHI
+ && single_imm_use (gimple_vdef (def), &use_p, &use_stmt)
+ && use_stmt == phi_def)
defs.unordered_remove (i);
- }
+ }
/* If all defs kill the ref we are done. */
if (defs.is_empty ())
--
2.12.3
