[patch][RFC] bitmaps as lists *or* trees

Steven Bosscher stevenb.gcc@gmail.com
Tue Mar 5 16:17:00 GMT 2013


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
-------------- next part --------------
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);
 

+/* Bitmap memory management.  */
 
-/* Add ELEM to the appropriate freelist.  */
+/* Add ELT to the appropriate freelist.  */
 static inline void
 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
 {
   bitmap_obstack *bit_obstack = head->obstack;
 
+  if (GATHER_STATISTICS)
+    register_overhead (head, -((int)sizeof (bitmap_element)));
+
   elt->next = NULL;
   if (bit_obstack)
     {
@@ -162,41 +165,6 @@ bitmap_elem_to_freelist (bitmap head, bi
     }
 }
 
-/* Free a bitmap element.  Since these are allocated off the
-   bitmap_obstack, "free" actually means "put onto the freelist".  */
-
-static inline void
-bitmap_element_free (bitmap head, bitmap_element *elt)
-{
-  bitmap_element *next = elt->next;
-  bitmap_element *prev = elt->prev;
-
-  if (prev)
-    prev->next = next;
-
-  if (next)
-    next->prev = prev;
-
-  if (head->first == elt)
-    head->first = next;
-
-  /* Since the first thing we try is to insert before current,
-     make current the next entry in preference to the previous.  */
-  if (head->current == elt)
-    {
-      head->current = next != 0 ? next : prev;
-      if (head->current)
-	head->indx = head->current->indx;
-      else
-	head->indx = 0;
-    }
-
-  if (GATHER_STATISTICS)
-    register_overhead (head, -((int)sizeof (bitmap_element)));
-
-  bitmap_elem_to_freelist (head, elt);
-}
-

 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
 
 static inline bitmap_element *
@@ -249,7 +217,8 @@ bitmap_element_allocate (bitmap head)
   return element;
 }
 
-/* Remove ELT and all following elements from bitmap HEAD.  */
+/* Remove ELT and all following elements from bitmap HEAD.
+   Put the released elements in the freelist for HEAD.  */
 
 void
 bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
