From patchwork Tue Apr 18 13:53:33 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 84876 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp2875398vqo; Tue, 18 Apr 2023 07:03:45 -0700 (PDT) X-Google-Smtp-Source: AKy350Z/YjskfR7wqauZ++KTyxZZYTsPOE+BJCt9wGS7tMZd0S778/6X/pn8zkSilIGbuU1/jTyX X-Received: by 2002:a17:906:6b97:b0:94b:958c:8827 with SMTP id l23-20020a1709066b9700b0094b958c8827mr9836678ejr.56.1681826625147; Tue, 18 Apr 2023 07:03:45 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1681826625; cv=none; d=google.com; s=arc-20160816; b=nhoXWfvSg7eVr5sfkq21CbecdLxQwccoHbkOn5vMh6Lo/KtmJB3IkVycNPFTZ8p0Bo OOA0RivZPVyvI3tjYe09YB7GFNbmQX9U7HdHgZcrRghj4uZbBSvRZRCd109OCpyjzZR3 ml71nneuVFTsYIYwDXUzHcGJniBJqqcYPXxeGKY5OD+M88jTLBJmlYuQmY30u7D3NdrN 3OUFUUxn5PO2n5msdKejp8CosNNH0Ox2B8lbXo3i75u0wFtThZiK4VJLIeBchWFKwhS6 rBnSjiS3x/0f7/SJ3KpFjeTnGeTyOxD+2SEIr1bm3QhCT2pgnjnoGi3sbxA2WkFf8ckU KX/Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:message-id :mime-version:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=JfsRv+rnyL4wHsvhe4eCleXCK+KQsDuBfwj9P9kV/Ro=; b=gGat3G94SsksbQ1KiOUKU5OPun2cuEgCnrVJvvpdh7X6RHQnjmrZxZgf+BsF3Mwsws sK2zjYXfRRgHmhyAuSYNqfqxyH1dJ5zTt4zSeF0ACT1c+tOoAyhOj0C7sFYZFMd/DdJv pGUVZvFz9uc7R+V5lVTCp9sjqTmo0h5mMGht1Wc6Pfo8AwAAf4wQAi1kdx+zQuOT4o7N 18rBs+e9yUJakUhn36pp948uptlbotf5UI271ZR9kl6AIWEFvpYisMhy1E3s/tfxIUcZ KdG7ZiQRlVmL/89VGJLm+IqR5IBxbFnWDLpSDWt5ekI/H4gETo6bU9/cbtWJUuZdUxAn UnWA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=LWVnqztm; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id g15-20020a170906c18f00b0093e5b108711si12369081ejz.942.2023.04.18.07.03.44 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 18 Apr 2023 07:03:45 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=LWVnqztm; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id EA8113959CAB for ; Tue, 18 Apr 2023 13:54:48 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org EA8113959CAB DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1681826089; bh=JfsRv+rnyL4wHsvhe4eCleXCK+KQsDuBfwj9P9kV/Ro=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=LWVnqztmOWOgBn9LdLWFaok4DILWV89F2hE0V2ORWyqt9Pzve3AUPxB7WNuVUrDHz eN2KFrZ/3O6KHsbEuWkEcMYNKksHfauTuc610Y+D+NM99ji85F5lu78NpDaJw8/M9S GZCKFfSpJiucx5aLlnUfwRtLmV6GI5IrlgsC83HQ= 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 0537D3952486 for ; Tue, 18 Apr 2023 13:53:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0537D3952486 Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 32DD121A48 for ; Tue, 18 Apr 2023 13:53:34 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 217FE13581 for ; Tue, 18 Apr 2023 13:53:34 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id KnoeB96gPmQ+RwAAMHmgww (envelope-from ) for ; Tue, 18 Apr 2023 13:53:34 +0000 Date: Tue, 18 Apr 2023 15:53:33 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH] middle-end/108786 - add bitmap_clear_first_set_bit MIME-Version: 1.0 Message-Id: <20230418135334.217FE13581@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1763523035301621040?= X-GMAIL-MSGID: =?utf-8?q?1763523035301621040?= This adds bitmap_clear_first_set_bit and uses it where previously bitmap_clear_bit followed bitmap_first_set_bit. The advantage is speeding up the search and avoiding to clobber ->current. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. Richard. PR middle-end/108786 * bitmap.h (bitmap_clear_first_set_bit): New. * bitmap.cc (bitmap_first_set_bit_worker): Rename from bitmap_first_set_bit and add optional clearing of the bit. (bitmap_first_set_bit): Wrap bitmap_first_set_bit_worker. (bitmap_clear_first_set_bit): Likewise. * df-core.cc (df_worklist_dataflow_doublequeue): Use bitmap_clear_first_set_bit. * graphite-scop-detection.cc (scop_detection::merge_sese): Likewise. * sanopt.cc (sanitize_asan_mark_unpoison): Likewise. (sanitize_asan_mark_poison): Likewise. * tree-cfgcleanup.cc (cleanup_tree_cfg_noloop): Likewise. * tree-into-ssa.cc (rewrite_blocks): Likewise. * tree-ssa-dce.cc (simple_dce_from_worklist): Likewise. * tree-ssa-sccvn.cc (do_rpo_vn_1): Likewise. --- gcc/bitmap.cc | 41 ++++++++++++++++++++++++++++++---- gcc/bitmap.h | 3 +++ gcc/df-core.cc | 3 +-- gcc/graphite-scop-detection.cc | 3 +-- gcc/sanopt.cc | 6 ++--- gcc/tree-cfgcleanup.cc | 3 +-- gcc/tree-into-ssa.cc | 3 +-- gcc/tree-ssa-dce.cc | 3 +-- gcc/tree-ssa-sccvn.cc | 3 +-- 9 files changed, 48 insertions(+), 20 deletions(-) diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc index 20de562caac..d1d0324b633 100644 --- a/gcc/bitmap.cc +++ b/gcc/bitmap.cc @@ -1217,12 +1217,12 @@ bitmap_single_bit_set_p (const_bitmap a) /* Return the bit number of the first set bit in the bitmap. The - bitmap must be non-empty. */ + bitmap must be non-empty. When CLEAR is true it clears the bit. */ -unsigned -bitmap_first_set_bit (const_bitmap a) +static unsigned +bitmap_first_set_bit_worker (bitmap a, bool clear) { - const bitmap_element *elt = a->first; + bitmap_element *elt = a->first; unsigned bit_no; BITMAP_WORD word; unsigned ix; @@ -1269,9 +1269,42 @@ bitmap_first_set_bit (const_bitmap a) gcc_checking_assert (word & 1); #endif + + if (clear) + { + elt->bits[ix] &= ~((BITMAP_WORD) 1 << (bit_no % BITMAP_WORD_BITS)); + /* If we cleared the entire word, free up the element. */ + if (!elt->bits[ix] + && bitmap_element_zerop (elt)) + { + if (!a->tree_form) + bitmap_list_unlink_element (a, elt); + else + bitmap_tree_unlink_element (a, elt); + } + } + return bit_no; } +/* Return the bit number of the first set bit in the bitmap. The + bitmap must be non-empty. */ + +unsigned +bitmap_first_set_bit (const_bitmap a) +{ + return bitmap_first_set_bit_worker (const_cast (a), false); +} + +/* Return and clear the bit number of the first set bit in the bitmap. The + bitmap must be non-empty. */ + +unsigned +bitmap_clear_first_set_bit (bitmap a) +{ + return bitmap_first_set_bit_worker (a, true); +} + /* Return the bit number of the first set bit in the bitmap. The bitmap must be non-empty. */ diff --git a/gcc/bitmap.h b/gcc/bitmap.h index 43337d2e9d9..5432f386dbd 100644 --- a/gcc/bitmap.h +++ b/gcc/bitmap.h @@ -110,6 +110,7 @@ along with GCC; see the file COPYING3. If not see * clear : bitmap_clear * smallest_member : bitmap_first_set_bit + * pop_smallest : bitmap_clear_first_set_bit * choose_one : (not implemented, but could be in constant time) @@ -133,6 +134,7 @@ along with GCC; see the file COPYING3. If not see amortized time with O(E) worst-case behavior. * smallest_member + * pop_smallest * largest_member * set_size * member_p @@ -501,6 +503,7 @@ extern void debug (const bitmap_head &ref); extern void debug (const bitmap_head *ptr); extern unsigned bitmap_first_set_bit (const_bitmap); +extern unsigned bitmap_clear_first_set_bit (bitmap); extern unsigned bitmap_last_set_bit (const_bitmap); /* Compute bitmap hash (for purposes of hashing etc.) */ diff --git a/gcc/df-core.cc b/gcc/df-core.cc index 38f69ac5743..3286ffda2ce 100644 --- a/gcc/df-core.cc +++ b/gcc/df-core.cc @@ -1040,8 +1040,7 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow, do { - unsigned index = bitmap_first_set_bit (worklist); - bitmap_clear_bit (worklist, index); + unsigned index = bitmap_clear_first_set_bit (worklist); unsigned bb_index; dcount++; diff --git a/gcc/graphite-scop-detection.cc b/gcc/graphite-scop-detection.cc index f976451949d..99551990e54 100644 --- a/gcc/graphite-scop-detection.cc +++ b/gcc/graphite-scop-detection.cc @@ -469,8 +469,7 @@ scop_detection::merge_sese (sese_l first, sese_l second) const its border it acts more like a visited bitmap. */ do { - int index = bitmap_first_set_bit (worklist); - bitmap_clear_bit (worklist, index); + int index = bitmap_clear_first_set_bit (worklist); basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index); edge_iterator ei; edge e; diff --git a/gcc/sanopt.cc b/gcc/sanopt.cc index 85489739507..ce8393b9518 100644 --- a/gcc/sanopt.cc +++ b/gcc/sanopt.cc @@ -1012,8 +1012,7 @@ sanitize_asan_mark_unpoison (void) /* 2) Propagate the information to all reachable blocks. */ while (!bitmap_empty_p (worklist)) { - unsigned i = bitmap_first_set_bit (worklist); - bitmap_clear_bit (worklist, i); + unsigned i = bitmap_clear_first_set_bit (worklist); basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i); gcc_assert (bb); @@ -1109,8 +1108,7 @@ sanitize_asan_mark_poison (void) /* 2) Propagate the information to all definitions blocks. */ while (!bitmap_empty_p (worklist)) { - unsigned i = bitmap_first_set_bit (worklist); - bitmap_clear_bit (worklist, i); + unsigned i = bitmap_clear_first_set_bit (worklist); basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i); gcc_assert (bb); diff --git a/gcc/tree-cfgcleanup.cc b/gcc/tree-cfgcleanup.cc index 64ff16fc45b..42b25312122 100644 --- a/gcc/tree-cfgcleanup.cc +++ b/gcc/tree-cfgcleanup.cc @@ -1133,8 +1133,7 @@ cleanup_tree_cfg_noloop (unsigned ssa_update_flags) /* Now process the altered blocks, as long as any are available. */ while (!bitmap_empty_p (cfgcleanup_altered_bbs)) { - unsigned i = bitmap_first_set_bit (cfgcleanup_altered_bbs); - bitmap_clear_bit (cfgcleanup_altered_bbs, i); + unsigned i = bitmap_clear_first_set_bit (cfgcleanup_altered_bbs); if (i < NUM_FIXED_BLOCKS) continue; diff --git a/gcc/tree-into-ssa.cc b/gcc/tree-into-ssa.cc index 2e322990456..5cfe7c516cc 100644 --- a/gcc/tree-into-ssa.cc +++ b/gcc/tree-into-ssa.cc @@ -2348,8 +2348,7 @@ rewrite_blocks (basic_block entry, enum rewrite_mode what) } while (!bitmap_empty_p (worklist)) { - int idx = bitmap_first_set_bit (worklist); - bitmap_clear_bit (worklist, idx); + int idx = bitmap_clear_first_set_bit (worklist); basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx); bb->flags |= in_region; extra_rgn.safe_push (bb); diff --git a/gcc/tree-ssa-dce.cc b/gcc/tree-ssa-dce.cc index 0ae998f86f9..bda780876f3 100644 --- a/gcc/tree-ssa-dce.cc +++ b/gcc/tree-ssa-dce.cc @@ -2102,8 +2102,7 @@ simple_dce_from_worklist (bitmap worklist) while (! bitmap_empty_p (worklist)) { /* Pop item. */ - unsigned i = bitmap_first_set_bit (worklist); - bitmap_clear_bit (worklist, i); + unsigned i = bitmap_clear_first_set_bit (worklist); tree def = ssa_name (i); /* Removed by somebody else or still in use. */ diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc index 9692911e31b..7fa2a154e84 100644 --- a/gcc/tree-ssa-sccvn.cc +++ b/gcc/tree-ssa-sccvn.cc @@ -8491,8 +8491,7 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs, bitmap_set_bit (worklist, 0); while (!bitmap_empty_p (worklist)) { - int idx = bitmap_first_set_bit (worklist); - bitmap_clear_bit (worklist, idx); + int idx = bitmap_clear_first_set_bit (worklist); basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[idx]); gcc_assert ((bb->flags & BB_EXECUTABLE) && !rpo_state[idx].visited);