From: Richard Biener <rguenther@suse.de>
To: gcc-patches@gcc.gnu.org
Subject: [PATCH] Support bitmap_copy across representations
Date: Wed, 17 Aug 2022 11:11:12 +0000 (UTC) [thread overview]
Message-ID: <20220817111112.9yhCUnIcP0UCY1RcJmwX7wkdktL8ZfevjT3HhnKwsE8@z> (raw)
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
next reply other threads:[~2022-08-17 11:11 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-08-17 11:11 Richard Biener [this message]
[not found] <20220817111127.E7BC13858C83@sourceware.org>
2022-08-31 16:00 ` Jeff Law
-- strict thread matches above, loose matches on Subject: below --
2022-08-17 11:11 Richard Biener
2022-08-17 11:11 Richard Biener
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20220817111112.9yhCUnIcP0UCY1RcJmwX7wkdktL8ZfevjT3HhnKwsE8@z \
--to=rguenther@suse.de \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).