@@ -257,7 +226,11 @@ bitmap_elt_clear_from (bitmap head, bitm
   bitmap_element *prev;
   bitmap_obstack *bit_obstack = head->obstack;
 
-  if (!elt) return;
+  if (!elt)
+    return;
+
+  if (head->tree_form)
+    elt = bitmap_tree_listify_from (head, elt);
 
   if (GATHER_STATISTICS)
     {
@@ -284,7 +257,7 @@ bitmap_elt_clear_from (bitmap head, bitm
       head->indx = 0;
     }
 
-  /* Put the entire list onto the free list in one operation. */
+  /* Put the entire list onto the freelist in one operation. */
   if (bit_obstack)
     {
       elt->prev = bit_obstack->elements;
@@ -296,14 +269,482 @@ bitmap_elt_clear_from (bitmap head, bitm
       bitmap_ggc_free = elt;
     }
 }
+

+/* Linked-list view of bitmaps.
+
+   In this representation, the bitmap elements form a double-linked list
+   with elements sorted by increasing index.  */
+
+/* Link the bitmap element into the current bitmap linked list.  */
+
+static inline void
+bitmap_list_link_element (bitmap head, bitmap_element *element)
+{
+  unsigned int indx = element->indx;
+  bitmap_element *ptr;
+
+  gcc_checking_assert (!head->tree_form);
+
+  /* If this is the first and only element, set it in.  */
+  if (head->first == 0)
+    {
+      element->next = element->prev = 0;
+      head->first = element;
+    }
+
+  /* If this index is less than that of the current element, it goes someplace
+     before the current element.  */
+  else if (indx < head->indx)
+    {
+      for (ptr = head->current;
+	   ptr->prev != 0 && ptr->prev->indx > indx;
+	   ptr = ptr->prev)
+	;
+
+      if (ptr->prev)
+	ptr->prev->next = element;
+      else
+	head->first = element;
+
+      element->prev = ptr->prev;
+      element->next = ptr;
+      ptr->prev = element;
+    }
+
+  /* Otherwise, it must go someplace after the current element.  */
+  else
+    {
+      for (ptr = head->current;
+	   ptr->next != 0 && ptr->next->indx < indx;
+	   ptr = ptr->next)
+	;
+
+      if (ptr->next)
+	ptr->next->prev = element;
+
+      element->next = ptr->next;
+      element->prev = ptr;
+      ptr->next = element;
+    }
+
+  /* Set up so this is the first element searched.  */
+  head->current = element;
+  head->indx = indx;
+}
+
+/* Unlink the bitmap element from the current bitmap linked list,
+   and return it to the freelist.  */
+
+static inline void
+bitmap_list_unlink_element (bitmap head, bitmap_element *element)
+{
+  bitmap_element *next = element->next;
+  bitmap_element *prev = element->prev;
+
+  gcc_checking_assert (!head->tree_form);
+
+  if (prev)
+    prev->next = next;
+
+  if (next)
+    next->prev = prev;
+
+  if (head->first == element)
+    head->first = next;
+
+  /* Since the first thing we try is to insert before current,
+     make current the next entry in preference to the previous.  */
+  if (head->current == element)
+    {
+      head->current = next != 0 ? next : prev;
+      if (head->current)
+	head->indx = head->current->indx;
+      else
+	head->indx = 0;
+    }
+
+  bitmap_elem_to_freelist (head, element);
+}
+
+/* Insert a new uninitialized element into bitmap HEAD after element
+   ELT.  If ELT is NULL, insert the element at the start.  Return the
+   new element.  */
+
+static bitmap_element *
+bitmap_list_insert_element_after (bitmap head,
+				  bitmap_element *elt, unsigned int indx)
+{
+  bitmap_element *node = bitmap_element_allocate (head);
+  node->indx = indx;
+
+  gcc_checking_assert (!head->tree_form);
+
+  if (!elt)
+    {
+      if (!head->current)
+	{
+	  head->current = node;
+	  head->indx = indx;
+	}
+      node->next = head->first;
+      if (node->next)
+	node->next->prev = node;
+      head->first = node;
+      node->prev = NULL;
+    }
+  else
+    {
+      gcc_checking_assert (head->current);
+      node->next = elt->next;
+      if (node->next)
+	node->next->prev = node;
+      elt->next = node;
+      node->prev = elt;
+    }
+  return node;
+}
+
+/* Return the element for INDX, or NULL if the element doesn't exist.  */
+
+static inline bitmap_element *
+bitmap_list_find_element (bitmap head, unsigned int indx)
+{
+  bitmap_element *element;
+  if (head->indx < indx)
+    /* INDX is beyond head->indx.  Search from head->current
+       forward.  */
+    for (element = head->current;
+	 element->next != 0 && element->indx < indx;
+	 element = element->next)
+      {
+	if (GATHER_STATISTICS)
+	  bitmap_descriptors[head->descriptor_id]->search_iter++;
+      }
+
+  else if (head->indx / 2 < indx)
+    /* INDX is less than head->indx and closer to head->indx than to
+       0.  Search from head->current backward.  */
+    for (element = head->current;
+	 element->prev != 0 && element->indx > indx;
+	 element = element->prev)
+      {
+	if (GATHER_STATISTICS)
+	  bitmap_descriptors[head->descriptor_id]->search_iter++;
+      }
+
+  else
+    /* INDX is less than head->indx and closer to 0 than to
+       head->indx.  Search from head->first forward.  */
+    for (element = head->first;
+	 element->next != 0 && element->indx < indx;
+	 element = element->next)
+      if (GATHER_STATISTICS)
+	{
+	  bitmap_descriptors[head->descriptor_id]->search_iter++;
+	}
+
+  /* `element' is the nearest to the one we want.  If it's not the one we
+     want, the one we want doesn't exist.  */
+  gcc_checking_assert (element != NULL);
+  head->current = element;
+  head->indx = element->indx;
+  if (element->indx != indx)
+    element = 0;
+  return element;
+}
+
+

+/* Splay-tree view of bitmaps.
+
+   This is an almost one-to-one the implementatin of the simple top-down
+   splay tree in Sleator and Tarjan's "Self-adjusting Binary Search Trees".
+   It is probably not the most efficient form of splay trees, but it should
+   be good enough to experiment with this idea of bitmaps-as-trees.
+   
+   For all functions below, the variable or function argument "t" is a node
+   in the tree, and "e" is a temporary or new node in the tree.  The rest
+   is sufficiently straigh-forward (and very well explained in the paper)
+   that comment would only clutter things.  */
+
+static inline void
+bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l)
+{
+  l->next = t;
+  l = t;
+  t = t->next;
+}
+
+static inline void
+bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r)
+{
+  r->prev = t;
+  r = t;
+  t = t->prev;
+}
+
+static inline void
+bitmap_tree_rotate_left (bitmap_element * &t)
+{
+  bitmap_element *e = t->next;
+  t->next = t->next->prev;
+  e->prev = t;
+  t = e;
+}
+
+static inline void
+bitmap_tree_rotate_right (bitmap_element * &t)
+{
+  bitmap_element *e = t->prev;
+  t->prev = t->prev->next;
+  e->next = t;
+  t = e;
+}
+
+static bitmap_element *
+bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx)
+{
+  bitmap_element N, *l, *r;
+
+  if (t == NULL)
+    return NULL;
+
+  N.prev = N.next = NULL;
+  l = r = &N;
+
+  while (indx != t->indx)
+    {
+      if (GATHER_STATISTICS)
+	bitmap_descriptors[head->descriptor_id]->search_iter++;
+
+      if (indx < t->indx)
+	{
+	  if (t->prev != NULL && indx < t->prev->indx)
+	    bitmap_tree_rotate_right (t);
+	  if (t->prev == NULL)
+	    break;
+	  bitmap_tree_link_right (t, r);
+	}
+      else if (indx > t->indx)
+	{
+	  if (t->next != NULL && indx > t->next->indx)
+	    bitmap_tree_rotate_left (t);
+	  if (t->next == NULL)
+	    break;
+	  bitmap_tree_link_left (t, l);
+	}
+    }
+
+  l->next = t->prev;
+  r->prev = t->next;
+  t->prev = N.next;
+  t->next = N.prev;
+  return t;
+}
+
+/* Link bitmap element E into the current bitmap splay tree.  */
+
+static inline void
+bitmap_tree_link_element (bitmap head, bitmap_element *e)
+{
+  if (head->first == NULL)
+    e->prev = e->next = NULL;
+  else
+    {
+      bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
+      if (e->indx < t->indx)
+	{
+	  e->prev = t->prev;
+	  e->next = t;
+	  t->prev = NULL;
+	}
+      else if (e->indx > t->indx)
+	{
+	  e->next = t->next;
+	  e->prev = t;
+	  t->next = NULL;
+	}
+      else
+	gcc_unreachable ();
+    }
+  head->first = e;
+  head->current = e;
+  head->indx = e->indx;
+}
+
+/* Unlink bitmap element E from the current bitmap splay tree,
+   and return it to the freelist.  */
+
+static void
+bitmap_tree_unlink_element (bitmap head, bitmap_element *e)
+{
+  bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
+
+  gcc_checking_assert (t == e);
+
+  if (e->prev == NULL)
+    t = e->next;
+  else
+    {
+      t = bitmap_tree_splay (head, e->prev, e->indx);
+      t->next = e->next;
+    }
+  head->first = t;
+  head->current = t;
+  head->indx = (t != NULL) ? t->indx : 0;
+
+  bitmap_elem_to_freelist (head, e);
+}
+
+/* Return the element for INDX, or NULL if the element doesn't exist.  */
+
+static inline bitmap_element *
+bitmap_tree_find_element (bitmap head, unsigned int indx)
+{
+  bitmap_element *element = bitmap_tree_splay (head, head->first, indx);
+  gcc_checking_assert (element != NULL);
+  head->first = element;
+  head->current = element;
+  head->indx = element->indx;
+  if (element->indx != indx)
+    element = 0;
+  return element;
+}
+

+/* Converting bitmap views from linked-list to tree and vice versa.  */
+
+/* Splice element E and all elements with a larger index from
+   bitmap HEAD, convert the spliced elements to the linked-list
+   view, and return the head of the list (which should be E again),  */
+
+static bitmap_element *
+bitmap_tree_listify_from (bitmap head, bitmap_element *e)
+{
+  bitmap_element *t, *erb;
+
+  /* Detach the right branch from E (all elements with indx > E->indx),
+     and splay E to the root.  */
+  erb = e->next;
+  e->next = NULL;
+  t = bitmap_tree_splay (head, head->first, e->indx);
+  gcc_checking_assert (t == e);
+
+  if (e->prev == NULL)
+    t = e->next;
+  else
+    {
+      t = bitmap_tree_splay (head, e->prev, e->indx);
+      t->next = e->next;
+    }
+  head->first = t;
+  head->current = t;
+  head->indx = (t != NULL) ? t->indx : 0;
+
+  gcc_assert (e->prev == NULL);
+  e->next = erb;
+
+  /* The tree is now valid again.  Now we need to "un-tree" E.
+     It is imperative that a non-recursive implementation is used
+     for this, because splay trees have a worst case depth of O(E).
+     A recursive implementation would result in a stack overflow
+     for a sufficiently large, unbalanced bitmap tree.  */
+  vec<bitmap_element *> stack = vNULL;
+  vec<bitmap_element *> sorted_elements = vNULL;
+  bitmap_element *n = e;
+
+  while (true)
+    {
+      while (n != NULL)
+	{
+	  stack.safe_push (n);
+	  n = n->prev;
+	}
+
+      if (stack.is_empty ())
+	break;
+
+      n = stack.pop ();
+      sorted_elements.safe_push (n);
+      n = n->next;
+    }
+  stack.release ();
+
+  gcc_assert (sorted_elements[0] == e);
+
+  bitmap_element *prev = NULL;
+  unsigned ix;
+  FOR_EACH_VEC_ELT (sorted_elements, ix, n)
+    {
+      if (prev != NULL)
+        prev->next = n;
+      n->prev = prev;
+      n->next = NULL;
+    }
+  sorted_elements.release ();
+
+  return e;
+}
 
