From 9bb06c2a9f8b83179cb76ba928b22aa3a2b57501 Mon Sep 17 00:00:00 2001 From: Richard Guenther Date: Wed, 22 Aug 2012 13:17:26 +0000 Subject: [PATCH] re PR tree-optimization/46590 (long compile time with -O2 and many loops) 2012-08-22 Richard Guenther 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. From-SVN: r190594 --- gcc/ChangeLog | 21 +++++++++++++++++++++ gcc/doc/invoke.texi | 8 ++++++++ gcc/params.def | 11 +++++++++++ gcc/tree-ssa-alias.c | 49 +++++++++++++++++++++++++++++++++---------------- gcc/tree-ssa-alias.h | 6 ++++-- gcc/tree-ssa-pre.c | 3 ++- gcc/tree-ssa-sccvn.c | 9 ++++++++- 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 + 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 + * 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; -- 2.7.4