* [patch][RFC] bitmaps as lists *or* trees
@ 2013-03-05 12:01 Steven Bosscher
2013-03-05 12:32 ` Richard Biener
0 siblings, 1 reply; 15+ messages in thread
From: Steven Bosscher @ 2013-03-05 12:01 UTC (permalink / raw)
To: GCC Patches; +Cc: Michael Matz, Richard Biener, Jeff Law
[-- Attachment #1: Type: text/plain, Size: 1449 bytes --]
Hello,
A recurring problem with GCC's sparse bitmap data structure is that it
performs poorly for random access patterns. Such patterns result in
linked-list walks, and can trigger behavior quadratic in the number of
linked-list member elements in the set.
The attached patch is a first stab at an idea I've had for a while:
Implement a "change of view" for bitmaps, such that a bitmap can be
either a linked list, or a binary tree. I've implemented this idea
with top-down splay trees because splay tree nodes do not need
meta-data on (unlike e.g. color for RB-trees, rank for AVL trees,
etc.) and top-down splay tree operations are very simple to implement
(less than 200 lines of code). As far as I'm aware, this is the first
attempt at allowing different views on bitmaps. The idea came from
Andrew Macleod's tree-ssa-live implementation.
The idea is to convert the bitmap to a tree view if the set
represented by the bitmap is mostly used for membership testing, and
not for iterations over the items (as e.g. for bitmap dataflow). A
typical example of this is e.g. invalid_mode_changes, which just
explodes for the test case of PR55135 at -O0.
I haven't tested this patch at all, except making sure that it
compiles. Just posting this for discussion, and for feedback on the
idea. I know there have been many others before me who've tried
different data structures for bitmaps, perhaps someone has already
tried this before.
Ciao!
Steven
[-- Attachment #2: tbitmap.diff.txt --]
[-- Type: text/plain, Size: 50722 bytes --]
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,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)
{
Index: bitmap.c
===================================================================
--- bitmap.c (revision 196410)
+++ bitmap.c (working copy)
@@ -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);
\f
+/* 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);
-}
-\f
/* 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,12 +269,453 @@ bitmap_elt_clear_from (bitmap head, bitm
bitmap_ggc_free = elt;
}
}
+\f
+/* 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. */
+ head->current = element;
+ head->indx = element->indx;
+ if (element != 0 && element->indx != indx)
+ element = 0;
+ return element;
+}
+
+\f
+/* 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;
+}
-/* Clear a bitmap by freeing the linked list. */
+/* 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;
+}
+
+/* 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 *e= bitmap_tree_splay (head, head->first, indx);
+ head->first = e;
+ if (e->indx == indx)
+ {
+ head->current = e;
+ head->indx = e->indx;
+ }
+ return e;
+}
+\f
+/* 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 = bitmap_tree_splay (head, head->first, e->indx);
+ gcc_checking_assert (t == e);
+
+ t = t->prev;
+ head->first = t;
+ head->current = t;
+ head->indx = (t != NULL) ? t->indx : 0;
+
+ /* 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;
+}
+
+/* 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;
+}
+\f
+/* Clear a bitmap by freeing all its elements. */
void
bitmap_clear (bitmap head)
{
+//listify the tree if head is in tree form
if (head->first)
bitmap_elt_clear_from (head, head->first);
}
@@ -427,96 +841,6 @@ bitmap_element_zerop (const bitmap_eleme
#endif
}
\f
-/* 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;
-}
-\f
/* Copy a bitmap to another bitmap. */
void
@@ -525,6 +849,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 +861,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 +899,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 +926,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 +950,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 +1022,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 +1053,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 +1089,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 +1145,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 +1191,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 +1213,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 +1251,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 +1261,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 +1283,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 +1325,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 +1348,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 +1397,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 +1420,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 +1461,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 +1497,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 +1515,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 +1533,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 +1550,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 +1616,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 +1655,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 +1725,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 +1747,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 +1768,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 +1795,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 +1840,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 +1880,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 +1927,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 +1966,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 +1984,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 +2020,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 +2046,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 +2059,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 +2088,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 +2108,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 +2132,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 +2161,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 +2198,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 +2291,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 +2323,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 +2391,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 +2399,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 +2414,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 +2452,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 +2470,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 +2487,9 @@ bitmap_print (FILE *file, const_bitmap h
comma = ", ";
}
fputs (suffix, file);
+
+ if (tree_form)
+ bitmap_tree_view (head);
}
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-05 12:01 [patch][RFC] bitmaps as lists *or* trees Steven Bosscher
@ 2013-03-05 12:32 ` Richard Biener
2013-03-05 14:48 ` Michael Matz
2013-03-05 14:51 ` Steven Bosscher
0 siblings, 2 replies; 15+ messages in thread
From: Richard Biener @ 2013-03-05 12:32 UTC (permalink / raw)
To: Steven Bosscher; +Cc: GCC Patches, Michael Matz, Jeff Law
On Tue, Mar 5, 2013 at 1:00 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> Hello,
>
> A recurring problem with GCC's sparse bitmap data structure is that it
> performs poorly for random access patterns. Such patterns result in
> linked-list walks, and can trigger behavior quadratic in the number of
> linked-list member elements in the set.
>
> The attached patch is a first stab at an idea I've had for a while:
> Implement a "change of view" for bitmaps, such that a bitmap can be
> either a linked list, or a binary tree. I've implemented this idea
> with top-down splay trees because splay tree nodes do not need
> meta-data on (unlike e.g. color for RB-trees, rank for AVL trees,
> etc.) and top-down splay tree operations are very simple to implement
> (less than 200 lines of code). As far as I'm aware, this is the first
> attempt at allowing different views on bitmaps. The idea came from
> Andrew Macleod's tree-ssa-live implementation.
>
> The idea is to convert the bitmap to a tree view if the set
> represented by the bitmap is mostly used for membership testing, and
> not for iterations over the items (as e.g. for bitmap dataflow). A
> typical example of this is e.g. invalid_mode_changes, which just
> explodes for the test case of PR55135 at -O0.
>
> I haven't tested this patch at all, except making sure that it
> compiles. Just posting this for discussion, and for feedback on the
> idea. I know there have been many others before me who've tried
> different data structures for bitmaps, perhaps someone has already
> tried this before.
Definitely a nice idea. Iteration should be easy to implement (without
actually splaying for each visited bit), the bit operations can use the
iteration as building block as well then.
Now, an instrumented bitmap to identify bitmaps that would benefit
from the tree view would be nice ;) [points-to sets are never modified
after being computed, but they are both random-tested and intersected]
What I missed often as well is a reference counted shared bitmap
implementation (we have various special case implementations).
I wonder if that could even use shared sub-trees/lists of bitmap_elts.
Richard.
> Ciao!
> Steven
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-05 12:32 ` Richard Biener
@ 2013-03-05 14:48 ` Michael Matz
2013-03-05 16:17 ` Steven Bosscher
2013-03-05 14:51 ` Steven Bosscher
1 sibling, 1 reply; 15+ messages in thread
From: Michael Matz @ 2013-03-05 14:48 UTC (permalink / raw)
To: Richard Biener; +Cc: Steven Bosscher, GCC Patches, Jeff Law
Hi,
On Tue, 5 Mar 2013, Richard Biener wrote:
> > I haven't tested this patch at all, except making sure that it
> > compiles. Just posting this for discussion, and for feedback on the
> > idea. I know there have been many others before me who've tried
> > different data structures for bitmaps, perhaps someone has already
> > tried this before.
>
> Definitely a nice idea. Iteration should be easy to implement (without
> actually splaying for each visited bit), the bit operations can use the
> iteration as building block as well then.
Iteration isn't easy on trees without a pointer to the parent (i.e.
enlarging each node), you need to remember variably sized context in the
iterator (e.g. the current stack of nodes).
I do like the idea of reusing the same internal data structure to
implement the tree. And I'm wondering about performance impact, I
wouldn't be surprised either way (i.e. that it brings about a large
improvement, or none at all), most bitmap membership tests in GCC are
surprisingly clustered so that the bitmaps cache of last accessed
element can work its magic (not all of them, as the testcase shows of
course :) ).
Ciao,
Michael.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-05 12:32 ` Richard Biener
2013-03-05 14:48 ` Michael Matz
@ 2013-03-05 14:51 ` Steven Bosscher
2013-03-05 16:03 ` Richard Biener
1 sibling, 1 reply; 15+ messages in thread
From: Steven Bosscher @ 2013-03-05 14:51 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Patches, Michael Matz, Jeff Law
On Tue, Mar 5, 2013 at 1:32 PM, Richard Biener wrote:
>> The attached patch is a first stab at an idea I've had for a while:
>> Implement a "change of view" for bitmaps, such that a bitmap can be
>> either a linked list, or a binary tree.
...
> Definitely a nice idea. Iteration should be easy to implement (without
> actually splaying for each visited bit), the bit operations can use the
> iteration as building block as well then.
It is really easy, you only have to "listify" the splay tree such that
the root is the element with the lowest index. AFAICT the iterators
only look at the "next" member of each bitmap_element, and a list is
also a valid splay tree.
> Now, an instrumented bitmap to identify bitmaps that would benefit
> from the tree view would be nice ;) [points-to sets are never modified
> after being computed, but they are both random-tested and intersected]
I have no idea how to create that kind of instrumentation.
> What I missed often as well is a reference counted shared bitmap
> implementation (we have various special case implementations).
> I wonder if that could even use shared sub-trees/lists of bitmap_elts.
And this idea, I don't even understand :-)
"reference counted shared bitmaps" as in, the same bitmap element
shared between different bitmaps? How would you link such elements
together in a tree or a list? It could be done with array bitmaps, but
those have other downsides (insert/delete is near impossible without a
lot of mem-moving around).
Ciao!
Steven
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-05 14:51 ` Steven Bosscher
@ 2013-03-05 16:03 ` Richard Biener
0 siblings, 0 replies; 15+ messages in thread
From: Richard Biener @ 2013-03-05 16:03 UTC (permalink / raw)
To: Steven Bosscher; +Cc: GCC Patches, Michael Matz, Jeff Law
On Tue, Mar 5, 2013 at 3:50 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Tue, Mar 5, 2013 at 1:32 PM, Richard Biener wrote:
>>> The attached patch is a first stab at an idea I've had for a while:
>>> Implement a "change of view" for bitmaps, such that a bitmap can be
>>> either a linked list, or a binary tree.
> ...
>> Definitely a nice idea. Iteration should be easy to implement (without
>> actually splaying for each visited bit), the bit operations can use the
>> iteration as building block as well then.
>
> It is really easy, you only have to "listify" the splay tree such that
> the root is the element with the lowest index. AFAICT the iterators
> only look at the "next" member of each bitmap_element, and a list is
> also a valid splay tree.
You'd have a "fat" iterator object with a (sorted) array of bitmap elements to
iterate over, similar to how loop iterators work.
>> Now, an instrumented bitmap to identify bitmaps that would benefit
>> from the tree view would be nice ;) [points-to sets are never modified
>> after being computed, but they are both random-tested and intersected]
>
> I have no idea how to create that kind of instrumentation.
>
>> What I missed often as well is a reference counted shared bitmap
>> implementation (we have various special case implementations).
>> I wonder if that could even use shared sub-trees/lists of bitmap_elts.
>
> And this idea, I don't even understand :-)
> "reference counted shared bitmaps" as in, the same bitmap element
> shared between different bitmaps? How would you link such elements
> together in a tree or a list? It could be done with array bitmaps, but
> those have other downsides (insert/delete is near impossible without a
> lot of mem-moving around).
You can share "leafs" of trees (not of lists due to the back pointer),
splaying of course destroys the shared properties ...
At the moment shared bitmaps (where used) are simply using hashtables
and bitmap_hash. The propagation parts of the points-to solver could
benefit from copy-on-write shared bitmaps.
Richard.
> Ciao!
> Steven
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-05 14:48 ` Michael Matz
@ 2013-03-05 16:17 ` Steven Bosscher
2013-03-05 22:56 ` Steven Bosscher
` (2 more replies)
0 siblings, 3 replies; 15+ messages in thread
From: Steven Bosscher @ 2013-03-05 16:17 UTC (permalink / raw)
To: Michael Matz; +Cc: Richard Biener, GCC Patches, Jeff Law
[-- Attachment #1: Type: text/plain, Size: 2308 bytes --]
On Tue, Mar 5, 2013 at 3:48 PM, Michael Matz wrote:
> Iteration isn't easy on trees without a pointer to the parent (i.e.
> enlarging each node), you need to remember variably sized context in the
> iterator (e.g. the current stack of nodes).
I was thinking of just making the "tree" a single forward-linked list,
that's a valid splay tree and one that is compatible with the
iterators, at least as long as the iterated bitmap are not modified
(but I think that isn't allowed anyway?). Obviously the tree is not
very well balanced after that, but splay trees have a way of
re-balancing themselves quickly. The other possibility is to create
vecs of bitmap_elements up front, but such iterators (fat iterators,
as Richi just now called them in another mail :-) have the downside
that you must always visit all bitmap elements, even if you want to be
able to break the iteration before reaching the end.
> I do like the idea of reusing the same internal data structure to
> implement the tree. And I'm wondering about performance impact, I
> wouldn't be surprised either way (i.e. that it brings about a large
> improvement, or none at all), most bitmap membership tests in GCC are
> surprisingly clustered so that the bitmaps cache of last accessed
> element can work its magic (not all of them, as the testcase shows of
> course :) ).
I've retained the cached last accessed element. In fact it's now
cached twice, because the root of the splay tree is always the last
accessed element. I've considered *not* updating bitmap->current if
bitmap_tree_find_element doesn't find the element it's looking for.
That way, the last accessed element would be the element that was
*really* last accessed, i.e. with a valid membership test, instead of
the element closest to the last tested bit. Not sure if that'd be a
good idea.
Anyway, updated patch attached. It compiles all my cc1-i files, and
it compiles the PR55135 test case, in 410s (I terminated cc1plus
unpatched after >7200s, more than 2 hours...).
An interesting question is, how can you identify bitmaps that could
benefit from viewing it as a tree (at least for some time). I have no
ideas here. Something with detailed memory stats, of course, but then
how to derive some measure for a trade-off between list or tree view.
Thoughts?
Ciao!
Steven
[-- Attachment #2: tbitmap.diff.txt --]
[-- Type: text/plain, Size: 52248 bytes --]
Index: bitmap.c
===================================================================
--- bitmap.c (revision 196410)
+++ bitmap.c (working copy)
@@ -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);
\f
+/* 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);
-}
-\f
/* 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;
}
}
+\f
+/* 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;
+}
+
+\f
+/* 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;
+}
+\f
+/* 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;
+}
+\f
+/* 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);
}
\f
/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
@@ -427,96 +868,6 @@ bitmap_element_zerop (const bitmap_eleme
#endif
}
\f
-/* 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;
-}
-\f
/* 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: 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,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)
{
Index: reginfo.c
===================================================================
--- reginfo.c (revision 196410)
+++ reginfo.c (working copy)
@@ -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)
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-05 16:17 ` Steven Bosscher
@ 2013-03-05 22:56 ` Steven Bosscher
2013-03-07 20:18 ` Steven Bosscher
2013-03-06 10:18 ` Richard Biener
2013-03-06 16:02 ` Jan Hubicka
2 siblings, 1 reply; 15+ messages in thread
From: Steven Bosscher @ 2013-03-05 22:56 UTC (permalink / raw)
To: Michael Matz; +Cc: Richard Biener, GCC Patches, Jeff Law
[-- Attachment #1: Type: text/plain, Size: 360 bytes --]
On Tue, Mar 5, 2013 at 5:16 PM, Steven Bosscher wrote:
> Anyway, updated patch attached. It compiles all my cc1-i files, and
> it compiles the PR55135 test case, in 410s (I terminated cc1plus
> unpatched after >7200s, more than 2 hours...).
Attached is a version that passes bootstrap&testing on
x86_64-unknown-linux-gnu. and with a ChangeLog.
Ciao!
Steven
[-- Attachment #2: tbitmap.diff.txt --]
[-- Type: text/plain, Size: 55322 bytes --]
* 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_descriptor> 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);
\f
+/* 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);
-}
-\f
/* 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;
}
}
+\f
+/* 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;
+}
+
+\f
+/* 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;
+}
+\f
+/* 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;
+}
+\f
+/* 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);
}
\f
/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
@@ -427,96 +868,6 @@ bitmap_element_zerop (const bitmap_eleme
#endif
}
\f
-/* 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;
-}
-\f
/* 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)
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-05 16:17 ` Steven Bosscher
2013-03-05 22:56 ` Steven Bosscher
@ 2013-03-06 10:18 ` Richard Biener
2013-03-06 16:02 ` Jan Hubicka
2 siblings, 0 replies; 15+ messages in thread
From: Richard Biener @ 2013-03-06 10:18 UTC (permalink / raw)
To: Steven Bosscher; +Cc: Michael Matz, GCC Patches, Jeff Law
On Tue, Mar 5, 2013 at 5:16 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Tue, Mar 5, 2013 at 3:48 PM, Michael Matz wrote:
>> Iteration isn't easy on trees without a pointer to the parent (i.e.
>> enlarging each node), you need to remember variably sized context in the
>> iterator (e.g. the current stack of nodes).
>
> I was thinking of just making the "tree" a single forward-linked list,
> that's a valid splay tree and one that is compatible with the
> iterators, at least as long as the iterated bitmap are not modified
> (but I think that isn't allowed anyway?). Obviously the tree is not
> very well balanced after that, but splay trees have a way of
> re-balancing themselves quickly. The other possibility is to create
> vecs of bitmap_elements up front, but such iterators (fat iterators,
> as Richi just now called them in another mail :-) have the downside
> that you must always visit all bitmap elements, even if you want to be
> able to break the iteration before reaching the end.
>
>> I do like the idea of reusing the same internal data structure to
>> implement the tree. And I'm wondering about performance impact, I
>> wouldn't be surprised either way (i.e. that it brings about a large
>> improvement, or none at all), most bitmap membership tests in GCC are
>> surprisingly clustered so that the bitmaps cache of last accessed
>> element can work its magic (not all of them, as the testcase shows of
>> course :) ).
>
> I've retained the cached last accessed element. In fact it's now
> cached twice, because the root of the splay tree is always the last
> accessed element. I've considered *not* updating bitmap->current if
> bitmap_tree_find_element doesn't find the element it's looking for.
> That way, the last accessed element would be the element that was
> *really* last accessed, i.e. with a valid membership test, instead of
> the element closest to the last tested bit. Not sure if that'd be a
> good idea.
>
> Anyway, updated patch attached. It compiles all my cc1-i files, and
> it compiles the PR55135 test case, in 410s (I terminated cc1plus
> unpatched after >7200s, more than 2 hours...).
>
> An interesting question is, how can you identify bitmaps that could
> benefit from viewing it as a tree (at least for some time). I have no
> ideas here. Something with detailed memory stats, of course, but then
> how to derive some measure for a trade-off between list or tree view.
> Thoughts?
That's indeed a good question. The mem-stats help to print a useful
location for where the bitmap was allocated. But whether to switch it
or not is more fine-grained - any iteration / bitwise op should "reset"
the stats we collect. For the rest I'd simply count # of elements
walked for the find vs. # of splays done (where of course a splay is
more expensive than a linked list element walk). That "vs." of course
doesn't work because we don't have both views at the same time,
but counting the list walks vs. the number of searches would be a start
(doesn't help deciding whether a switch to a tree was bad and should
be undone, of course ... we'd have to compute the "distance" in
bitmap_elts between successive searches).
What about simply providing a bitmap_test_set_only () with no
way to switch back and let the tree balance itself? Does the
splay () overhead matter?
Richard.
> Ciao!
> Steven
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-05 16:17 ` Steven Bosscher
2013-03-05 22:56 ` Steven Bosscher
2013-03-06 10:18 ` Richard Biener
@ 2013-03-06 16:02 ` Jan Hubicka
2013-03-06 16:06 ` Jan Hubicka
2013-03-06 17:59 ` Steven Bosscher
2 siblings, 2 replies; 15+ messages in thread
From: Jan Hubicka @ 2013-03-06 16:02 UTC (permalink / raw)
To: Steven Bosscher; +Cc: Michael Matz, Richard Biener, GCC Patches, Jeff Law
>
> An interesting question is, how can you identify bitmaps that could
> benefit from viewing it as a tree (at least for some time). I have no
> ideas here. Something with detailed memory stats, of course, but then
> how to derive some measure for a trade-off between list or tree view.
> Thoughts?
Well, I guess we can simply accumulate the counter on linked list walks (when
the one element cache is missed) and divide it by number of iterations. Where
this number thends to grow and not be counstant bounded, we have nonlinear
behaviour, right?
Honza
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-06 16:02 ` Jan Hubicka
@ 2013-03-06 16:06 ` Jan Hubicka
2013-03-06 18:07 ` Steven Bosscher
2013-03-06 17:59 ` Steven Bosscher
1 sibling, 1 reply; 15+ messages in thread
From: Jan Hubicka @ 2013-03-06 16:06 UTC (permalink / raw)
To: Jan Hubicka
Cc: Steven Bosscher, Michael Matz, Richard Biener, GCC Patches, Jeff Law
> >
> > An interesting question is, how can you identify bitmaps that could
> > benefit from viewing it as a tree (at least for some time). I have no
> > ideas here. Something with detailed memory stats, of course, but then
> > how to derive some measure for a trade-off between list or tree view.
> > Thoughts?
>
> Well, I guess we can simply accumulate the counter on linked list walks (when
> the one element cache is missed) and divide it by number of iterations. Where
> this number thends to grow and not be counstant bounded, we have nonlinear
> behaviour, right?
And for the RFC, i also find it interesting experiment. I implemented some
time ago splay tree based bitmap with API same as bitmap's but never attempted
to put it to mainline since Danny introduced his ebitmap and there was a lot of
discussion about whether one needs more than one bitmap in the compiler. I
never experimented with bitmap.c change itself, just tested that replacing all
bitmaps by tree based ones causes quite some memory consumption on RA side
(with old RA) because bitmaps are pretty good for regsets they were introduced
for.
Honza
>
> Honza
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-06 16:02 ` Jan Hubicka
2013-03-06 16:06 ` Jan Hubicka
@ 2013-03-06 17:59 ` Steven Bosscher
2013-03-06 18:03 ` Jan Hubicka
1 sibling, 1 reply; 15+ messages in thread
From: Steven Bosscher @ 2013-03-06 17:59 UTC (permalink / raw)
To: Jan Hubicka; +Cc: Michael Matz, Richard Biener, GCC Patches, Jeff Law
On Wed, Mar 6, 2013 at 5:02 PM, Jan Hubicka wrote:
>>
>> An interesting question is, how can you identify bitmaps that could
>> benefit from viewing it as a tree (at least for some time). I have no
>> ideas here. Something with detailed memory stats, of course, but then
>> how to derive some measure for a trade-off between list or tree view.
>> Thoughts?
>
> Well, I guess we can simply accumulate the counter on linked list walks (when
> the one element cache is missed) and divide it by number of iterations. Where
> this number thends to grow and not be counstant bounded, we have nonlinear
> behaviour, right?
Well, yes and no. This is not fine-grained enough to see if there are
specific usages of bitmaps that can be better represented as a
linked-list or as a tree. But yes, it's a place to start, and it's
what I've started doing last night for a set of files (large PR test
cases, cc1-i files, etc.).
Ciao!
Steven
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-06 17:59 ` Steven Bosscher
@ 2013-03-06 18:03 ` Jan Hubicka
0 siblings, 0 replies; 15+ messages in thread
From: Jan Hubicka @ 2013-03-06 18:03 UTC (permalink / raw)
To: Steven Bosscher
Cc: Jan Hubicka, Michael Matz, Richard Biener, GCC Patches, Jeff Law
> On Wed, Mar 6, 2013 at 5:02 PM, Jan Hubicka wrote:
> >>
> >> An interesting question is, how can you identify bitmaps that could
> >> benefit from viewing it as a tree (at least for some time). I have no
> >> ideas here. Something with detailed memory stats, of course, but then
> >> how to derive some measure for a trade-off between list or tree view.
> >> Thoughts?
> >
> > Well, I guess we can simply accumulate the counter on linked list walks (when
> > the one element cache is missed) and divide it by number of iterations. Where
> > this number thends to grow and not be counstant bounded, we have nonlinear
> > behaviour, right?
>
> Well, yes and no. This is not fine-grained enough to see if there are
> specific usages of bitmaps that can be better represented as a
> linked-list or as a tree. But yes, it's a place to start, and it's
> what I've started doing last night for a set of files (large PR test
> cases, cc1-i files, etc.).
Well, I meant with the --enable-gather-detailed-stats code. it should give you
data about individual bitmaps used thorough the compiler.
Honza
>
> Ciao!
> Steven
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-06 16:06 ` Jan Hubicka
@ 2013-03-06 18:07 ` Steven Bosscher
0 siblings, 0 replies; 15+ messages in thread
From: Steven Bosscher @ 2013-03-06 18:07 UTC (permalink / raw)
To: Jan Hubicka; +Cc: Michael Matz, Richard Biener, GCC Patches, Jeff Law
On Wed, Mar 6, 2013 at 5:06 PM, Jan Hubicka wrote:
> And for the RFC, i also find it interesting experiment. I implemented some
> time ago splay tree based bitmap with API same as bitmap's but never attempted
> to put it to mainline since Danny introduced his ebitmap and there was a lot of
> discussion about whether one needs more than one bitmap in the compiler. I
Right, I think the ebitmap.c experiment shows that there is *not* room
for another bitmap implementation. This is why I developed these
splay-tree bitmaps using the same data structures as the existing
linked-list sparse bitmaps: Not another bitmap, just another way of
looking at the existing bitmap. I required that changing the view of
the bitmap from linked-list to splay tree and vv. to be almost free.
> never experimented with bitmap.c change itself, just tested that replacing all
> bitmaps by tree based ones causes quite some memory consumption on RA side
> (with old RA) because bitmaps are pretty good for regsets they were introduced
> for.
Memory consumption as in higher peak memory? That cannot happen with
my splay-tree bitmaps. They take exactly the same amount of memory,
independent of whether the current view on the bitmap is linked-list
or splay tree. As for cache behavior or number of memory operations
(loads, stores) I think this is directly correlated to the lookup
success ratio, hence the access pattern, and so if the right view on
the bitmap is selected for the right circumstances then the number of
memory ops should also be no worse in splay tree view than in
linked-list view.
Another idea I'm currently (right now on gcc17 ;-) working on, is a
trivial speed-up for bitmaps used as regsets. The idea is that
bitmap_find_bit should look at head->first if head->current is not the
element containing the sought bit, and *not* update head->current if
head->first is the right element. This speeds up regsets because a
common access pattern is to look at sets containing both pseudos and
hardregs, and on most targets all hardregs are in head->first. Not
updating head->current preserves a pointer to the latest accessed
pseudos.
I'll implement this idea and come back with some timings.
Ciao!
Steven
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-05 22:56 ` Steven Bosscher
@ 2013-03-07 20:18 ` Steven Bosscher
2018-10-17 14:04 ` Richard Biener
0 siblings, 1 reply; 15+ messages in thread
From: Steven Bosscher @ 2013-03-07 20:18 UTC (permalink / raw)
To: GCC Patches; +Cc: Richard Biener, Michael Matz, Jan Hubicka
[-- Attachment #1: Type: text/plain, Size: 588 bytes --]
> Attached is a version that passes bootstrap&testing on
> x86_64-unknown-linux-gnu. and with a ChangeLog.
Hello,
Testing with some bitmap view changes revealed a few bugs:
- Listifying a tree was broken, the prev pointer was never set. Oops!
- As a result of the above, clearing bitmaps was broken, the whole
bitmap would be leaked instead of released.
- Likewise, changing view from tree to list would only retain
head->first and lose the rest of the set...
- bitmap_last_set_bit has to search from the root, as head->current
may be in the left branch of another node.
Ciao!
Steven
[-- Attachment #2: tbitmap.diff.txt --]
[-- Type: text/plain, Size: 55562 bytes --]
* 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 196505)
+++ 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 196505)
+++ 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_descriptor> 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);
\f
+/* 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);
-}
-\f
/* 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,481 @@ bitmap_elt_clear_from (bitmap head, bitm
bitmap_ggc_free = elt;
}
}
+\f
+/* 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;
+}
+
+\f
+/* 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;
+}
+\f
+/* 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);
+
+ /* Because E has no right branch, and we rotated it to the root,
+ the left branch is the new root. */
+ t = e->prev;
+ head->first = t;
+ head->current = t;
+ head->indx = (t != NULL) ? t->indx : 0;
+
+ /* Detach the tree from E, and re-attach the right branch of E. */
+ 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(N)
+ for a tree with N nodes. A recursive implementation could
+ 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;
+ prev = n;
+ }
+ 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;
+
+ gcc_assert (head->tree_form);
+
+ ptr = head->first;
+ if (ptr)
+ {
+ while (ptr->prev)
+ bitmap_tree_rotate_right (ptr);
+ head->first = ptr;
+ head->first = bitmap_tree_listify_from (head, ptr);
+ }
+
+ head->tree_form = 0;
+}
+
+/* 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;
+
+ gcc_assert (! head->tree_form);
+
+ ptr = head->first;
+ while (ptr)
+ {
+ ptr->prev = NULL;
+ ptr = ptr->next;
+ }
+
+ head->tree_form = 1;
+}
+\f
+/* 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);
}
\f
/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
@@ -427,96 +867,6 @@ bitmap_element_zerop (const bitmap_eleme
#endif
}
\f
-/* 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;
-}
-\f
/* Copy a bitmap to another bitmap. */
void
@@ -525,6 +875,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 +887,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 +925,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 +952,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 +976,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 +1048,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 +1079,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 +1115,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++)
{
@@ -833,14 +1165,20 @@ bitmap_first_set_bit (const_bitmap a)
unsigned
bitmap_last_set_bit (const_bitmap a)
{
- const bitmap_element *elt = a->current ? a->current : a->first;
+ const bitmap_element *elt;
unsigned bit_no;
BITMAP_WORD word;
int ix;
+ if (a->tree_form)
+ elt = a->first;
+ else
+ elt = a->current ? a->current : a->first;
gcc_checking_assert (elt);
+
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 +1220,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 +1242,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 +1280,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 +1290,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 +1312,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 +1354,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 +1377,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 +1426,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 +1449,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 +1490,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 +1526,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 +1544,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 +1562,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 +1579,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 +1645,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 +1684,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 +1754,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 +1776,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 +1797,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 +1824,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 +1869,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 +1909,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 +1956,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 +1995,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 +2013,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 +2049,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 +2075,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 +2088,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 +2117,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 +2137,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 +2161,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 +2190,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 +2227,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 +2320,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 +2352,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 +2420,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 +2428,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 +2443,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 +2481,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 +2499,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 +2516,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 196505)
+++ 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)
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch][RFC] bitmaps as lists *or* trees
2013-03-07 20:18 ` Steven Bosscher
@ 2018-10-17 14:04 ` Richard Biener
0 siblings, 0 replies; 15+ messages in thread
From: Richard Biener @ 2018-10-17 14:04 UTC (permalink / raw)
To: Steven Bosscher; +Cc: GCC Patches, Michael Matz, Jan Hubicka
[-- Attachment #1: Type: text/plain, Size: 1462 bytes --]
On Thu, Mar 7, 2013 at 9:18 PM Steven Bosscher <stevenb.gcc@gmail.com> wrote:
>
> > Attached is a version that passes bootstrap&testing on
> > x86_64-unknown-linux-gnu. and with a ChangeLog.
>
> Hello,
>
> Testing with some bitmap view changes revealed a few bugs:
>
> - Listifying a tree was broken, the prev pointer was never set. Oops!
> - As a result of the above, clearing bitmaps was broken, the whole
> bitmap would be leaked instead of released.
> - Likewise, changing view from tree to list would only retain
> head->first and lose the rest of the set...
> - bitmap_last_set_bit has to search from the root, as head->current
> may be in the left branch of another node.
I have updated the patch to trunk and fixed another bug (the patch applied
OK to gcc 4.8 where the same bug exists - not sure what you developed it
ontop of). We have a premature optimization in bitmap_find_bit:
@@ -506,7 +858,9 @@ bitmap_find_bit (bitmap head, unsigned i
if (head->current == NULL
|| head->indx == indx)
return head->current;
- if (head->current == head->first
+ /* ??? Premature optimization? */
+ if (!head->tree_form
+ && head->current == head->first
&& head->first->next == NULL)
return NULL;
the reginfo.c use-case seems to be gone so I put the use in the SSA
propagator instead where it is supposed to help PR63155.
Meanwhile bitmap_head->descriptor_id is dead so I made tree_form a bool.
Richard.
> Ciao!
> Steven
[-- Attachment #2: tree-bitmap --]
[-- Type: application/octet-stream, Size: 55144 bytes --]
2018-10-17 Steven Bosscher <steven@gcc.gnu.org>
* 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.
Index: gcc/bitmap.c
===================================================================
--- gcc/bitmap.c (revision 265236)
+++ gcc/bitmap.c (working copy)
@@ -26,6 +26,8 @@ along with GCC; see the file COPYING3.
/* Memory allocation statistics purpose instance. */
mem_alloc_description<bitmap_usage> bitmap_mem_desc;
+static bitmap_element *bitmap_tree_listify_from (bitmap, bitmap_element *);
+
/* Register new bitmap. */
void
bitmap_register (bitmap b MEM_STAT_DECL)
@@ -49,22 +51,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);
\f
+/* 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;
elt->indx = -1;
if (bit_obstack)
@@ -79,41 +77,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);
-}
-\f
/* Allocate a bitmap element. The bits are cleared, but nothing else is. */
static inline bitmap_element *
@@ -166,7 +129,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)
@@ -174,7 +138,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)
{
@@ -201,7 +169,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;
@@ -213,14 +181,485 @@ bitmap_elt_clear_from (bitmap head, bitm
bitmap_ggc_free = elt;
}
}
+\f
+/* 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;
+}
-/* Clear a bitmap by freeing the linked list. */
+/* 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_usage *usage)
+{
+ 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 && usage)
+ usage->m_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 && usage)
+ usage->m_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 && usage)
+ usage->m_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;
+}
+
+\f
+/* 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;
+
+ bitmap_usage *usage = NULL;
+ if (GATHER_STATISTICS)
+ usage = bitmap_mem_desc.get_descriptor_for_instance (head);
+
+ N.prev = N.next = NULL;
+ l = r = &N;
+
+ while (indx != t->indx)
+ {
+ if (GATHER_STATISTICS && usage)
+ usage->m_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;
+}
+\f
+/* 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);
+
+ /* Because E has no right branch, and we rotated it to the root,
+ the left branch is the new root. */
+ t = e->prev;
+ head->first = t;
+ head->current = t;
+ head->indx = (t != NULL) ? t->indx : 0;
+
+ /* Detach the tree from E, and re-attach the right branch of E. */
+ 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(N)
+ for a tree with N nodes. A recursive implementation could
+ 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;
+ prev = n;
+ }
+ sorted_elements.release ();
+
+ return e;
+}
+
+/* Convert bitmap HEAD from splay-tree view to linked-list view. */
+
+void
+bitmap_list_view (bitmap head)
+{
+ bitmap_element *ptr;
+
+ gcc_assert (head->tree_form);
+
+ ptr = head->first;
+ if (ptr)
+ {
+ while (ptr->prev)
+ bitmap_tree_rotate_right (ptr);
+ head->first = ptr;
+ head->first = bitmap_tree_listify_from (head, ptr);
+ }
+
+ head->tree_form = false;
+}
+
+/* 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;
+
+ gcc_assert (! head->tree_form);
+
+ ptr = head->first;
+ while (ptr)
+ {
+ ptr->prev = NULL;
+ ptr = ptr->next;
+ }
+
+ head->tree_form = true;
+}
+\f
+/* 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);
}
\f
/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
@@ -344,96 +783,6 @@ bitmap_element_zerop (const bitmap_eleme
#endif
}
\f
-/* 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;
-}
-\f
/* Copy a bitmap to another bitmap. */
void
@@ -442,6 +791,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. */
@@ -452,8 +803,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;
@@ -506,7 +858,9 @@ bitmap_find_bit (bitmap head, unsigned i
if (head->current == NULL
|| head->indx == indx)
return head->current;
- if (head->current == head->first
+ /* ??? Premature optimization? */
+ if (!head->tree_form
+ && head->current == head->first
&& head->first->next == NULL)
return NULL;
@@ -521,45 +875,10 @@ bitmap_find_bit (bitmap head, unsigned i
if (GATHER_STATISTICS && usage)
usage->m_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 && usage)
- usage->m_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 && usage)
- usage->m_search_iter++;
- }
-
+ if (!head->tree_form)
+ element = bitmap_list_find_element (head, indx, usage);
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 && usage)
- {
- usage->m_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->indx != indx)
- element = 0;
+ element = bitmap_tree_find_element (head, indx);
return element;
}
@@ -583,7 +902,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;
@@ -602,21 +926,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. */
@@ -692,6 +1017,7 @@ bitmap_count_bits (const_bitmap a)
unsigned long count = 0;
const bitmap_element *elt;
+ gcc_checking_assert (!a->tree_form);
for (elt = a->first; elt; elt = elt->next)
count += bitmap_count_bits_in_word (elt->bits);
@@ -748,9 +1074,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++)
@@ -782,6 +1110,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++)
{
@@ -827,14 +1160,20 @@ bitmap_first_set_bit (const_bitmap a)
unsigned
bitmap_last_set_bit (const_bitmap a)
{
- const bitmap_element *elt = a->current ? a->current : a->first;
+ const bitmap_element *elt;
unsigned bit_no;
BITMAP_WORD word;
int ix;
+ if (a->tree_form)
+ elt = a->first;
+ else
+ elt = a->current ? a->current : a->first;
gcc_checking_assert (elt);
+
while (elt->next)
elt = elt->next;
+
bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
{
@@ -876,6 +1215,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)
@@ -897,7 +1237,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++)
@@ -934,6 +1275,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;
@@ -942,7 +1285,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;
}
@@ -964,7 +1307,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;
}
@@ -1006,7 +1349,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));
@@ -1028,6 +1372,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)
@@ -1076,7 +1421,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
@@ -1098,7 +1444,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;
}
}
@@ -1139,6 +1485,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))
@@ -1173,7 +1521,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;
}
@@ -1191,6 +1539,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 +1563,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 +1580,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 +1646,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;
@@ -1339,7 +1691,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. */
@@ -1409,7 +1761,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;
}
@@ -1431,6 +1783,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))
@@ -1451,13 +1804,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;
@@ -1478,7 +1831,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;
@@ -1523,7 +1876,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++)
@@ -1562,6 +1916,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)
@@ -1610,6 +1965,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;
@@ -1648,7 +2004,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);
@@ -1664,7 +2022,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++)
@@ -1699,7 +2058,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));
@@ -1724,6 +2084,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);
@@ -1735,7 +2097,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;
@@ -1763,7 +2126,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;
}
}
@@ -1783,6 +2146,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)
@@ -1805,6 +2170,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;)
{
@@ -1832,6 +2199,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;)
{
@@ -1866,6 +2236,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). */
@@ -1958,16 +2331,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);
@@ -1988,6 +2363,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))
@@ -2054,6 +2431,7 @@ bitmap_ior_and_into (bitmap a, const_bit
}
/* Compute hash of bitmap (for purposes of hashing). */
+
hashval_t
bitmap_hash (const_bitmap head)
{
@@ -2061,6 +2439,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;
@@ -2074,9 +2454,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",
@@ -2108,13 +2492,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 (stderr, head);
}
@@ -2123,12 +2510,17 @@ 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,
+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;
+
+ /* ??? Avoid this somehow. */
+ if (tree_form)
+ bitmap_list_view (head);
fputs (prefix, file);
EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
@@ -2137,6 +2529,9 @@ bitmap_print (FILE *file, const_bitmap h
comma = ", ";
}
fputs (suffix, file);
+
+ if (tree_form)
+ bitmap_tree_view (head);
}
/* Output per-bitmap memory usage statistics. */
@@ -2150,13 +2545,13 @@ dump_bitmap_statistics (void)
}
DEBUG_FUNCTION void
-debug (const bitmap_head &ref)
+debug (bitmap_head &ref)
{
dump_bitmap (stderr, &ref);
}
DEBUG_FUNCTION void
-debug (const bitmap_head *ptr)
+debug (bitmap_head *ptr)
{
if (ptr)
debug (*ptr);
Index: gcc/bitmap.h
===================================================================
--- gcc/bitmap.h (revision 265236)
+++ gcc/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 tree.
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). 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" 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.).
-
- 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 "obstack.h"
@@ -225,30 +296,44 @@ struct GTY (()) bitmap_obstack {
linear in the number of elements to be freed. */
struct GTY((chain_next ("%h.next"), chain_prev ("%h.prev"))) bitmap_element {
- struct bitmap_element *next; /* Next element. */
- struct bitmap_element *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 *next;
+ /* In list form, the previous element in the linked list;
+ in tree form, the right child node in the tree. */
+ struct bitmap_element *prev;
+ /* regno/BITMAP_ELEMENT_ALL_BITS. */
+ unsigned int indx;
+ /* Bits that are set, counting from INDX, inclusive */
+ BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
};
/* Head of bitmap linked list. The 'current' member points to something
already pointed to by the chain started by first, so GTY((skip)) it. */
struct GTY(()) bitmap_head {
- 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;
+ /* False if the bitmap is in list form; true if the bitmap is in tree form.
+ Bitmap iterators only work on bitmaps in list form. */
+ bool tree_form;
+ /* 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;
};
/* Global data */
extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */
+/* 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 linked list. */
extern void bitmap_clear (bitmap);
@@ -315,15 +400,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 *);
@@ -338,6 +423,7 @@ static inline void
bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO)
{
head->first = head->current = NULL;
+ head->indx = head->tree_form = 0;
head->obstack = obstack;
if (GATHER_STATISTICS)
bitmap_register (head PASS_MEM_STAT);
@@ -351,12 +437,12 @@ extern bitmap bitmap_gc_alloc (ALONE_CXX
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");
}
-extern void debug (const bitmap_head &ref);
-extern void debug (const bitmap_head *ptr);
+extern void debug (bitmap_head &ref);
+extern void debug (bitmap_head *ptr);
extern unsigned bitmap_first_set_bit (const_bitmap);
extern unsigned bitmap_last_set_bit (const_bitmap);
@@ -397,6 +483,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)
{
@@ -439,6 +527,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)
@@ -497,8 +587,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,
@@ -508,6 +597,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: gcc/tree-ssa-propagate.c
===================================================================
--- gcc/tree-ssa-propagate.c (revision 265236)
+++ gcc/tree-ssa-propagate.c (working copy)
@@ -381,6 +381,8 @@ ssa_prop_init (void)
/* Worklists of SSA edges. */
ssa_edge_worklist = BITMAP_ALLOC (NULL);
ssa_edge_worklist_back = BITMAP_ALLOC (NULL);
+ bitmap_tree_view (ssa_edge_worklist);
+ bitmap_tree_view (ssa_edge_worklist_back);
/* Worklist of basic-blocks. */
bb_to_cfg_order = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1);
^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2018-10-17 12:31 UTC | newest]
Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-03-05 12:01 [patch][RFC] bitmaps as lists *or* trees Steven Bosscher
2013-03-05 12:32 ` Richard Biener
2013-03-05 14:48 ` Michael Matz
2013-03-05 16:17 ` Steven Bosscher
2013-03-05 22:56 ` Steven Bosscher
2013-03-07 20:18 ` Steven Bosscher
2018-10-17 14:04 ` Richard Biener
2013-03-06 10:18 ` Richard Biener
2013-03-06 16:02 ` Jan Hubicka
2013-03-06 16:06 ` Jan Hubicka
2013-03-06 18:07 ` Steven Bosscher
2013-03-06 17:59 ` Steven Bosscher
2013-03-06 18:03 ` Jan Hubicka
2013-03-05 14:51 ` Steven Bosscher
2013-03-05 16:03 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).