This finally limits the number of alias queries we do when looking
for redundant loads/stores from inside SCCVN (thus FRE and PRE).
Previously the number was bound roughly by O(n_loads * n_stores) while
now it is bound by O(n_loads) with the constant factor
--param sccvn-max-alias-queries-per-access. The patch should not
make any difference for any real-world testcase but SCCVN compile-time for
half of the artificial testcase in PR46590 goes down
from 230s to 13s.
I'm not sure limiting the walks more is necessary (we hit this
issue only for machine-generated code like this - where other
passes have similar issues, like loop header copying for this
particular case)
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Richard.
2012-08-22 Richard Guenther <rguent...@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.
Index: gcc/tree-ssa-alias.c
===================================================================
*** gcc/tree-ssa-alias.c.orig 2012-08-21 16:46:21.000000000 +0200
--- gcc/tree-ssa-alias.c 2012-08-22 13:38:45.502016867 +0200
*************** stmt_kills_ref_p (gimple stmt, tree ref)
*** 1929,1935 ****
static bool
maybe_skip_until (gimple phi, tree target, ao_ref *ref,
! tree vuse, bitmap *visited)
{
basic_block bb = gimple_bb (phi);
--- 1929,1935 ----
static bool
maybe_skip_until (gimple phi, tree target, ao_ref *ref,
! tree vuse, unsigned int *cnt, bitmap *visited)
{
basic_block bb = gimple_bb (phi);
*************** maybe_skip_until (gimple phi, tree targe
*** 1948,1962 ****
/* 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);
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))
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)
--- 1948,1967 ----
/* 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, cnt, visited);
if (!vuse)
return false;
continue;
}
! 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)
*************** maybe_skip_until (gimple phi, tree targe
*** 1976,1982 ****
static tree
get_continuation_for_phi_1 (gimple phi, tree arg0, tree arg1,
! ao_ref *ref, bitmap *visited)
{
gimple def0 = SSA_NAME_DEF_STMT (arg0);
gimple def1 = SSA_NAME_DEF_STMT (arg1);
--- 1981,1987 ----
static tree
get_continuation_for_phi_1 (gimple phi, tree arg0, tree arg1,
! ao_ref *ref, unsigned int *cnt, bitmap *visited)
{
gimple def0 = SSA_NAME_DEF_STMT (arg0);
gimple def1 = SSA_NAME_DEF_STMT (arg1);
*************** get_continuation_for_phi_1 (gimple phi,
*** 1989,2002 ****
&& dominated_by_p (CDI_DOMINATORS,
gimple_bb (def1), gimple_bb (def0))))
{
! if (maybe_skip_until (phi, arg0, ref, arg1, 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))
return arg1;
}
/* Special case of a diamond:
--- 1994,2007 ----
&& dominated_by_p (CDI_DOMINATORS,
gimple_bb (def1), gimple_bb (def0))))
{
! 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, cnt, visited))
return arg1;
}
/* Special case of a diamond:
*************** get_continuation_for_phi_1 (gimple phi,
*** 2015,2020 ****
--- 2020,2026 ----
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;
*************** get_continuation_for_phi_1 (gimple phi,
*** 2027,2037 ****
/* 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. */
tree
! get_continuation_for_phi (gimple phi, ao_ref *ref, bitmap *visited)
{
unsigned nargs = gimple_phi_num_args (phi);
--- 2033,2044 ----
/* 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. 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,
! unsigned int *cnt, bitmap *visited)
{
unsigned nargs = gimple_phi_num_args (phi);
*************** get_continuation_for_phi (gimple phi, ao
*** 2068,2074 ****
for (i = 0; i < nargs; ++i)
{
arg1 = PHI_ARG_DEF (phi, i);
! arg0 = get_continuation_for_phi_1 (phi, arg0, arg1, ref, visited);
if (!arg0)
return NULL_TREE;
}
--- 2075,2082 ----
for (i = 0; i < nargs; ++i)
{
arg1 = PHI_ARG_DEF (phi, i);
! arg0 = get_continuation_for_phi_1 (phi, arg0, arg1, ref,
! cnt, visited);
if (!arg0)
return NULL_TREE;
}
*************** get_continuation_for_phi (gimple phi, ao
*** 2099,2109 ****
void *
walk_non_aliased_vuses (ao_ref *ref, tree vuse,
! void *(*walker)(ao_ref *, tree, void *),
void *(*translate)(ao_ref *, tree, void *), void *data)
{
bitmap visited = NULL;
void *res;
timevar_push (TV_ALIAS_STMT_WALK);
--- 2107,2118 ----
void *
walk_non_aliased_vuses (ao_ref *ref, tree vuse,
! 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);
*************** walk_non_aliased_vuses (ao_ref *ref, tre
*** 2112,2128 ****
gimple def_stmt;
/* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
! res = (*walker) (ref, vuse, data);
! if (res)
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);
else
{
if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
{
if (!translate)
--- 2121,2145 ----
gimple def_stmt;
/* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
! 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, &cnt, &visited);
else
{
+ cnt++;
if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
{
if (!translate)
Index: gcc/tree-ssa-alias.h
===================================================================
*** gcc/tree-ssa-alias.h.orig 2012-08-21 16:46:21.000000000 +0200
--- gcc/tree-ssa-alias.h 2012-08-22 13:38:45.515016867 +0200
*************** extern bool stmt_may_clobber_ref_p (gimp
*** 107,115 ****
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 void *walk_non_aliased_vuses (ao_ref *, tree,
! void *(*)(ao_ref *, tree, void *),
void *(*)(ao_ref *, tree, void *), void *);
extern unsigned int walk_aliased_vdefs (ao_ref *, tree,
bool (*)(ao_ref *, tree, void *),
--- 107,117 ----
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 *,
! unsigned int *, bitmap *);
extern void *walk_non_aliased_vuses (ao_ref *, tree,
! 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 *),
Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c.orig 2012-08-20 13:56:21.000000000 +0200
--- gcc/tree-ssa-pre.c 2012-08-22 13:38:45.516016867 +0200
*************** translate_vuse_through_block (VEC (vn_re
*** 1289,1297 ****
if (use_oracle)
{
bitmap visited = NULL;
/* Try to find a vuse that dominates this phi node by skipping
non-clobbering statements. */
! vuse = get_continuation_for_phi (phi, &ref, &visited);
if (visited)
BITMAP_FREE (visited);
}
--- 1289,1298 ----
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, &cnt, &visited);
if (visited)
BITMAP_FREE (visited);
}
Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c.orig 2012-08-21 16:46:21.000000000 +0200
--- gcc/tree-ssa-sccvn.c 2012-08-22 13:40:03.232014176 +0200
*************** static vn_lookup_kind default_vn_walk_ki
*** 1330,1341 ****
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_t vr = (vn_reference_t)vr_;
void **slot;
hashval_t hash;
if (last_vuse_ptr)
*last_vuse_ptr = vuse;
--- 1330,1348 ----
with the current VUSE and performs the expression lookup. */
static void *
! 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;
Index: gcc/params.def
===================================================================
*** gcc/params.def.orig 2012-08-21 16:46:21.000000000 +0200
--- gcc/params.def 2012-08-22 13:46:33.323000670 +0200
*************** DEFPARAM (PARAM_SCCVN_MAX_SCC_SIZE,
*** 752,757 ****
--- 752,768 ----
"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",
Index: gcc/doc/invoke.texi
===================================================================
*** gcc/doc/invoke.texi.orig 2012-08-17 09:49:37.000000000 +0200
--- gcc/doc/invoke.texi 2012-08-22 13:46:36.765000551 +0200
*************** processing. If this limit is hit, SCCVN
*** 9221,9226 ****
--- 9221,9234 ----
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
