[PATCH 2/2] Optimize alias subset recording

[Richard Biener]

On Tue, 14 Jan 2020, Richard Biener wrote:

> On Tue, 14 Jan 2020, Richard Biener wrote:
> 
> > On Tue, 14 Jan 2020, Richard Biener wrote:
> > 
> > > When an alias-set is an already existing subset there is no need
> > > to re-record its children as childs of the parent.
> > > 
> > > I noticed this when doing 1/2 as trivial opportunity to squeeze
> > > back some performance for the non-caching recursion I added.  The
> > > whole thing is still quadratic in the depth of the structure, of course.
> > > 
> > > Bootstrapped and tested on x86_64-unknown-linux-gnu.
> > > 
> > > Since I'm curious I'll test a variant which checks the children
> > > are actually recorded before pushing this ... (OK, maybe I shouldn't
> > > do this...)
> > 
> > So I did it.  It works but for
> > 
> > FAIL: gnat.dg/interface2.adb 3 blank line(s) in output
> > FAIL: gnat.dg/interface2.adb (test for excess errors)
> > UNRESOLVED: gnat.dg/interface2.adb compilation failed to produce 
> > executable
> > FAIL: gnat.dg/predicate2_main.adb 3 blank line(s) in output
> > FAIL: gnat.dg/predicate2_main.adb (test for excess errors)
> > 
> > which ICE with the adjusted patch below.  Ada calls
> > record_component_aliases itself and eventually too early when
> > some types are not yet complete?  Which would also mean that
> > subsets could be failed to recorded properly.
> > 
> > So I'm still inclined to go with the original non-checking patch
> > unless Eric tells me I'm completely wrong and there isn't a
> > latent issue in the Ada frontend.
> 
> Btw, all the dance the Ada FE performs in relate_alias_sets isn't
> going to work with LTO unless it is no longer necessary anyways.
> 
> Oh, and we miss libbacktrace support for GNAT bug boxes, for the
> above I'd like to know whether its from record_component_aliases
> calls or calls of record_alias_subset.

And if I delay checking until we actually look for subsets
(alias_sets_conflict or alias_set_subset_of), verifying we collected
all subsets that fails when building the RTS, for example when
building g-awk.adb.  The patch below does that verification,
it doesn't actually look for a case where the final answer of
those predicates is wrong though.

It seems that Ada is the only frontend affected by this "bug" so
I pushed the original change.

Richard.

diff --git a/gcc/alias.c b/gcc/alias.c
index 9629b5a9f48..ffb2af9b34f 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -154,7 +154,7 @@ static int base_alias_check (rtx, rtx, rtx, rtx, machine_mode,
 			     machine_mode);
 static rtx find_base_value (rtx);
 static int mems_in_disjoint_alias_sets_p (const_rtx, const_rtx);
-static alias_set_entry *get_alias_set_entry (alias_set_type);
+static alias_set_entry *get_alias_set_entry (alias_set_type, bool = false);
 static tree decl_for_component_ref (tree);
 static int write_dependence_p (const_rtx,
 			       const_rtx, machine_mode, rtx,
@@ -372,9 +372,37 @@ rtx_refs_may_alias_p (const_rtx x, const_rtx mem, bool tbaa_p)
    such an entry, or NULL otherwise.  */
 
 static inline alias_set_entry *
-get_alias_set_entry (alias_set_type alias_set)
+get_alias_set_entry (alias_set_type alias_set, bool check)
 {
-  return (*alias_sets)[alias_set];
+  alias_set_entry *e = (*alias_sets)[alias_set];
+  if (check && e && e->children)
+    {
+      bitmap_obstack_initialize (NULL);
+      auto_vec<alias_set_type> worklist;
+      auto_bitmap visited;
+      hash_map<alias_set_hash, int>::iterator iter
+	= e->children->begin ();
+      for (; iter != e->children->end (); ++iter)
+	worklist.safe_push ((*iter).first);
+      while (!worklist.is_empty ())
+	{
+	  alias_set_type subset = worklist.pop ();
+	  if (!bitmap_set_bit (visited, subset))
+	    continue;
+	  alias_set_entry *se = (*alias_sets)[subset];
+	  if (se && se->children)
+	    for (iter = se->children->begin ();
+		 iter != se->children->end (); ++iter)
+	      {
+		if ((*iter).first == alias_set)
+		  continue;
+		gcc_assert (e->children->get ((*iter).first) != NULL);
+		worklist.safe_push ((*iter).first);
+	      }
+	}
+      bitmap_obstack_release (NULL);
+    }
+  return e;
 }
 
 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
@@ -404,7 +432,7 @@ alias_set_subset_of (alias_set_type set1, alias_set_type set2)
     return true;
 
   /* Check if set1 is a subset of set2.  */
-  ase2 = get_alias_set_entry (set2);
+  ase2 = get_alias_set_entry (set2, true);
   if (ase2 != 0
       && (ase2->has_zero_child
 	  || (ase2->children && ase2->children->get (set1))))
@@ -433,7 +461,7 @@ alias_set_subset_of (alias_set_type set1, alias_set_type set2)
      get_alias_set for more details.  */
   if (ase2 && ase2->has_pointer)
     {
-      alias_set_entry *ase1 = get_alias_set_entry (set1);
+      alias_set_entry *ase1 = get_alias_set_entry (set1, true);
 
       if (ase1 && ase1->is_pointer)
 	{
@@ -465,7 +493,7 @@ alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
     return 1;
 
   /* See if the first alias set is a subset of the second.  */
-  ase1 = get_alias_set_entry (set1);
+  ase1 = get_alias_set_entry (set1, true);
   if (ase1 != 0
       && ase1->children && ase1->children->get (set2))
     {
@@ -474,7 +502,7 @@ alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
     }
 
   /* Now do the same, but with the alias sets reversed.  */
-  ase2 = get_alias_set_entry (set2);
+  ase2 = get_alias_set_entry (set2, true);
   if (ase2 != 0
       && ase2->children && ase2->children->get (set1))
     {
@@ -1164,10 +1192,16 @@ record_alias_subset (alias_set_type superset, alias_set_type subset)
     superset_entry->has_zero_child = 1;
   else
     {
-      subset_entry = get_alias_set_entry (subset);
       if (!superset_entry->children)
 	superset_entry->children
 	  = hash_map<alias_set_hash, int>::create_ggc (64);
+
+      /* Enter the SUBSET itself as a child of the SUPERSET.  If it was
+	 already there we're done.  */
+      if (superset_entry->children->put (subset, 0))
+	return;
+
+      subset_entry = get_alias_set_entry (subset);
       /* If there is an entry for the subset, enter all of its children
 	 (if they are not already present) as children of the SUPERSET.  */
       if (subset_entry)
@@ -1182,12 +1216,13 @@ record_alias_subset (alias_set_type superset, alias_set_type subset)
 	      hash_map<alias_set_hash, int>::iterator iter
 		= subset_entry->children->begin ();
 	      for (; iter != subset_entry->children->end (); ++iter)
-		superset_entry->children->put ((*iter).first, (*iter).second);
+		/* It is possible in complex type situations for both sets
+		   to be the same, in which case we can ignore this
+		   operation.  */
+		if ((*iter).first != superset)
+		  superset_entry->children->put ((*iter).first, (*iter).second);
 	    }
 	}
-
-      /* Enter the SUBSET itself as a child of the SUPERSET.  */
-      superset_entry->children->put (subset, 0);
     }
 }