From patchwork Thu Mar 10 11:50:42 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 51849 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 EA1CE3857C4E for ; Thu, 10 Mar 2022 11:51:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org EA1CE3857C4E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1646913082; bh=+iKD0sVOQ4vCopHX19FQjFWDOKSakeWV0QRX/sxogYI=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=ukARNvARLP6Jjj58NNCuNjJcu9kg67pgUbOYhIIzBRAhdmFdZCSxge0LicneccpZe qXq7EFYKAG9z1R4BE1ZZMQLyrNUKwSgzBQOLMKT90nSUQUHhaFCtx5N5Ora3/p/E2I WklyAyH9aFOPiuNPsWPUTQFAZCrht9qw1O6ZZDZI= 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 84A6F3858C20 for ; Thu, 10 Mar 2022 11:50:44 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 84A6F3858C20 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 EAF5D210EE for ; Thu, 10 Mar 2022 11:50:42 +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 DAE0413FA3 for ; Thu, 10 Mar 2022 11:50:42 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id mJpqNBLmKWIYGAAAMHmgww (envelope-from ) for ; Thu, 10 Mar 2022 11:50:42 +0000 Date: Thu, 10 Mar 2022 12:50:42 +0100 (CET) To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/102943 - avoid (re-)computing dominance bitmap MIME-Version: 1.0 Message-Id: <20220310115042.DAE0413FA3@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.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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" Currently back_propagate_equivalences tries to optimize dominance queries in a smart way but it fails to notice that when fast indexes are available the dominance query is fast (when called from DOM). It also re-computes the dominance bitmap for each equivalence recorded on an edge, which for FP are usually several. Finally it fails to use the tree bitmap view for efficiency. Overall this cuts 7 seconds of compile-time from originally 77 in the slowest LTRANS unit when building 521.wrf_r. Bootstrap and regtest running on x86_64-unknown-linux-gnu. Richard. 2022-03-10 Richard Biener PR tree-optimization/102943 * tree-ssa-dom.cc (back_propagate_equivalences): Only populate the dominance bitmap if fast queries are not available. Use a tree view bitmap. (record_temporary_equivalences): Cache the dominance bitmap across all equivalences on the edge. --- gcc/tree-ssa-dom.cc | 58 +++++++++++++++++++++++++++------------------ 1 file changed, 35 insertions(+), 23 deletions(-) diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc index fc90c207b52..21745bf31d3 100644 --- a/gcc/tree-ssa-dom.cc +++ b/gcc/tree-ssa-dom.cc @@ -1025,12 +1025,13 @@ dom_valueize (tree t) additional equivalences that are valid on edge E. */ static void back_propagate_equivalences (tree lhs, edge e, - class const_and_copies *const_and_copies) + class const_and_copies *const_and_copies, + bitmap *domby) { use_operand_p use_p; imm_use_iterator iter; - bitmap domby = NULL; basic_block dest = e->dest; + bool domok = (dom_info_state (CDI_DOMINATORS) == DOM_OK); /* Iterate over the uses of LHS to see if any dominate E->dest. If so, they may create useful equivalences too. @@ -1053,27 +1054,38 @@ back_propagate_equivalences (tree lhs, edge e, if (!lhs2 || TREE_CODE (lhs2) != SSA_NAME) continue; - /* Profiling has shown the domination tests here can be fairly - expensive. We get significant improvements by building the - set of blocks that dominate BB. We can then just test - for set membership below. - - We also initialize the set lazily since often the only uses - are going to be in the same block as DEST. */ - if (!domby) + if (domok) { - domby = BITMAP_ALLOC (NULL); - basic_block bb = get_immediate_dominator (CDI_DOMINATORS, dest); - while (bb) + if (!dominated_by_p (CDI_DOMINATORS, dest, gimple_bb (use_stmt))) + continue; + } + else + { + /* Profiling has shown the domination tests here can be fairly + expensive when the fast indexes are not computed. + We get significant improvements by building the + set of blocks that dominate BB. We can then just test + for set membership below. + + We also initialize the set lazily since often the only uses + are going to be in the same block as DEST. */ + + if (!*domby) { - bitmap_set_bit (domby, bb->index); - bb = get_immediate_dominator (CDI_DOMINATORS, bb); + *domby = BITMAP_ALLOC (NULL); + bitmap_tree_view (*domby); + basic_block bb = get_immediate_dominator (CDI_DOMINATORS, dest); + while (bb) + { + bitmap_set_bit (*domby, bb->index); + bb = get_immediate_dominator (CDI_DOMINATORS, bb); + } } - } - /* This tests if USE_STMT does not dominate DEST. */ - if (!bitmap_bit_p (domby, gimple_bb (use_stmt)->index)) - continue; + /* This tests if USE_STMT does not dominate DEST. */ + if (!bitmap_bit_p (*domby, gimple_bb (use_stmt)->index)) + continue; + } /* At this point USE_STMT dominates DEST and may result in a useful equivalence. Try to simplify its RHS to a constant @@ -1083,9 +1095,6 @@ back_propagate_equivalences (tree lhs, edge e, if (res && (TREE_CODE (res) == SSA_NAME || is_gimple_min_invariant (res))) record_equality (lhs2, res, const_and_copies); } - - if (domby) - BITMAP_FREE (domby); } /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied @@ -1110,6 +1119,7 @@ record_temporary_equivalences (edge e, for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i) avail_exprs_stack->record_cond (eq); + bitmap domby = NULL; edge_info::equiv_pair *seq; for (i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i) { @@ -1146,8 +1156,10 @@ record_temporary_equivalences (edge e, /* Any equivalence found for LHS may result in additional equivalences for other uses of LHS that we have already processed. */ - back_propagate_equivalences (lhs, e, const_and_copies); + back_propagate_equivalences (lhs, e, const_and_copies, &domby); } + if (domby) + BITMAP_FREE (domby); } }