[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gcc-patches
Subject:    Re: [PATCH] middle-end/108500 - replace recursive domtree DFS traversal
From:       Richard Biener via Gcc-patches <gcc-patches () gcc ! gnu ! org>
Date:       2023-01-31 18:20:37
Message-ID: 90BD28AC-CE2D-4002-B4B1-F8510BCD681A () suse ! de
[Download RAW message or body]



> 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
> 
[prev in list] [next in list] [prev in thread] [next in thread]