[PATCH]: Fix alias grouping of name tags.

[Daniel Berlin]

During alias grouping, we will end up replacing each alias in an NMT
with an SMT if the SMT has been grouped.  However, this causes us to
replace symbols such that

NMT.67 aliases { a b c }

is now (assuming SMT.567, aliasing a b and c, gets grouped).

NMT.67 aliases { SMT.567 SMT.567 SMT.567 }

Whoops.

The attached fixes this.

Bootstrapped and regtested on i686-pc-darwin

Committed to mainline

2006-11-23  Daniel Berlin  <dberlin@dberlin.org>

	* tree-ssa-alias.c (tree_pointer_compare): New function.
	(compact_name_tags): New function.
	(group_aliases): Call compact_name_tags.
-------------- next part --------------
--- tree-ssa-alias.c	(/mirror/gcc-trunk/gcc/tree-ssa-alias.c)	(revision 258)
+++ tree-ssa-alias.c	(/local/gcc-clean/gcc/tree-ssa-alias.c)	(revision 258)
@@ -1436,6 +1437,72 @@ group_aliases_into (tree tag, bitmap tag
   tag_ann->may_aliases = NULL;
 }
 
+/* Simple comparison function for qsort that sorts based on pointer
+   address.  */
+static int
+tree_pointer_compare (const void *pa, const void *pb)
+{
+  const tree a = *((const tree *)pa);
+  const tree b = *((const tree *)pb);
+  
+  return b - a;
+}
+
+
+/* Replacing may aliases in name tags during grouping can up with the
+   same SMT multiple times in the may_alias list.  It's quicker to
+   just remove them post-hoc than it is to avoid them during
+   replacement.  Thus, this routine sorts the may-alias list and
+   removes duplicates.  */
+
+static void
+compact_name_tags (void)
+{
+  referenced_var_iterator rvi;
+  tree var;
+
+  FOR_EACH_REFERENCED_VAR (var, rvi)
+    {
+      if (TREE_CODE (var) == NAME_MEMORY_TAG)
+	{
+	  VEC(tree, gc) *aliases, *new_aliases;
+	  tree alias, last_alias;
+	  int i;
+	  
+	  last_alias = NULL;
+	  aliases = var_ann (var)->may_aliases;
+	  new_aliases = NULL;
+	  
+	  if (VEC_length (tree, aliases) > 1)
+	    {
+	      bool changed = false;
+	      qsort (VEC_address (tree, aliases), VEC_length (tree, aliases),
+		     sizeof (tree), tree_pointer_compare);
+	      
+	      for (i = 0; VEC_iterate (tree, aliases, i, alias); i++)
+		{
+		  if (alias == last_alias)
+		    {
+		      changed = true;
+		      continue;
+		    }
+		  
+		  VEC_safe_push (tree, gc, new_aliases, alias);
+		  last_alias = alias;
+		}
+
+	      /* Only replace the array if something has changed.  */
+	      if (changed)
+		{
+		  VEC_free (tree, gc, aliases);
+		  var_ann (var)->may_aliases = new_aliases;
+		}
+	      else
+		VEC_free (tree, gc, new_aliases);
+	    }
+	}
+    }
+}
 
 /* Group may-aliases sets to reduce the number of virtual operands due
    to aliasing.
@@ -1596,7 +1663,9 @@ group_aliases (struct alias_info *ai)
 	    }
 	}
     }
-
+  
+  compact_name_tags ();
+  
   if (dump_file)
     fprintf (dump_file,
 	     "%s: Total number of aliased vops after grouping: %ld%s\n",