Add access through parameter derference tracking to modref

re-add tracking of accesses which was unfinished in David's patch.
At the moment I only implemented tracking of the fact that access is based on
derefernece of the parameter (so we track THIS pointers).
Patch does not implement IPA propagation since it needs bit more work which
I will post shortly: ipa-fnsummary needs to track when parameter points to
local memory, summaries needs to be merged when function is inlined (because
jump functions are) and propagation needs to be turned into iterative dataflow
on SCC components.

Patch also adds documentation of -fipa-modref and params that was left uncommited
in my branch :(.

Even without this change it does lead to nice increase of disambiguations
for cc1plus build.

Alias oracle query stats:
  refs_may_alias_p: 62758323 disambiguations, 72935683 queries
  ref_maybe_used_by_call_p: 139511 disambiguations, 63654045 queries
  call_may_clobber_ref_p: 23502 disambiguations, 29242 queries
  nonoverlapping_component_refs_p: 0 disambiguations, 37654 queries
  nonoverlapping_refs_since_match_p: 19417 disambiguations, 55555 must overlaps, 75721 queries
  aliasing_component_refs_p: 54665 disambiguations, 752449 queries
  TBAA oracle: 21917926 disambiguations 53054678 queries
               15763411 are in alias set 0
               10162238 queries asked about the same object
               124 queries asked about the same alias set
               0 access volatile
               3681593 are dependent in the DAG
               1529386 are aritificially in conflict with void *

Modref stats:
  modref use: 8311 disambiguations, 32527 queries
  modref clobber: 742126 disambiguations, 1036986 queries
  1987054 tbaa queries (1.916182 per modref query)
  125479 base compares (0.121004 per modref query)

PTA query stats:
  pt_solution_includes: 968314 disambiguations, 13609584 queries
  pt_solutions_intersect: 1019136 disambiguations, 13147139 queries

So compared to
https://gcc.gnu.org/pipermail/gcc-patches/2020-September/554605.html
we get 41% more use disambiguations (with similar number of queries) and 8% more
clobber disambiguations.

For tramp3d:
Alias oracle query stats:
  refs_may_alias_p: 2052256 disambiguations, 2312703 queries
  ref_maybe_used_by_call_p: 7122 disambiguations, 2089118 queries
  call_may_clobber_ref_p: 234 disambiguations, 234 queries
  nonoverlapping_component_refs_p: 0 disambiguations, 4299 queries
  nonoverlapping_refs_since_match_p: 329 disambiguations, 10200 must overlaps, 10616 queries
  aliasing_component_refs_p: 857 disambiguations, 34555 queries
  TBAA oracle: 885546 disambiguations 1677080 queries
               132105 are in alias set 0
               469030 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               190084 are dependent in the DAG
               315 are aritificially in conflict with void *

Modref stats:
  modref use: 426 disambiguations, 1881 queries
  modref clobber: 10042 disambiguations, 16202 queries
  19405 tbaa queries (1.197692 per modref query)
  2775 base compares (0.171275 per modref query)

PTA query stats:
  pt_solution_includes: 313908 disambiguations, 526183 queries
  pt_solutions_intersect: 130510 disambiguations, 416084 queries

Here uses decrease by 4 disambiguations and clobber improve by 3.5%.  I think
the difference is caused by fact that gcc has much more alias set 0 accesses
originating from gimple and tree unions as I mentioned in original mail.

After pushing out the IPA propagation I will re-add code to track offsets and
sizes that further improve disambiguation. On tramp3d it enables a lot of DSE
for structure fields not acessed by uninlined function.

gcc/

	* doc/invoke.texi: Document -fipa-modref, ipa-modref-max-bases,
	ipa-modref-max-refs, ipa-modref-max-accesses, ipa-modref-max-tests.
	* ipa-modref-tree.c (test_insert_search_collapse): Update.
	(test_merge): Update.
	(gt_ggc_mx): New function.
	* ipa-modref-tree.h (struct modref_access_node): New structure.
	(struct modref_ref_node): Add every_access and accesses array.
	(modref_ref_node::modref_ref_node): Update ctor.
	(modref_ref_node::search): New member function.
	(modref_ref_node::collapse): New member function.
	(modref_ref_node::insert_access): New member function.
	(modref_base_node::insert_ref): Do not collapse base if ref is 0.
	(modref_base_node::collapse): Copllapse also refs.
	(modref_tree): Add accesses.
	(modref_tree::modref_tree): Initialize max_accesses.
	(modref_tree::insert): Add access parameter.
	(modref_tree::cleanup): New member function.
	(modref_tree::merge): Add parm_map; merge accesses.
	(modref_tree::copy_from): New member function.
	(modref_tree::create_ggc): Add max_accesses.
	* ipa-modref.c (dump_access): New function.
	(dump_records): Dump accesses.
	(dump_lto_records): Dump accesses.
	(get_access): New function.
	(record_access): Record access.
	(record_access_lto): Record access.
	(analyze_call): Compute parm_map.
	(analyze_function): Update construction of modref records.
	(modref_summaries::duplicate): Likewise; use copy_from.
	(write_modref_records): Stream accesses.
	(read_modref_records): Sream accesses.
	(pass_ipa_modref::execute): Update call of merge.
	* params.opt (-param=modref-max-accesses): New.
	* tree-ssa-alias.c (alias_stats): Add modref_baseptr_tests.
	(dump_alias_stats): Update.
	(base_may_alias_with_dereference_p): New function.
	(modref_may_conflict): Check accesses.
	(ref_maybe_used_by_call_p_1): Update call to modref_may_conflict.
	(call_may_clobber_ref_p_1): Update call to modref_may_conflict.

1 files changed, 195 insertions, 21 deletions

diff --git a/gcc/ipa-modref-tree.h b/gcc/ipa-modref-tree.h
index 82e959a..caf5d34 100644
--- a/gcc/ipa-modref-tree.h
+++ b/gcc/ipa-modref-tree.h
@@ -18,20 +18,101 @@ You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
+/* modref_tree represent a decision tree that can be used by alias analysis
+   oracle to determine whether given memory access can be affected by a function
+   call.  For every function we collect two trees, one for loads and other
+   for stores.  Tree consist of following levels:
+
+   1) Base: this level represent base alias set of the acecess and refers
+      to sons (ref nodes). Flag all_refs means that all possible references
+      are aliasing.
+
+      Because for LTO streaming we need to stream types rahter than alias sets
+      modref_base_node is implemented as a template.
+   2) Ref: this level represent ref alias set and links to acesses unless
+      all_refs flag is et.
+      Again ref is an template to allow LTO streaming.
+   3) Access: this level represent info about individual accesses.  Presently
+      we record whether access is trhough a dereference of a function parameter
+*/
+
 #ifndef GCC_MODREF_TREE_H
 #define GCC_MODREF_TREE_H
 
 struct ipa_modref_summary;
 
+/* Memory access.  */
+struct GTY(()) modref_access_node
+{
+  /* Index of parameter which specifies the base of access. -1 if base is not
+     a function parameter.  */
+  int parm_index;
+
+  /* Return true if access node holds no useful info.  */
+  bool useful_p ()
+    {
+      return parm_index != -1;
+    }
+};
 
 template <typename T>
 struct GTY((user)) modref_ref_node
 {
   T ref;
+  bool every_access;
+  vec <modref_access_node, va_gc> *accesses;
 
   modref_ref_node (T ref):
-    ref (ref)
+    ref (ref),
+    every_access (false),
+    accesses (NULL)
   {}
+
+  /* Search REF; return NULL if failed.  */
+  modref_access_node *search (modref_access_node access)
+  {
+    size_t i;
+    modref_access_node *a;
+    FOR_EACH_VEC_SAFE_ELT (accesses, i, a)
+      if (a->parm_index == access.parm_index)
+	return a;
+    return NULL;
+  }
+
+  /* Collapse the tree.  */
+  void collapse ()
+  {
+    vec_free (accesses);
+    accesses = NULL;
+    every_access = true;
+  }
+
+  /* Insert access with OFFSET and SIZE.
+     Collapse tree if it has more than MAX_ACCESSES entries.  */
+  void insert_access (modref_access_node a, size_t max_accesses)
+  {
+    /* If this base->ref pair has no access information, bail out.  */
+    if (every_access)
+      return;
+
+    /* Otherwise, insert a node for the ref of the access under the base.  */
+    modref_access_node *access_node = search (a);
+    if (access_node)
+      return;
+
+    /* If this base->ref pair has too many accesses stored, we will clear
+       all accesses and bail out.  */
+    if ((accesses && accesses->length () >= max_accesses)
+	|| !a.useful_p ())
+      {
+	if (dump_file && a.useful_p ())
+	  fprintf (dump_file,
+		   "--param param=modref-max-accesses limit reached\n");
+	collapse ();
+	return;
+      }
+    vec_safe_push (accesses, a);
+  }
 };
 
 /* Base of an access.  */
@@ -67,12 +148,6 @@ struct GTY((user)) modref_base_node
     if (every_ref)
       return NULL;
 
-    if (!ref)
-      {
-	collapse ();
-	return NULL;
-      }
-
     /* Otherwise, insert a node for the ref of the access under the base.  */
     ref_node = search (ref);
     if (ref_node)
@@ -101,7 +176,10 @@ struct GTY((user)) modref_base_node
     if (refs)
       {
 	FOR_EACH_VEC_SAFE_ELT (refs, i, r)
-	  ggc_free (r);
+	  {
+	    r->collapse ();
+	    ggc_free (r);
+	  }
 	vec_free (refs);
       }
     refs = NULL;
@@ -116,12 +194,14 @@ struct GTY((user)) modref_tree
   vec <modref_base_node <T> *, va_gc> *bases;
   size_t max_bases;
   size_t max_refs;
+  size_t max_accesses;
   bool every_base;
 
-  modref_tree (size_t max_bases, size_t max_refs):
+  modref_tree (size_t max_bases, size_t max_refs, size_t max_accesses):
     bases (NULL),
     max_bases (max_bases),
     max_refs (max_refs),
+    max_accesses (max_accesses),
     every_base (false) {}
 
   modref_base_node <T> *insert_base (T base)
@@ -153,31 +233,92 @@ struct GTY((user)) modref_tree
   }
 
   /* Insert memory access to the tree.	*/
