tree-ssa-alias.c (eq_ptr_info, [...]): New function.

	* tree-ssa-alias.c (eq_ptr_info, ptr_info_hash): New function.
	(create_name_tags): Instead of quadratic checking use hashtable.
	* bitmap.h: Include hashtab.h.
	(bitmap_hash): Declare.
	* bitmap.c (bitmap_hash): New function.

From-SVN: r116285

4 files changed, 60 insertions, 15 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 08ca50e..bb37d46 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,13 @@
 2006-08-20  Jan Hubicka  <jh@suse.cz>
 
+	* tree-ssa-alias.c (eq_ptr_info, ptr_info_hash): New function.
+	(create_name_tags): Instead of quadratic checking use hashtable.
+	* bitmap.h: Include hashtab.h.
+	(bitmap_hash): Declare.
+	* bitmap.c (bitmap_hash): New function.
+
+2006-08-20  Jan Hubicka  <jh@suse.cz>
+
 	PR rtl-optimization/28071
 	* tree-optimize.c (tree_rest_of_compilation): Do not remove edges
 	twice.
diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index efc789a..4ac38b0 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -1520,4 +1520,21 @@ bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
   fputs (suffix, file);
 }
 
+/* Compute hash of bitmap (for purposes of hashing).  */
+hashval_t
+bitmap_hash (bitmap head)
+{
+  bitmap_element *ptr;
+  BITMAP_WORD hash = 0;
+  int ix;
+
+  for (ptr = head->first; ptr; ptr = ptr->next)
+    {
+      hash ^= ptr->indx;
+      for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+	hash ^= ptr->bits[ix];
+    }
+  return (hashval_t)hash;
+}
+
 #include "gt-bitmap.h"
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index d11fa46..3da58c5 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -21,6 +21,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 
 #ifndef GCC_BITMAP_H
 #define GCC_BITMAP_H
+#include "hashtab.h"
 
 /* Fundamental storage type for bitmap.  */
 
@@ -164,6 +165,9 @@ extern void bitmap_obstack_free (bitmap);
 #define bitmap_zero(a) bitmap_clear (a)
 extern unsigned bitmap_first_set_bit (bitmap);
 
+/* Compute bitmap hash (for purposes of hashing etc.)  */
+extern hashval_t bitmap_hash(bitmap);
+
 /* Allocate a bitmap from a bit obstack.  */
 #define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
 
diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
index 6bfa4bb..cf5ed4e 100644
--- a/gcc/tree-ssa-alias.c
+++ b/gcc/tree-ssa-alias.c
@@ -987,6 +987,23 @@ delete_alias_info (struct alias_info *ai)
   delete_points_to_sets ();
 }
 
+/* Used for hashing to identify pointer infos with identical
+   pt_vars bitmaps.  */
+static int
+eq_ptr_info (const void *p1, const void *p2)
+{
+  const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1;
+  const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2;
+  return bitmap_equal_p (n1->pt_vars, n2->pt_vars);
+}
+
+static hashval_t
+ptr_info_hash (const void *p)
+{
+  const struct ptr_info_def *n = (const struct ptr_info_def *) p;
+  return bitmap_hash (n->pt_vars);
+}
+
 /* Create name tags for all the pointers that have been dereferenced.
    We only create a name tag for a pointer P if P is found to point to
    a set of variables (so that we can alias them to *P) or if it is
@@ -1002,6 +1019,7 @@ create_name_tags (void)
   size_t i;
   VEC (tree, heap) *with_ptvars = NULL;
   tree ptr;
+  htab_t ptr_hash;
 
   /* Collect the list of pointers with a non-empty points to set.  */
   for (i = 1; i < num_ssa_names; i++)
@@ -1036,15 +1054,15 @@ create_name_tags (void)
   if (!with_ptvars)
     return;
 
+  ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
   /* Now go through the pointers with pt_vars, and find a name tag
      with the same pt_vars as this pointer, or create one if one
      doesn't exist.  */
   for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
     {
       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
-      size_t j;
-      tree ptr2;
       tree old_name_tag = pi->name_mem_tag;
+      struct ptr_info_def **slot;
       
       /* If PTR points to a set of variables, check if we don't
 	 have another pointer Q with the same points-to set before
@@ -1057,22 +1075,19 @@ create_name_tags (void)
 	 problems if they both had different name tags because
 	 they would have different SSA version numbers (which
 	 would force us to take the name tags in and out of SSA).  */
-      for (j = 0; j < i && VEC_iterate (tree, with_ptvars, j, ptr2); j++)
+
+      slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
+      if (*slot)
+        pi->name_mem_tag = (*slot)->name_mem_tag;
+      else
 	{
-	  struct ptr_info_def *qi = SSA_NAME_PTR_INFO (ptr2);
-	  
-	  if (bitmap_equal_p (pi->pt_vars, qi->pt_vars))
-	    {
-	      pi->name_mem_tag = qi->name_mem_tag;
-	      break;
-	    }
+	  *slot = pi;
+	  /* If we didn't find a pointer with the same points-to set
+	     as PTR, create a new name tag if needed.  */
+	  if (pi->name_mem_tag == NULL_TREE)
+	    pi->name_mem_tag = get_nmt_for (ptr);
 	}
       
-      /* If we didn't find a pointer with the same points-to set
-	 as PTR, create a new name tag if needed.  */
-      if (pi->name_mem_tag == NULL_TREE)
-	pi->name_mem_tag = get_nmt_for (ptr);
-      
       /* If the new name tag computed for PTR is different than
 	 the old name tag that it used to have, then the old tag
 	 needs to be removed from the IL, so we mark it for
@@ -1086,6 +1101,7 @@ create_name_tags (void)
       /* Mark the new name tag for renaming.  */
       mark_sym_for_renaming (pi->name_mem_tag);
     }
+  htab_delete (ptr_hash);
 
   VEC_free (tree, heap, with_ptvars);
 }