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-5617] middle-end/108500 - replace recursive domtree DFS traversal Date: Wed, 1 Feb 2023 07:47:57 +0000 (GMT) [thread overview] Message-ID: <20230201074757.796C03858D38@sourceware.org> (raw) https://gcc.gnu.org/g:97258480438db77e52f4b3947fa2c075b09d3fe1 commit r13-5617-g97258480438db77e52f4b3947fa2c075b09d3fe1 Author: Richard Biener <rguenther@suse.de> Date: Tue Jan 31 15:45:43 2023 +0100 middle-end/108500 - replace recursive domtree DFS traversal The following replaces the recursive DFS traversal of the dominator tree in assign_dfs_numbers with a tree traversal using the fact that we have recorded parents. Bootstrapped and tested on x86_64-unknown-linux-gnu. This makes r13-5325 somewhat obsolete, though not computing the DFS numbers at all is beneficial in the cases where we perform immediate CFG manipulations. OK for trunk and later branch(es)? Thanks, Richard. PR middle-end/108500 * dominance.cc (assign_dfs_numbers): Replace recursive DFS with tree traversal algorithm. Diff: --- gcc/dominance.cc | 27 +++++++++++++++++---------- 1 file changed, 17 insertions(+), 10 deletions(-) diff --git a/gcc/dominance.cc b/gcc/dominance.cc index 099b8fd3f24..34fabe40c18 100644 --- a/gcc/dominance.cc +++ b/gcc/dominance.cc @@ -639,18 +639,25 @@ dom_info::calc_idoms () static void assign_dfs_numbers (struct et_node *node, int *num) { - struct et_node *son; - - node->dfs_num_in = (*num)++; - - if (node->son) + et_node *n = node; + while (1) { - assign_dfs_numbers (node->son, num); - for (son = node->son->right; son != node->son; son = son->right) - assign_dfs_numbers (son, num); + n->dfs_num_in = (*num)++; + if (n->son) + n = n->son; + else + { + while (!n->right || n->right == n->father->son) + { + n->dfs_num_out = (*num)++; + if (n == node) + return; + n = n->father; + } + n->dfs_num_out = (*num)++; + n = n->right; + } } - - node->dfs_num_out = (*num)++; } /* Compute the data necessary for fast resolving of dominator queries in a
reply other threads:[~2023-02-01 7:47 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=20230201074757.796C03858D38@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).