-  void insert (T base, T ref)
+  void insert (T base, T ref, modref_access_node a)
   {
-    modref_base_node <T> *base_node;
-
-    base_node = insert_base (base);
-
-    if (!base && !ref)
+    /* No useful information tracked; collapse everything.  */
+    if (!base && !ref && !a.useful_p ())
       {
 	collapse ();
 	return;
       }
+
+    modref_base_node <T> *base_node = insert_base (base);
     if (!base_node)
       return;
     gcc_assert (search (base) != NULL);
 
-    base_node->insert_ref (ref, max_refs);
+    modref_ref_node <T> *ref_node = base_node->insert_ref (ref, max_refs);
+
+    /* No useful ref information and no useful base; collapse everyting.  */
     if (!base && base_node->every_ref)
       {
 	collapse ();
 	return;
       }
+    if (ref_node)
+      {
+	/* No useful ref and access; collapse ref.  */
+	if (!ref && !a.useful_p ())
+	  ref_node->collapse ();
+	else
+	  {
+	    ref_node->insert_access (a, max_accesses);
+	    /* If ref has collapses and there is no useful base; collapse
+	       everything.  */
+	    if (!base && !ref && ref_node->every_access)
+	      collapse ();
+	  }
+      }
   }
 
-  /* Merge OTHER into the tree.  */
-  void merge (modref_tree <T> *other)
+ /* Remove tree branches that are not useful (i.e. they will allways pass).  */
+
+ void cleanup ()
+ {
+   size_t i, j;
+   modref_base_node <T> *base_node;
+   modref_ref_node <T> *ref_node;
+
+   if (!bases)
+     return;
+
+   for (i = 0; vec_safe_iterate (bases, i, &base_node);)
+     {
+       if (base_node->refs)
+	 for (j = 0; vec_safe_iterate (base_node->refs, j, &ref_node);)
+	   {
+	     if (!ref_node->every_access
+		 && (!ref_node->accesses
+		     || !ref_node->accesses->length ()))
+	       {
+		 base_node->refs->unordered_remove (j);
+		 vec_free (ref_node->accesses);
+		 ggc_delete (ref_node);
+	       }
+	     else
+	       j++;
+	   }
+       if (!base_node->every_ref
+	   && (!base_node->refs || !base_node->refs->length ()))
+	 {
+	   bases->unordered_remove (i);
+	   vec_free (base_node->refs);
+	   ggc_delete (base_node);
+	 }
+       else
+	 i++;
+     }
+   if (bases && !bases->length ())
+     {
+       vec_free (bases);
+       bases = NULL;
+     }
+ }
+
+  /* Merge OTHER into the tree.
+     PARM_MAP, if non-NULL, maps parm indexes of callee to caller.  -2 is used
+     to signalize that parameter is local and does not need to be tracked.  */
+  void merge (modref_tree <T> *other, vec <int> *parm_map)
   {
     if (!other)
       return;
@@ -187,9 +328,10 @@ struct GTY((user)) modref_tree
 	return;
       }
 
