[gcc r11-3473] Add support for iterative dataflow to ipa-modref-tree.h

[gcc r11-3473] Add support for iterative dataflow to ipa-modref-tree.h

[Jan Hubicka]

https://gcc.gnu.org/g:5a90a18668fef8d51e5b3fe9f69123f53cbd8f25

commit r11-3473-g5a90a18668fef8d51e5b3fe9f69123f53cbd8f25
Author: Jan Hubicka <jh@suse.cz>
Date:   Sat Sep 26 08:09:53 2020 +0200

    Add support for iterative dataflow to ipa-modref-tree.h
    
    Track if insert and merge operations changed anything in the summary.
    
    gcc/ChangeLog:
    
    2020-09-26  Jan Hubicka  <hubicka@ucw.cz>
    
            * ipa-modref-tree.h (modref_ref_node::insert_access): Track if something
            changed.
            (modref_base_node::insert_ref): Likewise (and add a new optional
            argument)
            (modref_tree::insert): Likewise.
            (modref_tree::merge): Rewrite

Diff:
---
 gcc/ipa-modref-tree.h | 192 ++++++++++++++++++++++++++++++++------------------
 1 file changed, 124 insertions(+), 68 deletions(-)

diff --git a/gcc/ipa-modref-tree.h b/gcc/ipa-modref-tree.h
index caf5d348dd8..abf3fc18b05 100644
--- a/gcc/ipa-modref-tree.h
+++ b/gcc/ipa-modref-tree.h
@@ -88,17 +88,18 @@ struct GTY((user)) modref_ref_node
   }
 
   /* 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)
+     Collapse tree if it has more than MAX_ACCESSES entries.
+     Return true if record was changed.  */
+  bool 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;
+      return false;
 
     /* Otherwise, insert a node for the ref of the access under the base.  */
     modref_access_node *access_node = search (a);
     if (access_node)
-      return;
+      return false;
 
     /* If this base->ref pair has too many accesses stored, we will clear
        all accesses and bail out.  */
@@ -109,9 +110,10 @@ struct GTY((user)) modref_ref_node
 	  fprintf (dump_file,
 		   "--param param=modref-max-accesses limit reached\n");
 	collapse ();
-	return;
+	return true;
       }
     vec_safe_push (accesses, a);
+    return true;
   }
 };
 
@@ -139,8 +141,11 @@ struct GTY((user)) modref_base_node
     return NULL;
   }
 
