public inbox for gcc-cvs@sourceware.org help / color / mirror / Atom feed
From: Richard Biener <rguenth@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-2211] Improve compute_control_dep_chain path finding Date: Fri, 26 Aug 2022 06:24:06 +0000 (GMT) [thread overview] Message-ID: <20220826062406.8E0243861020@sourceware.org> (raw) https://gcc.gnu.org/g:670961f051aedbac21bc769c21c5b28b338b6003 commit r13-2211-g670961f051aedbac21bc769c21c5b28b338b6003 Author: Richard Biener <rguenther@suse.de> 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<T, va_heap, vl_ptr>::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<edge>& 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<basic_block> &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<edge_iterator, 20> 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<edge> cd_chains[], unsigned *num_chains, vec<edge> &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<basic_block, 20> 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<edge> dep_chains[MAX_NUM_CHAINS]; auto_vec<edge, MAX_CHAIN_LEN + 1> 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; }
reply other threads:[~2022-08-26 6:24 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20220826062406.8E0243861020@sourceware.org \ --to=rguenth@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).