-    size_t i, j;
+    size_t i, j, k;
     modref_base_node <T> *base_node, *my_base_node;
     modref_ref_node <T> *ref_node, *my_ref_node;
+    modref_access_node *access_node;
     FOR_EACH_VEC_SAFE_ELT (other->bases, i, base_node)
       {
 	my_base_node = insert_base (base_node->base);
@@ -207,8 +349,36 @@ struct GTY((user)) modref_tree
 	    my_ref_node = my_base_node->insert_ref (ref_node->ref, max_refs);
 	    if (!my_ref_node)
 	      continue;
+
+	    if (ref_node->every_access)
+	      {
+		my_ref_node->collapse ();
+		continue;
+	      }
+	    FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
+	      {
+		modref_access_node a = *access_node;
+		if (a.parm_index != -1 && parm_map)
+		  {
+		    if (a.parm_index >= (int)parm_map->length ())
+		      a.parm_index = -1;
+		    else if ((*parm_map) [a.parm_index] == -2)
+		      continue;
+		    else
+		      a.parm_index = (*parm_map) [a.parm_index];
+		  }
+		my_ref_node->insert_access (a, max_accesses);
+	      }
 	  }
       }
+    if (parm_map)
+      cleanup ();
+  }
+
+  /* Copy OTHER to THIS.  */
+  void copy_from (modref_tree <T> *other)
+  {
+    merge (other, NULL);
   }
 
   /* Search BASE in tree; return NULL if failed.  */
@@ -225,12 +395,14 @@ struct GTY((user)) modref_tree
   /* Return ggc allocated instance.  We explicitly call destructors via
      ggc_delete and do not want finalizers to be registered and
      called at the garbage collection time.  */
-  static modref_tree<T> *create_ggc (size_t max_bases, size_t max_refs)
+  static modref_tree<T> *create_ggc (size_t max_bases, size_t max_refs,
+				     size_t max_accesses)
   {
     return new (ggc_alloc_no_dtor<modref_tree<T>> ())
-	 modref_tree<T> (max_bases, max_refs);
+	 modref_tree<T> (max_bases, max_refs, max_accesses);
   }
 
+  /* Remove all records and mark tree to alias with everything.  */
   void collapse ()
   {
     size_t i;
@@ -248,6 +420,8 @@ struct GTY((user)) modref_tree
     bases = NULL;
     every_base = true;
   }
+
+  /* Release memory.  */
   ~modref_tree ()
   {
     collapse ();