Re: Re: [PATCH] DSE: Enhance dse with def-ref analysis

["juzhe.zhong@rivai.ai" <juzhe.zhong@rivai.ai>]

[-- Attachment #1: Type: text/plain, Size: 6176 bytes --]

Does your local code exclude my codes?
I am using GCC12.2. When I delete all my codes and apply your codes only.
It fails to delete redundant stores and no auto-vecotorization of my RVV GCC in this test. 
I am not sure whether I am on the same page with you.




juzhe.zhong@rivai.ai
 
From: Richard Biener
Date: 2022-09-22 16:01
To: juzhe.zhong@rivai.ai
Subject: Re: Re: [PATCH] DSE: Enhance dse with def-ref analysis
On Thu, 22 Sep 2022, juzhe.zhong@rivai.ai wrote:
 
> I tried this solution you gave:
> >> else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
> >>   {
> >>       if (is_gimple_assign (use_stmt))
> >> {
> >>   data_reference_p dra, drb;
> >>   dra = create_data_ref (NULL, NULL, ref->ref, stmt,
> >> false, false);
> >>   drb = create_data_ref (NULL, NULL,
> >> gimple_assign_rhs1 (use_stmt),
> >> use_stmt, false, false);
> >>   bool alias_p = dr_may_alias_p (dra, drb, NULL);
> >>   free_data_ref (dra);
> >>   free_data_ref (drb);
> >>   if (!alias_p)
> >>     {
> >>       if (gimple_vdef (use_stmt))
> >> defs.safe_push (use_stmt);
> >>       continue;
> >>     }
> >> }
> 
> It still fails to delete the redundant store. The reason is when checking the redundant store.
> it didn't match the condtion: ref_maybe_used_by_stmt_p (use_stmt, ref).
 
It does for me:
 
  Deleted dead store: a[i_18] = _5;
 
...
 
  <bb 3> :
  _1 = b[i_18];
  _2 = c[i_18];
  _3 = d[i_18];
  _4 = _2 * _3;
  _5 = _1 + _4;
  _8 = e[i_18];
  _9 = _3 * _8;
  _10 = _5 + _9;
  b[i_18] = _10;
  _12 = i_18 + 1;
  _13 = a[_12];
  _15 = _3 * _13;
  _16 = _10 + _15;
  a[i_18] = _16;
 
the other relevant function is stmt_kills_ref_p, that one does
handle a[i_18] vs. a[i_18] just fine.
 
> Maybe we should first figure why it doesn't satisfy this situation?
> 
> 
> juzhe.zhong@rivai.ai
>  
> From: Richard Biener
> Date: 2022-09-22 15:44
> To: Ju-Zhe Zhong
> CC: gcc-patches; richard.sandiford
> Subject: Re: [PATCH] DSE: Enhance dse with def-ref analysis
> On Thu, 22 Sep 2022, Richard Biener wrote:
>  
> > On Thu, 22 Sep 2022, juzhe.zhong@rivai.ai wrote:
> > 
> > > From: Ju-Zhe Zhong <juzhe.zhong@rivai.ai>
> > > 
> > > This patch fix issue: PR 99407
> > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99407
> > > 
> > > The enhancement implementation is simple:
> > > 1.Search gimple statement in program reverse order.
> > > 2.Queue the store statement which may be possible kill the def
> > >   of previous store statement.
> > > 3.Perform dse_def_ref_analysis to remove stores will not kill
> > >   any def.
> > >   For example:
> > >     a[i_18] = _5;
> > >     ...
> > >     foo (&a);
> > >     a[i_18] = _7;
> > >     
> > >   a[i_18] = _7 is queued at the begining and will be removed
> > >   in dse_def_ref_analysis.
> > > 4.Remove the store if the def is confirmed to be killed.
> > 
> > But we already do the very same thing in dse_classify_store, I fail
> > to see why we need to have an alternate implementation?  It also
> > seems to be quadratic in the size of a basic-block?
> > 
> > The issue with dse_classify_store is that it relies on
> > ref_maybe_used_by_stmt_p but that doesn't handle
> > 
> >  a[i] = ..;
> >  .. = a[i+1];
> > 
> > but when seeing a[_1] vs. a[_2] (two variable offsets), it gives
> > up, asserting may-aliasing.  We do have infrastructure to catch
> > such cases with data reference analysis.  If we want to catch
> > these cases we should use that instead.  Given we have a
> > DSE/DCE pass pair right before loop optimizations we could even
> > move those inside of the loop pipeline and perform this more
> > expensive checks conditional on loop/scev availability.
>  
> Oh, and when doing non-loop aware analysis we don't need SCEV.  The
> following optimizes the testcase but as said I don't think we want
> to perform this for each of the DSE passes since it can be somewhat
> expensive, at least without doing more caching (we could keep a
> stmt -> data-ref hash-map and compute data-refs at most once for each
> statement, that would make it more acceptable).
>  
> Richard.
>  
> From 515b213e9d06c2bd36160e66728f57e48095bb84 Mon Sep 17 00:00:00 2001
> From: Richard Biener <rguenther@suse.de>
> Date: Thu, 22 Sep 2022 09:40:40 +0200
> Subject: [PATCH] tree-optimization/99407 - DSE with data-ref analysis
> To: gcc-patches@gcc.gnu.org
>  
> * tree-ssa-dse.c (dse_classify_store): Use data-ref analysis
> to disambiguate more uses.
> ---
> gcc/tree-ssa-dse.cc | 21 +++++++++++++++++++++
> 1 file changed, 21 insertions(+)
>  
> diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc
> index 34cfd1a8802..340a54f4105 100644
> --- a/gcc/tree-ssa-dse.cc
> +++ b/gcc/tree-ssa-dse.cc
> @@ -45,6 +45,8 @@ along with GCC; see the file COPYING3.  If not see
> #include "ipa-modref.h"
> #include "target.h"
> #include "tree-ssa-loop-niter.h"
> +#include "cfgloop.h"
> +#include "tree-data-ref.h"
> /* This file implements dead store elimination.
> @@ -1019,6 +1021,25 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
>   /* If the statement is a use the store is not dead.  */
>   else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
>     {
> +       if (is_gimple_assign (use_stmt))
> + {
> +   data_reference_p dra, drb;
> +   dra = create_data_ref (NULL, NULL, ref->ref, stmt,
> + false, false);
> +   drb = create_data_ref (NULL, NULL,
> + gimple_assign_rhs1 (use_stmt),
> + use_stmt, false, false);
> +   bool alias_p = dr_may_alias_p (dra, drb, NULL);
> +   free_data_ref (dra);
> +   free_data_ref (drb);
> +   if (!alias_p)
> +     {
> +       if (gimple_vdef (use_stmt))
> + defs.safe_push (use_stmt);
> +       continue;
> +     }
> + }
> +
>       /* 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.
> 
 
-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
HRB 36809 (AG Nuernberg)