This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Speedup aliasing (on tramp3d -O1)
> 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?
Looking at top, I didn't seen any difference. We have one entry per
memory tag and it is temporary usage, so I think it is down in the
noise.
HonzA
>
> 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"
> >