From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id 796C03858D38; Wed, 1 Feb 2023 07:47:57 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 796C03858D38 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1675237677; bh=x+4A12o0CirGYozn5CeJUTCBU77jWyYZmeww9c1vYbU=; h=From:To:Subject:Date:From; b=XkkTc6f4E7vNi3SzpOxHqJeIYuS3fZSRLzGA6iZI4J580RxYzahqTzpYdpXCMziSN EZlCSLKtUgUebP2CcRyAIMfGj2UZypG4P4vXedKib5SbW8lvP5ypkkn9svodpHYJU7 b0ia7Sf3Ktn8VV64qQQWQgAjAJb35CpbmeiJnjLQ= 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-5617] middle-end/108500 - replace recursive domtree DFS traversal X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/master X-Git-Oldrev: e2f939d30f5b397011d1dc06370dd8196aceebda X-Git-Newrev: 97258480438db77e52f4b3947fa2c075b09d3fe1 Message-Id: <20230201074757.796C03858D38@sourceware.org> Date: Wed, 1 Feb 2023 07:47:57 +0000 (GMT) List-Id: https://gcc.gnu.org/g:97258480438db77e52f4b3947fa2c075b09d3fe1 commit r13-5617-g97258480438db77e52f4b3947fa2c075b09d3fe1 Author: Richard Biener 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