| Message ID | 1347288007.4740.4.camel@oc2474580526.ibm.com |
|---|---|
| State | New |
| Headers | show |
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; > > > >
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
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; > > > > > > > > >
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 > >
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 > > > > >
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;