aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--gcc/ChangeLog21
-rw-r--r--gcc/doc/invoke.texi8
-rw-r--r--gcc/params.def11
-rw-r--r--gcc/tree-ssa-alias.c49
-rw-r--r--gcc/tree-ssa-alias.h6
-rw-r--r--gcc/tree-ssa-pre.c3
-rw-r--r--gcc/tree-ssa-sccvn.c9
7 files changed, 87 insertions, 20 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 1fec0b8..75cd34c 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,26 @@
2012-08-22 Richard Guenther <rguenther@suse.de>
+ PR tree-optimization/46590
+ * tree-ssa-alias.h (get_continuation_for_phi): Add alias query
+ counter output argument.
+ (walk_non_aliased_vuses): Add alias query counter argument
+ to the walker callback.
+ * tree-ssa-alias.c (maybe_skip_until): Add alias query counter
+ output argument and count alias queries.
+ (get_continuation_for_phi_1): Likewise.
+ (get_continuation_for_phi): Likewise.
+ (walk_non_aliased_vuses): Add alias query counter argument
+ to the walker callback and allow it to abort the walk by
+ returning -1.
+ * tree-ssa-pre.c (translate_vuse_through_block): Adjust.
+ * tree-ssa-sccvn.c (vn_reference_lookup_2): Add alias query
+ counter parmeter, abort walk if that is bigger than
+ --param sccvn-max-alias-queries-per-access.
+ * params.def (sccvn-max-alias-queries-per-access): New param.
+ * doc/invoke.texi (sccvn-max-alias-queries-per-access): Document.
+
+2012-08-22 Richard Guenther <rguenther@suse.de>
+
* tree-ssa-loop-ch.c (copy_loop_headers): Remove redundant checking.
* tree-into-ssa.c (initialize_flags_in_bb): Use gcc_checking_assert
instead of gcc_assert.
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index ae22ca9..599b0f6 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -9221,6 +9221,14 @@ processing. If this limit is hit, SCCVN processing for the whole
function is not done and optimizations depending on it are
disabled. The default maximum SCC size is 10000.
+@item sccvn-max-alias-queries-per-access
+Maximum number of alias-oracle queries we perform when looking for
+redundancies for loads and stores. If this limit is hit the search
+is aborted and the load or store is not considered redundant. The
+number of queries is algorithmically limited to the number of
+stores on all paths from the load to the function entry.
+The default maxmimum number of queries is 1000.
+
@item ira-max-loops-num
IRA uses regional register allocation by default. If a function
contains more loops than the number given by this parameter, only at most
diff --git a/gcc/params.def b/gcc/params.def
index cd8cb22..17351bf 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -752,6 +752,17 @@ DEFPARAM (PARAM_SCCVN_MAX_SCC_SIZE,
"Maximum size of a SCC before SCCVN stops processing a function",
10000, 10, 0)
+/* The following is used as a stop-gap limit for cases where really huge
+ functions blow up compile-time use too much. It limits the number of
+ alias-queries we do for finding common subexpressions for memory loads and
+ stores. The number of alias-queries is otherwise limited by the number of
+ stores on paths to function entry. */
+
+DEFPARAM (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS,
+ "sccvn-max-alias-queries-per-access",
+ "Maximum number of disambiguations to perform per memory access",
+ 1000, 0, 0)
+
DEFPARAM (PARAM_IRA_MAX_LOOPS_NUM,
"ira-max-loops-num",
"Max loops number for regional RA",
diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
index be0aa43..574f418 100644
--- a/gcc/tree-ssa-alias.c
+++ b/gcc/tree-ssa-alias.c
@@ -1929,7 +1929,7 @@ stmt_kills_ref_p (gimple stmt, tree ref)
static bool
maybe_skip_until (gimple phi, tree target, ao_ref *ref,
- tree vuse, bitmap *visited)
+ tree vuse, unsigned int *cnt, bitmap *visited)
{
basic_block bb = gimple_bb (phi);
@@ -1948,15 +1948,20 @@ maybe_skip_until (gimple phi, tree target, ao_ref *ref,
/* An already visited PHI node ends the walk successfully. */
if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (def_stmt))))
return true;
- vuse = get_continuation_for_phi (def_stmt, ref, visited);
+ vuse = get_continuation_for_phi (def_stmt, ref, cnt, visited);
if (!vuse)
return false;
continue;
}
- /* A clobbering statement or the end of the IL ends it failing. */
- else if (gimple_nop_p (def_stmt)
- || stmt_may_clobber_ref_p_1 (def_stmt, ref))
+ else if (gimple_nop_p (def_stmt))
return false;
+ else
+ {
+ /* A clobbering statement or the end of the IL ends it failing. */
+ ++*cnt;
+ if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
+ return false;
+ }
/* If we reach a new basic-block see if we already skipped it
in a previous walk that ended successfully. */
if (gimple_bb (def_stmt) != bb)
@@ -1976,7 +1981,7 @@ maybe_skip_until (gimple phi, tree target, ao_ref *ref,
static tree
get_continuation_for_phi_1 (gimple phi, tree arg0, tree arg1,
- ao_ref *ref, bitmap *visited)
+ ao_ref *ref, unsigned int *cnt, bitmap *visited)
{
gimple def0 = SSA_NAME_DEF_STMT (arg0);
gimple def1 = SSA_NAME_DEF_STMT (arg1);
@@ -1989,14 +1994,14 @@ get_continuation_for_phi_1 (gimple phi, tree arg0, tree arg1,
&& dominated_by_p (CDI_DOMINATORS,
gimple_bb (def1), gimple_bb (def0))))
{
- if (maybe_skip_until (phi, arg0, ref, arg1, visited))
+ if (maybe_skip_until (phi, arg0, ref, arg1, cnt, visited))
return arg0;
}
else if (gimple_nop_p (def1)
|| dominated_by_p (CDI_DOMINATORS,
gimple_bb (def0), gimple_bb (def1)))
{
- if (maybe_skip_until (phi, arg1, ref, arg0, visited))
+ if (maybe_skip_until (phi, arg1, ref, arg0, cnt, visited))
return arg1;
}
/* Special case of a diamond:
@@ -2015,6 +2020,7 @@ get_continuation_for_phi_1 (gimple phi, tree arg0, tree arg1,
else if ((common_vuse = gimple_vuse (def0))
&& common_vuse == gimple_vuse (def1))
{
+ *cnt += 2;
if (!stmt_may_clobber_ref_p_1 (def0, ref)
&& !stmt_may_clobber_ref_p_1 (def1, ref))
return common_vuse;
@@ -2027,11 +2033,12 @@ get_continuation_for_phi_1 (gimple phi, tree arg0, tree arg1,
/* Starting from a PHI node for the virtual operand of the memory reference
REF find a continuation virtual operand that allows to continue walking
statements dominating PHI skipping only statements that cannot possibly
- clobber REF. Returns NULL_TREE if no suitable virtual operand can
- be found. */
+ clobber REF. Increments *CNT for each alias disambiguation done.
+ Returns NULL_TREE if no suitable virtual operand can be found. */
tree
-get_continuation_for_phi (gimple phi, ao_ref *ref, bitmap *visited)
+get_continuation_for_phi (gimple phi, ao_ref *ref,
+ unsigned int *cnt, bitmap *visited)
{
unsigned nargs = gimple_phi_num_args (phi);
@@ -2068,7 +2075,8 @@ get_continuation_for_phi (gimple phi, ao_ref *ref, bitmap *visited)
for (i = 0; i < nargs; ++i)
{
arg1 = PHI_ARG_DEF (phi, i);
- arg0 = get_continuation_for_phi_1 (phi, arg0, arg1, ref, visited);
+ arg0 = get_continuation_for_phi_1 (phi, arg0, arg1, ref,
+ cnt, visited);
if (!arg0)
return NULL_TREE;
}
@@ -2099,11 +2107,12 @@ get_continuation_for_phi (gimple phi, ao_ref *ref, bitmap *visited)
void *
walk_non_aliased_vuses (ao_ref *ref, tree vuse,
- void *(*walker)(ao_ref *, tree, void *),
+ void *(*walker)(ao_ref *, tree, unsigned int, void *),
void *(*translate)(ao_ref *, tree, void *), void *data)
{
bitmap visited = NULL;
void *res;
+ unsigned int cnt = 0;
timevar_push (TV_ALIAS_STMT_WALK);
@@ -2112,17 +2121,25 @@ walk_non_aliased_vuses (ao_ref *ref, tree vuse,
gimple def_stmt;
/* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
- res = (*walker) (ref, vuse, data);
- if (res)
+ res = (*walker) (ref, vuse, cnt, data);
+ /* Abort walk. */
+ if (res == (void *)-1)
+ {
+ res = NULL;
+ break;
+ }
+ /* Lookup succeeded. */
+ else if (res != NULL)
break;
def_stmt = SSA_NAME_DEF_STMT (vuse);
if (gimple_nop_p (def_stmt))
break;
else if (gimple_code (def_stmt) == GIMPLE_PHI)
- vuse = get_continuation_for_phi (def_stmt, ref, &visited);
+ vuse = get_continuation_for_phi (def_stmt, ref, &cnt, &visited);
else
{
+ cnt++;
if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
{
if (!translate)
diff --git a/gcc/tree-ssa-alias.h b/gcc/tree-ssa-alias.h
index f350543..cdff381 100644
--- a/gcc/tree-ssa-alias.h
+++ b/gcc/tree-ssa-alias.h
@@ -107,9 +107,11 @@ extern bool stmt_may_clobber_ref_p (gimple, tree);
extern bool stmt_may_clobber_ref_p_1 (gimple, ao_ref *);
extern bool call_may_clobber_ref_p (gimple, tree);
extern bool stmt_kills_ref_p (gimple, tree);
-extern tree get_continuation_for_phi (gimple, ao_ref *, bitmap *);
+extern tree get_continuation_for_phi (gimple, ao_ref *,
+ unsigned int *, bitmap *);
extern void *walk_non_aliased_vuses (ao_ref *, tree,
- void *(*)(ao_ref *, tree, void *),
+ void *(*)(ao_ref *, tree,
+ unsigned int, void *),
void *(*)(ao_ref *, tree, void *), void *);
extern unsigned int walk_aliased_vdefs (ao_ref *, tree,
bool (*)(ao_ref *, tree, void *),
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index e113539..6d10df8 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -1289,9 +1289,10 @@ translate_vuse_through_block (VEC (vn_reference_op_s, heap) *operands,
if (use_oracle)
{
bitmap visited = NULL;
+ unsigned int cnt;
/* Try to find a vuse that dominates this phi node by skipping
non-clobbering statements. */
- vuse = get_continuation_for_phi (phi, &ref, &visited);
+ vuse = get_continuation_for_phi (phi, &ref, &cnt, &visited);
if (visited)
BITMAP_FREE (visited);
}
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 216d3f6..5d5a91c 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -1330,12 +1330,19 @@ static vn_lookup_kind default_vn_walk_kind;
with the current VUSE and performs the expression lookup. */
static void *
-vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse, void *vr_)
+vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse,
+ unsigned int cnt, void *vr_)
{
vn_reference_t vr = (vn_reference_t)vr_;
void **slot;
hashval_t hash;
+ /* This bounds the stmt walks we perform on reference lookups
+ to O(1) instead of O(N) where N is the number of dominating
+ stores. */
+ if (cnt > (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS))
+ return (void *)-1;
+
if (last_vuse_ptr)
*last_vuse_ptr = vuse;