From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 9F2573858C2F for ; Thu, 25 Aug 2022 15:03:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9F2573858C2F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de 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 7010E21EEE; Thu, 25 Aug 2022 15:03:01 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1661439781; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=4+G+dhQe+43OyNmUH5tKqQDB398aWCttAtTLRtLoJCw=; b=M8awpVFaHvrs0yeJK9jK8DcybvdVzHij9ZPuYPbnR5eqhzZq+SrBRlzIDChpxRkDER4Nq/ PctyM066eNr9Sv1BulsvLmw3ihtSIaxsFMzBS2e1qNYd6krPjw4HkQrVEulka0JTPNwExe dFtNfBB/Pp24wfZFuXoVYS9UY7vLFig= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1661439781; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=4+G+dhQe+43OyNmUH5tKqQDB398aWCttAtTLRtLoJCw=; b=QSk64wowceMGRq7oth2MLbz6H4AVx37RBR/yNozEqZk6q2hu+Qsn8ZR/p7H3eVhCUVnb/+ fdrQdKPqzeczgQCg== 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 481B013A8E; Thu, 25 Aug 2022 15:03:01 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id OGAuECWPB2MuXAAAMHmgww (envelope-from ); Thu, 25 Aug 2022 15:03:01 +0000 Date: Thu, 25 Aug 2022 17:03:00 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: matz@suse.de Subject: [PATCH] Improve compute_control_dep_chain path finding MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Message-Id: <20220825150301.481B013A8E@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.9 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 List-Id: This improves the compute_control_dep_chain path finding by first marking the dominating region we search and then making sure to not walk outside if it when enumerating all paths from the dominating block to the interesting PHI edge source. I have limited the DFS walk done for the marking in similar ways as we limit the walking in compute_control_dep_chain, more careful limiting might be necessary though - the --param uninit-control-dep-attempts param I re-use has a rather high default of 1000 which we might be able to reduce with this patch as well (I think we'll usually hit some of the other limits before ever reaching this). Bootstrap & regtest running on x86_64-unknown-linux-gnu. The true benefit will only be there when we can combine the multiple compute_control_dep_chain done from uninit_analysis::init_from_phi_def, but I've not yet managed to make that work. I guess I have to fully understand compute_control_dep_chain first ... * gimple-predicate-analysis.cc (dfs_mark_dominating_region): New helper. (compute_control_dep_chain): Adjust to honor marked region if provided. (uninit_analysis::init_from_phi_def): Pre-mark the dominating region to improve compute_control_dep_chain walking. * vec.h (vec::allocated): Add forwarder. --- gcc/gimple-predicate-analysis.cc | 81 ++++++++++++++++++++++++++++++-- gcc/vec.h | 3 ++ 2 files changed, 81 insertions(+), 3 deletions(-) diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc index 0d973a9e25a..e395c1b7052 100644 --- a/gcc/gimple-predicate-analysis.cc +++ b/gcc/gimple-predicate-analysis.cc @@ -1078,6 +1078,54 @@ simple_control_dep_chain (vec& chain, basic_block from, edge to) simple_control_dep_chain (chain, from, to->src); } +/* Perform a DFS walk on predecessor edges to mark the region denoted + by the EXIT edge and DOM which dominates EXIT->src, including DOM. + Blocks in the region are marked with FLAG and added to BBS. BBS is + filled up to its capacity only after which the walk is terminated + and false is returned. If the whole region was marked, true is returned. */ + +static bool +dfs_mark_dominating_region (edge exit, basic_block dom, int flag, + vec &bbs) +{ + if (exit->src == dom || exit->src->flags & flag) + return true; + if (!bbs.space (1)) + return false; + bbs.quick_push (exit->src); + exit->src->flags |= flag; + auto_vec stack (bbs.allocated () - bbs.length () + 1); + stack.quick_push (ei_start (exit->src->preds)); + while (!stack.is_empty ()) + { + /* Look at the edge on the top of the stack. */ + edge_iterator ei = stack.last (); + basic_block src = ei_edge (ei)->src; + + /* Check if the edge source has been visited yet. */ + if (!(src->flags & flag)) + { + /* Mark the source if there's still space. If not, return early. */ + if (!bbs.space (1)) + return false; + src->flags |= flag; + bbs.quick_push (src); + + /* Queue its predecessors if we didn't reach DOM. */ + if (src != dom && EDGE_COUNT (src->preds) > 0) + stack.quick_push (ei_start (src->preds)); + } + else + { + if (!ei_one_before_end_p (ei)) + ei_next (&stack.last ()); + else + stack.pop (); + } + } + return true; +} + /* Recursively compute the control dependence chains (paths of edges) from the dependent basic block, DEP_BB, up to the dominating basic block, DOM_BB (the head node of a chain should be dominated by it), @@ -1093,7 +1141,7 @@ static bool compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb, vec cd_chains[], unsigned *num_chains, vec &cur_cd_chain, unsigned *num_calls, - unsigned depth = 0) + unsigned in_region = 0, unsigned depth = 0) { if (*num_calls > (unsigned)param_uninit_control_dep_attempts) { @@ -1167,10 +1215,14 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb, break; } + /* If the dominating region has been marked avoid walking outside. */ + if (in_region != 0 && !(cd_bb->flags & in_region)) + break; + /* Check if DEP_BB is indirectly control-dependent on DOM_BB. */ if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains, num_chains, cur_cd_chain, - num_calls, depth + 1)) + num_calls, in_region, depth + 1)) { found_cd_chain = true; break; @@ -2238,6 +2290,25 @@ uninit_analysis::init_from_phi_def (gphi *phi) if (nedges == 0) return false; + auto_bb_flag in_region (cfun); + auto_vec region (MIN (n_basic_blocks_for_fn (cfun), + param_uninit_control_dep_attempts)); + /* Pre-mark the PHI incoming edges PHI block to make sure we only walk + interesting edges from there. */ + for (unsigned i = 0; i < nedges; i++) + { + if (!(def_edges[i]->dest->flags & in_region)) + { + if (!region.space (1)) + break; + def_edges[i]->dest->flags |= in_region; + region.quick_push (def_edges[i]->dest); + } + } + for (unsigned i = 0; i < nedges; i++) + if (!dfs_mark_dominating_region (def_edges[i], cd_root, in_region, region)) + break; + unsigned num_chains = 0; auto_vec dep_chains[MAX_NUM_CHAINS]; auto_vec cur_chain; @@ -2247,7 +2318,7 @@ uninit_analysis::init_from_phi_def (gphi *phi) unsigned num_calls = 0; unsigned prev_nc = num_chains; compute_control_dep_chain (cd_root, e->src, dep_chains, - &num_chains, cur_chain, &num_calls); + &num_chains, cur_chain, &num_calls, in_region); /* Update the newly added chains with the phi operand edge. */ if (EDGE_COUNT (e->src->succs) > 1) @@ -2259,6 +2330,10 @@ uninit_analysis::init_from_phi_def (gphi *phi) } } + /* Unmark the region. */ + for (auto bb : region) + bb->flags &= ~in_region; + /* Convert control dependence chains to the predicate in *THIS under which the PHI operands are defined to values for which M_EVAL is false. */ diff --git a/gcc/vec.h b/gcc/vec.h index eed075addc9..d048fa54ce8 100644 --- a/gcc/vec.h +++ b/gcc/vec.h @@ -1469,6 +1469,9 @@ public: bool is_empty (void) const { return m_vec ? m_vec->is_empty () : true; } + unsigned allocated (void) const + { return m_vec ? m_vec->allocated () : 0; } + unsigned length (void) const { return m_vec ? m_vec->length () : 0; } -- 2.35.3