From patchwork Wed Aug 17 11:11:12 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 56806 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 871A23858C83 for ; Wed, 17 Aug 2022 11:11:43 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 871A23858C83 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1660734703; bh=XpZrMD9X+ZqRA+Dae6OFYHWzz5j3Jo8rVHiFdUkmO04=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=Z9GExthqlF/2b/D2CROZU9fkvLJw5z68alzi4gULOqon0TwfzI0Xji/BhjMYZyjI2 bYyZM1C+2jqWcu3Exn3EYx0fTddTOnfKz5W3qX1HTUpyAghT6liPeHjxqgmAHPIpiv kCyF+cAhSO/wQeErCZkwfzTKfzyHpDlv/HAgfKzk= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 393973858D37 for ; Wed, 17 Aug 2022 11:11:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 393973858D37 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 0385F3714A for ; Wed, 17 Aug 2022 11:11:13 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id E380D2C178 for ; Wed, 17 Aug 2022 11:11:12 +0000 (UTC) Date: Wed, 17 Aug 2022 11:11:12 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH] Support bitmap_copy across representations User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 X-Spam-Status: No, score=-9.3 required=5.0 tests=BAYES_00, DKIM_INVALID, DKIM_SIGNED, GIT_PATCH_0, KAM_DMARC_STATUS, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Message-Id: <20220817111143.871A23858C83@sourceware.org> 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 } +/* 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 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