[PATCH] Limit SCCVN SCC size for obscure cases
Richard Guenther
rguenther@suse.de
Thu Dec 13 13:32:00 GMT 2007
With PR34450 we end up processing a SCC with ~100000 members (99%
SFTs) which ends up using around 2GB of ram and a noticable amount of
time. Now I expect us to get rid of SFTs in the 4.4 time-frame, but
limiting the SCC as a stop-gap is a good idea anyway. Note that the
amount of SFTs created is reasonable (we have lots of temporary
small vectors and matrices that get decomposed, limiting the number of
SFTs per structure to 5 does not help). What would probably help
as well (I have experimented with this in the past) is to run cleanup
passes after final inlining but before we compute aliasing, which
is able to reduce the amount of addressable variables (but maybe not
the number of structures we decompose).
So this patch limits the size of SCCs to 10000 members, which for this
testcase reduces compile-time and memory-usage back to 4.2 numbers.
Bootstrapped and tested on x86_64-unknown-linux-gnu, also bootstrapped
with --param sccvn-max-scc-size=10.
Ok?
Thanks,
Richard.
2007-12-13 Richard Guenther <rguenther@suse.de>
PR tree-optimization/34450
* params.def (PARAM_SCCVN_MAX_SCC_SIZE): New param.
* invoke.texi (sccvn-max-scc-size): Document.
* Makefile.in (tree-ssa-sccvn.o): Add $(PARAMS_H) dependency.
* tree-ssa-sccvn.h (run_scc_vn): Return true on success, false
on error.
* tree-ssa-sccvn.c (params.h): Include.
(DFS): Return true if all went well, return false as soon as
a SCC exceeds the size of PARAM_SCCVN_MAX_SCC_SIZE.
(run_scc_vn): Return true if all went well, return false if
we aborted during DFS.
* tree-ssa-pre.c (execute_pre): Check if SCCVN finished
successfully, otherwise bail out.
Index: Makefile.in
===================================================================
*** Makefile.in (revision 130795)
--- Makefile.in (working copy)
*************** tree-ssa-sccvn.o : tree-ssa-sccvn.c $(TR
*** 2075,2081 ****
$(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) \
$(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) $(CFGLOOP_H) \
alloc-pool.h $(BASIC_BLOCK_H) bitmap.h $(HASHTAB_H) $(TREE_GIMPLE_H) \
! $(TREE_INLINE_H) tree-iterator.h tree-ssa-propagate.h tree-ssa-sccvn.h
tree-vn.o : tree-vn.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(GGC_H) \
$(TREE_H) $(TREE_FLOW_H) $(HASHTAB_H) langhooks.h tree-pass.h \
$(TREE_DUMP_H) $(DIAGNOSTIC_H) tree-ssa-sccvn.h
--- 2075,2082 ----
$(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) \
$(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) $(CFGLOOP_H) \
alloc-pool.h $(BASIC_BLOCK_H) bitmap.h $(HASHTAB_H) $(TREE_GIMPLE_H) \
! $(TREE_INLINE_H) tree-iterator.h tree-ssa-propagate.h tree-ssa-sccvn.h \
! $(PARAMS_H)
tree-vn.o : tree-vn.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(GGC_H) \
$(TREE_H) $(TREE_FLOW_H) $(HASHTAB_H) langhooks.h tree-pass.h \
$(TREE_DUMP_H) $(DIAGNOSTIC_H) tree-ssa-sccvn.h
Index: params.def
===================================================================
*** params.def (revision 130795)
--- params.def (working copy)
*************** DEFPARAM (PARAM_MAX_PARTIAL_ANTIC_LENGTH
*** 713,718 ****
--- 713,729 ----
"Maximum length of partial antic set when performing tree pre optimization",
100, 0, 0)
+ /* The following is used as a stop-gap limit for cases where really huge
+ SCCs blow up memory and compile-time use too much. If we hit this limit,
+ SCCVN and such FRE and PRE will be not done at all for the current
+ function. */
+
+ DEFPARAM (PARAM_SCCVN_MAX_SCC_SIZE,
+ "sccvn-max-scc-size",
+ "Maximum size of a SCC before SCCVN stops processing a function",
+ 10000, 10, 0)
+
+
/*
Local variables:
mode:c
Index: tree-ssa-sccvn.h
===================================================================
*** tree-ssa-sccvn.h (revision 130795)
--- tree-ssa-sccvn.h (working copy)
*************** typedef struct vn_ssa_aux
*** 48,54 ****
/* Return the value numbering info for an SSA_NAME. */
extern vn_ssa_aux_t VN_INFO (tree);
extern vn_ssa_aux_t VN_INFO_GET (tree);
! void run_scc_vn (void);
void free_scc_vn (void);
void switch_to_PRE_table (void);
tree vn_binary_op_lookup (tree);
--- 48,54 ----
/* Return the value numbering info for an SSA_NAME. */
extern vn_ssa_aux_t VN_INFO (tree);
extern vn_ssa_aux_t VN_INFO_GET (tree);
! bool run_scc_vn (void);
void free_scc_vn (void);
void switch_to_PRE_table (void);
tree vn_binary_op_lookup (tree);
Index: doc/invoke.texi
===================================================================
*** doc/invoke.texi (revision 130795)
--- doc/invoke.texi (working copy)
*************** parameter sets a limit on the length of
*** 7159,7164 ****
--- 7159,7170 ----
which prevents the runaway behaviour. Setting a value of 0 for
this paramter will allow an unlimited set length.
+ @item sccvn-max-scc-size
+ Maximum size of a strongly connected component (SCC) during SCCVN
+ processing. If this limit is hit, SCCVN processing for the whole
+ function will not be done and optimizations depending on it will
+ be disabled. The default maximum SCC size is 10000.
+
@end table
@end table
Index: tree-ssa-sccvn.c
===================================================================
*** tree-ssa-sccvn.c (revision 130795)
--- tree-ssa-sccvn.c (working copy)
*************** along with GCC; see the file COPYING3.
*** 42,47 ****
--- 42,48 ----
#include "bitmap.h"
#include "langhooks.h"
#include "cfgloop.h"
+ #include "params.h"
#include "tree-ssa-propagate.h"
#include "tree-ssa-sccvn.h"
*************** process_scc (VEC (tree, heap) *scc)
*** 1837,1845 ****
/* 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
! popped off the stack in topological order. */
! static void
DFS (tree name)
{
ssa_op_iter iter;
--- 1838,1848 ----
/* 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
! popped off the stack in topological order.
! Returns true if successful, false if we stopped processing SCC's due
! to ressource constraints. */
! static bool
DFS (tree name)
{
ssa_op_iter iter;
*************** DFS (tree name)
*** 1870,1876 ****
if (! (VN_INFO (use)->visited))
{
! DFS (use);
VN_INFO (name)->low = MIN (VN_INFO (name)->low,
VN_INFO (use)->low);
}
--- 1873,1880 ----
if (! (VN_INFO (use)->visited))
{
! if (!DFS (use))
! return false;
VN_INFO (name)->low = MIN (VN_INFO (name)->low,
VN_INFO (use)->low);
}
*************** DFS (tree name)
*** 1899,1904 ****
--- 1903,1913 ----
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))
+ return false;
+
if (VEC_length (tree, scc) > 1)
sort_scc (scc);
*************** DFS (tree name)
*** 1909,1914 ****
--- 1918,1925 ----
VEC_free (tree, heap, scc);
}
+
+ return true;
}
static void
*************** free_scc_vn (void)
*** 2074,2080 ****
}
}
! void
run_scc_vn (void)
{
size_t i;
--- 2085,2094 ----
}
}
! /* Do SCCVN. Returns true if it finished, false if we bailed out
! due to ressource constraints. */
!
! bool
run_scc_vn (void)
{
size_t i;
*************** run_scc_vn (void)
*** 2100,2106 ****
if (name
&& VN_INFO (name)->visited == false
&& !has_zero_uses (name))
! DFS (name);
}
if (dump_file && (dump_flags & TDF_DETAILS))
--- 2114,2124 ----
if (name
&& VN_INFO (name)->visited == false
&& !has_zero_uses (name))
! if (!DFS (name))
! {
! free_scc_vn ();
! return false;
! }
}
if (dump_file && (dump_flags & TDF_DETAILS))
*************** run_scc_vn (void)
*** 2123,2126 ****
--- 2141,2146 ----
}
}
}
+
+ return true;
}
Index: tree-ssa-pre.c
===================================================================
*** tree-ssa-pre.c (revision 130795)
--- tree-ssa-pre.c (working copy)
*************** execute_pre (bool do_fre)
*** 3933,3939 ****
insert_fake_stores ();
/* Collect and value number expressions computed in each basic block. */
! run_scc_vn ();
switch_to_PRE_table ();
compute_avail ();
--- 3933,3945 ----
insert_fake_stores ();
/* Collect and value number expressions computed in each basic block. */
! if (!run_scc_vn ())
! {
! if (!do_fre)
! remove_dead_inserted_code ();
! fini_pre ();
! return;
! }
switch_to_PRE_table ();
compute_avail ();
More information about the Gcc-patches
mailing list