On Tue, Jan 31, 2023 at 03:45:43PM +0100, Richard Biener wrote:
> 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.
LGTM.
> 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)
Am I right that we could replace !n->right with n == node here too
(i.e. only node can have NULL father and in that case also NULL
left/right? Though !n->right might result in better code because
we need to load it anyway for the second comparison.
> + {
> + 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)++;
> }
>
Jakub
