From: Richard Biener <rguenther@suse.de>
To: Jakub Jelinek <jakub@redhat.com>
Cc: gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] middle-end/108500 - replace recursive domtree DFS traversal
Date: Tue, 31 Jan 2023 19:20:37 +0100 [thread overview]
Message-ID: <90BD28AC-CE2D-4002-B4B1-F8510BCD681A@suse.de> (raw)
In-Reply-To: <Y9k6u3sOcX/jIc9n@tucnak>
> 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 parent reply other threads:[~2023-01-31 18:20 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-01-31 14:45 Richard Biener
2023-01-31 15:58 ` Jakub Jelinek
2023-01-31 18:20 ` Richard Biener [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=90BD28AC-CE2D-4002-B4B1-F8510BCD681A@suse.de \
--to=rguenther@suse.de \
--cc=gcc-patches@gcc.gnu.org \
--cc=jakub@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).