Basic kill analysis for modref

Jan Hubicka hubicka@kam.mff.cuni.cz
Sun Nov 14 18:53:16 GMT 2021


> > 
> > I think you want get_addr_base_and_unit_offset here.  All
> > variable indexed addresses are in separate stmts.  That also means
> > you can eventually work with just byte sizes/offsets?
> 
> Will do.  The access range in modref summary is bit based (since we want
> to disabiguate bitfields like we do in rest of alias oracle) but indeed
> this part cna be in bytes.

Actually after the unifiation I can just use get_ao_ref which will call
ao_ref_init_from_ptr_and_range that has all the logic I need in there.
I also noticed that I ended up duplicating the code matching bases
and ranges which is done already twice in the function - once for store
targets and once for MEMSET and friends.  The later copy lacked overflow
checks so I took the first copy and moved it to helper function.  This
makes the gimple part of patch really straighforward: just build ao_ref
if possible and then pass it to this function.

I also added statistics.

I have bootstrapped/regtsed on x86_64-linux the updated patch and
comitted it so I can break out the patches that depends on it.
I have patch improving the kill tracking at modref side and also the
kill oracle itself can use fnspec and does not need to special case
mem* functions.

For cc1plus LTO link I now get:

Alias oracle query stats:
  refs_may_alias_p: 76106130 disambiguations, 100928932 queries
  on_includes: 12539931 disambiguations, 39864841 queries
  ref_maybe_used_by_call_p: 625857 disambiguations, 77138089 queries
  call_may_clobber_ref_p: 366420 disambiguations, 369293 queries
  stmt_kills_ref_p: 107503 kills, 5699589 queries
  nonoverlapping_component_refs_p: 0 disambiguations, 26176 queries
  nonoverlapping_refs_since_match_p: 30339 disambiguations, 65400 must overlaps, 96698 queries
  aliasing_component_refs_p: 57500 disambiguations, 15464678 queries
  TBAA oracle: 28248334 disambiguations 104710521 queries
               15220245 are in alias set 0
               8905994 queries asked about the same object
               98 queries asked about the same alias set
               0 access volatile
               50371110 are dependent in the DAG
               1964740 are aritificially in conflict with void *

Modref stats:  
  modref kill: 52 kills, 6655 queries
  modref use: 25204 disambiguations, 692151 queries
  modref clobber: 2309709 disambiguations, 21877806 queries
  5320532 tbaa queries (0.243193 per modref query)
  761785 base compares (0.034820 per modref query)

PTA query stats:
  pt_solution_includes: 12539931 disambiguations, 39864841 queries
  pt_solutions_intersect: 1713075 disambiguations, 14023484 queries

Newly we get statis of kill oracle itself:
  stmt_kills_ref_p: 107503 kills, 5699589 queries
and the modref part:
  modref kill: 52 kills, 6655 queries
So an improvemnet over 1 kill using modref I had before. Still not
really great.

Honza

gcc/ChangeLog:

            * ipa-modref-tree.c (modref_access_node::update_for_kills): New
            member function.
            (modref_access_node::merge_for_kills): Likewise.
            (modref_access_node::insert_kill): Likewise.
            * ipa-modref-tree.h (modref_access_node::update_for_kills,
            modref_access_node::merge_for_kills, modref_access_node::insert_kill):
            Declare.
            (modref_access_node::useful_for_kill): New member function.
            * ipa-modref.c (modref_summary::useful_p): Release useless kills.
            (lto_modref_summary): Add kills.
            (modref_summary::dump): Dump kills.
            (record_access): Add mdoref_access_node parameter.
            (record_access_lto): Likewise.
            (merge_call_side_effects): Merge kills.
            (analyze_call): Add ALWAYS_EXECUTED param and pass it around.
            (struct summary_ptrs): Add always_executed filed.
            (analyze_load): Update.
            (analyze_store): Update; record kills.
            (analyze_stmt): Add always_executed; record kills in clobbers.
            (analyze_function): Track always_executed.
            (modref_summaries::duplicate): Duplicate kills.
            (update_signature): Release kills.
            * ipa-modref.h (struct modref_summary): Add kills.
            * tree-ssa-alias.c (alias_stats): Add kill stats.
            (dump_alias_stats): Dump kill stats.
            (store_kills_ref_p): Break out from ...
            (stmt_kills_ref_p): Use it; handle modref info based kills.
    
    gcc/testsuite/ChangeLog:
    
    2021-11-14  Jan Hubicka  <hubicka@ucw.cz>
    
            * gcc.dg/tree-ssa/modref-dse-3.c: New test.


diff --git a/gcc/ipa-modref-tree.c b/gcc/ipa-modref-tree.c
index 6fc2b7298f4..bbe23a5a211 100644
--- a/gcc/ipa-modref-tree.c
+++ b/gcc/ipa-modref-tree.c
@@ -638,6 +638,185 @@ modref_access_node::get_ao_ref (const gcall *stmt, ao_ref *ref) const
   return true;
 }
 