-/* Clear a bitmap by freeing the linked list.  */
+/* Convert bitmap HEAD from splay-tree view to linked-list view.  */
+
+void
+bitmap_list_view (bitmap head)
+{
+  bitmap_element *ptr;
+
+  head->tree_form = 0;
+  if (! head->first)
+    return;
+
+  ptr = head->first;
+  while (ptr->prev)
+    ptr = ptr->prev;
+  head->first = bitmap_tree_listify_from (head, ptr);
+
+  head->current = head->first;
+  head->indx = head->first->indx;
+}
+
+/* Convert bitmap HEAD from linked-list view to splay-tree view.
+   This is simply a matter of dropping the prev or next pointers
+   and setting the tree_form flag.  The tree will balance itself
+   if and when it is used.  */
+
+void
+bitmap_tree_view (bitmap head)
+{
+  bitmap_element *ptr;
+
+  head->tree_form = 1;
+  if (! head->first)
+    return;
+
+  ptr = head->first;
+  while (ptr)
+    {
+      ptr->prev = NULL;
+      ptr = ptr->next;
+    }
+  head->current = head->first;
+  head->indx = head->first->indx;
+}
+

+/* Clear a bitmap by freeing all its elements.  */
 
 void
 bitmap_clear (bitmap head)
 {
-  if (head->first)
-    bitmap_elt_clear_from (head, head->first);
+  if (head->first == NULL)
+    return;
+  if (head->tree_form)
+    {
+      bitmap_element *e, *t;
+      for (e = head->first; e->prev; e = e->prev)
+	/* Loop to find the element with the smallest index.  */ ;
+      t = bitmap_tree_splay (head, head->first, e->indx);
+      gcc_checking_assert (t == e);
+      head->first = t;
+    }
+  bitmap_elt_clear_from (head, head->first);
 }
 

 /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
@@ -427,96 +868,6 @@ bitmap_element_zerop (const bitmap_eleme
 #endif
 }
 

-/* Link the bitmap element into the current bitmap linked list.  */
-
-static inline void
-bitmap_element_link (bitmap head, bitmap_element *element)
-{
-  unsigned int indx = element->indx;
-  bitmap_element *ptr;
-
-  /* If this is the first and only element, set it in.  */
-  if (head->first == 0)
-    {
-      element->next = element->prev = 0;
-      head->first = element;
-    }
-
-  /* If this index is less than that of the current element, it goes someplace
-     before the current element.  */
-  else if (indx < head->indx)
-    {
-      for (ptr = head->current;
-	   ptr->prev != 0 && ptr->prev->indx > indx;
-	   ptr = ptr->prev)
-	;
-
-      if (ptr->prev)
-	ptr->prev->next = element;
-      else
-	head->first = element;
-
-      element->prev = ptr->prev;
-      element->next = ptr;
-      ptr->prev = element;
-    }
-
-  /* Otherwise, it must go someplace after the current element.  */
-  else
-    {
-      for (ptr = head->current;
-	   ptr->next != 0 && ptr->next->indx < indx;
-	   ptr = ptr->next)
-	;
-
-      if (ptr->next)
-	ptr->next->prev = element;
-
-      element->next = ptr->next;
-      element->prev = ptr;
-      ptr->next = element;
-    }
-
-  /* Set up so this is the first element searched.  */
-  head->current = element;
-  head->indx = indx;
-}
-
-/* Insert a new uninitialized element into bitmap HEAD after element
-   ELT.  If ELT is NULL, insert the element at the start.  Return the
-   new element.  */
-
-static bitmap_element *
-bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
-{
-  bitmap_element *node = bitmap_element_allocate (head);
-  node->indx = indx;
-
-  if (!elt)
-    {
-      if (!head->current)
-	{
-	  head->current = node;
-	  head->indx = indx;
-	}
-      node->next = head->first;
-      if (node->next)
-	node->next->prev = node;
-      head->first = node;
-      node->prev = NULL;
-    }
-  else
-    {
-      gcc_checking_assert (head->current);
-      node->next = elt->next;
-      if (node->next)
-	node->next->prev = node;
-      elt->next = node;
-      node->prev = elt;
-    }
-  return node;
-}
-

 /* Copy a bitmap to another bitmap.  */
 
 void
