Speedup aliasing (on tramp3d -O1)

[Jan Hubicka <jh at suse dot cz>]

Hi,
on tramp3d (and my favorite testcase too), aliasing spends about 6-10%
of -O1 compilation time by checking bitmaps for equivalency.
Bootstrapped/regtested i686-linux, OK?

Honza

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

Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 116257)
+++ tree-ssa-alias.c	(working copy)
@@ -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_checksum (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);
 }
Index: bitmap.h
===================================================================
--- bitmap.h	(revision 116257)
+++ bitmap.h	(working copy)
@@ -164,6 +164,9 @@ extern void bitmap_obstack_free (bitmap)
 #define bitmap_zero(a) bitmap_clear (a)
 extern unsigned bitmap_first_set_bit (bitmap);
 
+/* Compute bitmap checksum (for purposes of hashing etc.)  */
+extern unsigned long bitmap_checksum(bitmap);
+
 /* Allocate a bitmap from a bit obstack.  */
 #define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
 
Index: bitmap.c
===================================================================
--- bitmap.c	(revision 116257)
+++ bitmap.c	(working copy)
@@ -1520,4 +1520,21 @@ bitmap_print (FILE *file, bitmap head, c
   fputs (suffix, file);
 }
 
+/* Compute checksum of bitmap (for purposes of hashing).  */
+unsigned long
+bitmap_checksum (bitmap head)
+{
+  bitmap_element *ptr;
+  unsigned long checksum = 0;
+  int ix;
+
+  for (ptr = head->first; ptr; ptr = ptr->next)
+    {
+      checksum ^= ptr->indx;
+      for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+	checksum ^= ptr->bits[ix];
+    }
+  return checksum;
+}
+
 #include "gt-bitmap.h"