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

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

[Richard Biener]

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.
---
 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
-- 
2.35.3

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

[Jakub Jelinek]

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

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

[Richard Biener]

> Am 31.01.2023 um 16:59 schrieb Jakub Jelinek via Gcc-patches <gcc-patches@gcc.gnu.org>:
> 
> 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?  

Yes.

> 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
>