From b955080a5ab8690902f7cc99a770f9c3da171d6f Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Tue, 31 Jan 2023 15:45:43 +0100 Subject: [PATCH] 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. (cherry picked from commit 97258480438db77e52f4b3947fa2c075b09d3fe1) --- gcc/dominance.cc | 27 +++++++++++++++++---------- 1 file changed, 17 insertions(+), 10 deletions(-) diff --git a/gcc/dominance.cc b/gcc/dominance.cc index 09d12d0f618..60b19637935 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 -- 2.47.2