This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

bitmap.c tweeks


The recent change to use xmalloc is somewhat less than optimal.
The rest of the routines in the file allocate the temporary
directly.

Also, the use of EXECUTE_IF_SET_IN_BITMAP to search for the last
bit in the map -- iterating over every bit to get there, note --
is the worst way this could be done.  I've reimplemented both of
these search routines to use binary search on the bits.

Tested on alphaev56-linux.


r~


        * bitmap.c (bitmap_release_memory): Move adjacent to the
        allocation functions.
        (bitmap_first_set_bit, bitmap_last_set_bit): Streamline knowing
        the implementation.  Binary search for the set bit.
        (bitmap_union_of_diff): Allocate the temporary on the stack
        instead of using xmalloc.

Index: bitmap.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/bitmap.c,v
retrieving revision 1.27
diff -c -p -d -r1.27 bitmap.c
*** bitmap.c	2001/07/04 17:25:58	1.27
--- bitmap.c	2001/07/06 20:58:43
*************** bitmap_element_allocate ()
*** 135,140 ****
--- 135,153 ----
    return element;
  }
  
+ /* Release any memory allocated by bitmaps.  */
+ 
+ void
+ bitmap_release_memory ()
+ {
+   bitmap_free = 0;
+   if (bitmap_obstack_init)
+     {
+       bitmap_obstack_init = FALSE;
+       obstack_free (&bitmap_obstack, NULL);
+     }
+ }
+ 
  /* Return nonzero if all bits in an element are zero.  */
  
  static INLINE int
*************** bitmap_bit_p (head, bit)
*** 384,389 ****
--- 397,503 ----
    return (ptr->bits[word_num] >> bit_num) & 1;
  }
  
+ 
+ int 
+ bitmap_first_set_bit (a)
+      bitmap a;
+ {
+   bitmap_element *ptr = a->first;
+   unsigned HOST_WIDE_INT word;
+   unsigned word_num, bit_num;
+ 
+   if (ptr == NULL)
+     return -1;
+ 
+ #if BITMAP_ELEMENT_WORDS == 2
+   word_num = 0, word = ptr->bits[0];
+   if (word == 0)
+     word_num = 1, word = ptr->bits[1];
+ #else
+   for (word_num = 0; word_num < BITMAP_ELEMENT_WORDS; ++word_num)
+     if ((word = ptr->bits[word_num]) != 0)
+       break;
+ #endif
+ 
+   /* Binary search for the first set bit.  */
+   /* ??? It'd be nice to know if ffs or ffsl was available.  */
+ 
+   bit_num = 0;
+   word = word & -word;
+ 
+ #if HOST_BITS_PER_WIDE_INT > 64
+  #error "Fill out the table."
+ #endif
+ #if HOST_BITS_PER_WIDE_INT > 32
+   if ((word & 0xffffffff) == 0)
+     word >>= 32, bit_num += 32;
+ #endif
+   if ((word & 0xffff) == 0)
+     word >>= 16, bit_num += 16;
+   if ((word & 0xff) == 0)
+     word >>= 8, bit_num += 8;
+   if (word & 0xf0)
+     bit_num += 4;
+   if (word & 0xcc)
+     bit_num += 2;
+   if (word & 0xaa)
+     bit_num += 1;
+ 
+   return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
+ 	  + word_num * HOST_BITS_PER_WIDE_INT
+ 	  + bit_num);
+ }
+ 
+ int 
+ bitmap_last_set_bit (a)
+      bitmap a;
+ {
+   bitmap_element *ptr = a->first;
+   unsigned HOST_WIDE_INT word;
+   unsigned word_num, bit_num;
+ 
+   if (ptr == NULL)
+     return -1;
+ 
+   while (ptr->next != NULL)
+     ptr = ptr->next;
+ 
+ #if BITMAP_ELEMENT_WORDS == 2
+   word_num = 1, word = ptr->bits[1];
+   if (word == 0)
+     word_num = 0, word = ptr->bits[0];
+ #else
+   for (word_num = BITMAP_ELEMENT_WORDS; word_num-- > 0; )
+     if ((word = ptr->bits[word_num]) != 0)
+       break;
+ #endif
+ 
+   /* Binary search for the last set bit.  */
+ 
+   bit_num = 0;
+ #if HOST_BITS_PER_WIDE_INT > 64
+  #error "Fill out the table."
+ #endif
+ #if HOST_BITS_PER_WIDE_INT > 32
+   if (word & ~ (unsigned HOST_WIDE_INT) 0xffffffff)
+     word >>= 32, bit_num += 32;
+ #endif
+   if (word & 0xffff0000)
+     word >>= 16, bit_num += 16;
+   if (word & 0xff00)
+     word >>= 8, bit_num += 8;
+   if (word & 0xf0)
+     word >>= 4, bit_num += 4;
+   if (word & 0xc)
+     word >>= 2, bit_num += 2;
+   if (word & 0x2)
+     word >>= 1, bit_num += 1;
+ 
+   return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
+ 	  + word_num * HOST_BITS_PER_WIDE_INT
+ 	  + bit_num);
+ }
+ 
  /* Store in bitmap TO the result of combining bitmap FROM1 and FROM2 using
     a specific bit manipulation.  Return true if TO changes.  */
  
*************** bitmap_ior_and_compl (to, from1, from2)
*** 576,581 ****
--- 690,714 ----
    bitmap_operation (to, to, &tmp, BITMAP_IOR);
    bitmap_clear (&tmp);
  }
+ 
+ int
+ bitmap_union_of_diff (dst, a, b, c)
+      bitmap dst;
+      bitmap a;
+      bitmap b;
+      bitmap c;
+ {
+   bitmap_head tmp;
+   int changed;
+ 
+   tmp.first = tmp.current = 0;
+ 
+   bitmap_operation (&tmp, b, c, BITMAP_AND_COMPL);
+   changed = bitmap_operation (dst, &tmp, a, BITMAP_IOR);
+   bitmap_clear (&tmp);
+ 
+   return changed;
+ }
  
  /* Initialize a bitmap header.  */
  
*************** bitmap_print (file, head, prefix, suffix
*** 664,716 ****
  			      comma = ", ";
  			    });
    fputs (suffix, file);
- }
- 
- /* Release any memory allocated by bitmaps.  */
- 
- void
- bitmap_release_memory ()
- {
-   bitmap_free = 0;
-   if (bitmap_obstack_init)
-     {
-       bitmap_obstack_init = FALSE;
-       obstack_free (&bitmap_obstack, NULL);
-     }
- }
- 
- int
- bitmap_union_of_diff (dst, a, b, c)
-      bitmap dst;
-      bitmap a;
-      bitmap b;
-      bitmap c;
- {
-   int changed = 0;
-   bitmap temp = BITMAP_XMALLOC ();
-   
-   bitmap_operation (temp, b, c, BITMAP_AND_COMPL);
-   changed = bitmap_operation (dst, temp, a, BITMAP_IOR);
-   BITMAP_XFREE (temp);
-   return changed;
- }
- 
- int 
- bitmap_first_set_bit (a)
-      bitmap a;
- {
-   int i;
-   EXECUTE_IF_SET_IN_BITMAP (a, 0, i, return i;);
-   return -1;
- }
- 
- int 
- bitmap_last_set_bit (a)
-      bitmap a;
- {
-   int i;
-   EXECUTE_IF_SET_IN_BITMAP (a, 0, i, ;);
-   if (bitmap_bit_p (a, i))
-     return i;
-   return -1;
  }
--- 797,800 ----


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]