[PATCH] Fix PR54492

[Richard Guenther]

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.

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

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend