public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] Add splay-tree "view" for bitmap
@ 2018-10-18 13:58 Richard Biener
  2018-10-18 15:43 ` Richard Sandiford
                   ` (2 more replies)
  0 siblings, 3 replies; 15+ messages in thread
From: Richard Biener @ 2018-10-18 13:58 UTC (permalink / raw)
  To: gcc-patches; +Cc: stevenb.gcc

[-- Attachment #1: Type: text/plain, Size: 65408 bytes --]


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 <steven@gcc.gnu.org>
	Richard Biener  <rguenther@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);
 \f
+/* Bitmap memory management.  */
 
-/* Add ELEM to the appropriate freelist.  */
+/* Add ELT to the appropriate freelist.  */
 static inline void
 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
 {
   bitmap_obstack *bit_obstack = head->obstack;
 
+  if (GATHER_STATISTICS)
+    register_overhead (head, -((int)sizeof (bitmap_element)));
+
   elt->next = NULL;
   elt->indx = -1;
   if (bit_obstack)
@@ -79,41 +77,6 @@ bitmap_elem_to_freelist (bitmap head, bi
     }
 }
 
-/* Free a bitmap element.  Since these are allocated off the
-   bitmap_obstack, "free" actually means "put onto the freelist".  */
-
-static inline void
-bitmap_element_free (bitmap head, bitmap_element *elt)
-{
-  bitmap_element *next = elt->next;
-  bitmap_element *prev = elt->prev;
-
-  if (prev)
-    prev->next = next;
-
-  if (next)
-    next->prev = prev;
-
-  if (head->first == elt)
-    head->first = next;
-
-  /* Since the first thing we try is to insert before current,
-     make current the next entry in preference to the previous.  */
-  if (head->current == elt)
-    {
-      head->current = next != 0 ? next : prev;
-      if (head->current)
-	head->indx = head->current->indx;
-      else
-	head->indx = 0;
-    }
-
-  if (GATHER_STATISTICS)
-    register_overhead (head, -((int)sizeof (bitmap_element)));
-
-  bitmap_elem_to_freelist (head, elt);
-}
-\f
 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
 
 static inline bitmap_element *
@@ -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;
+    }
+}
+\f
+/* Linked-list view of bitmaps.
+
+   In this representation, the bitmap elements form a double-linked list
+   with elements sorted by increasing index.  */
+
+/* Link the bitmap element into the current bitmap linked list.  */
+
+static inline void
+bitmap_list_link_element (bitmap head, bitmap_element *element)
+{
+  unsigned int indx = element->indx;
+  bitmap_element *ptr;
+
+  gcc_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;
+}
+
+\f
+/* Splay-tree view of bitmaps.
+
+   This is an almost one-to-one the implementatin of the simple top-down
+   splay tree in Sleator and Tarjan's "Self-adjusting Binary Search Trees".
+   It is probably not the most efficient form of splay trees, but it should
+   be good enough to experiment with this idea of bitmaps-as-trees.
+   
+   For all functions below, the variable or function argument "t" is a node
+   in the tree, and "e" is a temporary or new node in the tree.  The rest
+   is sufficiently straigh-forward (and very well explained in the paper)
+   that comment would only clutter things.  */
+
+static inline void
+bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l)
+{
+  l->next = t;
+  l = t;
+  t = t->next;
+}
+
+static inline void
+bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r)
+{
+  r->prev = t;
+  r = t;
+  t = t->prev;
+}
+
+static inline void
+bitmap_tree_rotate_left (bitmap_element * &t)
+{
+  bitmap_element *e = t->next;
+  t->next = t->next->prev;
+  e->prev = t;
+  t = e;
+}
+
+static inline void
+bitmap_tree_rotate_right (bitmap_element * &t)
+{
+  bitmap_element *e = t->prev;
+  t->prev = t->prev->next;
+  e->next = t;
+  t = e;
+}
+
+static bitmap_element *
+bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx)
+{
+  bitmap_element N, *l, *r;
+
+  if (t == NULL)
+    return NULL;
+
+  bitmap_usage *usage = NULL;
+  if (GATHER_STATISTICS)
+    usage = bitmap_mem_desc.get_descriptor_for_instance (head);
+
+  N.prev = N.next = NULL;
+  l = r = &N;
+
+  while (indx != t->indx)
+    {
+      if (GATHER_STATISTICS && usage)
+	usage->m_search_iter++;
+
+      if (indx < t->indx)
+	{
+	  if (t->prev != NULL && indx < t->prev->indx)
+	    bitmap_tree_rotate_right (t);
+	  if (t->prev == NULL)
+	    break;
+	  bitmap_tree_link_right (t, r);
+	}
+      else if (indx > t->indx)
+	{
+	  if (t->next != NULL && indx > t->next->indx)
+	    bitmap_tree_rotate_left (t);
+	  if (t->next == NULL)
+	    break;
+	  bitmap_tree_link_left (t, l);
+	}
+    }
+
+  l->next = t->prev;
+  r->prev = t->next;
+  t->prev = N.next;
+  t->next = N.prev;
+  return t;
+}
+
+/* Link bitmap element E into the current bitmap splay tree.  */
+
+static inline void
+bitmap_tree_link_element (bitmap head, bitmap_element *e)
+{
+  if (head->first == NULL)
+    e->prev = e->next = NULL;
+  else
+    {
+      bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
+      if (e->indx < t->indx)
+	{
+	  e->prev = t->prev;
+	  e->next = t;
+	  t->prev = NULL;
+	}
+      else if (e->indx > t->indx)
+	{
+	  e->next = t->next;
+	  e->prev = t;
+	  t->next = NULL;
+	}
+      else
+	gcc_unreachable ();
+    }
+  head->first = e;
+  head->current = e;
+  head->indx = e->indx;
+}
+
+/* Unlink bitmap element E from the current bitmap splay tree,
+   and return it to the freelist.  */
+
+static void
+bitmap_tree_unlink_element (bitmap head, bitmap_element *e)
+{
+  bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
+
+  gcc_checking_assert (t == e);
+
+  if (e->prev == NULL)
+    t = e->next;
+  else
+    {
+      t = bitmap_tree_splay (head, e->prev, e->indx);
+      t->next = e->next;
+    }
+  head->first = t;
+  head->current = t;
+  head->indx = (t != NULL) ? t->indx : 0;
+
+  bitmap_elem_to_freelist (head, e);
+}
+
+/* Return the element for INDX, or NULL if the element doesn't exist.  */
+
+static inline bitmap_element *
+bitmap_tree_find_element (bitmap head, unsigned int indx)
+{
+  bitmap_element *element = bitmap_tree_splay (head, head->first, indx);
+  gcc_checking_assert (element != NULL);
+  head->first = element;
+  head->current = element;
+  head->indx = element->indx;
+  if (element->indx != indx)
+    element = 0;
+  return element;
+}
+\f
+/* Converting bitmap views from linked-list to tree and vice versa.  */
+
+/* Splice element E and all elements with a larger index from
+   bitmap HEAD, convert the spliced elements to the linked-list
+   view, and return the head of the list (which should be E again),  */
+
+static bitmap_element *
+bitmap_tree_listify_from (bitmap head, bitmap_element *e)
+{
+  bitmap_element *t, *erb;
+
+  /* Detach the right branch from E (all elements with indx > E->indx),
+     and splay E to the root.  */
+  erb = e->next;
+  e->next = NULL;
+  t = bitmap_tree_splay (head, head->first, e->indx);
+  gcc_checking_assert (t == e);
+
+  /* Because E has no right branch, and we rotated it to the root,
+     the left branch is the new root.  */
+  t = e->prev;
+  head->first = t;
+  head->current = t;
+  head->indx = (t != NULL) ? t->indx : 0;
+
+  /* Detach the tree from E, and re-attach the right branch of E.  */
+  e->prev = NULL;
+  e->next = erb;
+
+  /* The tree is now valid again.  Now we need to "un-tree" E.
+     It is imperative that a non-recursive implementation is used
+     for this, because splay trees have a worst case depth of O(N)
+     for a tree with N nodes.  A recursive implementation could
+     result in a stack overflow for a sufficiently large, unbalanced
+     bitmap tree.  */
+
+  vec<bitmap_element *> stack = vNULL;
+  vec<bitmap_element *> sorted_elements = vNULL;
+  bitmap_element *n = e;
+
+  while (true)
+    {
+      while (n != NULL)
+	{
+	  stack.safe_push (n);
+	  n = n->prev;
+	}
+
+      if (stack.is_empty ())
+	break;
+
+      n = stack.pop ();
+      sorted_elements.safe_push (n);
+      n = n->next;
+    }
+  stack.release ();
+
+  gcc_assert (sorted_elements[0] == e);
 
-  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;
+}
+\f
+/* Clear a bitmap by freeing all its elements.  */
 
 void
 bitmap_clear (bitmap head)
 {
-  if (head->first)
-    bitmap_elt_clear_from (head, head->first);
+  if (head->first == NULL)
+    return;
+  if (head->tree_form)
+    {
+      bitmap_element *e, *t;
+      for (e = head->first; e->prev; e = e->prev)
+	/* Loop to find the element with the smallest index.  */ ;
+      t = bitmap_tree_splay (head, head->first, e->indx);
+      gcc_checking_assert (t == e);
+      head->first = t;
+    }
+  bitmap_elt_clear_from (head, head->first);
 }
 \f
 /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
@@ -344,96 +783,6 @@ bitmap_element_zerop (const bitmap_eleme
 #endif
 }
 \f
-/* Link the bitmap element into the current bitmap linked list.  */
-
-static inline void
-bitmap_element_link (bitmap head, bitmap_element *element)
-{
-  unsigned int indx = element->indx;
-  bitmap_element *ptr;
-
-  /* If this is the first and only element, set it in.  */
-  if (head->first == 0)
-    {
-      element->next = element->prev = 0;
-      head->first = element;
-    }
-
-  /* If this index is less than that of the current element, it goes someplace
-     before the current element.  */
-  else if (indx < head->indx)
-    {
-      for (ptr = head->current;
-	   ptr->prev != 0 && ptr->prev->indx > indx;
-	   ptr = ptr->prev)
-	;
-
-      if (ptr->prev)
-	ptr->prev->next = element;
-      else
-	head->first = element;
-
-      element->prev = ptr->prev;
-      element->next = ptr;
-      ptr->prev = element;
-    }
-
-  /* Otherwise, it must go someplace after the current element.  */
-  else
-    {
-      for (ptr = head->current;
-	   ptr->next != 0 && ptr->next->indx < indx;
-	   ptr = ptr->next)
-	;
-
-      if (ptr->next)
-	ptr->next->prev = element;
-
-      element->next = ptr->next;
-      element->prev = ptr;
-      ptr->next = element;
-    }
-
-  /* Set up so this is the first element searched.  */
-  head->current = element;
-  head->indx = indx;
-}
-
-/* Insert a new uninitialized element into bitmap HEAD after element
-   ELT.  If ELT is NULL, insert the element at the start.  Return the
-   new element.  */
-
-static bitmap_element *
-bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
-{
-  bitmap_element *node = bitmap_element_allocate (head);
-  node->indx = indx;
-
-  if (!elt)
-    {
-      if (!head->current)
-	{
-	  head->current = node;
-	  head->indx = indx;
-	}
-      node->next = head->first;
-      if (node->next)
-	node->next->prev = node;
-      head->first = node;
-      node->prev = NULL;
-    }
-  else
-    {
-      gcc_checking_assert (head->current);
-      node->next = elt->next;
-      if (node->next)
-	node->next->prev = node;
-      elt->next = node;
-      node->prev = elt;
-    }
-  return node;
-}
-\f
 /* Copy a bitmap to another bitmap.  */
 
 void
@@ -442,6 +791,8 @@ bitmap_copy (bitmap to, const_bitmap fro
   const bitmap_element *from_ptr;
   bitmap_element *to_ptr = 0;
 
+  gcc_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)
 }
 
 \f
+/* 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);

^ permalink raw reply	[flat|nested] 15+ messages in thread
end of thread, other threads:[~2018-10-22 10:31 UTC | newest]

Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-10-18 13:58 [PATCH] Add splay-tree "view" for bitmap Richard Biener
2018-10-18 15:43 ` Richard Sandiford
2018-10-18 15:46   ` Richard Biener
2018-10-18 22:27     ` Richard Sandiford
2018-10-19  7:20       ` Richard Biener
2018-10-19  8:44         ` Richard Sandiford
2018-10-19 13:33           ` Richard Biener
2018-10-19 14:32             ` Richard Biener
2018-10-20 12:38             ` Richard Sandiford
2018-10-22 12:17               ` Richard Biener
2018-10-19  9:10         ` Steven Bosscher
2018-10-19 13:14           ` Richard Biener
2018-10-18 15:53 ` David Malcolm
2018-10-19 13:37   ` Richard Biener
2018-10-18 18:01 ` Jeff Law

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).