Re: Speedup aliasing (on tramp3d -O1)

[Daniel Berlin <dberlin at dberlin dot org>]

Jan Hubicka wrote:
> 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?
> 

Rename bitmap_checksum to bitmap_hash, IMHO.

Also you need someone who can review the bitmap changes.
As for the alias changes, I assume memory usage from the hashtable is
not too large?

Assuming so, the tree-ssa-alias.c changes are fine by me.

(Note that with the ebitmap stuff i will submit for stage1, we eliminate
basically all the equality tests anyway because we track more
information, like number of words with set bits, etc)

> 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"
>