[PATCHv2] Change recursive prepare_block_for_update to use a worklist
diff mbox series

Message ID 1579598802-718-1-git-send-email-apinski@marvell.com
State New
Headers show
Series
  • [PATCHv2] Change recursive prepare_block_for_update to use a worklist
Related show

Commit Message

Andrew Pinski Jan. 21, 2020, 9:26 a.m. UTC
From: Andrew Pinski <apinski@marvell.com>

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

OK?  Bootstrapped and tested on x86_64-linux-gnu with no regressions.

ChangeLog:
	* tree-into-ssa.c (prepare_block_for_update_1): Split out from ...
	(prepare_block_for_update): This.  Use a worklist instead of recursiving
	into the function.  Remove bb argument.
	(update_ssa): Update call to prepare_block_for_update.
---
 gcc/tree-into-ssa.c | 61 +++++++++++++++++++++++++++++++++++----------
 1 file changed, 48 insertions(+), 13 deletions(-)

Comments

Richard Biener Jan. 21, 2020, 10:54 a.m. UTC | #1
On Tue, Jan 21, 2020 at 10:27 AM <apinski@marvell.com> wrote:
>
> From: Andrew Pinski <apinski@marvell.com>
>
> 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
>
> OK?  Bootstrapped and tested on x86_64-linux-gnu with no regressions.

Can you keep the start_bb argument please?  Without it the callers setting
of start_bb and the comment doesn't make much sense.

OK with that change.
Thanks,
Richard.

> ChangeLog:
>         * tree-into-ssa.c (prepare_block_for_update_1): Split out from ...
>         (prepare_block_for_update): This.  Use a worklist instead of recursiving
>         into the function.  Remove bb argument.
>         (update_ssa): Update call to prepare_block_for_update.
> ---
>  gcc/tree-into-ssa.c | 61 +++++++++++++++++++++++++++++++++++----------
>  1 file changed, 48 insertions(+), 13 deletions(-)
>
> diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c
> index c27bf2ce121..9f1e8ece737 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 entry block 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 (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 entry BB to the worklist.  */
> +  worklist[sp++] = ENTRY_BLOCK_PTR_FOR_FN (cfun);
> +
> +  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
> @@ -3392,7 +3427,7 @@ update_ssa (unsigned update_flags)
>          symbols in SSA operands.  Mark interesting blocks and
>          statements and set local live-in information for the PHI
>          placement heuristics.  */
> -      prepare_block_for_update (start_bb, insert_phi_p);
> +      prepare_block_for_update (insert_phi_p);
>
>        tree name;
>
> --
> 2.17.1
>

Patch
diff mbox series

diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c
index c27bf2ce121..9f1e8ece737 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 entry block 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 (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 entry BB to the worklist.  */
+  worklist[sp++] = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+
+  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
@@ -3392,7 +3427,7 @@  update_ssa (unsigned update_flags)
 	 symbols in SSA operands.  Mark interesting blocks and
 	 statements and set local live-in information for the PHI
 	 placement heuristics.  */
-      prepare_block_for_update (start_bb, insert_phi_p);
+      prepare_block_for_update (insert_phi_p);
 
       tree name;