[gcc r13-2769] tree-optimization/99407 - DSE with data-ref analysis

[Richard Biener <rguenth@gcc.gnu.org>]

https://gcc.gnu.org/g:4bdf739f835520ccbc433dc9eac461895741f317

commit r13-2769-g4bdf739f835520ccbc433dc9eac461895741f317
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Sep 22 09:40:40 2022 +0200

    tree-optimization/99407 - DSE with data-ref analysis
    
    The following resolves the issue that DSE cannot handle references
    with variable offsets well when identifying possible uses of a store.
    Instead of just relying on ref_maybe_used_by_stmt_p we use data-ref
    analysis, making sure to perform that at most once per stmt.  The
    new mode is only exercised by the DSE pass before loop optimization
    as specified by a new pass parameter and when expensive optimizations
    are enabled, so it's disabled below -O2.
    
            PR tree-optimization/99407
            * tree-ssa-dse.cc (dse_stmt_to_dr_map): New global.
            (dse_classify_store): Use data-ref analysis to disambiguate more uses.
            (pass_dse::use_dr_analysis_p): New pass parameter.
            (pass_dse::set_pass_param): Implement.
            (pass_dse::execute): Allocate and deallocate dse_stmt_to_dr_map.
            * passes.def: Allow DR analysis for the DSE pass before loop.
    
            * gcc.dg/vect/tsvc/vect-tsvc-s243.c: Remove XFAIL.

Diff:
---
 gcc/passes.def                                  |  2 +-
 gcc/testsuite/gcc.dg/vect/tsvc/vect-tsvc-s243.c |  2 +-
 gcc/tree-ssa-dse.cc                             | 51 ++++++++++++++++++++++++-
 3 files changed, 52 insertions(+), 3 deletions(-)

diff --git a/gcc/passes.def b/gcc/passes.def
index 6bb92efacd4..939ec3e29c8 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -263,7 +263,7 @@ along with GCC; see the file COPYING3.  If not see
       NEXT_PASS (pass_sancov);
       NEXT_PASS (pass_asan);
       NEXT_PASS (pass_tsan);
-      NEXT_PASS (pass_dse);
+      NEXT_PASS (pass_dse, true /* use DR analysis */);
       NEXT_PASS (pass_dce);
       /* Pass group that runs when 1) enabled, 2) there are loops
 	 in the function.  Make sure to run pass_fix_loops before
diff --git a/gcc/testsuite/gcc.dg/vect/tsvc/vect-tsvc-s243.c b/gcc/testsuite/gcc.dg/vect/tsvc/vect-tsvc-s243.c
index 93618213c74..6eb0240da40 100644
--- a/gcc/testsuite/gcc.dg/vect/tsvc/vect-tsvc-s243.c
+++ b/gcc/testsuite/gcc.dg/vect/tsvc/vect-tsvc-s243.c
@@ -38,4 +38,4 @@ int main (int argc, char **argv)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump "vectorized 1 loops" "vect" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump "vectorized 1 loops" "vect" } } */
diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc
index 34cfd1a8802..2411ac711de 100644
--- a/gcc/tree-ssa-dse.cc
+++ b/gcc/tree-ssa-dse.cc
@@ -18,6 +18,7 @@ along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
 #include "config.h"
+#define INCLUDE_MEMORY
 #include "system.h"
 #include "coretypes.h"
 #include "backend.h"
@@ -45,6 +46,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.
 
@@ -937,6 +940,10 @@ contains_phi_arg (gphi *phi, tree arg)
   return false;
 }
 
+/* Hash map of the memory use in a GIMPLE assignment to its
+   data reference.  If NULL data-ref analysis isn't used.  */
+static hash_map<gimple *, data_reference_p> *dse_stmt_to_dr_map;
+
 /* 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
@@ -951,6 +958,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
   gimple *temp;
   int cnt = 0;
   auto_bitmap visited;
+  std::unique_ptr<data_reference, void(*)(data_reference_p)>
+    dra (nullptr, free_data_ref);
 
   if (by_clobber_p)
     *by_clobber_p = true;
@@ -1019,6 +1028,28 @@ 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 (dse_stmt_to_dr_map
+		  && ref->ref
+		  && is_gimple_assign (use_stmt))
+		{
+		  if (!dra)
+		    dra.reset (create_data_ref (NULL, NULL, ref->ref, stmt,
+						false, false));
+		  bool existed_p;
+		  data_reference_p &drb
+		    = dse_stmt_to_dr_map->get_or_insert (use_stmt, &existed_p);
+		  if (!existed_p)
+		    drb = create_data_ref (NULL, NULL,
+					   gimple_assign_rhs1 (use_stmt),
+					   use_stmt, false, false);
+		  if (!dr_may_alias_p (dra.get (), drb, NULL))
+		    {
+		      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.
@@ -1535,14 +1566,21 @@ class pass_dse : public gimple_opt_pass
 {
 public:
   pass_dse (gcc::context *ctxt)
-    : gimple_opt_pass (pass_data_dse, ctxt)
+    : gimple_opt_pass (pass_data_dse, ctxt), use_dr_analysis_p (false)
   {}
 
   /* opt_pass methods: */
   opt_pass * clone () final override { return new pass_dse (m_ctxt); }
+  void set_pass_param (unsigned n, bool param) final override
+    {
+      gcc_assert (n == 0);
+      use_dr_analysis_p = param;
+    }
   bool gate (function *) final override { return flag_tree_dse != 0; }
   unsigned int execute (function *) final override;
 
+private:
+  bool use_dr_analysis_p;
 }; // class pass_dse
 
 unsigned int
@@ -1554,6 +1592,8 @@ pass_dse::execute (function *fun)
   need_eh_cleanup = BITMAP_ALLOC (NULL);
   need_ab_cleanup = BITMAP_ALLOC (NULL);
   auto_sbitmap live_bytes (param_dse_max_object_size);
+  if (flag_expensive_optimizations && use_dr_analysis_p)
+    dse_stmt_to_dr_map = new hash_map<gimple *, data_reference_p>;
 
   renumber_gimple_stmt_uids (fun);
 
@@ -1644,6 +1684,15 @@ pass_dse::execute (function *fun)
   if (released_def)
     free_numbers_of_iterations_estimates (fun);
 
+  if (flag_expensive_optimizations && use_dr_analysis_p)
+    {
+      for (auto i = dse_stmt_to_dr_map->begin ();
+	   i != dse_stmt_to_dr_map->end (); ++i)
+	free_data_ref ((*i).second);
+      delete dse_stmt_to_dr_map;
+      dse_stmt_to_dr_map = NULL;
+    }
+
   return todo;
 }