Re: [PATCH] middle-end/108500 - replace recursive domtree DFS traversal

[Jakub Jelinek <jakub@redhat.com>]

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