+/* Return true A is a subkill.  */
+bool
+modref_access_node::contains_for_kills (const modref_access_node &a) const
+{
+  poly_int64 aoffset_adj = 0;
+
+  gcc_checking_assert (parm_index != MODREF_UNKNOWN_PARM
+		       && a.parm_index != MODREF_UNKNOWN_PARM);
+  if (parm_index != a.parm_index)
+    return false;
+  gcc_checking_assert (parm_offset_known && a.parm_offset_known);
+  aoffset_adj = (a.parm_offset - parm_offset)
+		* BITS_PER_UNIT;
+  gcc_checking_assert (range_info_useful_p () && a.range_info_useful_p ());
+  return known_subrange_p (a.offset + aoffset_adj,
+			   a.max_size, offset, max_size);
+}
+
+/* Merge two ranges both starting at parm_offset1 and update THIS
+   with result.  */
+bool
+modref_access_node::update_for_kills (poly_int64 parm_offset1,
+				      poly_int64 offset1,
+				      poly_int64 max_size1,
+				      poly_int64 offset2,
+				      poly_int64 max_size2,
+				      bool record_adjustments)
+{
+  if (known_le (offset1, offset2))
+    ;
+  else if (known_le (offset2, offset1))
+    {
+      std::swap (offset1, offset2);
+      std::swap (max_size1, max_size2);
+    }
+  else
+    gcc_unreachable ();
+
+  poly_int64 new_max_size = max_size2 + offset2 - offset1;
+  if (known_le (new_max_size, max_size1))
+    new_max_size = max_size1;
+  if (known_eq (parm_offset, parm_offset1)
+      && known_eq (offset, offset1)
+      && known_eq (size, new_max_size)
+      && known_eq (max_size, new_max_size))
+    return false;
+
+  if (!record_adjustments
+      || (++adjustments) < param_modref_max_adjustments)
+    {
+      parm_offset = parm_offset1;
+      offset = offset1;
+      max_size = new_max_size;
+      size = new_max_size;
+      gcc_checking_assert (useful_for_kill_p ());
+      return true;
+    }
+  return false;
+}
+
+/* Merge in access A if it is possible to do without losing
+   precision.  Return true if successful.
+   Unlike merge assume that both accesses are always executed
+   and merge size the same was as max_size.  */
+bool
+modref_access_node::merge_for_kills (const modref_access_node &a,
+				     bool record_adjustments)
+{
+  poly_int64 offset1 = 0;
+  poly_int64 aoffset1 = 0;
+  poly_int64 new_parm_offset = 0;
+
+  /* We assume that containment was tested earlier.  */
+  gcc_checking_assert (!contains_for_kills (a) && !a.contains_for_kills (*this)
+		       && useful_for_kill_p () && a.useful_for_kill_p ());
+
+  if (parm_index != a.parm_index
+      || !combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
+    return false;
+
+  if (known_le (offset1, aoffset1))
+   {
+     if (!known_size_p (max_size)
+	 || known_ge (offset1 + max_size, aoffset1))
+       return update_for_kills (new_parm_offset, offset1, max_size,
+				aoffset1, a.max_size, record_adjustments);
+   }
+  else if (known_le (aoffset1, offset1))
+   {
+     if (!known_size_p (a.max_size)
+	 || known_ge (aoffset1 + a.max_size, offset1))
+       return update_for_kills (new_parm_offset, offset1, max_size,
+				aoffset1, a.max_size, record_adjustments);
+   }
+  return false;
+}
+
+/* Insert new kill A into KILLS.  If RECORD_ADJUSTMENTS is true limit number
+   of changes to each entry.  Return true if something changed.  */
+
+bool
+modref_access_node::insert_kill (vec<modref_access_node> &kills,
+				 modref_access_node &a, bool record_adjustments)
+{
+  size_t index;
+  modref_access_node *a2;
+  bool merge = false;
+
+  gcc_checking_assert (a.useful_for_kill_p ());
+
+  /* See if we have corresponding entry already or we can merge with
+     neighbouring entry.  */
+  FOR_EACH_VEC_ELT (kills, index, a2)
+    {
+      if (a2->contains_for_kills (a))
+	return false;
+      if (a.contains_for_kills (*a2))
+	{
+	  a.adjustments = 0;
+	  *a2 = a;
+	  merge = true;
+	  break;
+	}
+      if (a2->merge_for_kills (a, record_adjustments))
+	{
+	  merge = true;
+	  break;
+	}
+    }
+  /* If entry was not found, insert it.  */
+  if (!merge)
+    {
+      if ((int)kills.length () >= param_modref_max_accesses)
+	{
+	  if (dump_file)
+	    fprintf (dump_file,
+		     "--param param=modref-max-accesses limit reached:");
+	  return false;
+	}
+      a.adjustments = 0;
+      kills.safe_push (a);
+      return true;
+    }
+  /* Extending range in an entry may make it possible to merge it with
+     other entries.  */
+  size_t i;
+
+  for (i = 0; i < kills.length ();)
+    if (i != index)
+      {
+	bool found = false, restart = false;
+	modref_access_node *a = &kills[i];
+	modref_access_node *n = &kills[index];
+
+	if (n->contains_for_kills (*a))
+	  found = true;
+	if (!found && n->merge_for_kills (*a, false))
+	  found = restart = true;
+	gcc_checking_assert (found || !a->merge_for_kills (*n, false));
+	if (found)
+	  {
+	    kills.unordered_remove (i);
+	    if (index == kills.length ())
+	      {
+		index = i;
+		i++;
+	      }
+	    if (restart)
+	      i = 0;
+	  }
+	else
+	  i++;
+      }
+    else
+      i++;
+  return true;
+}
+
+
 #if CHECKING_P
 
 namespace selftest {
diff --git a/gcc/ipa-modref-tree.h b/gcc/ipa-modref-tree.h
index 2fcabe480bd..1bf2aa8460e 100644
--- a/gcc/ipa-modref-tree.h
+++ b/gcc/ipa-modref-tree.h
@@ -82,6 +82,13 @@ struct GTY(()) modref_access_node
     {
       return parm_index != MODREF_UNKNOWN_PARM;
     }
+  /* Return true if access can be used to determine a kill.  */
+  bool useful_for_kill_p () const
+    {
+      return parm_offset_known && parm_index != MODREF_UNKNOWN_PARM
+	     && parm_index != MODREF_RETSLOT_PARM && known_size_p (size)
+	     && known_eq (max_size, size);
+    }
   /* Dump range to debug OUT.  */
   void dump (FILE *out);
   /* Return true if both accesses are the same.  */
@@ -98,10 +105,18 @@ struct GTY(()) modref_access_node
   static int insert (vec <modref_access_node, va_gc> *&accesses,
 		     modref_access_node a, size_t max_accesses,
 		     bool record_adjustments);
+  /* Same as insert but for kills where we are conservative the other way
+     around: if information is lost, the kill is lost.  */
+  static bool insert_kill (vec<modref_access_node> &kills,
+			   modref_access_node &a, bool record_adjustments);
 private:
   bool contains (const modref_access_node &) const;
+  bool contains_for_kills (const modref_access_node &) const;
   void update (poly_int64, poly_int64, poly_int64, poly_int64, bool);
+  bool update_for_kills (poly_int64, poly_int64, poly_int64,
+			 poly_int64, poly_int64, bool);
   bool merge (const modref_access_node &, bool);
+  bool merge_for_kills (const modref_access_node &, bool);
   static bool closer_pair_p (const modref_access_node &,
 			     const modref_access_node &,
 			     const modref_access_node &,
diff --git a/gcc/ipa-modref.c b/gcc/ipa-modref.c
index b75ed84135b..df4612bbff9 100644
--- a/gcc/ipa-modref.c
+++ b/gcc/ipa-modref.c
@@ -335,6 +335,8 @@ modref_summary::useful_p (int ecf_flags, bool check_flags)
     return (!side_effects && (ecf_flags & ECF_LOOPING_CONST_OR_PURE));
   if (loads && !loads->every_base)
     return true;
+  else
+    kills.release ();
   if (ecf_flags & ECF_PURE)
     return (!side_effects && (ecf_flags & ECF_LOOPING_CONST_OR_PURE));
   return stores && !stores->every_base;
@@ -351,6 +353,7 @@ struct GTY(()) modref_summary_lto
      more verbose and thus more likely to hit the limits.  */
   modref_records_lto *loads;
   modref_records_lto *stores;
+  auto_vec<modref_access_node> GTY((skip)) kills;
   auto_vec<eaf_flags_t> GTY((skip)) arg_flags;
   eaf_flags_t retslot_flags;
   eaf_flags_t static_chain_flags;
@@ -570,6 +573,15 @@ modref_summary::dump (FILE *out)
       fprintf (out, "  stores:\n");
       dump_records (stores, out);
     }
+  if (kills.length ())
+    {
+      fprintf (out, "  kills:\n");
+      for (auto kill : kills)
+	{
+	  fprintf (out, "    ");
+	  kill.dump (out);
+	}
+    }
   if (writes_errno)
     fprintf (out, "  Writes errno\n");
   if (side_effects)
@@ -762,13 +774,12 @@ get_access (ao_ref *ref)
 /* Record access into the modref_records data structure.  */
 
 static void
-record_access (modref_records *tt, ao_ref *ref)
+record_access (modref_records *tt, ao_ref *ref, modref_access_node &a)
 {
   alias_set_type base_set = !flag_strict_aliasing ? 0
 			    : ao_ref_base_alias_set (ref);
   alias_set_type ref_set = !flag_strict_aliasing ? 0
 			    : (ao_ref_alias_set (ref));
-  modref_access_node a = get_access (ref);
   if (dump_file)
     {
        fprintf (dump_file, "   - Recording base_set=%i ref_set=%i ",
@@ -781,7 +792,7 @@ record_access (modref_records *tt, ao_ref *ref)
 /* IPA version of record_access_tree.  */
 
 static void
-record_access_lto (modref_records_lto *tt, ao_ref *ref)
+record_access_lto (modref_records_lto *tt, ao_ref *ref, modref_access_node &a)
 {
   /* get_alias_set sometimes use different type to compute the alias set
      than TREE_TYPE (base).  Do same adjustments.  */
@@ -828,7 +839,6 @@ record_access_lto (modref_records_lto *tt, ao_ref *ref)
 		       || variably_modified_type_p (ref_type, NULL_TREE)))
 	ref_type = NULL_TREE;
     }
-  modref_access_node a = get_access (ref);
   if (dump_file)
     {
       fprintf (dump_file, "   - Recording base type:");
@@ -932,13 +942,17 @@ bool
 merge_call_side_effects (modref_summary *cur_summary,
 			 gimple *stmt, modref_summary *callee_summary,
 			 bool ignore_stores, cgraph_node *callee_node,
-			 bool record_adjustments)
+			 bool record_adjustments, bool always_executed)
 {
   auto_vec <modref_parm_map, 32> parm_map;
   modref_parm_map chain_map;
   bool changed = false;
   int flags = gimple_call_flags (stmt);
 
+  if ((flags & (ECF_CONST | ECF_NOVOPS))
+      && !(flags & ECF_LOOPING_CONST_OR_PURE))
+    return changed;
+
   if (!cur_summary->side_effects && callee_summary->side_effects)
     {
       if (dump_file)
@@ -950,6 +964,38 @@ merge_call_side_effects (modref_summary *cur_summary,
   if (flags & (ECF_CONST | ECF_NOVOPS))
     return changed;
 
+  if (always_executed
+      && callee_summary->kills.length ()
+      && (!cfun->can_throw_non_call_exceptions
+	  || !stmt_could_throw_p (cfun, stmt)))
+    {
+      /* Watch for self recursive updates.  */
+      auto_vec<modref_access_node, 32> saved_kills;
+
+      saved_kills.reserve_exact (callee_summary->kills.length ());
+      saved_kills.splice (callee_summary->kills);
+      for (auto kill : saved_kills)
+	{
+	  if (kill.parm_index >= (int)parm_map.length ())
+	    continue;
+	  modref_parm_map &m
+		  = kill.parm_index == MODREF_STATIC_CHAIN_PARM
+		    ? chain_map
+		    : parm_map[kill.parm_index];
+	  if (m.parm_index == MODREF_LOCAL_MEMORY_PARM
+	      || m.parm_index == MODREF_UNKNOWN_PARM
+	      || m.parm_index == MODREF_RETSLOT_PARM
+	      || !m.parm_offset_known)
+	    continue;
+	  modref_access_node n = kill;
+	  n.parm_index = m.parm_index;
+	  n.parm_offset += m.parm_offset;
+	  if (modref_access_node::insert_kill (cur_summary->kills, n,
+					       record_adjustments))
+	    changed = true;
+	}
+    }
+
   /* We can not safely optimize based on summary of callee if it does
      not always bind to current def: it is possible that memory load
      was optimized out earlier which may not happen in the interposed
@@ -1218,7 +1264,8 @@ process_fnspec (modref_summary *cur_summary,
 
 static bool
 analyze_call (modref_summary *cur_summary, modref_summary_lto *cur_summary_lto,
-	      gcall *stmt, vec <gimple *> *recursive_calls)
+	      gcall *stmt, vec <gimple *> *recursive_calls,
+	      bool always_executed)
 {
   /* Check flags on the function call.  In certain cases, analysis can be
      simplified.  */
@@ -1305,7 +1352,7 @@ analyze_call (modref_summary *cur_summary, modref_summary_lto *cur_summary_lto,
     }
 
   merge_call_side_effects (cur_summary, stmt, callee_summary, ignore_stores,
-			   callee_node, false);
+			   callee_node, false, always_executed);
 
   return true;
 }
@@ -1316,6 +1363,7 @@ struct summary_ptrs
 {
   struct modref_summary *nolto;
   struct modref_summary_lto *lto;
+  bool always_executed;
 };
 
 /* Helper for analyze_stmt.  */
@@ -1350,18 +1398,19 @@ analyze_load (gimple *, tree, tree op, void *data)
 
   ao_ref r;
   ao_ref_init (&r, op);
+  modref_access_node a = get_access (&r);
 
   if (summary)
-    record_access (summary->loads, &r);
+    record_access (summary->loads, &r, a);
   if (summary_lto)
-    record_access_lto (summary_lto->loads, &r);
+    record_access_lto (summary_lto->loads, &r, a);
   return false;
 }
 
 /* Helper for analyze_stmt.  */
 
 static bool
-analyze_store (gimple *, tree, tree op, void *data)
+analyze_store (gimple *stmt, tree, tree op, void *data)
 {
   modref_summary *summary = ((summary_ptrs *)data)->nolto;
   modref_summary_lto *summary_lto = ((summary_ptrs *)data)->lto;
@@ -1390,11 +1439,22 @@ analyze_store (gimple *, tree, tree op, void *data)
 
   ao_ref r;
   ao_ref_init (&r, op);
+  modref_access_node a = get_access (&r);
 
   if (summary)
-    record_access (summary->stores, &r);
+    record_access (summary->stores, &r, a);
   if (summary_lto)
-    record_access_lto (summary_lto->stores, &r);
+    record_access_lto (summary_lto->stores, &r, a);
+  if (summary
+      && ((summary_ptrs *)data)->always_executed
+      && a.useful_for_kill_p ()
+      && (!cfun->can_throw_non_call_exceptions
+	  || !stmt_could_throw_p (cfun, stmt)))
+    {
+      if (dump_file)
+	fprintf (dump_file, "   - Recording kill\n");
+      modref_access_node::insert_kill (summary->kills, a, false);
+    }
   return false;
 }
 
@@ -1403,16 +1463,32 @@ analyze_store (gimple *, tree, tree op, void *data)
 
 static bool
 analyze_stmt (modref_summary *summary, modref_summary_lto *summary_lto,
-	      gimple *stmt, bool ipa, vec <gimple *> *recursive_calls)
+	      gimple *stmt, bool ipa, vec <gimple *> *recursive_calls,
+	      bool always_executed)
 {
   /* In general we can not ignore clobbers because they are barriers for code
      motion, however after inlining it is safe to do because local optimization
      passes do not consider clobbers from other functions.
      Similar logic is in ipa-pure-const.c.  */
   if ((ipa || cfun->after_inlining) && gimple_clobber_p (stmt))
-    return true;
+    {
+      if (summary
+	  && always_executed && record_access_p (gimple_assign_lhs (stmt)))
+	{
+	  ao_ref r;
+	  ao_ref_init (&r, gimple_assign_lhs (stmt));
+	  modref_access_node a = get_access (&r);
+	  if (a.useful_for_kill_p ())
+	    {
+	      if (dump_file)
+		fprintf (dump_file, "   - Recording kill\n");
+	      modref_access_node::insert_kill (summary->kills, a, false);
+	    }
+	}
+      return true;
+    }
 
-  struct summary_ptrs sums = {summary, summary_lto};
+  struct summary_ptrs sums = {summary, summary_lto, always_executed};
 
   /* Analyze all loads and stores in STMT.  */
   walk_stmt_load_store_ops (stmt, &sums,
@@ -1441,7 +1517,8 @@ analyze_stmt (modref_summary *summary, modref_summary_lto *summary_lto,
    case GIMPLE_CALL:
      if (!ipa || gimple_call_internal_p (stmt))
        return analyze_call (summary, summary_lto,
-			    as_a <gcall *> (stmt), recursive_calls);
+			    as_a <gcall *> (stmt), recursive_calls,
+			    always_executed);
      else
       {
 	attr_fnspec fnspec = gimple_call_fnspec (as_a <gcall *>(stmt));
@@ -2779,11 +2856,15 @@ analyze_function (function *f, bool ipa)
   FOR_EACH_BB_FN (bb, f)
     {
       gimple_stmt_iterator si;
+      bool always_executed
+	      = bb == single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->dest;
+
       for (si = gsi_start_nondebug_after_labels_bb (bb);
 	   !gsi_end_p (si); gsi_next_nondebug (&si))
 	{
 	  if (!analyze_stmt (summary, summary_lto,
-			     gsi_stmt (si), ipa, &recursive_calls)
+			     gsi_stmt (si), ipa, &recursive_calls,
+			     always_executed)
 	      || ((!summary || !summary->useful_p (ecf_flags, false))
 		  && (!summary_lto
 		      || !summary_lto->useful_p (ecf_flags, false))))
@@ -2792,6 +2873,9 @@ analyze_function (function *f, bool ipa)
 	      collapse_stores (summary, summary_lto);
 	      break;
 	    }
+	  if (always_executed
+	      && stmt_can_throw_external (cfun, gsi_stmt (si)))
+	    always_executed = false;
 	}
     }
 
@@ -2811,7 +2895,7 @@ analyze_function (function *f, bool ipa)
 			   ignore_stores_p (current_function_decl,
 					    gimple_call_flags
 						 (recursive_calls[i])),
-			   fnode, !first);
+			   fnode, !first, false);
 	      if (!summary->useful_p (ecf_flags, false))
 		{
 		  remove_summary (lto, nolto, ipa);
@@ -3061,6 +3145,8 @@ modref_summaries::duplicate (cgraph_node *, cgraph_node *dst,
 			 src_data->loads->max_refs,
 			 src_data->loads->max_accesses);
   dst_data->loads->copy_from (src_data->loads);
+  dst_data->kills.reserve_exact (src_data->kills.length ());
+  dst_data->kills.splice (src_data->kills);
   dst_data->writes_errno = src_data->writes_errno;
   dst_data->side_effects = src_data->side_effects;
   if (src_data->arg_flags.length ())
@@ -3710,6 +3796,8 @@ update_signature (struct cgraph_node *node)
     {
       r->loads->remap_params (&map);
       r->stores->remap_params (&map);
+      /* TODO: One we do IPA kills analysis, update the table here.  */
+      r->kills.release ();
       if (r->arg_flags.length ())
 	remap_arg_flags (r->arg_flags, info);
     }
@@ -3717,6 +3805,8 @@ update_signature (struct cgraph_node *node)
     {
       r_lto->loads->remap_params (&map);
       r_lto->stores->remap_params (&map);
+      /* TODO: One we do IPA kills analysis, update the table here.  */
+      r_lto->kills.release ();
       if (r_lto->arg_flags.length ())
 	remap_arg_flags (r_lto->arg_flags, info);
     }
diff --git a/gcc/ipa-modref.h b/gcc/ipa-modref.h
index 118dc5f2abf..9e8a30fd80a 100644
--- a/gcc/ipa-modref.h
+++ b/gcc/ipa-modref.h
@@ -30,6 +30,7 @@ struct GTY(()) modref_summary
   /* Load and stores in function (transitively closed to all callees)  */
   modref_records *loads;
   modref_records *stores;
+  auto_vec<modref_access_node> GTY((skip)) kills;
   auto_vec<eaf_flags_t> GTY((skip)) arg_flags;
   eaf_flags_t retslot_flags;
   eaf_flags_t static_chain_flags;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modref-dse-3.c b/gcc/testsuite/gcc.dg/tree-ssa/modref-dse-3.c
new file mode 100644
index 00000000000..c69e423c6fd
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modref-dse-3.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dse1-details"  } */
+__attribute__ ((noinline))
+void write (int *a)
+{
+	*a=1;
+	a[1]=2;
+}
+int test ()
+{
+	int a;
+	a=2;
+	write (&a);
+	return a;
+}
+int test2 (int *a)
+{
+	*a=2;
+	write (a);
+	return *a;
+}
+/* { dg-final { scan-tree-dump-times "Deleted dead store" 2 "dse1"} } */
diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
index 29be1f848b5..093d65cc003 100644
--- a/gcc/tree-ssa-alias.c
+++ b/gcc/tree-ssa-alias.c
@@ -116,10 +116,14 @@ static struct {
   unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_may_alias;
   unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_must_overlap;
   unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_no_alias;
+  unsigned HOST_WIDE_INT stmt_kills_ref_p_no;
+  unsigned HOST_WIDE_INT stmt_kills_ref_p_yes;
   unsigned HOST_WIDE_INT modref_use_may_alias;
   unsigned HOST_WIDE_INT modref_use_no_alias;
   unsigned HOST_WIDE_INT modref_clobber_may_alias;
   unsigned HOST_WIDE_INT modref_clobber_no_alias;
+  unsigned HOST_WIDE_INT modref_kill_no;
+  unsigned HOST_WIDE_INT modref_kill_yes;
   unsigned HOST_WIDE_INT modref_tests;
   unsigned HOST_WIDE_INT modref_baseptr_tests;
 } alias_stats;
@@ -146,6 +150,12 @@ dump_alias_stats (FILE *s)
 	   alias_stats.call_may_clobber_ref_p_no_alias,
 	   alias_stats.call_may_clobber_ref_p_no_alias
 	   + alias_stats.call_may_clobber_ref_p_may_alias);
+  fprintf (s, "  stmt_kills_ref_p: "
+	   HOST_WIDE_INT_PRINT_DEC" kills, "
+	   HOST_WIDE_INT_PRINT_DEC" queries\n",
+	   alias_stats.stmt_kills_ref_p_yes + alias_stats.modref_kill_yes,
+	   alias_stats.stmt_kills_ref_p_yes + alias_stats.modref_kill_yes
+	   + alias_stats.stmt_kills_ref_p_no + alias_stats.modref_kill_no);
   fprintf (s, "  nonoverlapping_component_refs_p: "
 	   HOST_WIDE_INT_PRINT_DEC" disambiguations, "
 	   HOST_WIDE_INT_PRINT_DEC" queries\n",
@@ -169,6 +179,12 @@ dump_alias_stats (FILE *s)
 	   + alias_stats.aliasing_component_refs_p_may_alias);
   dump_alias_stats_in_alias_c (s);
   fprintf (s, "\nModref stats:\n");
+  fprintf (s, "  modref kill: "
+	   HOST_WIDE_INT_PRINT_DEC" kills, "
+	   HOST_WIDE_INT_PRINT_DEC" queries\n",
+	   alias_stats.modref_kill_yes,
+	   alias_stats.modref_kill_yes
+	   + alias_stats.modref_kill_no);
   fprintf (s, "  modref use: "
 	   HOST_WIDE_INT_PRINT_DEC" disambiguations, "
 	   HOST_WIDE_INT_PRINT_DEC" queries\n",
@@ -3220,6 +3236,51 @@ same_addr_size_stores_p (tree base1, poly_int64 offset1, poly_int64 size1,
 	  && known_eq (wi::to_poly_offset (DECL_SIZE (obj)), size1));
 }
 
+/* Return true if REF is killed by an store described by
+   BASE, OFFSET, SIZE and MAX_SIZE.  */
+
+static bool
+store_kills_ref_p (tree base, poly_int64 offset, poly_int64 size,
+		   poly_int64 max_size, ao_ref *ref)
+{
+  poly_int64 ref_offset = ref->offset;
+  /* We can get MEM[symbol: sZ, index: D.8862_1] here,
+     so base == ref->base does not always hold.  */
+  if (base != ref->base)
+    {
+      /* Try using points-to info.  */
+      if (same_addr_size_stores_p (base, offset, size, max_size, ref->base,
+				   ref->offset, ref->size, ref->max_size))
+	return true;
+
+      /* If both base and ref->base are MEM_REFs, only compare the
+	 first operand, and if the second operand isn't equal constant,
+	 try to add the offsets into offset and ref_offset.  */
+      if (TREE_CODE (base) == MEM_REF && TREE_CODE (ref->base) == MEM_REF
+	  && TREE_OPERAND (base, 0) == TREE_OPERAND (ref->base, 0))
+	{
+	  if (!tree_int_cst_equal (TREE_OPERAND (base, 1),
+				   TREE_OPERAND (ref->base, 1)))
+	    {
+	      poly_offset_int off1 = mem_ref_offset (base);
+	      off1 <<= LOG2_BITS_PER_UNIT;
+	      off1 += offset;
+	      poly_offset_int off2 = mem_ref_offset (ref->base);
+	      off2 <<= LOG2_BITS_PER_UNIT;
+	      off2 += ref_offset;
+	      if (!off1.to_shwi (&offset) || !off2.to_shwi (&ref_offset))
+		size = -1;
+	    }
+	}
+      else
+	size = -1;
+    }
+  /* For a must-alias check we need to be able to constrain
+     the access properly.  */
+  return (known_eq (size, max_size)
+	  && known_subrange_p (ref_offset, ref->max_size, offset, size));
+}
+
 /* If STMT kills the memory reference REF return true, otherwise
    return false.  */
 
@@ -3293,7 +3354,10 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
 		      && operand_equal_p (lhs, base,
 					  OEP_ADDRESS_OF
 					  | OEP_MATCH_SIDE_EFFECTS))))
