public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r13-5617] middle-end/108500 - replace recursive domtree DFS traversal
@ 2023-02-01  7:47 Richard Biener
  0 siblings, 0 replies; only message in thread
From: Richard Biener @ 2023-02-01  7:47 UTC (permalink / raw)
  To: gcc-cvs

https://gcc.gnu.org/g:97258480438db77e52f4b3947fa2c075b09d3fe1

commit r13-5617-g97258480438db77e52f4b3947fa2c075b09d3fe1
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Jan 31 15:45:43 2023 +0100

    middle-end/108500 - replace recursive domtree DFS traversal
    
    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.

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

^ permalink raw reply	[flat|nested] only message in thread

only message in thread, other threads:[~2023-02-01  7:47 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-02-01  7:47 [gcc r13-5617] middle-end/108500 - replace recursive domtree DFS traversal Richard Biener

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