[PATCH] Support bitmap_copy across representations

[PATCH] Support bitmap_copy across representations

[Richard Biener]

The following started as making the backward threader m_imports
use the tree representation.  Since that interfaces to a list
representation bitmap in ranger by copying rewriting the tree
to list to perform the copy is inefficient in that it loses
balancing.  The following adds bitmap_copy_tree_to_list and
integrates it with the generic bitmap_copy routine.  For symmetry
I also added list to tree copy, relying on auto-balancing, and
tree to tree copy which I didn't optimize to preserve the
source balancing but instead use bitmap_copy_tree_to_list and
have the result auto-balanced again.

I've only exercised the tree to list path and I won't actually
end up using it but it's at least worth posting.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Worth pushing?

	* bitmap.h: Document set_copy aka bitmap_copy as usable
	for tree representation.
	* bitmap.cc (bitmap_copy_tree_to_list): New helper.
	(bitmap_copy): Support copying all bitmap representation
	combinations.
---
 gcc/bitmap.cc | 78 +++++++++++++++++++++++++++++++++++++++++++++++++--
 gcc/bitmap.h  |  6 +++-
 2 files changed, 81 insertions(+), 3 deletions(-)

diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc
index 88c329f9325..d9520397992 100644
--- a/gcc/bitmap.cc
+++ b/gcc/bitmap.cc
@@ -847,6 +847,58 @@ bitmap_element_zerop (const bitmap_element *element)
 #endif
 }
 \f
+/* Copy bitmap FROM which is in tree form to bitmap TO in list form.  */
+
+static void
+bitmap_copy_tree_to_list (bitmap to, const_bitmap from)
+{
+  bitmap_element *to_ptr = nullptr;
+
+  gcc_checking_assert (!to->tree_form && from->tree_form);
+
+  /* Do like bitmap_tree_to_vec but populate the destination bitmap
+     instead of a vector.  */
+  auto_vec<bitmap_element *, 32> stack;
+  bitmap_element *e = from->first;
+  while (true)
+    {
+      while (e != NULL)
+	{
+	  stack.safe_push (e);
+	  e = e->prev;
+	}
+      if (stack.is_empty ())
+	break;
+
+      bitmap_element *from_ptr = stack.pop ();
+	{
+	  bitmap_element *to_elt = bitmap_element_allocate (to);
+
+	  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_list_link_element,
+	     for the case where we know the links are being entered
+	     in sequence.  */
+	  if (to_ptr == nullptr)
+	    {
+	      to->first = to->current = to_elt;
+	      to->indx = from_ptr->indx;
+	      to_elt->next = to_elt->prev = nullptr;
+	    }
+	  else
+	    {
+	      to_elt->prev = to_ptr;
+	      to_elt->next = nullptr;
+	      to_ptr->next = to_elt;
+	    }
+
+	  to_ptr = to_elt;
+	}
+      e = from_ptr->next;
+    }
+}
+
 /* Copy a bitmap to another bitmap.  */
 
 void
@@ -854,11 +906,29 @@ bitmap_copy (bitmap to, const_bitmap from)
 {
   const bitmap_element *from_ptr;
   bitmap_element *to_ptr = 0;
-
-  gcc_checking_assert (!to->tree_form && !from->tree_form);
+  bool to_tree = to->tree_form;
 
   bitmap_clear (to);
 
+  /* From tree form first copy to list form, avoiding debalancing from,
+     then if the result is in tree form have it rebalance itself.  */
+  if (from->tree_form)
+    {
+      if (to_tree)
+	bitmap_list_view (to);
+      bitmap_copy_tree_to_list (to, from);
+      if (to_tree)
+	bitmap_tree_view (to);
+      return;
+    }
+
+  /* We are copying from list form - first copy the list representation
+     so temporarily switch the destination to list form.  */
+  if (to_tree)
+    bitmap_list_view (to);
+
+  gcc_checking_assert (!to->tree_form && !from->tree_form);
+
   /* Copy elements in forward direction one at a time.  */
   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
     {
@@ -885,6 +955,10 @@ bitmap_copy (bitmap to, const_bitmap from)
 
       to_ptr = to_elt;
     }
+
+  /* To tree, result will balance itself.  */
+  if (to_tree)
+    bitmap_tree_view (to);
 }
 
 /* Move a bitmap to another bitmap.  */
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 7fba443aff1..9a007855d0c 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -139,11 +139,15 @@ along with GCC; see the file COPYING3.  If not see
      * add_member
      * remove_member
 