-	    return true;
+	    {
+	      ++alias_stats.stmt_kills_ref_p_yes;
+	      return true;
+	    }
 	}
 
       /* Now look for non-literal equal bases with the restriction of
@@ -3301,52 +3365,72 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
       /* For a must-alias check we need to be able to constrain
 	 the access properly.  */
       if (!ref->max_size_known_p ())
-	return false;
-      poly_int64 size, offset, max_size, ref_offset = ref->offset;
+	{
+	  ++alias_stats.stmt_kills_ref_p_no;
+	  return false;
+	}
+      poly_int64 size, offset, max_size;
       bool reverse;
       tree base = get_ref_base_and_extent (lhs, &offset, &size, &max_size,
 					   &reverse);
-      /* We can get MEM[symbol: sZ, index: D.8862_1] here,
-	 so base == ref->base does not always hold.  */
-      if (base != ref->base)
+      if (store_kills_ref_p (base, offset, size, max_size, ref))
 	{
-	  /* Try using points-to info.  */
-	  if (same_addr_size_stores_p (base, offset, size, max_size, ref->base,
-				       ref->offset, ref->size, ref->max_size))
-	    return true;
-
-	  /* If both base and ref->base are MEM_REFs, only compare the
-	     first operand, and if the second operand isn't equal constant,
-	     try to add the offsets into offset and ref_offset.  */
-	  if (TREE_CODE (base) == MEM_REF && TREE_CODE (ref->base) == MEM_REF
-	      && TREE_OPERAND (base, 0) == TREE_OPERAND (ref->base, 0))
-	    {
-	      if (!tree_int_cst_equal (TREE_OPERAND (base, 1),
-				       TREE_OPERAND (ref->base, 1)))
-		{
-		  poly_offset_int off1 = mem_ref_offset (base);
-		  off1 <<= LOG2_BITS_PER_UNIT;
-		  off1 += offset;
-		  poly_offset_int off2 = mem_ref_offset (ref->base);
-		  off2 <<= LOG2_BITS_PER_UNIT;
-		  off2 += ref_offset;
-		  if (!off1.to_shwi (&offset) || !off2.to_shwi (&ref_offset))
-		    size = -1;
-		}
-	    }
-	  else
-	    size = -1;
+	  ++alias_stats.stmt_kills_ref_p_yes;
+	  return true;
 	}
