Patchwork Fix PR54492

login
register
mail settings
Submitter William J. Schmidt
Date Sept. 10, 2012, 2:40 p.m.
Message ID <1347288007.4740.4.camel@oc2474580526.ibm.com>
Download mbox | patch
Permalink /patch/182899/
State New
Headers show

Comments

William J. Schmidt - Sept. 10, 2012, 2:40 p.m.
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  <wschmidt@linux.vnet.ibm.com>

	* gimple-ssa-strength-reduction.c (find_basis_for_candidate): Limit
	the time spent searching for a basis.
Richard Guenther - Sept. 10, 2012, 2:45 p.m.
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;
>  
> 
> 
>
Jakub Jelinek - Sept. 10, 2012, 2:50 p.m.
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?

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

	Jakub
William J. Schmidt - Sept. 10, 2012, 2:54 p.m.
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;
> >  
> > 
> > 
> > 
>
Richard Guenther - Sept. 10, 2012, 2:56 p.m.
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  <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;
> 
> 	Jakub
> 
>
William J. Schmidt - Sept. 10, 2012, 3:37 p.m.
On Mon, 2012-09-10 at 16:56 +0200, Richard Guenther wrote:
> 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.

OK, I'll get a param in place and get back to you.  Thanks...

Bill

> 
> Richard.
> 
> > > > 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;
> > 
> > 	Jakub
> > 
> > 
>

Patch

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;