===================================================================
@@ -44,6 +44,8 @@ struct bitmap_descriptor_d
typedef struct bitmap_descriptor_d *bitmap_descriptor;
typedef const struct bitmap_descriptor_d *const_bitmap_descriptor;
+static bitmap_element *bitmap_tree_listify_from (bitmap, bitmap_element *);
+
/* Next available unique id number for bitmap desciptors. */
static int next_bitmap_desc_id = 0;
@@ -95,6 +97,11 @@ get_bitmap_descriptor (const char *file,
if (*slot)
return *slot;
+ /* The descriptor ID can be at most 31 bits long, because the most
+ significant of the (half)word is used to identify the mode of
+ the bitmap, i.e. whether its current form is list or tree. */
+ gcc_assert (next_bitmap_desc_id < (1 << 30) - 1); // TODO: make descriptor ID unsigned
+
*slot = XCNEW (struct bitmap_descriptor_d);
bitmap_descriptors.safe_push (*slot);
(*slot)->id = next_bitmap_desc_id++;
@@ -133,22 +140,18 @@ static int bitmap_default_obstack_depth;
static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
GC'd elements. */
-static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
-static void bitmap_element_free (bitmap, bitmap_element *);
-static bitmap_element *bitmap_element_allocate (bitmap);
-static int bitmap_element_zerop (const bitmap_element *);
-static void bitmap_element_link (bitmap, bitmap_element *);
-static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
-static void bitmap_elt_clear_from (bitmap, bitmap_element *);
-static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
+/* Bitmap memory management. */
-/* Add ELEM to the appropriate freelist. */
+/* Add ELT to the appropriate freelist. */
static inline void
bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
{
bitmap_obstack *bit_obstack = head->obstack;
+ if (GATHER_STATISTICS)
+ register_overhead (head, -((int)sizeof (bitmap_element)));
+
elt->next = NULL;
if (bit_obstack)
{
@@ -162,41 +165,6 @@ bitmap_elem_to_freelist (bitmap head, bi
}
}
-/* Free a bitmap element. Since these are allocated off the
- bitmap_obstack, "free" actually means "put onto the freelist". */
-
-static inline void
-bitmap_element_free (bitmap head, bitmap_element *elt)
-{
- bitmap_element *next = elt->next;
- bitmap_element *prev = elt->prev;
-
- if (prev)
- prev->next = next;
-
- if (next)
- next->prev = prev;
-
- if (head->first == elt)
- head->first = next;
-
- /* Since the first thing we try is to insert before current,
- make current the next entry in preference to the previous. */
- if (head->current == elt)
- {
- head->current = next != 0 ? next : prev;
- if (head->current)
- head->indx = head->current->indx;
- else
- head->indx = 0;
- }
-
- if (GATHER_STATISTICS)
- register_overhead (head, -((int)sizeof (bitmap_element)));
-
- bitmap_elem_to_freelist (head, elt);
-}
-
/* Allocate a bitmap element. The bits are cleared, but nothing else is. */
static inline bitmap_element *
@@ -249,7 +217,8 @@ bitmap_element_allocate (bitmap head)
return element;
}
-/* Remove ELT and all following elements from bitmap HEAD. */
+/* Remove ELT and all following elements from bitmap HEAD.
+ Put the released elements in the freelist for HEAD. */
void
bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
@@ -257,7 +226,11 @@ bitmap_elt_clear_from (bitmap head, bitm
bitmap_element *prev;
bitmap_obstack *bit_obstack = head->obstack;
- if (!elt) return;
+ if (!elt)
+ return;
+
+ if (head->tree_form)
+ elt = bitmap_tree_listify_from (head, elt);
if (GATHER_STATISTICS)
{
@@ -284,7 +257,7 @@ bitmap_elt_clear_from (bitmap head, bitm
head->indx = 0;
}
- /* Put the entire list onto the free list in one operation. */
+ /* Put the entire list onto the freelist in one operation. */
if (bit_obstack)
{
elt->prev = bit_obstack->elements;
@@ -296,14 +269,482 @@ bitmap_elt_clear_from (bitmap head, bitm
bitmap_ggc_free = elt;
}
}
+
+/* Linked-list view of bitmaps.
+
+ In this representation, the bitmap elements form a double-linked list
+ with elements sorted by increasing index. */
+
+/* Link the bitmap element into the current bitmap linked list. */
+
+static inline void
+bitmap_list_link_element (bitmap head, bitmap_element *element)
+{
+ unsigned int indx = element->indx;
+ bitmap_element *ptr;
+
+ gcc_checking_assert (!head->tree_form);
+
+ /* If this is the first and only element, set it in. */
+ if (head->first == 0)
+ {
+ element->next = element->prev = 0;
+ head->first = element;
+ }
+
+ /* If this index is less than that of the current element, it goes someplace
+ before the current element. */
+ else if (indx < head->indx)
+ {
+ for (ptr = head->current;
+ ptr->prev != 0 && ptr->prev->indx > indx;
+ ptr = ptr->prev)
+ ;
+
+ if (ptr->prev)
+ ptr->prev->next = element;
+ else
+ head->first = element;
+
+ element->prev = ptr->prev;
+ element->next = ptr;
+ ptr->prev = element;
+ }
+
+ /* Otherwise, it must go someplace after the current element. */
+ else
+ {
+ for (ptr = head->current;
+ ptr->next != 0 && ptr->next->indx < indx;
+ ptr = ptr->next)
+ ;
+
+ if (ptr->next)
+ ptr->next->prev = element;
+
+ element->next = ptr->next;
+ element->prev = ptr;
+ ptr->next = element;
+ }
+
+ /* Set up so this is the first element searched. */
+ head->current = element;
+ head->indx = indx;
+}
+
+/* Unlink the bitmap element from the current bitmap linked list,
+ and return it to the freelist. */
+
+static inline void
+bitmap_list_unlink_element (bitmap head, bitmap_element *element)
+{
+ bitmap_element *next = element->next;
+ bitmap_element *prev = element->prev;
+
+ gcc_checking_assert (!head->tree_form);
+
+ if (prev)
+ prev->next = next;
+
+ if (next)
+ next->prev = prev;
+
+ if (head->first == element)
+ head->first = next;
+
+ /* Since the first thing we try is to insert before current,
+ make current the next entry in preference to the previous. */
+ if (head->current == element)
+ {
+ head->current = next != 0 ? next : prev;
+ if (head->current)
+ head->indx = head->current->indx;
+ else
+ head->indx = 0;
+ }
+
+ bitmap_elem_to_freelist (head, element);
+}
+
+/* Insert a new uninitialized element into bitmap HEAD after element
+ ELT. If ELT is NULL, insert the element at the start. Return the
+ new element. */
+
+static bitmap_element *
+bitmap_list_insert_element_after (bitmap head,
+ bitmap_element *elt, unsigned int indx)
+{
+ bitmap_element *node = bitmap_element_allocate (head);
+ node->indx = indx;
+
+ gcc_checking_assert (!head->tree_form);
+
+ if (!elt)
+ {
+ if (!head->current)
+ {
+ head->current = node;
+ head->indx = indx;
+ }
+ node->next = head->first;
+ if (node->next)
+ node->next->prev = node;
+ head->first = node;
+ node->prev = NULL;
+ }
+ else
+ {
+ gcc_checking_assert (head->current);
+ node->next = elt->next;
+ if (node->next)
+ node->next->prev = node;
+ elt->next = node;
+ node->prev = elt;
+ }
+ return node;
+}
+
+/* Return the element for INDX, or NULL if the element doesn't exist. */
+
+static inline bitmap_element *
+bitmap_list_find_element (bitmap head, unsigned int indx)
+{
+ bitmap_element *element;
+ if (head->indx < indx)
+ /* INDX is beyond head->indx. Search from head->current
+ forward. */
+ for (element = head->current;
+ element->next != 0 && element->indx < indx;
+ element = element->next)
+ {
+ if (GATHER_STATISTICS)
+ bitmap_descriptors[head->descriptor_id]->search_iter++;
+ }
+
+ else if (head->indx / 2 < indx)
+ /* INDX is less than head->indx and closer to head->indx than to
+ 0. Search from head->current backward. */
+ for (element = head->current;
+ element->prev != 0 && element->indx > indx;
+ element = element->prev)
+ {
+ if (GATHER_STATISTICS)
+ bitmap_descriptors[head->descriptor_id]->search_iter++;
+ }
+
+ else
+ /* INDX is less than head->indx and closer to 0 than to
+ head->indx. Search from head->first forward. */
+ for (element = head->first;
+ element->next != 0 && element->indx < indx;
+ element = element->next)
+ if (GATHER_STATISTICS)
+ {
+ bitmap_descriptors[head->descriptor_id]->search_iter++;
+ }
+
+ /* `element' is the nearest to the one we want. If it's not the one we
+ want, the one we want doesn't exist. */
+ gcc_checking_assert (element != NULL);
+ head->current = element;
+ head->indx = element->indx;
+ if (element->indx != indx)
+ element = 0;
+ return element;
+}
+
+
+/* Splay-tree view of bitmaps.
+
+ This is an almost one-to-one the implementatin of the simple top-down
+ splay tree in Sleator and Tarjan's "Self-adjusting Binary Search Trees".
+ It is probably not the most efficient form of splay trees, but it should
+ be good enough to experiment with this idea of bitmaps-as-trees.
+
+ For all functions below, the variable or function argument "t" is a node
+ in the tree, and "e" is a temporary or new node in the tree. The rest
+ is sufficiently straigh-forward (and very well explained in the paper)
+ that comment would only clutter things. */
+
+static inline void
+bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l)
+{
+ l->next = t;
+ l = t;
+ t = t->next;
+}
+
+static inline void
+bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r)
+{
+ r->prev = t;
+ r = t;
+ t = t->prev;
+}
+
+static inline void
+bitmap_tree_rotate_left (bitmap_element * &t)
+{
+ bitmap_element *e = t->next;
+ t->next = t->next->prev;
+ e->prev = t;
+ t = e;
+}
+
+static inline void
+bitmap_tree_rotate_right (bitmap_element * &t)
+{
+ bitmap_element *e = t->prev;
+ t->prev = t->prev->next;
+ e->next = t;
+ t = e;
+}
+
+static bitmap_element *
+bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx)
+{
+ bitmap_element N, *l, *r;
+
+ if (t == NULL)
+ return NULL;
+
+ N.prev = N.next = NULL;
+ l = r = &N;
+
+ while (indx != t->indx)
+ {
+ if (GATHER_STATISTICS)
+ bitmap_descriptors[head->descriptor_id]->search_iter++;
+
+ if (indx < t->indx)
+ {
+ if (t->prev != NULL && indx < t->prev->indx)
+ bitmap_tree_rotate_right (t);
+ if (t->prev == NULL)
+ break;
+ bitmap_tree_link_right (t, r);
+ }
+ else if (indx > t->indx)
+ {
+ if (t->next != NULL && indx > t->next->indx)
+ bitmap_tree_rotate_left (t);
+ if (t->next == NULL)
+ break;
+ bitmap_tree_link_left (t, l);
+ }
+ }
+
+ l->next = t->prev;
+ r->prev = t->next;
+ t->prev = N.next;
+ t->next = N.prev;
+ return t;
+}
+
+/* Link bitmap element E into the current bitmap splay tree. */
+
+static inline void
+bitmap_tree_link_element (bitmap head, bitmap_element *e)
+{
+ if (head->first == NULL)
+ e->prev = e->next = NULL;
+ else
+ {
+ bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
+ if (e->indx < t->indx)
+ {
+ e->prev = t->prev;
+ e->next = t;
+ t->prev = NULL;
+ }
+ else if (e->indx > t->indx)
+ {
+ e->next = t->next;
+ e->prev = t;
+ t->next = NULL;
+ }
+ else
+ gcc_unreachable ();
+ }
+ head->first = e;
+ head->current = e;
+ head->indx = e->indx;
+}
+
+/* Unlink bitmap element E from the current bitmap splay tree,
+ and return it to the freelist. */
+
+static void
+bitmap_tree_unlink_element (bitmap head, bitmap_element *e)
+{
+ bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
+
+ gcc_checking_assert (t == e);
+
+ if (e->prev == NULL)
+ t = e->next;
+ else
+ {
+ t = bitmap_tree_splay (head, e->prev, e->indx);
+ t->next = e->next;
+ }
+ head->first = t;
+ head->current = t;
+ head->indx = (t != NULL) ? t->indx : 0;
+
+ bitmap_elem_to_freelist (head, e);
+}
+
+/* Return the element for INDX, or NULL if the element doesn't exist. */
+
+static inline bitmap_element *
+bitmap_tree_find_element (bitmap head, unsigned int indx)
+{
+ bitmap_element *element = bitmap_tree_splay (head, head->first, indx);
+ gcc_checking_assert (element != NULL);
+ head->first = element;
+ head->current = element;
+ head->indx = element->indx;
+ if (element->indx != indx)
+ element = 0;
+ return element;
+}
+
+/* Converting bitmap views from linked-list to tree and vice versa. */
+
+/* Splice element E and all elements with a larger index from
+ bitmap HEAD, convert the spliced elements to the linked-list
+ view, and return the head of the list (which should be E again), */
+
+static bitmap_element *
+bitmap_tree_listify_from (bitmap head, bitmap_element *e)
+{
+ bitmap_element *t, *erb;
+
+ /* Detach the right branch from E (all elements with indx > E->indx),
+ and splay E to the root. */
+ erb = e->next;
+ e->next = NULL;
+ t = bitmap_tree_splay (head, head->first, e->indx);
+ gcc_checking_assert (t == e);
+
+ if (e->prev == NULL)
+ t = e->next;
+ else
+ {
+ t = bitmap_tree_splay (head, e->prev, e->indx);
+ t->next = e->next;
+ }
+ head->first = t;
+ head->current = t;
+ head->indx = (t != NULL) ? t->indx : 0;
+
+ gcc_assert (e->prev == NULL);
+ e->next = erb;
+
+ /* The tree is now valid again. Now we need to "un-tree" E.
+ It is imperative that a non-recursive implementation is used
+ for this, because splay trees have a worst case depth of O(E).
+ A recursive implementation would result in a stack overflow
+ for a sufficiently large, unbalanced bitmap tree. */
+ vec<bitmap_element *> stack = vNULL;
+ vec<bitmap_element *> sorted_elements = vNULL;
+ bitmap_element *n = e;
+
+ while (true)
+ {
+ while (n != NULL)
+ {
+ stack.safe_push (n);
+ n = n->prev;
+ }
+
+ if (stack.is_empty ())
+ break;
+
+ n = stack.pop ();
+ sorted_elements.safe_push (n);
+ n = n->next;
+ }
+ stack.release ();
+
+ gcc_assert (sorted_elements[0] == e);
+
+ bitmap_element *prev = NULL;
+ unsigned ix;
+ FOR_EACH_VEC_ELT (sorted_elements, ix, n)
+ {
+ if (prev != NULL)
+ prev->next = n;
+ n->prev = prev;
+ n->next = NULL;
+ }
+ sorted_elements.release ();
+
+ return e;
+}
-/* Clear a bitmap by freeing the linked list. */
+/* Convert bitmap HEAD from splay-tree view to linked-list view. */
+
+void
+bitmap_list_view (bitmap head)
+{
+ bitmap_element *ptr;
+
+ head->tree_form = 0;
+ if (! head->first)
+ return;
+
+ ptr = head->first;
+ while (ptr->prev)
+ ptr = ptr->prev;
+ head->first = bitmap_tree_listify_from (head, ptr);
+
+ head->current = head->first;
+ head->indx = head->first->indx;
+}
+
+/* Convert bitmap HEAD from linked-list view to splay-tree view.
+ This is simply a matter of dropping the prev or next pointers
+ and setting the tree_form flag. The tree will balance itself
+ if and when it is used. */
+
+void
+bitmap_tree_view (bitmap head)
+{
+ bitmap_element *ptr;
+
+ head->tree_form = 1;
+ if (! head->first)
+ return;
+
+ ptr = head->first;
+ while (ptr)
+ {
+ ptr->prev = NULL;
+ ptr = ptr->next;
+ }
+ head->current = head->first;
+ head->indx = head->first->indx;
+}
+
+/* Clear a bitmap by freeing all its elements. */
void
bitmap_clear (bitmap head)
{
- if (head->first)
- bitmap_elt_clear_from (head, head->first);
+ if (head->first == NULL)
+ return;
+ if (head->tree_form)
+ {
+ bitmap_element *e, *t;
+ for (e = head->first; e->prev; e = e->prev)
+ /* Loop to find the element with the smallest index. */ ;
+ t = bitmap_tree_splay (head, head->first, e->indx);
+ gcc_checking_assert (t == e);
+ head->first = t;
+ }
+ bitmap_elt_clear_from (head, head->first);
}
/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
@@ -427,96 +868,6 @@ bitmap_element_zerop (const bitmap_eleme
#endif
}
-/* Link the bitmap element into the current bitmap linked list. */
-
-static inline void
-bitmap_element_link (bitmap head, bitmap_element *element)
-{
- unsigned int indx = element->indx;
- bitmap_element *ptr;
-
- /* If this is the first and only element, set it in. */
- if (head->first == 0)
- {
- element->next = element->prev = 0;
- head->first = element;
- }
-
- /* If this index is less than that of the current element, it goes someplace
- before the current element. */
- else if (indx < head->indx)
- {
- for (ptr = head->current;
- ptr->prev != 0 && ptr->prev->indx > indx;
- ptr = ptr->prev)
- ;
-
- if (ptr->prev)
- ptr->prev->next = element;
- else
- head->first = element;
-
- element->prev = ptr->prev;
- element->next = ptr;
- ptr->prev = element;
- }
-
- /* Otherwise, it must go someplace after the current element. */
- else
- {
- for (ptr = head->current;
- ptr->next != 0 && ptr->next->indx < indx;
- ptr = ptr->next)
- ;
-
- if (ptr->next)
- ptr->next->prev = element;
-
- element->next = ptr->next;
- element->prev = ptr;
- ptr->next = element;
- }
-
- /* Set up so this is the first element searched. */
- head->current = element;
- head->indx = indx;
-}
-
-/* Insert a new uninitialized element into bitmap HEAD after element
- ELT. If ELT is NULL, insert the element at the start. Return the
- new element. */
-
-static bitmap_element *
-bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
-{
- bitmap_element *node = bitmap_element_allocate (head);
- node->indx = indx;
-
- if (!elt)
- {
- if (!head->current)
- {
- head->current = node;
- head->indx = indx;
- }
- node->next = head->first;
- if (node->next)
- node->next->prev = node;
- head->first = node;
- node->prev = NULL;
- }
- else
- {
- gcc_checking_assert (head->current);
- node->next = elt->next;
- if (node->next)
- node->next->prev = node;
- elt->next = node;
- node->prev = elt;
- }
- return node;
-}
-
/* Copy a bitmap to another bitmap. */
void
@@ -525,6 +876,8 @@ bitmap_copy (bitmap to, const_bitmap fro
const bitmap_element *from_ptr;
bitmap_element *to_ptr = 0;
+ gcc_checking_assert (!to->tree_form && !from->tree_form);
+
bitmap_clear (to);
/* Copy elements in forward direction one at a time. */
@@ -535,8 +888,9 @@ bitmap_copy (bitmap to, const_bitmap fro
to_elt->indx = from_ptr->indx;
memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
- /* Here we have a special case of bitmap_element_link, for the case
- where we know the links are being entered in sequence. */
+ /* Here we have a special case of bitmap_list_link_element,
+ for the case where we know the links are being entered
+ in sequence. */
if (to_ptr == 0)
{
to->first = to->current = to_elt;
@@ -572,45 +926,10 @@ bitmap_find_bit (bitmap head, unsigned i
if (GATHER_STATISTICS)
bitmap_descriptors[head->descriptor_id]->nsearches++;
- if (head->indx < indx)
- /* INDX is beyond head->indx. Search from head->current
- forward. */
- for (element = head->current;
- element->next != 0 && element->indx < indx;
- element = element->next)
- {
- if (GATHER_STATISTICS)
- bitmap_descriptors[head->descriptor_id]->search_iter++;
- }
-
- else if (head->indx / 2 < indx)
- /* INDX is less than head->indx and closer to head->indx than to
- 0. Search from head->current backward. */
- for (element = head->current;
- element->prev != 0 && element->indx > indx;
- element = element->prev)
- {
- if (GATHER_STATISTICS)
- bitmap_descriptors[head->descriptor_id]->search_iter++;
- }
-
+ if (!head->tree_form)
+ element = bitmap_list_find_element (head, indx);
else
- /* INDX is less than head->indx and closer to 0 than to
- head->indx. Search from head->first forward. */
- for (element = head->first;
- element->next != 0 && element->indx < indx;
- element = element->next)
- if (GATHER_STATISTICS)
- {
- bitmap_descriptors[head->descriptor_id]->search_iter++;
- }
-
- /* `element' is the nearest to the one we want. If it's not the one we
- want, the one we want doesn't exist. */
- head->current = element;
- head->indx = element->indx;
- if (element != 0 && element->indx != indx)
- element = 0;
+ element = bitmap_tree_find_element (head, indx);
return element;
}
@@ -634,7 +953,12 @@ bitmap_clear_bit (bitmap head, int bit)
/* If we cleared the entire word, free up the element. */
if (!ptr->bits[word_num]
&& bitmap_element_zerop (ptr))
- bitmap_element_free (head, ptr);
+ {
+ if (!head->tree_form)
+ bitmap_list_unlink_element (head, ptr);
+ else
+ bitmap_tree_unlink_element (head, ptr);
+ }
}
return res;
@@ -653,21 +977,22 @@ bitmap_set_bit (bitmap head, int bit)
unsigned bit_num = bit % BITMAP_WORD_BITS;
BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
- if (ptr == 0)
- {
- ptr = bitmap_element_allocate (head);
- ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
- ptr->bits[word_num] = bit_val;
- bitmap_element_link (head, ptr);
- return true;
- }
- else
+ if (ptr != 0)
{
bool res = (ptr->bits[word_num] & bit_val) == 0;
if (res)
ptr->bits[word_num] |= bit_val;
return res;
}
+
+ ptr = bitmap_element_allocate (head);
+ ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
+ ptr->bits[word_num] = bit_val;
+ if (!head->tree_form)
+ bitmap_list_link_element (head, ptr);
+ else
+ bitmap_tree_link_element (head, ptr);
+ return true;
}
/* Return whether a bit is set within a bitmap. */
@@ -724,13 +1049,14 @@ bitmap_count_bits (const_bitmap a)
const bitmap_element *elt;
unsigned ix;
+ gcc_checking_assert (!a->tree_form);
for (elt = a->first; elt; elt = elt->next)
{
for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
{
#if GCC_VERSION >= 3400
- /* Note that popcountl matches BITMAP_WORD in type, so the actual size
- of BITMAP_WORD is not material. */
+ /* Note that popcountl matches BITMAP_WORD in type,
+ so the actual size of BITMAP_WORD is not material. */
count += __builtin_popcountl (elt->bits[ix]);
#else
count += bitmap_popcount (elt->bits[ix]);
@@ -754,9 +1080,11 @@ bitmap_single_bit_set_p (const_bitmap a)
return false;
elt = a->first;
+
/* As there are no completely empty bitmap elements, a second one
means we have more than one bit set. */
- if (elt->next != NULL)
+ if (elt->next != NULL
+ && (!a->tree_form || elt->prev != NULL))
return false;
for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
@@ -788,6 +1116,11 @@ bitmap_first_set_bit (const_bitmap a)
unsigned ix;
gcc_checking_assert (elt);
+
+ if (a->tree_form)
+ while (elt->prev)
+ elt = elt->prev;
+
bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
{
@@ -839,8 +1172,11 @@ bitmap_last_set_bit (const_bitmap a)
int ix;
gcc_checking_assert (elt);
+
+ /* This works for linked-list and binary tree representation alike. */
while (elt->next)
elt = elt->next;
+
bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
{
@@ -882,6 +1218,7 @@ bitmap_and (bitmap dst, const_bitmap a,
const bitmap_element *b_elt = b->first;
bitmap_element *dst_prev = NULL;
+ gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
gcc_assert (dst != a && dst != b);
if (a == b)
@@ -903,7 +1240,8 @@ bitmap_and (bitmap dst, const_bitmap a,
BITMAP_WORD ior = 0;
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+ a_elt->indx);
else
dst_elt->indx = a_elt->indx;
for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
@@ -940,6 +1278,8 @@ bitmap_and_into (bitmap a, const_bitmap
bitmap_element *next;
bool changed = false;
+ gcc_checking_assert (!a->tree_form && !b->tree_form);
+
if (a == b)
return false;
@@ -948,7 +1288,7 @@ bitmap_and_into (bitmap a, const_bitmap
if (a_elt->indx < b_elt->indx)
{
next = a_elt->next;
- bitmap_element_free (a, a_elt);
+ bitmap_list_unlink_element (a, a_elt);
a_elt = next;
changed = true;
}
@@ -970,7 +1310,7 @@ bitmap_and_into (bitmap a, const_bitmap
}
next = a_elt->next;
if (!ior)
- bitmap_element_free (a, a_elt);
+ bitmap_list_unlink_element (a, a_elt);
a_elt = next;
b_elt = b_elt->next;
}
@@ -1012,7 +1352,8 @@ bitmap_elt_copy (bitmap dst, bitmap_elem
{
changed = true;
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx);
+ dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+ src_elt->indx);
else
dst_elt->indx = src_elt->indx;
memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
@@ -1034,6 +1375,7 @@ bitmap_and_compl (bitmap dst, const_bitm
bitmap_element **dst_prev_pnext = &dst->first;
bool changed = false;
+ gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
gcc_assert (dst != a && dst != b);
if (a == b)
@@ -1082,7 +1424,8 @@ bitmap_and_compl (bitmap dst, const_bitm
bool new_element;
if (!dst_elt || dst_elt->indx > a_elt->indx)
{
- dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+ a_elt->indx);
new_element = true;
}
else
@@ -1104,7 +1447,7 @@ bitmap_and_compl (bitmap dst, const_bitm
else
{
changed |= !new_element;
- bitmap_element_free (dst, dst_elt);
+ bitmap_list_unlink_element (dst, dst_elt);
dst_elt = *dst_prev_pnext;
}
}
@@ -1145,6 +1488,8 @@ bitmap_and_compl_into (bitmap a, const_b
bitmap_element *next;
BITMAP_WORD changed = 0;
+ gcc_checking_assert (!a->tree_form && !b->tree_form);
+
if (a == b)
{
if (bitmap_empty_p (a))
@@ -1179,7 +1524,7 @@ bitmap_and_compl_into (bitmap a, const_b
}
next = a_elt->next;
if (!ior)
- bitmap_element_free (a, a_elt);
+ bitmap_list_unlink_element (a, a_elt);
a_elt = next;
b_elt = b_elt->next;
}
@@ -1197,6 +1542,8 @@ bitmap_set_range (bitmap head, unsigned
bitmap_element *elt, *elt_prev;
unsigned int i;
+ gcc_checking_assert (!head->tree_form);
+
if (!count)
return;
@@ -1213,7 +1560,7 @@ bitmap_set_range (bitmap head, unsigned
{
elt = bitmap_element_allocate (head);
elt->indx = first_index;
- bitmap_element_link (head, elt);
+ bitmap_list_link_element (head, elt);
}
gcc_checking_assert (elt->indx == first_index);
@@ -1230,7 +1577,7 @@ bitmap_set_range (bitmap head, unsigned
unsigned int ix;
if (!elt || elt->indx != i)
- elt = bitmap_elt_insert_after (head, elt_prev, i);
+ elt = bitmap_list_insert_element_after (head, elt_prev, i);
if (elt_start_bit <= start)
{
@@ -1296,6 +1643,8 @@ bitmap_clear_range (bitmap head, unsigne
unsigned int first_index, end_bit_plus1, last_index;
bitmap_element *elt;
+ gcc_checking_assert (!head->tree_form);
+
if (!count)
return;
@@ -1333,7 +1682,7 @@ bitmap_clear_range (bitmap head, unsigne
if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
/* Get rid of the entire elt and go to the next one. */
- bitmap_element_free (head, elt);
+ bitmap_list_unlink_element (head, elt);
else
{
/* Going to have to knock out some bits in this elt. */
@@ -1403,7 +1752,7 @@ bitmap_clear_range (bitmap head, unsigne
}
/* Check to see if there are any bits left. */
if (clear)
- bitmap_element_free (head, elt);
+ bitmap_list_unlink_element (head, elt);
}
elt = next_elt;
}
@@ -1425,6 +1774,7 @@ bitmap_compl_and_into (bitmap a, const_b
bitmap_element *a_prev = NULL;
bitmap_element *next;
+ gcc_checking_assert (!a->tree_form && !b->tree_form);
gcc_assert (a != b);
if (bitmap_empty_p (a))
@@ -1445,13 +1795,13 @@ bitmap_compl_and_into (bitmap a, const_b
/* A is before B. Remove A */
next = a_elt->next;
a_prev = a_elt->prev;
- bitmap_element_free (a, a_elt);
+ bitmap_list_unlink_element (a, a_elt);
a_elt = next;
}
else if (!a_elt || b_elt->indx < a_elt->indx)
{
/* B is before A. Copy B. */
- next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
+ next = bitmap_list_insert_element_after (a, a_prev, b_elt->indx);
memcpy (next->bits, b_elt->bits, sizeof (next->bits));
a_prev = next;
b_elt = b_elt->next;
@@ -1472,7 +1822,7 @@ bitmap_compl_and_into (bitmap a, const_b
}
next = a_elt->next;
if (!ior)
- bitmap_element_free (a, a_elt);
+ bitmap_list_unlink_element (a, a_elt);
else
a_prev = a_elt;
a_elt = next;
@@ -1517,7 +1867,8 @@ bitmap_elt_ior (bitmap dst, bitmap_eleme
{
changed = true;
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+ a_elt->indx);
else
dst_elt->indx = a_elt->indx;
for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
@@ -1556,6 +1907,7 @@ bitmap_ior (bitmap dst, const_bitmap a,
bitmap_element **dst_prev_pnext = &dst->first;
bool changed = false;
+ gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
gcc_assert (dst != a && dst != b);
while (a_elt || b_elt)
@@ -1602,6 +1954,7 @@ bitmap_ior_into (bitmap a, const_bitmap
bitmap_element **a_prev_pnext = &a->first;
bool changed = false;
+ gcc_checking_assert (!a->tree_form && !b->tree_form);
if (a == b)
return false;
@@ -1640,7 +1993,9 @@ bitmap_xor (bitmap dst, const_bitmap a,
const bitmap_element *b_elt = b->first;
bitmap_element *dst_prev = NULL;
+ gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
gcc_assert (dst != a && dst != b);
+
if (a == b)
{
bitmap_clear (dst);
@@ -1656,7 +2011,8 @@ bitmap_xor (bitmap dst, const_bitmap a,
BITMAP_WORD ior = 0;
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+ a_elt->indx);
else
dst_elt->indx = a_elt->indx;
for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
@@ -1691,7 +2047,8 @@ bitmap_xor (bitmap dst, const_bitmap a,
}
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
+ dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+ src->indx);
else
dst_elt->indx = src->indx;
memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
@@ -1716,6 +2073,8 @@ bitmap_xor_into (bitmap a, const_bitmap
const bitmap_element *b_elt = b->first;
bitmap_element *a_prev = NULL;
+ gcc_checking_assert (!a->tree_form && !b->tree_form);
+
if (a == b)
{
bitmap_clear (a);
@@ -1727,7 +2086,8 @@ bitmap_xor_into (bitmap a, const_bitmap
if (!a_elt || b_elt->indx < a_elt->indx)
{
/* Copy b_elt. */
- bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
+ bitmap_element *dst = bitmap_list_insert_element_after (a, a_prev,
+ b_elt->indx);
memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
a_prev = dst;
b_elt = b_elt->next;
@@ -1755,7 +2115,7 @@ bitmap_xor_into (bitmap a, const_bitmap
if (ior)
a_prev = a_elt;
else
- bitmap_element_free (a, a_elt);
+ bitmap_list_unlink_element (a, a_elt);
a_elt = next;
}
}
@@ -1775,6 +2135,8 @@ bitmap_equal_p (const_bitmap a, const_bi
const bitmap_element *b_elt;
unsigned ix;
+ gcc_checking_assert (!a->tree_form && !b->tree_form);
+
for (a_elt = a->first, b_elt = b->first;
a_elt && b_elt;
a_elt = a_elt->next, b_elt = b_elt->next)
@@ -1797,6 +2159,8 @@ bitmap_intersect_p (const_bitmap a, cons
const bitmap_element *b_elt;
unsigned ix;
+ gcc_checking_assert (!a->tree_form && !b->tree_form);
+
for (a_elt = a->first, b_elt = b->first;
a_elt && b_elt;)
{
@@ -1824,6 +2188,9 @@ bitmap_intersect_compl_p (const_bitmap a
const bitmap_element *a_elt;
const bitmap_element *b_elt;
unsigned ix;
+
+ gcc_checking_assert (!a->tree_form && !b->tree_form);
+
for (a_elt = a->first, b_elt = b->first;
a_elt && b_elt;)
{
@@ -1858,6 +2225,9 @@ bitmap_ior_and_compl (bitmap dst, const_
bitmap_element *dst_prev = NULL;
bitmap_element **dst_prev_pnext = &dst->first;
+ gcc_checking_assert (!dst->tree_form
+ && !a->tree_form && !b->tree_form
+ && !kill->tree_form);
gcc_assert (dst != a && dst != b && dst != kill);
/* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
@@ -1948,16 +2318,18 @@ bitmap_ior_and_compl (bitmap dst, const_
return changed;
}
-/* A |= (FROM1 & ~FROM2). Return true if A changes. */
+/* A |= (B & ~C). Return true if A changes. */
bool
-bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2)
+bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c)
{
bitmap_head tmp;
bool changed;
+ gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
+
bitmap_initialize (&tmp, &bitmap_default_obstack);
- bitmap_and_compl (&tmp, from1, from2);
+ bitmap_and_compl (&tmp, b, c);
changed = bitmap_ior_into (a, &tmp);
bitmap_clear (&tmp);
@@ -1978,6 +2350,8 @@ bitmap_ior_and_into (bitmap a, const_bit
bool changed = false;
unsigned ix;
+ gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
+
if (b == c)
return bitmap_ior_into (a, b);
if (bitmap_empty_p (b) || bitmap_empty_p (c))
@@ -2044,6 +2418,7 @@ bitmap_ior_and_into (bitmap a, const_bit
}
/* Compute hash of bitmap (for purposes of hashing). */
+
hashval_t
bitmap_hash (const_bitmap head)
{
@@ -2051,6 +2426,8 @@ bitmap_hash (const_bitmap head)
BITMAP_WORD hash = 0;
int ix;
+ gcc_checking_assert (!head->tree_form);
+
for (ptr = head->first; ptr; ptr = ptr->next)
{
hash ^= ptr->indx;
@@ -2064,9 +2441,13 @@ bitmap_hash (const_bitmap head)
/* Debugging function to print out the contents of a bitmap. */
DEBUG_FUNCTION void
-debug_bitmap_file (FILE *file, const_bitmap head)
+debug_bitmap_file (FILE *file, bitmap head)
{
const bitmap_element *ptr;
+ bool tree_form = head->tree_form;
+
+ if (tree_form)
+ bitmap_list_view (head);
fprintf (file, "\nfirst = " HOST_PTR_PRINTF
" current = " HOST_PTR_PRINTF " indx = %u\n",
@@ -2098,13 +2479,16 @@ debug_bitmap_file (FILE *file, const_bit
fprintf (file, " }\n");
}
+
+ if (tree_form)
+ bitmap_tree_view (head);
}
/* Function to be called from the debugger to print the contents
of a bitmap. */
DEBUG_FUNCTION void
-debug_bitmap (const_bitmap head)
+debug_bitmap (bitmap head)
{
debug_bitmap_file (stdout, head);
}
@@ -2113,11 +2497,15 @@ debug_bitmap (const_bitmap head)
it does not print anything but the bits. */
DEBUG_FUNCTION void
-bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix)
+bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
{
const char *comma = "";
unsigned i;
bitmap_iterator bi;
+ bool tree_form = head->tree_form;
+
+ if (tree_form)
+ bitmap_list_view (head);
fputs (prefix, file);
EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
@@ -2126,6 +2514,9 @@ bitmap_print (FILE *file, const_bitmap h
comma = ", ";
}
fputs (suffix, file);
+
+ if (tree_form)
+ bitmap_tree_view (head);
}
===================================================================
@@ -20,16 +20,21 @@ along with GCC; see the file COPYING3.
#ifndef GCC_BITMAP_H
#define GCC_BITMAP_H
-/* Implementation of sparse integer sets as a linked list.
+/* Implementation of sparse integer sets as a linked list or trees.
This sparse set representation is suitable for sparse sets with an
- unknown (a priori) universe. The set is represented as a double-linked
- list of container nodes (struct bitmap_element_def). Each node consists
- of an index for the first member that could be held in the container,
- a small array of integers that represent the members in the container,
- and pointers to the next and previous element in the linked list. The
- elements in the list are sorted in ascending order, i.e. the head of
+ unknown (a priori) universe.
+
+ Sets are represented as double-linked lists of container nodes of
+ type "struct bitmap_element_def" or as a binary trees of the same
+ container nodes. Each container node consists of an index for the
+ first member that could be held in the container, a small array of
+ integers that represent the members in the container, and pointers
+ to the next and previous element in the linked list, or left and
+ right children in the tree. In linked-list form, the container
+ nodes in the list are sorted in ascending order, i.e. the head of
the list holds the element with the smallest member of the set.
+ In tree form, nodes to the left have a smaller container index.
For a given member I in the set:
- the element for I will have index is I / (bits per element)
@@ -42,17 +47,67 @@ along with GCC; see the file COPYING3.
high storage overhead *per element*, but a small overall overhead if
the set is very sparse.
- The downside is that many operations are relatively slow because the
- linked list has to be traversed to test membership (i.e. member_p/
- add_member/remove_member). To improve the performance of this set
- representation, the last accessed element and its index are cached.
- For membership tests on members close to recently accessed members,
- the cached last element improves membership test to a constant-time
- operation.
+ The storage requirements for linked-list sparse sets are O(E), with E->N
+ in the worst case (a sparse set with large distances between the values
+ of the set members).
+
+ This representation also works well for data flow problems where the size
+ of the set may grow dynamically, but care must be taken that the member_p,
+ add_member, and remove_member operations occur with a suitable access
+ pattern.
+
+ The linked-list set representation works well for problems involving very
+ sparse sets. The canonical example in GCC is, of course, the "set of
+ sets" for some CFG-based data flow problems (liveness analysis, dominance
+ frontiers, etc.).
+
+ For random-access sparse sets of unknown universe, the binary tree
+ representation is likely to be a more suitable choice. Theoretical
+ access times for the binary tree representation are better than those
+ for the linked-list, but in practice this is only true for truely
+ random access.
+
+ Often the most suitable representation during construction of the set
+ is not the best choice for the usage of the set. For such cases, the
+ "view" of the set can be changed from one representation to the other.
+ This is an O(E) operation.
+
+ TODO: Document bitmap view changes! -- STEVEN
+
+ Traversing linked lists or trees can be cache-unfriendly. Performance
+ can be improved by keeping container nodes in the set grouped together
+ in memory, using a dedicated obstack for a set (or group of related
+ sets). Elements allocated on obstacks are released to a free-list and
+ taken off the free list. If multiple sets are allocated on the same
+ obstack, elements freed from one set may be re-used for one of the other
+ sets. This usually helps avoid cache misses.
+
+ A single free-list is used for all sets allocated in GGC space. This is
+ bad for persistent sets, so persistent sets should be allocated on an
+ obstack whenever possible.
+
+ For random-access sets with a known, relatively small universe size, the
+ SparseSet or simple bitmap representations may be more efficient than a
+ linked-list set.
+
+
+ LINKED LIST FORM
+ ================
+
+ In linked-list form, in-order iterations of the set can be executed
+ efficiently. The downside is that many random-access operations are
+ relatively slow, because the linked list has to be traversed to test
+ membership (i.e. member_p/ add_member/remove_member).
+
+ To improve the performance of this set representation, the last
+ accessed element and its index are cached. For membership tests on
+ members close to recently accessed members, the cached last element
+ improves membership test to a constant-time operation.
The following operations can always be performed in O(1) time:
* clear : bitmap_clear
+ * smallest_member : bitmap_first_set_bit
* choose_one : (not implemented, but could be
implemented in constant time)
@@ -61,15 +116,16 @@ along with GCC; see the file COPYING3.
suitable access patterns:
* member_p : bitmap_bit_p
- * add_member : bitmap_set_bit
- * remove_member : bitmap_clear_bit
+ * add_member : bitmap_set_bit / bitmap_set_range
+ * remove_member : bitmap_clear_bit / bitmap_clear_range
The following operations can be performed in O(E) time:
* cardinality : bitmap_count_bits
- * set_size : bitmap_last_set_bit (but this could
+ * largest_member : bitmap_last_set_bit (but this could
in constant time with a pointer to
the last element in the chain)
+ * set_size : bitmap_last_set_bit
Additionally, the linked-list sparse set representation supports
enumeration of the members in O(E) time:
@@ -93,39 +149,53 @@ along with GCC; see the file COPYING3.
* A | (B & ~C) : bitmap_ior_and_compl /
bitmap_ior_and_compl_into
- The storage requirements for linked-list sparse sets are O(E), with E->N
- in the worst case (a sparse set with large distances between the values
- of the set members).
- The linked-list set representation works well for problems involving very
- sparse sets. The canonical example in GCC is, of course, the "set of
- sets" for some CFG-based data flow problems (liveness analysis, dominance
- frontiers, etc.).
-
- This representation also works well for data flow problems where the size
- of the set may grow dynamically, but care must be taken that the member_p,
- add_member, and remove_member operations occur with a suitable access
- pattern.
+ BINARY TREE FORM
+ ================
+ An alternate "view" of a bitmap is its binary tree representation.
+ For this representation, splay trees are used because they can be
+ implemented using the same data structures as the linked list, with
+ no overhead for meta-data (like color, or rank) on the tree nodes.
+
+ In binary tree form, random-access to the set is much more efficient
+ than for the linked-list representation. Downsides are the high cost
+ of clearing the set, and the relatively large number of operations
+ necessary to balance the tree. Also, iterating the set members is
+ not supported.
- For random-access sets with a known, relatively small universe size, the
- SparseSet or simple bitmap representations may be more efficient than a
- linked-list set. For random-access sets of unknown universe, a hash table
- or a balanced binary tree representation is likely to be a more suitable
- choice.
+ As for the linked-list representation, the last accessed element and
+ its index are cached, so that membership tests on the latest accessed
+ members is a constant-time operation. Other lookups take O(logE)
+ time amortized (but O(E) time worst-case).
- Traversing linked lists is usually cache-unfriendly, even with the last
- accessed element cached.
-
- Cache performance can be improved by keeping the elements in the set
- grouped together in memory, using a dedicated obstack for a set (or group
- of related sets). Elements allocated on obstacks are released to a
- free-list and taken off the free list. If multiple sets are allocated on
- the same obstack, elements freed from one set may be re-used for one of
- the other sets. This usually helps avoid cache misses.
+ The following operations can always be performed in O(1) time:
- A single free-list is used for all sets allocated in GGC space. This is
- bad for persistent sets, so persistent sets should be allocated on an
- obstack whenever possible. */
+ * choose_one : (not implemented, but could be
+ implemented in constant time)
+
+ The following operations can be performed in O(logE) time amortized
+ but O(E) time worst-case, but in O(1) time if the same element is
+ accessed.
+
+ * member_p : bitmap_bit_p
+ * add_member : bitmap_set_bit
+ * remove_member : bitmap_clear_bit
+
+ The following operations can be performed in O(logE) time amortized
+ but O(E) time worst-case:
+
+ * smallest_member : bitmap_first_set_bit
+ * largest_member : bitmap_last_set_bit
+ * set_size : bitmap_last_set_bit
+
+ The following operations can be performed in O(E) time:
+
+ * clear : bitmap_clear
+
+ The binary tree sparse set representation does *not* support any form
+ of enumeration, and does also *not* support logical operations on sets.
+ The binary tree representation is only supposed to be used for sets
+ on which many random-access membership tests will happen. */
#include "hashtab.h"
#include "statistics.h"
@@ -168,24 +238,46 @@ typedef struct GTY (()) bitmap_obstack {
linear in the number of elements to be freed. */
typedef struct GTY((chain_next ("%h.next"), chain_prev ("%h.prev"))) bitmap_element_def {
- struct bitmap_element_def *next; /* Next element. */
- struct bitmap_element_def *prev; /* Previous element. */
- unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */
- BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */
+ /* In list form, the next element in the linked list;
+ in tree form, the left child node in the tree. */
+ struct bitmap_element_def *next;
+
+ /* In list form, the previous element in the linked list;
+ in tree form, the right child node in the tree. */
+ struct bitmap_element_def *prev;
+
+ /* regno/BITMAP_ELEMENT_ALL_BITS. */
+ unsigned int indx;
+
+ /* Bits that are set, counting from INDX, inclusive. */
+ BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
} bitmap_element;
/* Head of bitmap linked list. The 'current' member points to something
already pointed to by the chain started by first, so GTY((skip)) it. */
typedef struct GTY(()) bitmap_head_def {
- unsigned int indx; /* Index of last element looked at. */
- unsigned int descriptor_id; /* Unique identifier for the allocation
- site of this bitmap, for detailed
- statistics gathering. */
- bitmap_element *first; /* First element in linked list. */
- bitmap_element * GTY((skip(""))) current; /* Last element looked at. */
- bitmap_obstack *obstack; /* Obstack to allocate elements from.
- If NULL, then use GGC allocation. */
+ /* Index of last element looked at. */
+ unsigned int indx;
+
+ /* Unique identifier for the allocation site of this bitmap,
+ for detailed statistics gathering. */
+ unsigned int descriptor_id : 31;
+
+ /* 0 if the bitmap is in list form; 1 if the bitmap is in tree form.
+ Bitmap iterators only work on bitmaps in list form. */
+ unsigned int tree_form : 1;
+
+ /* In list form, the first element in the linked list;
+ in tree form, The root of the tree. */
+ bitmap_element *first;
+
+ /* Last element looked at. */
+ bitmap_element * GTY((skip(""))) current;
+
+ /* Obstack to allocate elements from.
+ If NULL, then use GGC allocation. */
+ bitmap_obstack *obstack;
} bitmap_head;
/* Global data */
@@ -252,15 +344,15 @@ extern bool bitmap_clear_bit (bitmap, in
/* Set a single bit in a bitmap. Return true if the bit changed. */
extern bool bitmap_set_bit (bitmap, int);
-/* Return true if a register is set in a register set. */
+/* Return true if a bit is set in a bitmap. */
extern int bitmap_bit_p (bitmap, int);
-/* Debug functions to print a bitmap linked list. */
-extern void debug_bitmap (const_bitmap);
-extern void debug_bitmap_file (FILE *, const_bitmap);
+/* Debug functions to print a bitmap. */
+extern void debug_bitmap (bitmap);
+extern void debug_bitmap_file (FILE *, bitmap);
/* Print a bitmap. */
-extern void bitmap_print (FILE *, const_bitmap, const char *, const char *);
+extern void bitmap_print (FILE *, bitmap, const char *, const char *);
/* Initialize and release a bitmap obstack. */
extern void bitmap_obstack_initialize (bitmap_obstack *);
@@ -275,6 +367,7 @@ static inline void
bitmap_initialize_stat (bitmap head, bitmap_obstack *obstack MEM_STAT_DECL)
{
head->first = head->current = NULL;
+ head->indx = head->tree_form = 0;
head->obstack = obstack;
if (GATHER_STATISTICS)
bitmap_register (head PASS_MEM_STAT);
@@ -289,7 +382,7 @@ extern bitmap bitmap_gc_alloc_stat (ALON
extern void bitmap_obstack_free (bitmap);
/* A few compatibility/functions macros for compatibility with sbitmaps */
-inline void dump_bitmap (FILE *file, const_bitmap map)
+inline void dump_bitmap (FILE *file, bitmap map)
{
bitmap_print (file, map, "", "\n");
}
@@ -310,7 +403,9 @@ extern hashval_t bitmap_hash(const_bitma
#define BITMAP_FREE(BITMAP) \
((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL))
-/* Iterator for bitmaps. */
+/* Iterator for bitmaps.
+ TODO: These iterators only work on bitmaps in list form.
+ Having them working for tree bitmaps also would be nice. */
typedef struct
{
@@ -339,6 +434,8 @@ bmp_iter_set_init (bitmap_iterator *bi,
bi->elt1 = map->first;
bi->elt2 = NULL;
+ gcc_checking_assert (!map->tree_form);
+
/* Advance elt1 until it is not before the block containing start_bit. */
while (1)
{
@@ -381,6 +478,8 @@ bmp_iter_and_init (bitmap_iterator *bi,
bi->elt1 = map1->first;
bi->elt2 = map2->first;
+ gcc_checking_assert (!map1->tree_form && !map2->tree_form);
+
/* Advance elt1 until it is not before the block containing
start_bit. */
while (1)
@@ -439,8 +538,7 @@ bmp_iter_and_init (bitmap_iterator *bi,
*bit_no = start_bit;
}
-/* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.
- */
+/* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. */
static inline void
bmp_iter_and_compl_init (bitmap_iterator *bi,
@@ -450,6 +548,8 @@ bmp_iter_and_compl_init (bitmap_iterator
bi->elt1 = map1->first;
bi->elt2 = map2->first;
+ gcc_checking_assert (!map1->tree_form && !map2->tree_form);
+
/* Advance elt1 until it is not before the block containing start_bit. */
while (1)
{
===================================================================
@@ -1239,6 +1239,8 @@ find_subregs_of_mode (rtx x, bitmap subr
}
}
+extern void bitmap_tree_view (bitmap);
+
void
init_subregs_of_mode (void)
{
@@ -1251,6 +1253,8 @@ init_subregs_of_mode (void)
invalid_mode_changes = BITMAP_ALLOC (NULL);
bitmap_obstack_initialize (&srom_obstack);
subregs_of_mode = BITMAP_ALLOC (&srom_obstack);
+ bitmap_tree_view (invalid_mode_changes);
+ bitmap_tree_view (subregs_of_mode);
FOR_EACH_BB (bb)
FOR_BB_INSNS (bb, insn)