On Mon, 2012-09-10 at 16:45 +0200, Richard Guenther wrote: > On Mon, 10 Sep 2012, William J. Schmidt wrote: > > > 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? > > Hm, rather than stopping the search, can we stop adding new candidates > instead so the list never grows that long? If that's not easy > the patch is ok as-is.
I think this way is probably better. Right now the potential bases are organized as a stack with new ones added to the front and considered first. To disable it there would require adding state to keep a count, and then we would only be looking at the most distant ones. This way the 50 most recently added potential bases (most likely to be local) are considered. Thanks, Bill > > Thanks, > Richard. > > > 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; > > > > > > > > >