Richard found some N^2 behavior in SLSR that has to be suppressed. Searching for the best possible basis is overkill when there are hundreds of thousands of possibilities. This patch constrains the search to "good enough" in such cases.
Bootstrapped and tested on powerpc64-unknown-linux-gnu with no regressions. Ok for trunk? Thanks, Bill 2012-08-10 Bill Schmidt <wschm...@linux.vnet.ibm.com> * gimple-ssa-strength-reduction.c (find_basis_for_candidate): Limit the time spent searching for a basis. Index: gcc/gimple-ssa-strength-reduction.c =================================================================== --- gcc/gimple-ssa-strength-reduction.c (revision 191135) +++ gcc/gimple-ssa-strength-reduction.c (working copy) @@ -353,10 +353,14 @@ find_basis_for_candidate (slsr_cand_t c) cand_chain_t chain; slsr_cand_t basis = NULL; + // Limit potential of N^2 behavior for long candidate chains. + int iters = 0; + const int MAX_ITERS = 50; + mapping_key.base_expr = c->base_expr; chain = (cand_chain_t) htab_find (base_cand_map, &mapping_key); - for (; chain; chain = chain->next) + for (; chain && iters < MAX_ITERS; chain = chain->next, ++iters) { slsr_cand_t one_basis = chain->cand;