[gcc r14-2815] Remove recursive post-dominator traversal in sinking

[gcc r14-2815] Remove recursive post-dominator traversal in sinking

[Richard Biener]

https://gcc.gnu.org/g:e7cda6ef77d65839a21a0160cb0a81aa0cc5a7dc

commit r14-2815-ge7cda6ef77d65839a21a0160cb0a81aa0cc5a7dc
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Jul 27 10:23:16 2023 +0200

    Remove recursive post-dominator traversal in sinking
    
    The following turns the recursive post-dominator traversal in GIMPLE
    code sinking to a worklist.
    
            * tree-ssa-sink.cc (sink_code_in_bb): Remove recursion, instead
            use a worklist ...
            (pass_sink_code::execute): ... in the caller.

Diff:
---
 gcc/tree-ssa-sink.cc | 27 ++++++++++++++++-----------
 1 file changed, 16 insertions(+), 11 deletions(-)

diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
index b1ba7a2ad6c..cf0a32a954b 100644
--- a/gcc/tree-ssa-sink.cc
+++ b/gcc/tree-ssa-sink.cc
@@ -671,7 +671,6 @@ sink_common_stores_to_bb (basic_block bb)
 static unsigned
 sink_code_in_bb (basic_block bb)
 {
-  basic_block son;
   gimple_stmt_iterator gsi;
   edge_iterator ei;
   edge e;
@@ -684,12 +683,12 @@ sink_code_in_bb (basic_block bb)
   /* If this block doesn't dominate anything, there can't be any place to sink
      the statements to.  */
   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
-    goto earlyout;
+    return todo;
 
   /* We can't move things across abnormal edges, so don't try.  */
   FOR_EACH_EDGE (e, ei, bb->succs)
     if (e->flags & EDGE_ABNORMAL)
-      goto earlyout;
+      return todo;
 
   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
     {
@@ -763,13 +762,6 @@ sink_code_in_bb (basic_block bb)
 	gsi_prev (&gsi);
 
     }
- earlyout:
-  for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
-       son;
-       son = next_dom_son (CDI_POST_DOMINATORS, son))
-    {
-      todo |= sink_code_in_bb (son);
-    }
 
   return todo;
 }
@@ -859,7 +851,20 @@ pass_sink_code::execute (function *fun)
   memset (&sink_stats, 0, sizeof (sink_stats));
   calculate_dominance_info (CDI_DOMINATORS);
   calculate_dominance_info (CDI_POST_DOMINATORS);
-  todo |= sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun));
+
+  auto_vec<basic_block, 64> worklist;
+  worklist.quick_push (EXIT_BLOCK_PTR_FOR_FN (fun));
+  do
+    {
+      basic_block bb = worklist.pop ();
+      todo |= sink_code_in_bb (bb);
+      for (basic_block son = first_dom_son (CDI_POST_DOMINATORS, bb);
+	   son;
+	   son = next_dom_son (CDI_POST_DOMINATORS, son))
+	worklist.safe_push (son);
+    }
+  while (!worklist.is_empty ());
+
   statistics_counter_event (fun, "Sunk statements", sink_stats.sunk);
   statistics_counter_event (fun, "Commoned stores", sink_stats.commoned);
   free_dominance_info (CDI_POST_DOMINATORS);