patch to speedup bitmap operations.

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

Changed freelist structure for bitmap_elements from simple linked list
to list of lists structure.  This allows bitmap_elt_clear_from to be a
unit time operation rather than take time proportional to the number
of elements being freed.  Also changed bitmap_clear to call
bitmap_elt_clear_from rather than clearing the blocks itself.

This patch causes a modest speedup (.5%) for "make restage3" on the mainline
branch but has a more significant speedup on the tree profiling branch
where new transformations make more extensive use of bitmaps.  There
are no regressions (performance or correctness) or changes in api
associated with this patch.


2005-03-29  Kenneth Zadeck <zadeck@naturalbridge.com>

   *bitmap.c (bitmap_elmt_to_freelist, bitmap_element_allocate,
   bitmap_elt_clear_from, bitmap_clear): Changed freelist structure.
   *bitmap.h: Fixed comments.

Index: bitmap.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bitmap.c,v
retrieving revision 1.68
diff -c -3 -p -r1.68 bitmap.c
*** bitmap.c	10 Mar 2005 15:40:11 -0000	1.68
--- bitmap.c	28 Mar 2005 21:57:57 -0000
*************** bitmap_elem_to_freelist (bitmap head, bi
*** 51,64 ****
  {
    bitmap_obstack *bit_obstack = head->obstack;
    
    if (bit_obstack)
      {
!       elt->next = bit_obstack->elements;
        bit_obstack->elements = elt;
      }
    else
      {
!       elt->next = bitmap_ggc_free;
        bitmap_ggc_free = elt;
      }
  }
--- 51,65 ----
  {
    bitmap_obstack *bit_obstack = head->obstack;
    
+   elt->next = NULL;
    if (bit_obstack)
      {
!       elt->prev = bit_obstack->elements;
        bit_obstack->elements = elt;
      }
    else
      {
!       elt->prev = bitmap_ggc_free;
        bitmap_ggc_free = elt;
      }
  }
*************** bitmap_element_allocate (bitmap head)
*** 105,111 ****
        element = bit_obstack->elements;
        
        if (element)
! 	bit_obstack->elements = element->next;
        else
  	element = XOBNEW (&bit_obstack->obstack, bitmap_element);
      }
--- 106,121 ----
        element = bit_obstack->elements;
        
        if (element)
! 	/* Use up the inner list first before looking at the next
! 	   element of the outer list.  */
! 	if (element->next)
! 	  {
! 	    bit_obstack->elements = element->next;
! 	    bit_obstack->elements->prev = element->prev;
! 	  }
! 	else
! 	  /*  Inner list was just a singleton.  */
! 	  bit_obstack->elements = element->prev;
        else
  	element = XOBNEW (&bit_obstack->obstack, bitmap_element);
      }
*************** bitmap_element_allocate (bitmap head)
*** 113,119 ****
      {
        element = bitmap_ggc_free;
        if (element)
! 	bitmap_ggc_free = element->next;
        else
  	element = GGC_NEW (bitmap_element);
      }
--- 123,138 ----
      {
        element = bitmap_ggc_free;
        if (element)
! 	/* Use up the inner list first before looking at the next
! 	   element of the outer list.  */
! 	if (element->next)
! 	  {
! 	    bitmap_ggc_free = element->next;
! 	    bitmap_ggc_free->prev = element->prev;
! 	  }
! 	else
! 	  /*  Inner list was just a singleton.  */
! 	  bitmap_ggc_free = element->prev;
        else
  	element = GGC_NEW (bitmap_element);
      }
*************** bitmap_element_allocate (bitmap head)
*** 128,140 ****
  void
  bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
  {
!   bitmap_element *next;
  
!   while (elt)
      {
!       next = elt->next;
!       bitmap_element_free (head, elt);
!       elt = next;
      }
  }
  
--- 147,184 ----
  void
  bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
  {
!   bitmap_element *prev;
!   bitmap_obstack *bit_obstack = head->obstack;
! 
!   if (!elt) return;
  
!   prev = elt->prev;
!   if (prev)
      {
!       prev->next = NULL;
!       if (head->current->indx > prev->indx)
! 	{
! 	  head->current = prev;
! 	  head->indx = prev->indx;
! 	}
!     } 
!   else
!     {
!       head->first = NULL;
!       head->current = NULL;
!       head->indx = 0;
!     }
! 
!   /* Put the entire list onto the free list in one operation. */ 
!   if (bit_obstack)
!     {
!       elt->prev = bit_obstack->elements; 
!       bit_obstack->elements = elt;
!     }
!   else
!     {
!       elt->prev = bitmap_ggc_free;
!       bitmap_ggc_free = elt;
      }
  }
  
*************** bitmap_elt_clear_from (bitmap head, bitm
*** 143,157 ****
  inline void
  bitmap_clear (bitmap head)
  {
!   bitmap_element *element, *next;
! 
!   for (element = head->first; element != 0; element = next)
!     {
!       next = element->next;
!       bitmap_elem_to_freelist (head, element);
!     }
! 
!   head->first = head->current = 0;
  }
  
  /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
--- 187,194 ----
  inline void
  bitmap_clear (bitmap head)
  {
!   if (head->first)
!     bitmap_elt_clear_from (head, head->first);
  }
  
  /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
Index: bitmap.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bitmap.h,v
retrieving revision 1.56
diff -c -3 -p -r1.56 bitmap.h
*** bitmap.h	17 Feb 2005 16:19:26 -0000	1.56
--- bitmap.h	28 Mar 2005 21:57:57 -0000
*************** typedef struct bitmap_obstack GTY (())
*** 49,56 ****
  
  /* Bitmap set element.  We use a linked list to hold only the bits that
     are set.  This allows for use to grow the bitset dynamically without
!    having to realloc and copy a giant bit array.  The `prev' field is
!    undefined for an element on the free list.  */
  
  typedef struct bitmap_element_def GTY(())
  {
--- 49,63 ----
  
  /* Bitmap set element.  We use a linked list to hold only the bits that
     are set.  This allows for use to grow the bitset dynamically without
!    having to realloc and copy a giant bit array.  
! 
!    The free list is implemented as a list of lists.  There is one
!    outer list connected together by prev fields.  Each element of that
!    outer is an inner list (that may consist only of the outer list
!    element) that are connected by the next fields.  The prev pointer
!    is undefined for interior elements.  This allows
!    bitmap_elt_clear_from to be implemented in unit time rather than
!    linear in the number of elements to be freed.  */
  
  typedef struct bitmap_element_def GTY(())
  {
*************** extern void debug_bitmap_file (FILE *, b
*** 129,135 ****
  /* Print a bitmap.  */
  extern void bitmap_print (FILE *, bitmap, const char *, const char *);
  
! /* Initialize and releas a bitmap obstack.  */
  extern void bitmap_obstack_initialize (bitmap_obstack *);
  extern void bitmap_obstack_release (bitmap_obstack *);
  
--- 136,142 ----
  /* Print a bitmap.  */
  extern void bitmap_print (FILE *, bitmap, const char *, const char *);
  
! /* Initialize and release a bitmap obstack.  */
  extern void bitmap_obstack_initialize (bitmap_obstack *);
  extern void bitmap_obstack_release (bitmap_obstack *);