* bitmap.h: Update data structure documentation, including a description of bitmap views as either linked-lists or splay trees. (struct bitmap_element_def): Update comments for splay tree bitmaps. (struct bitmap_head_def): Likewise. (bitmap_list_view, bitmap_tree_view): New prototypes. (debug_bitmap, debug_bitmap_file, bitmap_print): Update prototypes. (dump_bitmap): Update to take non-const bitmap. (bitmap_initialize_stat): Initialize a bitmap_head's indx and tree_form fields. (bmp_iter_set_init): Assert the iterated bitmaps are in list form. (bmp_iter_and_init, bmp_iter_and_compl_init): Likewise. * bitmap.c (next_bitmap_desc_id): Make unsigned. (get_bitmap_descriptor): Make sure there are no more than 2^31 bitmap descriptors. (bitmap_elem_to_freelist): Unregister overhead of a released bitmap element here. (bitmap_element_free): Remove. (bitmap_elt_clear_from): Work on splay tree bitmaps. (bitmap_list_link_element): Renamed from bitmap_element_link. Move this function similar ones such that linked-list bitmap implementation functions are grouped. (bitmap_list_unlink_element): Renamed from bitmap_element_unlink, and moved for grouping. (bitmap_list_insert_element_after): Renamed from bitmap_elt_insert_after, and moved for grouping. (bitmap_list_find_element): New function spliced from bitmap_find_bit. (bitmap_tree_link_left, bitmap_tree_link_right, bitmap_tree_rotate_left, bitmap_tree_rotate_right, bitmap_tree_splay, bitmap_tree_link_element, bitmap_tree_unlink_element, bitmap_tree_find_element): New functions for splay-tree bitmap implementation. (bitmap_element_link, bitmap_element_unlink, bitmap_elt_insert_after): Renamed and moved, see above entries. (bitmap_tree_listify_from): New function to convert part of a splay tree bitmap to a linked-list bitmap. (bitmap_list_view): Convert a splay tree bitmap to linked-list form. (bitmap_tree_view): Convert a linked-list bitmap to splay tree form. (bitmap_find_bit, bitmap_clear, bitmap_clear_bit, bitmap_set_bit, bitmap_single_bit_set_p, bitmap_first_set_bit, bitmap_last_set_bit): Handle splay tree bitmaps. (bitmap_copy, bitmap_count_bits, bitmap_and, bitmap_and_into, bitmap_elt_copy, bitmap_and_compl, bitmap_and_compl_into, bitmap_compl_and_into, bitmap_elt_ior, bitmap_ior, bitmap_ior_into, bitmap_xor, bitmap_xor_into, bitmap_equal_p, bitmap_intersect_p, bitmap_intersect_compl_p, bitmap_ior_and_compl, bitmap_ior_and_compl_into, bitmap_set_range, bitmap_clear_range, bitmap_hash): Reject trying to act on splay tree bitmaps. Make corresponding changes to use linked-list specific bitmap_element manipulation functions as applicable for efficiency. (debug_bitmap_file): Handle splay tree bitmaps by converting the bitmap to linked-list form and back. (bitmap_print): Likewise. (debug_bitmap): Take a non-const bitmap. * reginfo.c (init_subregs_of_mode): View invalid_mode_changes and subregs_of_mode bitmaps as splay tree bitmaps. Index: bitmap.h =================================================================== --- bitmap.h (revision 196410) +++ bitmap.h (working copy) @@ -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,68 @@ 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: + + * from list to tree view : bitmap_tree_view + * from tree to list view : bitmap_list_view + + 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 +117,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 +150,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.). + 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. - 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. - - 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,31 +239,57 @@ 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 */ extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */ -/* Clear a bitmap by freeing up the linked list. */ +/* Change the view of the bitmap to list, or tree. */ +void bitmap_list_view (bitmap); +void bitmap_tree_view (bitmap); + +/* Clear a bitmap by freeing up the elements. */ extern void bitmap_clear (bitmap); /* Copy a bitmap to another bitmap. */ @@ -252,15 +349,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 +372,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 +387,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"); } @@ -339,6 +437,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 +481,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 +541,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 +551,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) { Index: bitmap.c =================================================================== --- bitmap.c (revision 196410) +++ bitmap.c (working copy) @@ -44,8 +44,10 @@ 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; +static unsigned int next_bitmap_desc_id = 0; /* Vector mapping descriptor ids to descriptors. */ static vec bitmap_descriptors; @@ -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 < ((unsigned) 1 << 31) - 1); + *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 stack = vNULL; + vec 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); } Index: reginfo.c =================================================================== --- reginfo.c (revision 196410) +++ reginfo.c (working copy) @@ -1251,6 +1251,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)