[PATCH/commited] Change recursive prepare_block_for_update to use a worklist

[apinski@marvell.com]

From: Andrew Pinski <apinski@marvell.com>


This is what I committed.

Reported as PR 93321, prepare_block_for_update with some huge
recusive inlining can go past the stack limit. Transforming this
recursive into worklist improves the stack usage here and we no
longer seg fault for the testcase.  Note the order we walk the siblings
change.

ChangeLog:
	PR tree-opt/93321
	* tree-into-ssa.c (prepare_block_for_update_1): Split out from ...
	(prepare_block_for_update): This.  Use a worklist instead of recursing.
---
 gcc/ChangeLog       |  8 ++++++
 gcc/tree-into-ssa.c | 59 ++++++++++++++++++++++++++++++++++++---------
 2 files changed, 55 insertions(+), 12 deletions(-)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8c17e5992d2..262f0d6506f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2020-01-21  Andrew Pinski  <apinski@marvel.com>
+
+	PR tree-opt/93321
+	* tree-into-ssa.c (prepare_block_for_update_1): Split out
+	from ...
+	(prepare_block_for_update): This.  Use a worklist instead of
+	recursing.
+
 2020-01-21  Mihail-Calin Ionescu  <mihail.ionescu@arm.com>
 
 	* gcc/config/arm/arm.c (clear_operation_p):
diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c
index c27bf2ce121..6528acac31a 100644
--- a/gcc/tree-into-ssa.c
+++ b/gcc/tree-into-ssa.c
@@ -2593,11 +2593,9 @@ mark_use_interesting (tree var, gimple *stmt, basic_block bb,
     }
 }
 
-
-/* Do a dominator walk starting at BB processing statements that
-   reference symbols in SSA operands.  This is very similar to
-   mark_def_sites, but the scan handles statements whose operands may
-   already be SSA names.
+/* Processing statements in BB that reference symbols in SSA operands.
+   This is very similar to mark_def_sites, but the scan handles
+   statements whose operands may already be SSA names.
 
    If INSERT_PHI_P is true, mark those uses as live in the
    corresponding block.  This is later used by the PHI placement
@@ -2610,9 +2608,8 @@ mark_use_interesting (tree var, gimple *stmt, basic_block bb,
 	   that.  */
 
 static void
-prepare_block_for_update (basic_block bb, bool insert_phi_p)
+prepare_block_for_update_1 (basic_block bb, bool insert_phi_p)
 {
-  basic_block son;
   edge e;
   edge_iterator ei;
 
@@ -2694,13 +2691,51 @@ prepare_block_for_update (basic_block bb, bool insert_phi_p)
 	}
     }
 
-  /* Now visit all the blocks dominated by BB.  */
-  for (son = first_dom_son (CDI_DOMINATORS, bb);
-       son;
-       son = next_dom_son (CDI_DOMINATORS, son))
-    prepare_block_for_update (son, insert_phi_p);
 }
 
+/* Do a dominator walk starting at BB processing statements that
+   reference symbols in SSA operands.  This is very similar to
+   mark_def_sites, but the scan handles statements whose operands may
+   already be SSA names.
+
+   If INSERT_PHI_P is true, mark those uses as live in the
+   corresponding block.  This is later used by the PHI placement
+   algorithm to make PHI pruning decisions.
+
+   FIXME.  Most of this would be unnecessary if we could associate a
+	   symbol to all the SSA names that reference it.  But that
+	   sounds like it would be expensive to maintain.  Still, it
+	   would be interesting to see if it makes better sense to do
+	   that.  */
+static void
+prepare_block_for_update (basic_block bb, bool insert_phi_p)
+{
+  size_t sp = 0;
+  basic_block *worklist;
+
+  /* Allocate the worklist.  */
+  worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
+  /* Add the BB to the worklist.  */
+  worklist[sp++] = bb;
+
+  while (sp)
+    {
+      basic_block bb;
+      basic_block son;
+
+      /* Pick a block from the worklist.  */
+      bb = worklist[--sp];
+
+      prepare_block_for_update_1 (bb, insert_phi_p);
+
+      /* Now add all the blocks dominated by BB to the worklist.  */
+      for (son = first_dom_son (CDI_DOMINATORS, bb);
+	   son;
+	   son = next_dom_son (CDI_DOMINATORS, son))
+	worklist[sp++] = son;
+    }
+  free (worklist);
+}
 
 /* Helper for prepare_names_to_update.  Mark all the use sites for
    NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
-- 
2.17.1