[PATCH] Fix stack usage of SCCVN, PR35204
Richard Guenther
rguenther@suse.de
Tue Feb 19 12:28:00 GMT 2008
The DFS walk in SCCVN is done recursively and is in some cases such as
PR35204 using up more than the soft stack size limit on x86_64-linux,
which is 8MB. This patch addresses this by not recursing, but keeping
multiple SSA use iterators on a heap allocated stack instead.
The patch doesn't show adverse effects on compile-time or memory usage
when applied to our daily testers of SPEC & friends.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
Ok for mainline?
Thanks,
Richard.
2008-02-16 Richard Guenther <rguenther@suse.de>
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.
Index: tree-ssa-sccvn.c
===================================================================
*** tree-ssa-sccvn.c (revision 132268)
--- tree-ssa-sccvn.c (working copy)
*************** process_scc (VEC (tree, heap) *scc)
*** 1857,1862 ****
--- 1857,1909 ----
}
}
+ 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
*************** process_scc (VEC (tree, heap) *scc)
*** 1867,1876 ****
static bool
DFS (tree name)
{
! ssa_op_iter iter;
use_operand_p usep;
! tree defstmt;
/* SCC info */
VN_INFO (name)->dfsnum = next_dfs_num++;
VN_INFO (name)->visited = true;
--- 1914,1926 ----
static bool
DFS (tree name)
{
! VEC(ssa_op_iter, heap) *itervec = NULL;
! VEC(tree, heap) *namevec = NULL;
use_operand_p usep;
! tree defstmt, use;
! ssa_op_iter iter;
+ start_over:
/* SCC info */
VN_INFO (name)->dfsnum = next_dfs_num++;
VN_INFO (name)->visited = true;
*************** DFS (tree name)
*** 1883,1902 ****
/* 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)
{
! tree 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)
! continue;
if (! (VN_INFO (use)->visited))
{
! if (!DFS (use))
! return false;
VN_INFO (name)->low = MIN (VN_INFO (name)->low,
VN_INFO (use)->low);
}
--- 1933,1995 ----
/* Recursively DFS on our operands, looking for SCC's. */
if (!IS_EMPTY_STMT (defstmt))
{
! /* 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))
{
! /* 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;
! }
!
! /* 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))
{
! /* 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);
}
*************** DFS (tree name)
*** 1907,1953 ****
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);
}
-
- return true;
}
/* Allocate a value number table. */
--- 2000,2008 ----
VN_INFO (name)->low);
}
}
! usep = op_iter_next_use (&iter);
}
}
/* Allocate a value number table. */
More information about the Gcc-patches
mailing list