public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: Richard Biener <rguenther@suse.de>
To: Ju-Zhe Zhong <juzhe.zhong@rivai.ai>
Cc: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com
Subject: Re: [PATCH] DSE: Enhance dse with def-ref analysis
Date: Thu, 22 Sep 2022 07:44:11 +0000 (UTC)	[thread overview]
Message-ID: <nycvar.YFH.7.77.849.2209220741420.6652@jbgna.fhfr.qr> (raw)
In-Reply-To: <nycvar.YFH.7.77.849.2209220721430.6652@jbgna.fhfr.qr>

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.
-- 
2.35.3


  parent reply	other threads:[~2022-09-22  7:44 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-09-22  7:06 juzhe.zhong
2022-09-22  7:32 ` Richard Biener
2022-09-22  7:40   ` juzhe.zhong
2022-09-22  7:44   ` Richard Biener [this message]
     [not found]     ` <2794D55ECC21EB61+2022092215574700429612@rivai.ai>
     [not found]       ` <nycvar.YFH.7.77.849.2209220800020.6652@jbgna.fhfr.qr>
2022-09-22  8:08         ` juzhe.zhong
2022-09-22  8:48           ` Richard Biener
2022-09-22  8:51             ` juzhe.zhong
2022-09-22  9:12             ` juzhe.zhong
2022-09-22  9:29               ` Richard Biener
  -- strict thread matches above, loose matches on Subject: below --
2022-09-22  6:58 juzhe.zhong

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=nycvar.YFH.7.77.849.2209220741420.6652@jbgna.fhfr.qr \
    --to=rguenther@suse.de \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=juzhe.zhong@rivai.ai \
    --cc=richard.sandiford@arm.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).