+   Additionally both representations support enumeration of the
+   members in O(E) time for the following operations:
+
+     * set_copy			: bitmap_copy
+
    Additionally, the linked-list sparse set representation supports
    enumeration of the members in O(E) time:
 
      * forall			: EXECUTE_IF_SET_IN_BITMAP
-     * set_copy			: bitmap_copy
      * set_intersection		: bitmap_intersect_p /
 				  bitmap_and / bitmap_and_into /
 				  EXECUTE_IF_AND_IN_BITMAP
-- 
2.35.3

Re: [PATCH] Support bitmap_copy across representations

[Jeff Law]

On 8/17/2022 5:11 AM, Richard Biener via Gcc-patches wrote:
> The following started as making the backward threader m_imports
> use the tree representation.  Since that interfaces to a list
> representation bitmap in ranger by copying rewriting the tree
> to list to perform the copy is inefficient in that it loses
> balancing.  The following adds bitmap_copy_tree_to_list and
> integrates it with the generic bitmap_copy routine.  For symmetry
> I also added list to tree copy, relying on auto-balancing, and
> tree to tree copy which I didn't optimize to preserve the
> source balancing but instead use bitmap_copy_tree_to_list and
> have the result auto-balanced again.
>
> I've only exercised the tree to list path and I won't actually
> end up using it but it's at least worth posting.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> Worth pushing?
>
> 	* bitmap.h: Document set_copy aka bitmap_copy as usable
> 	for tree representation.
> 	* bitmap.cc (bitmap_copy_tree_to_list): New helper.
> 	(bitmap_copy): Support copying all bitmap representation
> 	combinations.
I'd lean against unless you expect to be using it.   But it's not a 
strongly held opinion.

jeff

[PATCH] Support bitmap_copy across representations

[Richard Biener]

The following started as making the backward threader m_imports
use the tree representation.  Since that interfaces to a list
representation bitmap in ranger by copying rewriting the tree
to list to perform the copy is inefficient in that it loses
balancing.  The following adds bitmap_copy_tree_to_list and
integrates it with the generic bitmap_copy routine.  For symmetry
I also added list to tree copy, relying on auto-balancing, and
tree to tree copy which I didn't optimize to preserve the
source balancing but instead use bitmap_copy_tree_to_list and
have the result auto-balanced again.

I've only exercised the tree to list path and I won't actually
end up using it but it's at least worth posting.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Worth pushing?

	* bitmap.h: Document set_copy aka bitmap_copy as usable
	for tree representation.
	* bitmap.cc (bitmap_copy_tree_to_list): New helper.
	(bitmap_copy): Support copying all bitmap representation
	combinations.
---
 gcc/bitmap.cc | 78 +++++++++++++++++++++++++++++++++++++++++++++++++--
 gcc/bitmap.h  |  6 +++-
 2 files changed, 81 insertions(+), 3 deletions(-)

diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc
index 88c329f9325..d9520397992 100644
--- a/gcc/bitmap.cc
+++ b/gcc/bitmap.cc
@@ -847,6 +847,58 @@ bitmap_element_zerop (const bitmap_element *element)
 #endif
 }
 \f
