[PATCH] Fix PR54492

William J. Schmidt wschmidt@linux.vnet.ibm.com
Mon Sep 10 14:55:00 GMT 2012


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  <wschmidt@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;
> >  
> > 
> > 
> > 
> 




More information about the Gcc-patches mailing list