-      /* For a must-alias check we need to be able to constrain
-	 the access properly.  */
-      if (known_eq (size, max_size)
-	  && known_subrange_p (ref_offset, ref->max_size, offset, size))
-	return true;
     }
 
   if (is_gimple_call (stmt))
     {
       tree callee = gimple_call_fndecl (stmt);
+      struct cgraph_node *node;
+      modref_summary *summary;
+
+      /* Try to disambiguate using modref summary.  Modref records a vector
+	 of stores with known offsets relative to function parameters that must
+	 happen every execution of function.  Find if we have a matching
+	 store and verify that function can not use the value.  */
+      if (callee != NULL_TREE
+	  && (node = cgraph_node::get (callee)) != NULL
+	  && node->binds_to_current_def_p ()
+	  && (summary = get_modref_function_summary (node)) != NULL
+	  && summary->kills.length ()
+	  && (!cfun->can_throw_non_call_exceptions
+	      || !stmt_can_throw_internal (cfun, stmt)))
+	{
+	  for (auto kill : summary->kills)
+	    {
+	      ao_ref dref;
+
+	      /* We only can do useful compares if we know the access range
+		 precisely.  */
+	      if (!kill.get_ao_ref (as_a <gcall *> (stmt), &dref))
+		continue;
+	      if (store_kills_ref_p (ao_ref_base (&dref), dref.offset,
+				     dref.size, dref.max_size, ref))
+		{
+		  /* For store to be killed it needs to not be used
+		     earlier.  */
+		  if (ref_maybe_used_by_call_p_1 (as_a <gcall *> (stmt), ref,
+						  true)
+		      || !dbg_cnt (ipa_mod_ref))
+		    break;
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    {
+		      fprintf (dump_file,
+			       "ipa-modref: call stmt ");
+		      print_gimple_stmt (dump_file, stmt, 0);
+		      fprintf (dump_file,
+			       "ipa-modref: call to %s kills ",
+			       node->dump_name ());
+		      print_generic_expr (dump_file, ref->base);
+		    }
+		    ++alias_stats.modref_kill_yes;
+		    return true;
+		}
+	    }
+	  ++alias_stats.modref_kill_no;
+	}
       if (callee != NULL_TREE
 	  && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
 	switch (DECL_FUNCTION_CODE (callee))
@@ -3357,7 +3441,10 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
 	      tree base = ao_ref_base (ref);
 	      if (base && TREE_CODE (base) == MEM_REF
 		  && TREE_OPERAND (base, 0) == ptr)
-		return true;
+		{
+		  ++alias_stats.stmt_kills_ref_p_yes;
+		  return true;
+		}
 	      break;
 	    }
 
@@ -3376,7 +3463,10 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
 	      /* For a must-alias check we need to be able to constrain
 		 the access properly.  */
 	      if (!ref->max_size_known_p ())
-		return false;
+		{
+		  ++alias_stats.stmt_kills_ref_p_no;
+		  return false;
+		}
 	      tree dest;
 	      tree len;
 
@@ -3391,11 +3481,17 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
 		  tree arg1 = gimple_call_arg (stmt, 1);
 		  if (TREE_CODE (arg0) != INTEGER_CST
 		      || TREE_CODE (arg1) != INTEGER_CST)
-		    return false;
+		    {
+		      ++alias_stats.stmt_kills_ref_p_no;
+		      return false;
+		    }
 
 		  dest = gimple_call_lhs (stmt);
 		  if (!dest)
-		    return false;
+		    {
+		      ++alias_stats.stmt_kills_ref_p_no;
+		      return false;
+		    }
 		  len = fold_build2 (MULT_EXPR, TREE_TYPE (arg0), arg0, arg1);
 		}
 	      else
