From 6be349364986cc95bf8e7691476c197f1ee629ea Mon Sep 17 00:00:00 2001 From: Richard Guenther Date: Tue, 20 May 2008 20:40:23 +0000 Subject: [PATCH] re PR middle-end/35204 (crash by too deep recursion in DFS tree-ssa-sccvn.c:1898) 2008-05-20 Richard Guenther PR tree-optimization/35204 * tree-ssa-sccvn.c (extract_and_process_scc_for_name): New helper, split out from ... (DFS): ... here. Make the DFS walk non-recursive. From-SVN: r135676 --- gcc/ChangeLog | 7 ++ gcc/tree-ssa-sccvn.c | 155 +++++++++++++++++++++++++++++-------------- 2 files changed, 112 insertions(+), 50 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 65cb134a461..cdc2b9dd0e0 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2008-05-20 Richard Guenther + + PR tree-optimization/35204 + * tree-ssa-sccvn.c (extract_and_process_scc_for_name): New + helper, split out from ... + (DFS): ... here. Make the DFS walk non-recursive. + 2008-05-20 Sebastian Pop Jan Sjodin diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index 2bc9cb2e3ef..86777c784f0 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -1956,6 +1956,53 @@ process_scc (VEC (tree, heap) *scc) } } +DEF_VEC_O(ssa_op_iter); +DEF_VEC_ALLOC_O(ssa_op_iter,heap); + +/* Pop the components of the found SCC for NAME off the SCC stack + and process them. Returns true if all went well, false if + we run into resource limits. */ + +static bool +extract_and_process_scc_for_name (tree name) +{ + VEC (tree, heap) *scc = NULL; + tree x; + + /* Found an SCC, pop the components off the SCC stack and + process them. */ + do + { + x = VEC_pop (tree, sccstack); + + VN_INFO (x)->on_sccstack = false; + VEC_safe_push (tree, heap, scc, x); + } while (x != name); + + /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */ + if (VEC_length (tree, scc) + > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE)) + { + if (dump_file) + fprintf (dump_file, "WARNING: Giving up with SCCVN due to " + "SCC size %u exceeding %u\n", VEC_length (tree, scc), + (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE)); + return false; + } + + if (VEC_length (tree, scc) > 1) + sort_scc (scc); + + if (dump_file && (dump_flags & TDF_DETAILS)) + print_scc (dump_file, scc); + + process_scc (scc); + + VEC_free (tree, heap, scc); + + return true; +} + /* Depth first search on NAME to discover and process SCC's in the SSA graph. Execution of this algorithm relies on the fact that the SCC's are @@ -1966,10 +2013,13 @@ process_scc (VEC (tree, heap) *scc) static bool DFS (tree name) { + VEC(ssa_op_iter, heap) *itervec = NULL; + VEC(tree, heap) *namevec = NULL; + use_operand_p usep = NULL; + tree defstmt, use; ssa_op_iter iter; - use_operand_p usep; - tree defstmt; +start_over: /* SCC info */ VN_INFO (name)->dfsnum = next_dfs_num++; VN_INFO (name)->visited = true; @@ -1982,20 +2032,63 @@ DFS (tree name) /* Recursively DFS on our operands, looking for SCC's. */ if (!IS_EMPTY_STMT (defstmt)) { - FOR_EACH_PHI_OR_STMT_USE (usep, SSA_NAME_DEF_STMT (name), iter, - SSA_OP_ALL_USES) + /* Push a new iterator. */ + if (TREE_CODE (defstmt) == PHI_NODE) + usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES); + else + usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES); + } + else + iter.done = true; + + while (1) + { + /* If we are done processing uses of a name, go up the stack + of iterators and process SCCs as we found them. */ + if (op_iter_done (&iter)) { - tree use = USE_FROM_PTR (usep); + /* See if we found an SCC. */ + if (VN_INFO (name)->low == VN_INFO (name)->dfsnum) + if (!extract_and_process_scc_for_name (name)) + { + VEC_free (tree, heap, namevec); + VEC_free (ssa_op_iter, heap, itervec); + return false; + } - /* Since we handle phi nodes, we will sometimes get - invariants in the use expression. */ - if (TREE_CODE (use) != SSA_NAME) - continue; + /* Check if we are done. */ + if (VEC_empty (tree, namevec)) + { + VEC_free (tree, heap, namevec); + VEC_free (ssa_op_iter, heap, itervec); + return true; + } + + /* Restore the last use walker and continue walking there. */ + use = name; + name = VEC_pop (tree, namevec); + memcpy (&iter, VEC_last (ssa_op_iter, itervec), + sizeof (ssa_op_iter)); + VEC_pop (ssa_op_iter, itervec); + goto continue_walking; + } + use = USE_FROM_PTR (usep); + + /* Since we handle phi nodes, we will sometimes get + invariants in the use expression. */ + if (TREE_CODE (use) == SSA_NAME) + { if (! (VN_INFO (use)->visited)) { - if (!DFS (use)) - return false; + /* Recurse by pushing the current use walking state on + the stack and starting over. */ + VEC_safe_push(ssa_op_iter, heap, itervec, &iter); + VEC_safe_push(tree, heap, namevec, name); + name = use; + goto start_over; + +continue_walking: VN_INFO (name)->low = MIN (VN_INFO (name)->low, VN_INFO (use)->low); } @@ -2006,47 +2099,9 @@ DFS (tree name) VN_INFO (name)->low); } } - } - - /* See if we found an SCC. */ - if (VN_INFO (name)->low == VN_INFO (name)->dfsnum) - { - VEC (tree, heap) *scc = NULL; - tree x; - - /* Found an SCC, pop the components off the SCC stack and - process them. */ - do - { - x = VEC_pop (tree, sccstack); - - VN_INFO (x)->on_sccstack = false; - VEC_safe_push (tree, heap, scc, x); - } while (x != name); - - /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */ - if (VEC_length (tree, scc) - > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE)) - { - if (dump_file) - fprintf (dump_file, "WARNING: Giving up with SCCVN due to " - "SCC size %u exceeding %u\n", VEC_length (tree, scc), - (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE)); - return false; - } - if (VEC_length (tree, scc) > 1) - sort_scc (scc); - - if (dump_file && (dump_flags & TDF_DETAILS)) - print_scc (dump_file, scc); - - process_scc (scc); - - VEC_free (tree, heap, scc); + usep = op_iter_next_use (&iter); } - - return true; } /* Allocate a value number table. */ -- 2.30.2