+/* Copy bitmap FROM which is in tree form to bitmap TO in list form.  */
+
+static void
+bitmap_copy_tree_to_list (bitmap to, const_bitmap from)
+{
+  bitmap_element *to_ptr = nullptr;
+
+  gcc_checking_assert (!to->tree_form && from->tree_form);
+
+  /* Do like bitmap_tree_to_vec but populate the destination bitmap
+     instead of a vector.  */
+  auto_vec<bitmap_element *, 32> stack;
+  bitmap_element *e = from->first;
+  while (true)
+    {
+      while (e != NULL)
+	{
+	  stack.safe_push (e);
+	  e = e->prev;
+	}
+      if (stack.is_empty ())
+	break;
+
+      bitmap_element *from_ptr = stack.pop ();
+	{
+	  bitmap_element *to_elt = bitmap_element_allocate (to);
+
+	  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_list_link_element,
+	     for the case where we know the links are being entered
+	     in sequence.  */
+	  if (to_ptr == nullptr)
+	    {
+	      to->first = to->current = to_elt;
+	      to->indx = from_ptr->indx;
+	      to_elt->next = to_elt->prev = nullptr;
+	    }
+	  else
+	    {
+	      to_elt->prev = to_ptr;
+	      to_elt->next = nullptr;
+	      to_ptr->next = to_elt;
+	    }
+
+	  to_ptr = to_elt;
+	}
+      e = from_ptr->next;
+    }
+}
+
 /* Copy a bitmap to another bitmap.  */
 
 void
@@ -854,11 +906,29 @@ bitmap_copy (bitmap to, const_bitmap from)
 {
   const bitmap_element *from_ptr;
   bitmap_element *to_ptr = 0;
-
-  gcc_checking_assert (!to->tree_form && !from->tree_form);
+  bool to_tree = to->tree_form;
 
   bitmap_clear (to);
 
+  /* From tree form first copy to list form, avoiding debalancing from,
+     then if the result is in tree form have it rebalance itself.  */
+  if (from->tree_form)
+    {
+      if (to_tree)
+	bitmap_list_view (to);
+      bitmap_copy_tree_to_list (to, from);
+      if (to_tree)
+	bitmap_tree_view (to);
+      return;
+    }
+
+  /* We are copying from list form - first copy the list representation
+     so temporarily switch the destination to list form.  */
+  if (to_tree)
+    bitmap_list_view (to);
+
+  gcc_checking_assert (!to->tree_form && !from->tree_form);
+
   /* Copy elements in forward direction one at a time.  */
   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
     {
@@ -885,6 +955,10 @@ bitmap_copy (bitmap to, const_bitmap from)
 
       to_ptr = to_elt;
     }
+
+  /* To tree, result will balance itself.  */
+  if (to_tree)
+    bitmap_tree_view (to);
 }
 
 /* Move a bitmap to another bitmap.  */
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 7fba443aff1..9a007855d0c 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -139,11 +139,15 @@ along with GCC; see the file COPYING3.  If not see
      * add_member
      * remove_member
 
+   Additionally both representations support enumeration of the
+   members in O(E) time for the following operations:
+
+     * set_copy			: bitmap_copy
+
    Additionally, the linked-list sparse set representation supports
    enumeration of the members in O(E) time:
 
      * forall			: EXECUTE_IF_SET_IN_BITMAP
-     * set_copy			: bitmap_copy
      * set_intersection		: bitmap_intersect_p /
 				  bitmap_and / bitmap_and_into /
 				  EXECUTE_IF_AND_IN_BITMAP
-- 
2.35.3

[PATCH] Support bitmap_copy across representations

[Richard Biener]

The following started as making the backward threader m_imports
use the tree representation.  Since that interfaces to a list
representation bitmap in ranger by copying rewriting the tree
to list to perform the copy is inefficient in that it loses
balancing.  The following adds bitmap_copy_tree_to_list and
integrates it with the generic bitmap_copy routine.  For symmetry
I also added list to tree copy, relying on auto-balancing, and
tree to tree copy which I didn't optimize to preserve the
source balancing but instead use bitmap_copy_tree_to_list and
have the result auto-balanced again.

I've only exercised the tree to list path and I won't actually
end up using it but it's at least worth posting.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Worth pushing?

	* bitmap.h: Document set_copy aka bitmap_copy as usable
	for tree representation.
	* bitmap.cc (bitmap_copy_tree_to_list): New helper.
	(bitmap_copy): Support copying all bitmap representation
	combinations.