-  /* Insert REF; collapse tree if there are more than MAX_REFS.  */
-  modref_ref_node <T> *insert_ref (T ref, size_t max_refs)
+  /* Insert REF; collapse tree if there are more than MAX_REFS.
+     Return inserted ref and if CHANGED is non-null set it to true if
+     something changed.  */
+  modref_ref_node <T> *insert_ref (T ref, size_t max_refs,
+				   bool *changed = NULL)
   {
     modref_ref_node <T> *ref_node;
 
@@ -153,6 +158,9 @@ struct GTY((user)) modref_base_node
     if (ref_node)
       return ref_node;
 
+    if (changed)
+      *changed = true;
+
     /* Collapse the node if too full already.  */
     if (refs && refs->length () >= max_refs)
       {
@@ -204,7 +212,11 @@ struct GTY((user)) modref_tree
     max_accesses (max_accesses),
     every_base (false) {}
 
-  modref_base_node <T> *insert_base (T base)
+  /* Insert BASE; collapse tree if there are more than MAX_REFS.
+     Return inserted base and if CHANGED is non-null set it to true if
+     something changed.  */
+
+  modref_base_node <T> *insert_base (T base, bool *changed = NULL)
   {
     modref_base_node <T> *base_node;
 
@@ -217,6 +229,9 @@ struct GTY((user)) modref_tree
     if (base_node)
       return base_node;
 
+    if (changed)
+      *changed = true;
+
     /* Collapse the node if too full already.  */
     if (bases && bases->length () >= max_bases)
       {
@@ -232,43 +247,72 @@ struct GTY((user)) modref_tree
     return base_node;
   }
 
-  /* Insert memory access to the tree.	*/
-  void insert (T base, T ref, modref_access_node a)
+  /* Insert memory access to the tree.
+     Return true if something changed.  */
+  bool insert (T base, T ref, modref_access_node a)
   {
+    if (every_base)
+      return false;
+
+    bool changed = false;
+
     /* No useful information tracked; collapse everything.  */
     if (!base && !ref && !a.useful_p ())
       {
 	collapse ();
-	return;
+	return true;
       }
 
-    modref_base_node <T> *base_node = insert_base (base);
-    if (!base_node)
-      return;
-    gcc_assert (search (base) != NULL);
+    modref_base_node <T> *base_node = insert_base (base, &changed);
+    if (!base_node || base_node->every_ref)
+      return changed;
+    gcc_checking_assert (search (base) != NULL);
+
+    /* No useful ref info tracked; collapse base.  */
+    if (!ref && !a.useful_p ())
+      {
+	base_node->collapse ();
+	return true;
+      }
 
-    modref_ref_node <T> *ref_node = base_node->insert_ref (ref, max_refs);
+    modref_ref_node <T> *ref_node = base_node->insert_ref (ref, max_refs,
+							   &changed);
 
-    /* No useful ref information and no useful base; collapse everyting.  */
-    if (!base && base_node->every_ref)
+    /* If we failed to insert ref, just see if there is a cleanup possible.  */
+    if (!ref_node)
       {
-	collapse ();
-	return;
+	/* No useful ref information and no useful base; collapse everyting.  */
+	if (!base && base_node->every_ref)
+	  {
+	    collapse ();
+	    gcc_checking_assert (changed);
+	  }
+	else if (changed)
+	  cleanup ();
       }
-    if (ref_node)
+    else
       {
-	/* No useful ref and access; collapse ref.  */
-	if (!ref && !a.useful_p ())
-	  ref_node->collapse ();
-	else
+	if (ref_node->every_access)
+	  return changed;
+	changed |= ref_node->insert_access (a, max_accesses);
+	/* See if we failed to add useful access.  */
+	if (ref_node->every_access)
 	  {
-	    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 ();
+	    /* Collapse everything if there is no useful base and ref.  */
+	    if (!base && !ref)
+	      {
+		collapse ();
+		gcc_checking_assert (changed);
+	      }
+	    /* Collapse base if there is no useful ref.  */
+	    else if (!ref)
+	      {
+		base_node->collapse ();
+		gcc_checking_assert (changed);
+	      }
 	  }
       }
+    return changed;
   }
 
  /* Remove tree branches that are not useful (i.e. they will allways pass).  */
@@ -317,62 +361,74 @@ struct GTY((user)) modref_tree
 
   /* 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)
+     to signalize that parameter is local and does not need to be tracked.
+     Return true if something has changed.  */
+  bool merge (modref_tree <T> *other, vec <int> *parm_map)
   {
-    if (!other)
-      return;
+    if (!other || every_base)
+      return false;
     if (other->every_base)
       {
 	collapse ();
-	return;
+	return true;
       }
 
+    bool changed = false;
     size_t i, j, k;
     modref_base_node <T> *base_node, *my_base_node;
-    modref_ref_node <T> *ref_node, *my_ref_node;
+    modref_ref_node <T> *ref_node;
     modref_access_node *access_node;
-    FOR_EACH_VEC_SAFE_ELT (other->bases, i, base_node)
+    bool release = false;
+
+    /* For self-recursive functions we may end up merging summary into itself;
+       produce copy first so we do not modify summary under our own hands.  */
+    if (other == this)
       {
-	my_base_node = insert_base (base_node->base);
-	if (!my_base_node)
-	  continue;
+	release = true;
+	other = modref_tree<T>::create_ggc (max_bases, max_refs, max_accesses);
+	other->copy_from (this);
+      }
 
+    FOR_EACH_VEC_SAFE_ELT (other->bases, i, base_node)
+      {
 	if (base_node->every_ref)
 	  {
-	    my_base_node->collapse ();
-	    continue;
-	  }
-
-	FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
-	  {
-	    my_ref_node = my_base_node->insert_ref (ref_node->ref, max_refs);
-	    if (!my_ref_node)
-	      continue;
-
-	    if (ref_node->every_access)
+	    my_base_node = insert_base (base_node->base, &changed);
+	    if (my_base_node && !my_base_node->every_ref)
 	      {
-		my_ref_node->collapse ();
-		continue;
+		my_base_node->collapse ();
+		cleanup ();
+		changed = true;
 	      }
-	    FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
-	      {
-		modref_access_node a = *access_node;
-		if (a.parm_index != -1 && parm_map)
+	  }
+	else
+	  FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
+	    {
+	      if (ref_node->every_access)
+		{
+		  modref_access_node a = {-1};
+		  changed |= insert (base_node->base, ref_node->ref, a);
+		}
+	      else
+		FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
 		  {
-		    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];
+		    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];
+		      }
+		    changed |= insert (base_node->base, ref_node->ref, a);
 		  }
-		my_ref_node->insert_access (a, max_accesses);
-	      }
-	  }
+	    }
       }
-    if (parm_map)
-      cleanup ();
+    if (release)
+      ggc_delete (other);
+    return changed;
   }
 
   /* Copy OTHER to THIS.  */