From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id 8E0243861020; Fri, 26 Aug 2022 06:24:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8E0243861020 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661495046; bh=TBH7Du1mNh63L93/oq7LiXfrPvxpRltwQNlEyvF++lo=; h=From:To:Subject:Date:From; b=aRkwKfKSOPuHqqpB8Fk7eC2AJqoHBZWEORbBm35zHKt43whpvaXlxidCyVesPv/EW +hAywlEraM3nofGxxXw3cB3jKN07l+iOEMyjOCCsXQOtqKCEV0w3sR87vU8PQtFa0K /eGAmmSj9CfMGnyRDLvgSFsUh44sYffUElOfD3Qc= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Biener To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-2211] Improve compute_control_dep_chain path finding X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/master X-Git-Oldrev: 8b4d528d8c57ad7a2d5e39427bf4af7b8c1668c3 X-Git-Newrev: 670961f051aedbac21bc769c21c5b28b338b6003 Message-Id: <20220826062406.8E0243861020@sourceware.org> Date: Fri, 26 Aug 2022 06:24:06 +0000 (GMT) List-Id: https://gcc.gnu.org/g:670961f051aedbac21bc769c21c5b28b338b6003 commit r13-2211-g670961f051aedbac21bc769c21c5b28b338b6003 Author: Richard Biener Date: Thu Aug 25 13:04:43 2022 +0200 Improve compute_control_dep_chain path finding 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). * 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. Diff: --- 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; }