---
 gcc/bitmap.cc | 78 +++++++++++++++++++++++++++++++++++++++++++++++++--
 gcc/bitmap.h  |  6 +++-
 2 files changed, 81 insertions(+), 3 deletions(-)

diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc
index 88c329f9325..d9520397992 100644
--- a/gcc/bitmap.cc
+++ b/gcc/bitmap.cc
@@ -847,6 +847,58 @@ bitmap_element_zerop (const bitmap_element *element)
 #endif
 }
 \f
+/* Copy bitmap FROM which is in tree form to bitmap TO in list form.  */
+
+static void
+bitmap_copy_tree_to_list (bitmap to, const_bitmap from)
+{
+  bitmap_element *to_ptr = nullptr;
+
+  gcc_checking_assert (!to->tree_form && from->tree_form);
+
+  /* Do like bitmap_tree_to_vec but populate the destination bitmap
+     instead of a vector.  */
+  auto_vec<bitmap_element *, 32> stack;
+  bitmap_element *e = from->first;
+  while (true)
+    {
+      while (e != NULL)
+	{
+	  stack.safe_push (e);
+	  e = e->prev;
+	}
+      if (stack.is_empty ())
+	break;
+
+      bitmap_element *from_ptr = stack.pop ();
+	{
+	  bitmap_element *to_elt = bitmap_element_allocate (to);
+
+	  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_list_link_element,
+	     for the case where we know the links are being entered
+	     in sequence.  */
+	  if (to_ptr == nullptr)
+	    {
+	      to->first = to->current = to_elt;
+	      to->indx = from_ptr->indx;
+	      to_elt->next = to_elt->prev = nullptr;
+	    }
+	  else
+	    {
+	      to_elt->prev = to_ptr;
+	      to_elt->next = nullptr;
+	      to_ptr->next = to_elt;
+	    }
+
+	  to_ptr = to_elt;
+	}
+      e = from_ptr->next;
+    }
+}
+
 /* Copy a bitmap to another bitmap.  */
 
 void
@@ -854,11 +906,29 @@ bitmap_copy (bitmap to, const_bitmap from)
 {
   const bitmap_element *from_ptr;
   bitmap_element *to_ptr = 0;
-
-  gcc_checking_assert (!to->tree_form && !from->tree_form);
+  bool to_tree = to->tree_form;
 
   bitmap_clear (to);
 
+  /* From tree form first copy to list form, avoiding debalancing from,
+     then if the result is in tree form have it rebalance itself.  */
+  if (from->tree_form)
+    {
+      if (to_tree)
+	bitmap_list_view (to);
+      bitmap_copy_tree_to_list (to, from);
+      if (to_tree)
+	bitmap_tree_view (to);
+      return;
+    }
+
+  /* We are copying from list form - first copy the list representation
+     so temporarily switch the destination to list form.  */
+  if (to_tree)
+    bitmap_list_view (to);
+
+  gcc_checking_assert (!to->tree_form && !from->tree_form);
+
   /* Copy elements in forward direction one at a time.  */
   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
     {
@@ -885,6 +955,10 @@ bitmap_copy (bitmap to, const_bitmap from)
 
       to_ptr = to_elt;
     }
+
+  /* To tree, result will balance itself.  */
+  if (to_tree)
+    bitmap_tree_view (to);
 }
 
 /* Move a bitmap to another bitmap.  */
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 7fba443aff1..9a007855d0c 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -139,11 +139,15 @@ along with GCC; see the file COPYING3.  If not see
      * add_member
      * remove_member
 
+   Additionally both representations support enumeration of the
+   members in O(E) time for the following operations:
+
+     * set_copy			: bitmap_copy
+
    Additionally, the linked-list sparse set representation supports
    enumeration of the members in O(E) time:
 
      * forall			: EXECUTE_IF_SET_IN_BITMAP
-     * set_copy			: bitmap_copy
      * set_intersection		: bitmap_intersect_p /
 				  bitmap_and / bitmap_and_into /
 				  EXECUTE_IF_AND_IN_BITMAP
-- 
2.35.3