[PATCH] Fix PR54492
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
* 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;
Re: [PATCH] Fix PR54492
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
>
> * 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
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
Re: [PATCH] Fix PR54492
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
> >
> > * 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
Re: [PATCH] Fix PR54492
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
> >
> > * 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;
> >
> >
> >
> >
>
Re: [PATCH] Fix PR54492
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
> > >
> > > * 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
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
Re: [PATCH] Fix PR54492
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
> > > >
> > > > * 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
> >
> >
>
Re: [PATCH] Fix PR54492
Here's the revised patch with a param. Bootstrapped and tested in the
same manner. Ok for trunk?
Thanks,
Bill
2012-08-10 Bill Schmidt
* doc/invoke.texi (max-slsr-cand-scan): New description.
* gimple-ssa-strength-reduction.c (find_basis_for_candidate): Limit
the time spent searching for a basis.
* params.def (PARAM_MAX_SLSR_CANDIDATE_SCAN): New param.
Index: gcc/doc/invoke.texi
===
--- gcc/doc/invoke.texi (revision 191135)
+++ gcc/doc/invoke.texi (working copy)
@@ -9407,6 +9407,11 @@ having a regular register file and accurate regist
See @file{haifa-sched.c} in the GCC sources for more details.
The default choice depends on the target.
+
+@item max-slsr-cand-scan
+Set the maximum number of existing candidates that will be considered when
+seeking a basis for a new straight-line strength reduction candidate.
+
@end table
@end table
Index: gcc/gimple-ssa-strength-reduction.c
===
--- gcc/gimple-ssa-strength-reduction.c (revision 191135)
+++ gcc/gimple-ssa-strength-reduction.c (working copy)
@@ -54,6 +54,7 @@ along with GCC; see the file COPYING3. If not see
#include "domwalk.h"
#include "pointer-set.h"
#include "expmed.h"
+#include "params.h"
/* Information about a strength reduction candidate. Each statement
in the candidate table represents an expression of one of the
@@ -353,10 +354,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;
+ int max_iters = PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN);
+
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;
Index: gcc/params.def
===
--- gcc/params.def (revision 191135)
+++ gcc/params.def (working copy)
@@ -973,6 +973,13 @@ DEFPARAM (PARAM_SCHED_PRESSURE_ALGORITHM,
"Which -fsched-pressure algorithm to apply",
1, 1, 2)
+/* Maximum length of candidate scans in straight-line strength reduction. */
+DEFPARAM (PARAM_MAX_SLSR_CANDIDATE_SCAN,
+ "max-slsr-cand-scan",
+ "Maximum length of candidate scans for straight-line "
+ "strength reduction",
+ 50, 1, 99)
+
/*
Local variables:
mode:c
Re: [PATCH] Fix PR54492
On Mon, 10 Sep 2012, William J. Schmidt wrote:
> Here's the revised patch with a param. Bootstrapped and tested in the
> same manner. Ok for trunk?
Ok.
Thanks,
Richard.
> Thanks,
> Bill
>
>
> 2012-08-10 Bill Schmidt
>
> * doc/invoke.texi (max-slsr-cand-scan): New description.
> * gimple-ssa-strength-reduction.c (find_basis_for_candidate): Limit
> the time spent searching for a basis.
> * params.def (PARAM_MAX_SLSR_CANDIDATE_SCAN): New param.
>
>
> Index: gcc/doc/invoke.texi
> ===
> --- gcc/doc/invoke.texi (revision 191135)
> +++ gcc/doc/invoke.texi (working copy)
> @@ -9407,6 +9407,11 @@ having a regular register file and accurate regist
> See @file{haifa-sched.c} in the GCC sources for more details.
>
> The default choice depends on the target.
> +
> +@item max-slsr-cand-scan
> +Set the maximum number of existing candidates that will be considered when
> +seeking a basis for a new straight-line strength reduction candidate.
> +
> @end table
> @end table
>
> Index: gcc/gimple-ssa-strength-reduction.c
> ===
> --- gcc/gimple-ssa-strength-reduction.c (revision 191135)
> +++ gcc/gimple-ssa-strength-reduction.c (working copy)
> @@ -54,6 +54,7 @@ along with GCC; see the file COPYING3. If not see
> #include "domwalk.h"
> #include "pointer-set.h"
> #include "expmed.h"
> +#include "params.h"
>
> /* Information about a strength reduction candidate. Each statement
> in the candidate table represents an expression of one of the
> @@ -353,10 +354,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;
> + int max_iters = PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN);
> +
>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;
>
> Index: gcc/params.def
> ===
> --- gcc/params.def(revision 191135)
> +++ gcc/params.def(working copy)
> @@ -973,6 +973,13 @@ DEFPARAM (PARAM_SCHED_PRESSURE_ALGORITHM,
> "Which -fsched-pressure algorithm to apply",
> 1, 1, 2)
>
> +/* Maximum length of candidate scans in straight-line strength reduction. */
> +DEFPARAM (PARAM_MAX_SLSR_CANDIDATE_SCAN,
> + "max-slsr-cand-scan",
> + "Maximum length of candidate scans for straight-line "
> + "strength reduction",
> + 50, 1, 99)
> +
> /*
> Local variables:
> mode:c
>
>
>
--
Richard Biener
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
