Hi Richard,
On 15 May 2018 at 19:20, Richard Biener <rguent...@suse.de> 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).
Thanks for the explanation and thanks for working on this.
>
> 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).
Since byte tracking is tracking the killed subset of bytes in the
original def, in your patch can we calculate the bytes killed by each
defs[i] and then find the intersection for the iteration. If we don't
have complete kill, we can use this to set live bytes and iterate till
all the live_bytes are cleared like it was done earlier.
Thanks,
Kugan
>
> 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.
>
> Richard.
>
> 2018-05-15 Richard Biener <rguent...@suse.de>
>
> * tree-ssa-dse.c (dse_classify_store): Remove use_stmt parameter,
> add by_clobber_p one. Change algorithm to collect all defs
> representing uses we need to walk and try reducing them to
> a single one before failing.
> (dse_dom_walker::dse_optimize_stmt): Adjust.
>
> * gcc.dg/tree-ssa/ssa-dse-31.c: New testcase.
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-31.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-31.c
> new file mode 100644
> index 00000000000..9ea9268fe1d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-31.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-dse1-details" } */
> +
> +void g();
> +void f(int n, char *p)
> +{
> + *p = 0;
> + if (n)
> + {
> + *p = 1;
> + g();
> + }
> + *p = 2;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Deleted dead store" 1 "dse1" } } */
> diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
> index 9220fea7f2e..126592a1d13 100644
> --- a/gcc/tree-ssa-dse.c
> +++ b/gcc/tree-ssa-dse.c
> @@ -516,18 +516,21 @@ live_bytes_read (ao_ref use_ref, ao_ref *ref, sbitmap
> live)
> }
>
> /* A helper of dse_optimize_stmt.
> - Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate
> - statement *USE_STMT that may prove STMT to be dead.
> - Return TRUE if the above conditions are met, otherwise FALSE. */
> + Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
> + according to downstream uses and defs. Sets *BY_CLOBBER_P to true
> + if only clobber statements influenced the classification result.
> + Returns the classification. */
>
> static dse_store_status
> -dse_classify_store (ao_ref *ref, gimple *stmt, gimple **use_stmt,
> - bool byte_tracking_enabled, sbitmap live_bytes)
> +dse_classify_store (ao_ref *ref, gimple *stmt,
> + bool byte_tracking_enabled, sbitmap live_bytes,
> + bool *by_clobber_p = NULL)
> {
> gimple *temp;
> unsigned cnt = 0;
>
> - *use_stmt = NULL;
> + if (by_clobber_p)
> + *by_clobber_p = true;
>
> /* Find the first dominated statement that clobbers (part of) the
> memory stmt stores to with no intermediate statement that may use
> @@ -551,7 +554,7 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple
> **use_stmt,
> else
> defvar = gimple_vdef (temp);
> defvar_def = temp;
> - temp = NULL;
> + auto_vec<gimple *, 10> defs;
> FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
> {
> cnt++;
> @@ -569,9 +572,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple
> **use_stmt,
> See gcc.c-torture/execute/20051110-*.c. */
> else if (gimple_code (use_stmt) == GIMPLE_PHI)
> {
> - if (temp
> - /* Make sure we are not in a loop latch block. */
> - || gimple_bb (stmt) == gimple_bb (use_stmt)
> + /* Make sure we are not in a loop latch block. */
> + if (gimple_bb (stmt) == gimple_bb (use_stmt)
> || dominated_by_p (CDI_DOMINATORS,
> gimple_bb (stmt), gimple_bb (use_stmt))
> /* We can look through PHIs to regions post-dominating
> @@ -589,7 +591,7 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple
> **use_stmt,
> && !dominated_by_p (CDI_DOMINATORS,
> gimple_bb (defvar_def),
> gimple_bb (use_stmt)))
> - temp = use_stmt;
> + defs.safe_push (use_stmt);
> }
> /* If the statement is a use the store is not dead. */
> else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
> @@ -597,7 +599,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple
> **use_stmt,
> /* Handle common cases where we can easily build an ao_ref
> structure for USE_STMT and in doing so we find that the
> references hit non-live bytes and thus can be ignored. */
> - if (byte_tracking_enabled && (!gimple_vdef (use_stmt) || !temp))
> + if (byte_tracking_enabled
> + && (!gimple_vdef (use_stmt) || defs.is_empty ()))
> {
> if (is_gimple_assign (use_stmt))
> {
> @@ -613,7 +616,7 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple
> **use_stmt,
> /* If this statement has a VDEF, then it is the
> first store we have seen, so walk through it. */
> if (gimple_vdef (use_stmt))
> - temp = use_stmt;
> + defs.safe_push (use_stmt);
> continue;
> }
> }
> @@ -622,17 +625,10 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple
> **use_stmt,
> fail = true;
> BREAK_FROM_IMM_USE_STMT (ui);
> }
> - /* If this is a store, remember it or bail out if we have
> - multiple ones (the will be in different CFG parts then). */
> + /* If this is a store, remember it as we possibly need to walk the
> + defs uses. */
> else if (gimple_vdef (use_stmt))
> - {
> - if (temp)
> - {
> - fail = true;
> - BREAK_FROM_IMM_USE_STMT (ui);
> - }
> - temp = use_stmt;
> - }
> + defs.safe_push (use_stmt);
> }
>
> if (fail)
> @@ -647,25 +643,54 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple
> **use_stmt,
> /* If we didn't find any definition this means the store is dead
> if it isn't a store to global reachable memory. In this case
> just pretend the stmt makes itself dead. Otherwise fail. */
> - if (!temp)
> + if (defs.is_empty ())
> {
> if (ref_may_alias_global_p (ref))
> return DSE_STORE_LIVE;
>
> - temp = stmt;
> - break;
> + if (by_clobber_p)
> + *by_clobber_p = false;
> + return DSE_STORE_DEAD;
> }
>
> - if (byte_tracking_enabled && temp)
> - clear_bytes_written_by (live_bytes, temp, ref);
> - }
> - /* Continue walking until we reach a full kill as a single statement
> - or there are no more live bytes. */
> - while (!stmt_kills_ref_p (temp, ref)
> - && !(byte_tracking_enabled && bitmap_empty_p (live_bytes)));
> + /* Process defs and remove paths starting with a kill from further
> + processing. */
> + 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;
> + defs.unordered_remove (i);
> + }
> +
> + /* If all defs kill the ref we are done. */
> + if (defs.is_empty ())
> + return DSE_STORE_DEAD;
> + /* If more than one def survives fail. */
> + if (defs.length () > 1)
> + {
> + /* STMT might be partially dead and we may be able to reduce
> + how many memory locations it stores into. */
> + if (byte_tracking_enabled && !gimple_clobber_p (stmt))
> + return DSE_STORE_MAYBE_PARTIAL_DEAD;
> + return DSE_STORE_LIVE;
> + }
> + temp = defs[0];
>
> - *use_stmt = temp;
> - return DSE_STORE_DEAD;
> + /* Track partial kills. */
> + if (byte_tracking_enabled)
> + {
> + clear_bytes_written_by (live_bytes, temp, ref);
> + if (bitmap_empty_p (live_bytes))
> + {
> + if (by_clobber_p && !gimple_clobber_p (temp))
> + *by_clobber_p = false;
> + return DSE_STORE_DEAD;
> + }
> + }
> + }
> + /* Continue walking until there are no more live bytes. */
> + while (1);
> }
>
>
> @@ -795,11 +820,10 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator
> *gsi)
> return;
> }
>
> - gimple *use_stmt;
> enum dse_store_status store_status;
> m_byte_tracking_enabled
> = setup_live_bytes_from_ref (&ref, m_live_bytes);
> - store_status = dse_classify_store (&ref, stmt, &use_stmt,
> + store_status = dse_classify_store (&ref, stmt,
> m_byte_tracking_enabled,
> m_live_bytes);
> if (store_status == DSE_STORE_LIVE)
> @@ -823,20 +847,20 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator
> *gsi)
>
> if (is_gimple_assign (stmt))
> {
> - gimple *use_stmt;
> + bool by_clobber_p = false;
>
> /* Self-assignments are zombies. */
> if (operand_equal_p (gimple_assign_rhs1 (stmt),
> gimple_assign_lhs (stmt), 0))
> - use_stmt = stmt;
> + ;
> else
> {
> m_byte_tracking_enabled
> = setup_live_bytes_from_ref (&ref, m_live_bytes);
> enum dse_store_status store_status;
> - store_status = dse_classify_store (&ref, stmt, &use_stmt,
> + store_status = dse_classify_store (&ref, stmt,
> m_byte_tracking_enabled,
> - m_live_bytes);
> + m_live_bytes, &by_clobber_p);
> if (store_status == DSE_STORE_LIVE)
> return;
>
> @@ -852,7 +876,7 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator
> *gsi)
> /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
> another clobber stmt. */
> if (gimple_clobber_p (stmt)
> - && !gimple_clobber_p (use_stmt))
> + && !by_clobber_p)
> return;
>
> delete_dead_assignment (gsi);