@@ -3405,29 +3501,14 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
 		}
 	      if (!poly_int_tree_p (len))
 		return false;
-	      tree rbase = ref->base;
-	      poly_offset_int roffset = ref->offset;
 	      ao_ref dref;
 	      ao_ref_init_from_ptr_and_size (&dref, dest, len);
-	      tree base = ao_ref_base (&dref);
-	      poly_offset_int offset = dref.offset;
-	      if (!base || !known_size_p (dref.size))
-		return false;
-	      if (TREE_CODE (base) == MEM_REF)
+	      if (store_kills_ref_p (ao_ref_base (&dref), dref.offset,
+				     dref.size, dref.max_size, ref))
 		{
-		  if (TREE_CODE (rbase) != MEM_REF)
-		    return false;
-		  // Compare pointers.
-		  offset += mem_ref_offset (base) << LOG2_BITS_PER_UNIT;
-		  roffset += mem_ref_offset (rbase) << LOG2_BITS_PER_UNIT;
-		  base = TREE_OPERAND (base, 0);
-		  rbase = TREE_OPERAND (rbase, 0);
+		  ++alias_stats.stmt_kills_ref_p_yes;
+		  return true;
 		}
-	      if (base == rbase
-		  && known_subrange_p (roffset, ref->max_size, offset,
-				       wi::to_poly_offset (len)
-				       << LOG2_BITS_PER_UNIT))
-		return true;
 	      break;
 	    }
 
@@ -3438,7 +3519,10 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
 		{
 		  tree base = ao_ref_base (ref);
 		  if (TREE_OPERAND (ptr, 0) == base)
-		    return true;
+		    {
+		      ++alias_stats.stmt_kills_ref_p_yes;
+		      return true;
+		    }
 		}
 	      break;
 	    }
@@ -3446,6 +3530,7 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
 	  default:;
 	  }
     }
+  ++alias_stats.stmt_kills_ref_p_no;
   return false;
 }
 


More information about the Gcc-patches mailing list