@@ -525,6 +876,8 @@ bitmap_copy (bitmap to, const_bitmap fro
   const bitmap_element *from_ptr;
   bitmap_element *to_ptr = 0;
 
+  gcc_checking_assert (!to->tree_form && !from->tree_form);
+
   bitmap_clear (to);
 
   /* Copy elements in forward direction one at a time.  */
@@ -535,8 +888,9 @@ bitmap_copy (bitmap to, const_bitmap fro
       to_elt->indx = from_ptr->indx;
       memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
 
-      /* Here we have a special case of bitmap_element_link, for the case
-	 where we know the links are being entered in sequence.  */
+      /* Here we have a special case of bitmap_list_link_element,
+         for the case where we know the links are being entered
+	 in sequence.  */
       if (to_ptr == 0)
 	{
 	  to->first = to->current = to_elt;
@@ -572,45 +926,10 @@ bitmap_find_bit (bitmap head, unsigned i
   if (GATHER_STATISTICS)
     bitmap_descriptors[head->descriptor_id]->nsearches++;
 
-  if (head->indx < indx)
-    /* INDX is beyond head->indx.  Search from head->current
-       forward.  */
-    for (element = head->current;
-	 element->next != 0 && element->indx < indx;
-	 element = element->next)
-      {
-	if (GATHER_STATISTICS)
-	  bitmap_descriptors[head->descriptor_id]->search_iter++;
-      }
-
-  else if (head->indx / 2 < indx)
-    /* INDX is less than head->indx and closer to head->indx than to
-       0.  Search from head->current backward.  */
-    for (element = head->current;
-	 element->prev != 0 && element->indx > indx;
-	 element = element->prev)
-      {
-	if (GATHER_STATISTICS)
-	  bitmap_descriptors[head->descriptor_id]->search_iter++;
-      }
-
+  if (!head->tree_form)
+    element = bitmap_list_find_element (head, indx);
   else
-    /* INDX is less than head->indx and closer to 0 than to
-       head->indx.  Search from head->first forward.  */
-    for (element = head->first;
-	 element->next != 0 && element->indx < indx;
-	 element = element->next)
-      if (GATHER_STATISTICS)
-	{
-	  bitmap_descriptors[head->descriptor_id]->search_iter++;
-	}
-
-  /* `element' is the nearest to the one we want.  If it's not the one we
-     want, the one we want doesn't exist.  */
-  head->current = element;
-  head->indx = element->indx;
-  if (element != 0 && element->indx != indx)
-    element = 0;
+    element = bitmap_tree_find_element (head, indx);
 
   return element;
 }
@@ -634,7 +953,12 @@ bitmap_clear_bit (bitmap head, int bit)
 	  /* If we cleared the entire word, free up the element.  */
 	  if (!ptr->bits[word_num]
 	      && bitmap_element_zerop (ptr))
-	    bitmap_element_free (head, ptr);
+	    {
+	      if (!head->tree_form)
+		bitmap_list_unlink_element (head, ptr);
+	      else
+		bitmap_tree_unlink_element (head, ptr);
+	    }
 	}
 
       return res;
@@ -653,21 +977,22 @@ bitmap_set_bit (bitmap head, int bit)
   unsigned bit_num  = bit % BITMAP_WORD_BITS;
   BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
 
-  if (ptr == 0)
-    {
-      ptr = bitmap_element_allocate (head);
-      ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
-      ptr->bits[word_num] = bit_val;
-      bitmap_element_link (head, ptr);
-      return true;
-    }
-  else
+  if (ptr != 0)
     {
       bool res = (ptr->bits[word_num] & bit_val) == 0;
       if (res)
 	ptr->bits[word_num] |= bit_val;
       return res;
     }
+
+  ptr = bitmap_element_allocate (head);
+  ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
+  ptr->bits[word_num] = bit_val;
+  if (!head->tree_form)
+    bitmap_list_link_element (head, ptr);
+  else
+    bitmap_tree_link_element (head, ptr);
+  return true;
 }
 
 /* Return whether a bit is set within a bitmap.  */
@@ -724,13 +1049,14 @@ bitmap_count_bits (const_bitmap a)
   const bitmap_element *elt;
   unsigned ix;
 
+  gcc_checking_assert (!a->tree_form);
   for (elt = a->first; elt; elt = elt->next)
     {
       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 	{
 #if GCC_VERSION >= 3400
- 	  /* Note that popcountl matches BITMAP_WORD in type, so the actual size
-	 of BITMAP_WORD is not material.  */
+ 	  /* Note that popcountl matches BITMAP_WORD in type,
+	     so the actual size of BITMAP_WORD is not material.  */
 	  count += __builtin_popcountl (elt->bits[ix]);
 #else
 	  count += bitmap_popcount (elt->bits[ix]);
@@ -754,9 +1080,11 @@ bitmap_single_bit_set_p (const_bitmap a)
     return false;
 
   elt = a->first;
+
   /* As there are no completely empty bitmap elements, a second one
      means we have more than one bit set.  */
-  if (elt->next != NULL)
+  if (elt->next != NULL
+      && (!a->tree_form || elt->prev != NULL))
     return false;
 
   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
@@ -788,6 +1116,11 @@ bitmap_first_set_bit (const_bitmap a)
   unsigned ix;
 
   gcc_checking_assert (elt);
+
+  if (a->tree_form)
+    while (elt->prev)
+      elt = elt->prev;
+
   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
     {
@@ -839,8 +1172,11 @@ bitmap_last_set_bit (const_bitmap a)
   int ix;
 
   gcc_checking_assert (elt);
+
+  /* This works for linked-list and binary tree representation alike.  */
   while (elt->next)
     elt = elt->next;
+
   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
   for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
     {
@@ -882,6 +1218,7 @@ bitmap_and (bitmap dst, const_bitmap a,
   const bitmap_element *b_elt = b->first;
   bitmap_element *dst_prev = NULL;
 
+  gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
   gcc_assert (dst != a && dst != b);
 
   if (a == b)
@@ -903,7 +1240,8 @@ bitmap_and (bitmap dst, const_bitmap a,
 	  BITMAP_WORD ior = 0;
 
 	  if (!dst_elt)
-	    dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+	    dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+							a_elt->indx);
 	  else
 	    dst_elt->indx = a_elt->indx;
 	  for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
@@ -940,6 +1278,8 @@ bitmap_and_into (bitmap a, const_bitmap
   bitmap_element *next;
   bool changed = false;
 
+  gcc_checking_assert (!a->tree_form && !b->tree_form);
+
   if (a == b)
     return false;
 
@@ -948,7 +1288,7 @@ bitmap_and_into (bitmap a, const_bitmap
       if (a_elt->indx < b_elt->indx)
 	{
 	  next = a_elt->next;
-	  bitmap_element_free (a, a_elt);
+	  bitmap_list_unlink_element (a, a_elt);
 	  a_elt = next;
 	  changed = true;
 	}
@@ -970,7 +1310,7 @@ bitmap_and_into (bitmap a, const_bitmap
 	    }
 	  next = a_elt->next;
 	  if (!ior)
-	    bitmap_element_free (a, a_elt);
+	    bitmap_list_unlink_element (a, a_elt);
 	  a_elt = next;
 	  b_elt = b_elt->next;
 	}
@@ -1012,7 +1352,8 @@ bitmap_elt_copy (bitmap dst, bitmap_elem
     {
       changed = true;
       if (!dst_elt)
-	dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx);
+	dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+						    src_elt->indx);
       else
 	dst_elt->indx = src_elt->indx;
       memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
@@ -1034,6 +1375,7 @@ bitmap_and_compl (bitmap dst, const_bitm
   bitmap_element **dst_prev_pnext = &dst->first;
   bool changed = false;
 
+  gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
   gcc_assert (dst != a && dst != b);
 
   if (a == b)
@@ -1082,7 +1424,8 @@ bitmap_and_compl (bitmap dst, const_bitm
 	      bool new_element;
 	      if (!dst_elt || dst_elt->indx > a_elt->indx)
 		{
-		  dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+		  dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+							      a_elt->indx);
 		  new_element = true;
 		}
 	      else
@@ -1104,7 +1447,7 @@ bitmap_and_compl (bitmap dst, const_bitm
 	      else
 	        {
 	          changed |= !new_element;
-		  bitmap_element_free (dst, dst_elt);
+		  bitmap_list_unlink_element (dst, dst_elt);
 		  dst_elt = *dst_prev_pnext;
 		}
 	    }
@@ -1145,6 +1488,8 @@ bitmap_and_compl_into (bitmap a, const_b
   bitmap_element *next;
   BITMAP_WORD changed = 0;
 
+  gcc_checking_assert (!a->tree_form && !b->tree_form);
+
   if (a == b)
     {
       if (bitmap_empty_p (a))
@@ -1179,7 +1524,7 @@ bitmap_and_compl_into (bitmap a, const_b
 	    }
 	  next = a_elt->next;
 	  if (!ior)
-	    bitmap_element_free (a, a_elt);
+	    bitmap_list_unlink_element (a, a_elt);
 	  a_elt = next;
 	  b_elt = b_elt->next;
 	}
@@ -1197,6 +1542,8 @@ bitmap_set_range (bitmap head, unsigned
   bitmap_element *elt, *elt_prev;
   unsigned int i;
 
+  gcc_checking_assert (!head->tree_form);
+
   if (!count)
     return;
 
@@ -1213,7 +1560,7 @@ bitmap_set_range (bitmap head, unsigned
     {
       elt = bitmap_element_allocate (head);
       elt->indx = first_index;
-      bitmap_element_link (head, elt);
+      bitmap_list_link_element (head, elt);
     }
 
   gcc_checking_assert (elt->indx == first_index);
@@ -1230,7 +1577,7 @@ bitmap_set_range (bitmap head, unsigned
       unsigned int ix;
 
       if (!elt || elt->indx != i)
-	elt = bitmap_elt_insert_after (head, elt_prev, i);
+	elt = bitmap_list_insert_element_after (head, elt_prev, i);
 
       if (elt_start_bit <= start)
 	{
@@ -1296,6 +1643,8 @@ bitmap_clear_range (bitmap head, unsigne
   unsigned int first_index, end_bit_plus1, last_index;
   bitmap_element *elt;
 
+  gcc_checking_assert (!head->tree_form);
+
   if (!count)
     return;
 
@@ -1333,7 +1682,7 @@ bitmap_clear_range (bitmap head, unsigne
 
       if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
 	/* Get rid of the entire elt and go to the next one.  */
-	bitmap_element_free (head, elt);
+	bitmap_list_unlink_element (head, elt);
       else
 	{
 	  /* Going to have to knock out some bits in this elt.  */
@@ -1403,7 +1752,7 @@ bitmap_clear_range (bitmap head, unsigne
 	      }
 	  /* Check to see if there are any bits left.  */
 	  if (clear)
-	    bitmap_element_free (head, elt);
+	    bitmap_list_unlink_element (head, elt);
 	}
       elt = next_elt;
     }
@@ -1425,6 +1774,7 @@ bitmap_compl_and_into (bitmap a, const_b
   bitmap_element *a_prev = NULL;
   bitmap_element *next;
 
+  gcc_checking_assert (!a->tree_form && !b->tree_form);
   gcc_assert (a != b);
 
   if (bitmap_empty_p (a))
@@ -1445,13 +1795,13 @@ bitmap_compl_and_into (bitmap a, const_b
 	  /* A is before B.  Remove A */
 	  next = a_elt->next;
 	  a_prev = a_elt->prev;
-	  bitmap_element_free (a, a_elt);
+	  bitmap_list_unlink_element (a, a_elt);
 	  a_elt = next;
 	}
       else if (!a_elt || b_elt->indx < a_elt->indx)
 	{
 	  /* B is before A.  Copy B. */
-	  next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
+	  next = bitmap_list_insert_element_after (a, a_prev, b_elt->indx);
 	  memcpy (next->bits, b_elt->bits, sizeof (next->bits));
 	  a_prev = next;
 	  b_elt = b_elt->next;
@@ -1472,7 +1822,7 @@ bitmap_compl_and_into (bitmap a, const_b
 	    }
 	  next = a_elt->next;
 	  if (!ior)
-	    bitmap_element_free (a, a_elt);
+	    bitmap_list_unlink_element (a, a_elt);
 	  else
 	    a_prev = a_elt;
 	  a_elt = next;
@@ -1517,7 +1867,8 @@ bitmap_elt_ior (bitmap dst, bitmap_eleme
 	{
 	  changed = true;
 	  if (!dst_elt)
-	    dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+	    dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+							a_elt->indx);
 	  else
 	    dst_elt->indx = a_elt->indx;
 	  for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
@@ -1556,6 +1907,7 @@ bitmap_ior (bitmap dst, const_bitmap a,
   bitmap_element **dst_prev_pnext = &dst->first;
   bool changed = false;
 
+  gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
   gcc_assert (dst != a && dst != b);
 
   while (a_elt || b_elt)
@@ -1602,6 +1954,7 @@ bitmap_ior_into (bitmap a, const_bitmap
   bitmap_element **a_prev_pnext = &a->first;
   bool changed = false;
 
+  gcc_checking_assert (!a->tree_form && !b->tree_form);
   if (a == b)
     return false;
 
@@ -1640,7 +1993,9 @@ bitmap_xor (bitmap dst, const_bitmap a,
   const bitmap_element *b_elt = b->first;
   bitmap_element *dst_prev = NULL;
 
+  gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
   gcc_assert (dst != a && dst != b);
+
   if (a == b)
     {
       bitmap_clear (dst);
@@ -1656,7 +2011,8 @@ bitmap_xor (bitmap dst, const_bitmap a,
 	  BITMAP_WORD ior = 0;
 
 	  if (!dst_elt)
-	    dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+	    dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+							a_elt->indx);
 	  else
 	    dst_elt->indx = a_elt->indx;
 	  for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
@@ -1691,7 +2047,8 @@ bitmap_xor (bitmap dst, const_bitmap a,
 	    }
 
 	  if (!dst_elt)
-	    dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
+	    dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
+							src->indx);
 	  else
 	    dst_elt->indx = src->indx;
 	  memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
@@ -1716,6 +2073,8 @@ bitmap_xor_into (bitmap a, const_bitmap
   const bitmap_element *b_elt = b->first;
   bitmap_element *a_prev = NULL;
 
+  gcc_checking_assert (!a->tree_form && !b->tree_form);
+
   if (a == b)
     {
       bitmap_clear (a);
@@ -1727,7 +2086,8 @@ bitmap_xor_into (bitmap a, const_bitmap
       if (!a_elt || b_elt->indx < a_elt->indx)
 	{
 	  /* Copy b_elt.  */
-	  bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
+	  bitmap_element *dst = bitmap_list_insert_element_after (a, a_prev,
+								  b_elt->indx);
 	  memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
 	  a_prev = dst;
 	  b_elt = b_elt->next;
@@ -1755,7 +2115,7 @@ bitmap_xor_into (bitmap a, const_bitmap
 	  if (ior)
 	    a_prev = a_elt;
 	  else
-	    bitmap_element_free (a, a_elt);
+	    bitmap_list_unlink_element (a, a_elt);
 	  a_elt = next;
 	}
     }
@@ -1775,6 +2135,8 @@ bitmap_equal_p (const_bitmap a, const_bi
   const bitmap_element *b_elt;
   unsigned ix;
 
+  gcc_checking_assert (!a->tree_form && !b->tree_form);
+
   for (a_elt = a->first, b_elt = b->first;
        a_elt && b_elt;
        a_elt = a_elt->next, b_elt = b_elt->next)
@@ -1797,6 +2159,8 @@ bitmap_intersect_p (const_bitmap a, cons
   const bitmap_element *b_elt;
   unsigned ix;
 
+  gcc_checking_assert (!a->tree_form && !b->tree_form);
+
   for (a_elt = a->first, b_elt = b->first;
        a_elt && b_elt;)
     {
@@ -1824,6 +2188,9 @@ bitmap_intersect_compl_p (const_bitmap a
   const bitmap_element *a_elt;
   const bitmap_element *b_elt;
   unsigned ix;
+
+  gcc_checking_assert (!a->tree_form && !b->tree_form);
+
   for (a_elt = a->first, b_elt = b->first;
        a_elt && b_elt;)
     {
@@ -1858,6 +2225,9 @@ bitmap_ior_and_compl (bitmap dst, const_
   bitmap_element *dst_prev = NULL;
   bitmap_element **dst_prev_pnext = &dst->first;
 
+  gcc_checking_assert (!dst->tree_form
+		       && !a->tree_form && !b->tree_form
+		       && !kill->tree_form);
   gcc_assert (dst != a && dst != b && dst != kill);
 
   /* Special cases.  We don't bother checking for bitmap_equal_p (b, kill).  */
@@ -1948,16 +2318,18 @@ bitmap_ior_and_compl (bitmap dst, const_
   return changed;
 }
 
-/* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
+/* A |= (B & ~C).  Return true if A changes.  */
 
 bool
-bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2)
+bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c)
 {
   bitmap_head tmp;
   bool changed;
 
+  gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
+
   bitmap_initialize (&tmp, &bitmap_default_obstack);
-  bitmap_and_compl (&tmp, from1, from2);
+  bitmap_and_compl (&tmp, b, c);
   changed = bitmap_ior_into (a, &tmp);
   bitmap_clear (&tmp);
 
@@ -1978,6 +2350,8 @@ bitmap_ior_and_into (bitmap a, const_bit
   bool changed = false;
   unsigned ix;
 
+  gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
+
   if (b == c)
     return bitmap_ior_into (a, b);
   if (bitmap_empty_p (b) || bitmap_empty_p (c))
@@ -2044,6 +2418,7 @@ bitmap_ior_and_into (bitmap a, const_bit
 }
 
 /* Compute hash of bitmap (for purposes of hashing).  */
+
 hashval_t
 bitmap_hash (const_bitmap head)
 {
@@ -2051,6 +2426,8 @@ bitmap_hash (const_bitmap head)
   BITMAP_WORD hash = 0;
   int ix;
 
+  gcc_checking_assert (!head->tree_form);
+
   for (ptr = head->first; ptr; ptr = ptr->next)
     {
       hash ^= ptr->indx;
@@ -2064,9 +2441,13 @@ bitmap_hash (const_bitmap head)
 /* Debugging function to print out the contents of a bitmap.  */
 
 DEBUG_FUNCTION void
-debug_bitmap_file (FILE *file, const_bitmap head)
+debug_bitmap_file (FILE *file, bitmap head)
 {
   const bitmap_element *ptr;
+  bool tree_form = head->tree_form;
+
+  if (tree_form)
+    bitmap_list_view (head);
 
   fprintf (file, "\nfirst = " HOST_PTR_PRINTF
 	   " current = " HOST_PTR_PRINTF " indx = %u\n",
@@ -2098,13 +2479,16 @@ debug_bitmap_file (FILE *file, const_bit
 
       fprintf (file, " }\n");
     }
+
+  if (tree_form)
+    bitmap_tree_view (head);
 }
 
 /* Function to be called from the debugger to print the contents
    of a bitmap.  */
 
 DEBUG_FUNCTION void
-debug_bitmap (const_bitmap head)
+debug_bitmap (bitmap head)
 {
   debug_bitmap_file (stdout, head);
 }
@@ -2113,11 +2497,15 @@ debug_bitmap (const_bitmap head)
    it does not print anything but the bits.  */
 
 DEBUG_FUNCTION void
-bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix)
+bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
 {
   const char *comma = "";
   unsigned i;
   bitmap_iterator bi;
+  bool tree_form = head->tree_form;
+
+  if (tree_form)
+    bitmap_list_view (head);
 
   fputs (prefix, file);
   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
@@ -2126,6 +2514,9 @@ bitmap_print (FILE *file, const_bitmap h
       comma = ", ";
     }
   fputs (suffix, file);
+
+  if (tree_form)
+    bitmap_tree_view (head);
 }
 
 
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)


More information about the Gcc-patches mailing list