PR63155 made me pick up this old work from Steven, it turns our
linked-list implementation to a two-mode one with one being a
splay tree featuring O(log N) complexity for find/remove.
Over Stevens original patch I added a bitmap_tree_to_vec helper
that I use from the debug/print methods to avoid changing view
there. In theory the bitmap iterator could get a "stack"
as well and we could at least support EXECUTE_IF_SET_IN_BITMAP.
This can be used to fix the two biggest bottlenecks in the PRs
testcase, namely SSA propagator worklist handling and out-of-SSA
coalesce list building. perf shows the following data, first
unpatched, second patched - also watch the thrid coulumn (samples)
when comparing percentages.
-O0
- 18.19% 17.35% 407 cc1 cc1 [.] bitmap_set_b▒
- bitmap_set_bit ▒
+ 8.77% create_coalesce_list_for_region ▒
+ 4.21% calculate_live_ranges ▒
+ 2.02% build_ssa_conflict_graph ▒
+ 1.66% insert_phi_nodes_for ▒
+ 0.86% coalesce_ssa_name
patched:
- 12.39% 10.48% 129 cc1 cc1 [.] bitmap_set_b▒
- bitmap_set_bit ▒
+ 5.27% calculate_live_ranges ▒
+ 2.76% insert_phi_nodes_for ▒
+ 1.90% create_coalesce_list_for_region ▒
+ 1.63% build_ssa_conflict_graph ▒
+ 0.35% coalesce_ssa_name
-O1
- 17.53% 17.53% 842 cc1 cc1 [.] bitmap_set_b▒
- bitmap_set_bit ▒
+ 12.39% add_ssa_edge ▒
+ 1.48% create_coalesce_list_for_region ▒
+ 0.82% solve_constraints ▒
+ 0.71% calculate_live_ranges ▒
+ 0.64% add_implicit_graph_edge ▒
+ 0.41% insert_phi_nodes_for ▒
+ 0.34% build_ssa_conflict_graph
patched:
- 5.79% 5.00% 167 cc1 cc1 [.] bitmap_set_b▒
- bitmap_set_bit ▒
+ 1.41% add_ssa_edge ▒
+ 0.88% calculate_live_ranges ▒
+ 0.75% add_implicit_graph_edge ▒
+ 0.68% solve_constraints ▒
+ 0.48% insert_phi_nodes_for ▒
+ 0.45% build_ssa_conflict_graph
-O3
- 12.37% 12.34% 1145 cc1 cc1 [.] bitmap_set_b▒
- bitmap_set_bit ▒
+ 9.14% add_ssa_edge ▒
+ 0.80% create_coalesce_list_for_region ▒
+ 0.69% add_implicit_graph_edge ▒
+ 0.54% solve_constraints ▒
+ 0.34% calculate_live_ranges ▒
+ 0.27% insert_phi_nodes_for ▒
+ 0.21% build_ssa_conflict_graph
- 4.36% 3.86% 227 cc1 cc1 [.] bitmap_set_b▒
- bitmap_set_bit ▒
+ 0.98% add_ssa_edge ▒
+ 0.86% add_implicit_graph_edge ▒
+ 0.64% solve_constraints ▒
+ 0.57% calculate_live_ranges ▒
+ 0.32% build_ssa_conflict_graph ▒
+ 0.29% mark_all_vars_used_1 ▒
+ 0.20% insert_phi_nodes_for ▒
+ 0.16% create_coalesce_list_for_region
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Any objections?
Thanks,
Richard.
2018-10-18 Steven Bosscher <ste...@gcc.gnu.org>
Richard Biener <rguent...@suse.de>
* 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.
PR tree-optimization/63155
* tree-ssa-propagate.c (ssa_prop_init): Use tree-view for the
SSA edge worklists.
* tree-ssa-coalesce.c (coalesce_ssa_name): Populate used_in_copies
in tree-view.
Index: gcc/bitmap.c
===================================================================
--- gcc/bitmap.c (revision 265259)
+++ 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);
+/* 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);
-}
-
/* Allocate a bitmap element. The bits are cleared, but nothing else is. */
static inline bitmap_element *
@@ -158,69 +121,545 @@ bitmap_element_allocate (bitmap head)
element = ggc_alloc<bitmap_element> ();
}
- if (GATHER_STATISTICS)
- register_overhead (head, sizeof (bitmap_element));
+ if (GATHER_STATISTICS)
+ register_overhead (head, sizeof (bitmap_element));
+
+ memset (element->bits, 0, sizeof (element->bits));
+
+ return element;
+}
+
+/* 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)
+{
+ bitmap_element *prev;
+ bitmap_obstack *bit_obstack = head->obstack;
+
+ if (!elt)
+ return;
+
+ if (head->tree_form)
+ elt = bitmap_tree_listify_from (head, elt);
+
+ if (GATHER_STATISTICS)
+ {
+ int n = 0;
+ for (prev = elt; prev; prev = prev->next)
+ n++;
+ register_overhead (head, -sizeof (bitmap_element) * n);
+ }
+
+ prev = elt->prev;
+ if (prev)
+ {
+ prev->next = NULL;
+ if (head->current->indx > prev->indx)
+ {
+ head->current = prev;
+ head->indx = prev->indx;
+ }
+ }
+ else
+ {
+ head->first = NULL;
+ head->current = NULL;
+ head->indx = 0;
+ }
+
+ /* Put the entire list onto the freelist in one operation. */
+ if (bit_obstack)
+ {
+ elt->prev = bit_obstack->elements;
+ bit_obstack->elements = elt;
+ }
+ else
+ {
+ elt->prev = bitmap_ggc_free;
+ bitmap_ggc_free = elt;
+ }
+}
+
+/* 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_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_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_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_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;
+}
+
+
+/* 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;
+}
+
+/* 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);
- memset (element->bits, 0, sizeof (element->bits));
+ 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 element;
+ return e;
}
-/* Remove ELT and all following elements from bitmap HEAD. */
+/* Convert bitmap HEAD from splay-tree view to linked-list view. */
void
-bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
+bitmap_list_view (bitmap head)
{
- bitmap_element *prev;
- bitmap_obstack *bit_obstack = head->obstack;
+ bitmap_element *ptr;
- if (!elt) return;
+ gcc_assert (head->tree_form);
- if (GATHER_STATISTICS)
+ ptr = head->first;
+ if (ptr)
{
- int n = 0;
- for (prev = elt; prev; prev = prev->next)
- n++;
- register_overhead (head, -sizeof (bitmap_element) * n);
+ while (ptr->prev)
+ bitmap_tree_rotate_right (ptr);
+ head->first = ptr;
+ head->first = bitmap_tree_listify_from (head, ptr);
}
- prev = elt->prev;
- if (prev)
- {
- prev->next = NULL;
- if (head->current->indx > prev->indx)
- {
- head->current = prev;
- head->indx = prev->indx;
- }
- }
- else
- {
- head->first = NULL;
- head->current = NULL;
- head->indx = 0;
- }
+ head->tree_form = false;
+}
- /* Put the entire list onto the free list in one operation. */
- if (bit_obstack)
- {
- elt->prev = bit_obstack->elements;
- bit_obstack->elements = elt;
- }
- else
+/* 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)
{
- elt->prev = bitmap_ggc_free;
- bitmap_ggc_free = elt;
+ ptr->prev = NULL;
+ ptr = ptr->next;
}
-}
-/* Clear a bitmap by freeing the linked list. */
+ head->tree_form = true;
+}
+
+/* Clear a bitmap by freeing all its elements. */
void
bitmap_clear (bitmap head)
{
- if (head->first)
- bitmap_elt_clear_from (head, head->first);
+ if (head->first == NULL)
+ return;
+ if (head->tree_form)
+ {
+ bitmap_element *e, *t;
+ for (e = head->first; e->prev; e = e->prev)
+ /* Loop to find the element with the smallest index. */ ;
+ t = bitmap_tree_splay (head, head->first, e->indx);
+ gcc_checking_assert (t == e);
+ head->first = t;
+ }
+ bitmap_elt_clear_from (head, head->first);
}
/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
@@ -344,96 +783,6 @@ bitmap_element_zerop (const bitmap_eleme
#endif
}
-/* Link the bitmap element into the current bitmap linked list. */
-
-static inline void
-bitmap_element_link (bitmap head, bitmap_element *element)
-{
- unsigned int indx = element->indx;
- bitmap_element *ptr;
-
- /* If this is the first and only element, set it in. */
- if (head->first == 0)
- {
- element->next = element->prev = 0;
- head->first = element;
- }
-
- /* If this index is less than that of the current element, it goes someplace
- before the current element. */
- else if (indx < head->indx)
- {
- for (ptr = head->current;
- ptr->prev != 0 && ptr->prev->indx > indx;
- ptr = ptr->prev)
- ;
-
- if (ptr->prev)
- ptr->prev->next = element;
- else
- head->first = element;
-
- element->prev = ptr->prev;
- element->next = ptr;
- ptr->prev = element;
- }
-
- /* Otherwise, it must go someplace after the current element. */
- else
- {
- for (ptr = head->current;
- ptr->next != 0 && ptr->next->indx < indx;
- ptr = ptr->next)
- ;
-
- if (ptr->next)
- ptr->next->prev = element;
-
- element->next = ptr->next;
- element->prev = ptr;
- ptr->next = element;
- }
-
- /* Set up so this is the first element searched. */
- head->current = element;
- head->indx = indx;
-}
-
-/* Insert a new uninitialized element into bitmap HEAD after element
- ELT. If ELT is NULL, insert the element at the start. Return the
- new element. */
-
-static bitmap_element *
-bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
-{
- bitmap_element *node = bitmap_element_allocate (head);
- node->indx = indx;
-
- if (!elt)
- {
- if (!head->current)
- {
- head->current = node;
- head->indx = indx;
- }
- node->next = head->first;
- if (node->next)
- node->next->prev = node;
- head->first = node;
- node->prev = NULL;
- }
- else
- {
- gcc_checking_assert (head->current);
- node->next = elt->next;
- if (node->next)
- node->next->prev = node;
- elt->next = node;
- node->prev = elt;
- }
- return node;
-}
-
/* Copy a bitmap to another bitmap. */
void
@@ -442,6 +791,8 @@ bitmap_copy (bitmap to, const_bitmap fro
const bitmap_element *from_ptr;
bitmap_element *to_ptr = 0;
+ gcc_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_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_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_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_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_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_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_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_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_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_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_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_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_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_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_assert (!a->tree_form && !b->tree_form);
+
for (a_elt = a->first, b_elt = b->first;
a_elt && b_elt;)
{
@@ -1866,6 +2236,8 @@ bitmap_ior_and_compl (bitmap dst, const_
bitmap_element *dst_prev = NULL;
bitmap_element **dst_prev_pnext = &dst->first;
+ gcc_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 +2330,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_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 +2362,8 @@ bitmap_ior_and_into (bitmap a, const_bit
bool changed = false;
unsigned ix;
+ gcc_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 +2430,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 +2438,8 @@ bitmap_hash (const_bitmap head)
BITMAP_WORD hash = 0;
int ix;
+ gcc_assert (!head->tree_form);
+
for (ptr = head->first; ptr; ptr = ptr->next)
{
hash ^= ptr->indx;
@@ -2071,10 +2450,67 @@ bitmap_hash (const_bitmap head)
}
+/* Function to obtain a vector of bitmap elements in bit order from
+ HEAD in tree view. */
+
+static void
+bitmap_tree_to_vec (vec<bitmap_element *> &elts, const_bitmap head)
+{
+ gcc_assert (head->tree_form);
+ auto_vec<bitmap_element *, 32> stack;
+ bitmap_element *e = head->first;
+ while (e)
+ {
+ stack.safe_push (e);
+ e = e->prev;
+ }
+ while (!stack.is_empty ())
+ {
+ bitmap_element *e = stack.pop ();
+ elts.safe_push (e);
+ e = e->next;
+ while (e)
+ {
+ stack.safe_push (e);
+ e = e->prev;
+ }
+ }
+}
+
+/* Debugging function to print out the contents of a bitmap element. */
+
+DEBUG_FUNCTION void
+debug_bitmap_elt_file (FILE *file, const bitmap_element *ptr)
+{
+ unsigned int i, j, col = 26;
+
+ fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
+ " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
+ (const void*) ptr, (const void*) ptr->next,
+ (const void*) ptr->prev, ptr->indx);
+
+ for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
+ for (j = 0; j < BITMAP_WORD_BITS; j++)
+ if ((ptr->bits[i] >> j) & 1)
+ {
+ if (col > 70)
+ {
+ fprintf (file, "\n\t\t\t");
+ col = 24;
+ }
+
+ fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
+ + i * BITMAP_WORD_BITS + j));
+ col += 4;
+ }
+
+ fprintf (file, " }\n");
+}
+
/* 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;
@@ -2082,39 +2518,23 @@ debug_bitmap_file (FILE *file, const_bit
" current = " HOST_PTR_PRINTF " indx = %u\n",
(void *) head->first, (void *) head->current, head->indx);
- for (ptr = head->first; ptr; ptr = ptr->next)
+ if (head->tree_form)
{
- unsigned int i, j, col = 26;
-
- fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
- " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
- (const void*) ptr, (const void*) ptr->next,
- (const void*) ptr->prev, ptr->indx);
-
- for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
- for (j = 0; j < BITMAP_WORD_BITS; j++)
- if ((ptr->bits[i] >> j) & 1)
- {
- if (col > 70)
- {
- fprintf (file, "\n\t\t\t");
- col = 24;
- }
-
- fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
- + i * BITMAP_WORD_BITS + j));
- col += 4;
- }
-
- fprintf (file, " }\n");
+ auto_vec<bitmap_element *, 32> elts;
+ bitmap_tree_to_vec (elts, head);
+ for (unsigned i = 0; i < elts.length (); ++i)
+ debug_bitmap_elt_file (file, elts[i]);
}
+ else
+ for (ptr = head->first; ptr; ptr = ptr->next)
+ debug_bitmap_elt_file (file, ptr);
}
/* 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,18 +2543,39 @@ 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;
fputs (prefix, file);
- EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
+ if (head->tree_form)
+ {
+ auto_vec<bitmap_element *, 32> elts;
+ bitmap_tree_to_vec (elts, head);
+ for (i = 0; i < elts.length (); ++i)
+ for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ++ix)
+ {
+ BITMAP_WORD word = elts[i]->bits[ix];
+ for (unsigned bit = 0; bit != BITMAP_WORD_BITS; ++bit)
+ if (word & ((BITMAP_WORD)1 << bit))
+ {
+ fprintf (file, "%s%d", comma,
+ (bit + BITMAP_WORD_BITS * ix
+ + elts[i]->indx * BITMAP_ELEMENT_ALL_BITS));
+ comma = ", ";
+ }
+ }
+ }
+ else
{
- fprintf (file, "%s%d", comma, i);
- comma = ", ";
+ bitmap_iterator bi;
+ EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
+ {
+ fprintf (file, "%s%d", comma, i);
+ comma = ", ";
+ }
}
fputs (suffix, file);
}
@@ -2150,13 +2591,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 265259)
+++ 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,34 +47,97 @@ 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).
- The following operations can always be performed in O(1) time:
+ 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 in
+ list view:
* clear : bitmap_clear
+ * smallest_member : bitmap_first_set_bit
* choose_one : (not implemented, but could be
- implemented in constant time)
+ in constant time)
- The following operations can be performed in O(E) time worst-case (with
- E the number of elements in the linked list), but in O(1) time with a
- suitable access patterns:
+ The following operations can be performed in O(E) time worst-case in
+ list view (with E the number of elements in the linked list), but in
+ O(1) time with a 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:
+ The following operations can be performed in O(E) time in list view:
* 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
+
+ In tree view the following operations can all be performed in O(log E)
+ amortized time with O(E) worst-case behavior.
+
+ * smallest_member
+ * largest_member
+ * set_size
+ * member_p
+ * add_member
+ * remove_member
Additionally, the linked-list sparse set representation supports
enumeration of the members in O(E) time:
@@ -93,39 +161,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 "obstack.h"
@@ -225,24 +307,34 @@ 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;
void dump ();
};
@@ -250,6 +342,10 @@ struct GTY(()) bitmap_head {
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);
@@ -316,15 +412,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 *);
@@ -339,6 +435,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);
@@ -352,12 +449,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);
@@ -398,6 +495,8 @@ bmp_iter_set_init (bitmap_iterator *bi,
bi->elt1 = map->first;
bi->elt2 = NULL;
+ gcc_assert (!map->tree_form);
+
/* Advance elt1 until it is not before the block containing start_bit. */
while (1)
{
@@ -440,6 +539,8 @@ bmp_iter_and_init (bitmap_iterator *bi,
bi->elt1 = map1->first;
bi->elt2 = map2->first;
+ gcc_assert (!map1->tree_form && !map2->tree_form);
+
/* Advance elt1 until it is not before the block containing
start_bit. */
while (1)
@@ -498,8 +599,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,
@@ -509,6 +609,8 @@ bmp_iter_and_compl_init (bitmap_iterator
bi->elt1 = map1->first;
bi->elt2 = map2->first;
+ gcc_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 265259)
+++ 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);
Index: gcc/tree-ssa-coalesce.c
===================================================================
--- gcc/tree-ssa-coalesce.c (revision 265259)
+++ gcc/tree-ssa-coalesce.c (working copy)
@@ -1703,9 +1709,11 @@ coalesce_ssa_name (var_map map)
coalesce_list *cl;
auto_bitmap used_in_copies;
+ bitmap_tree_view (used_in_copies);
cl = create_coalesce_list_for_region (map, used_in_copies);
if (map->outofssa_p)
populate_coalesce_list_for_outofssa (cl, used_in_copies);
+ bitmap_list_view (used_in_copies);
if (dump_file && (dump_flags & TDF_DETAILS))
dump_var_map (dump_file, map);
