From 6fc2f9337311c11dabcc464c808cbef205f17a52 Mon Sep 17 00:00:00 2001 From: Andrew Pinski Date: Tue, 21 Jan 2020 08:34:42 +0000 Subject: [PATCH] Change recursive prepare_block_for_update to use a worklist 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 8c17e59..262f0d6 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2020-01-21 Andrew Pinski + + 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 * gcc/config/arm/arm.c (clear_operation_p): diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c index c27bf2c..6528aca 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.7.4