On Mon, 10 Sep 2012, Jakub Jelinek wrote:
> On Mon, Sep 10, 2012 at 04:45:24PM +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.
>
> Don't we want a param for that, or is a hardcoded magic constant fine here?
I suppose a param for it would be nice.
Richard.
> > > 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;
>
> Jakub
>
>
--
Richard Biener <rguent...@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
