| Message ID | 1367932960.4938.21.camel@oc8801110288.ibm.com |
|---|---|
| State | New |
| Headers | show |
On Tue, 7 May 2013, Bill Schmidt wrote: > This handles the unlikely case where there are many different increments > associated with a group of related SLSR candidates, which could result > in poor performance when doing linear searches of the increment vector. > The size of the increment vector is limited to a reasonable constant, > and increments that do not appear in the increment vector are not > processed. > > Bootstrapped and tested on powerpc64-unknown-linux-gnu with no new > regressions. Ok for trunk? Ok. Thanks, Richard. > Thanks, > Bill > > > 2013-05-06 Bill Schmidt <wschmidt@linux.vnet.ibm.com> > > * gimple-ssa-strength-reduction.c (MAX_INCR_VEC_LEN): New constant. > (incr_vec_index): Return -1 if increment not found. > (create_add_on_incoming_edge): Assert if increment not found. > (record_increment): Limit number of increments recorded. > (all_phi_incrs_profitable): Return false if an increment not found. > (replace_profitable_candidates): Don't process increments that were > not recorded. > (analyze_candidates_and_replace): Limit size of incr_vec. > > > Index: gcc/gimple-ssa-strength-reduction.c > =================================================================== > --- gcc/gimple-ssa-strength-reduction.c (revision 198680) > +++ gcc/gimple-ssa-strength-reduction.c (working copy) > @@ -366,9 +366,11 @@ static struct obstack chain_obstack; > > /* An array INCR_VEC of incr_infos is used during analysis of related > candidates having an SSA name for a stride. INCR_VEC_LEN describes > - its current length. */ > + its current length. MAX_INCR_VEC_LEN is used to avoid costly > + pathological cases. */ > static incr_info_t incr_vec; > static unsigned incr_vec_len; > +const int MAX_INCR_VEC_LEN = 16; > > /* For a chain of candidates with unknown stride, indicates whether or not > we must generate pointer arithmetic when replacing statements. */ > @@ -1960,9 +1962,11 @@ replace_unconditional_candidate (slsr_cand_t c) > replace_mult_candidate (c, gimple_assign_lhs (basis->cand_stmt), bump); > } > > -/* Return the index in the increment vector of the given INCREMENT. */ > +/* Return the index in the increment vector of the given INCREMENT, > + or -1 if not found. The latter can occur if more than > + MAX_INCR_VEC_LEN increments have been found. */ > > -static inline unsigned > +static inline int > incr_vec_index (double_int increment) > { > unsigned i; > @@ -1970,8 +1974,10 @@ incr_vec_index (double_int increment) > for (i = 0; i < incr_vec_len && increment != incr_vec[i].incr; i++) > ; > > - gcc_assert (i < incr_vec_len); > - return i; > + if (i < incr_vec_len) > + return i; > + else > + return -1; > } > > /* Create a new statement along edge E to add BASIS_NAME to the product > @@ -2015,9 +2021,10 @@ create_add_on_incoming_edge (slsr_cand_t c, tree b > } > else > { > - unsigned i; > + int i; > bool negate_incr = (!address_arithmetic_p && increment.is_negative ()); > i = incr_vec_index (negate_incr ? -increment : increment); > + gcc_assert (i >= 0); > > if (incr_vec[i].initializer) > { > @@ -2323,7 +2330,7 @@ record_increment (slsr_cand_t c, double_int increm > } > } > > - if (!found) > + if (!found && incr_vec_len < MAX_INCR_VEC_LEN - 1) > { > /* The first time we see an increment, create the entry for it. > If this is the root candidate which doesn't have a basis, set > @@ -3025,7 +3032,7 @@ all_phi_incrs_profitable (slsr_cand_t c, gimple ph > } > else > { > - unsigned j; > + int j; > slsr_cand_t arg_cand = base_cand_from_table (arg); > double_int increment = arg_cand->index - basis->index; > > @@ -3041,14 +3048,19 @@ all_phi_incrs_profitable (slsr_cand_t c, gimple ph > print_gimple_stmt (dump_file, phi, 0, 0); > fputs (" increment: ", dump_file); > dump_double_int (dump_file, increment, false); > - fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost); > - if (profitable_increment_p (j)) > - fputs (" Replacing...\n", dump_file); > - else > - fputs (" Not replaced.\n", dump_file); > + if (j < 0) > + fprintf (dump_file, > + "\n Not replaced; incr_vec overflow.\n"); > + else { > + fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost); > + if (profitable_increment_p (j)) > + fputs (" Replacing...\n", dump_file); > + else > + fputs (" Not replaced.\n", dump_file); > + } > } > > - if (!profitable_increment_p (j)) > + if (j < 0 || !profitable_increment_p (j)) > return false; > } > } > @@ -3268,13 +3280,14 @@ replace_profitable_candidates (slsr_cand_t c) > { > double_int increment = cand_abs_increment (c); > enum tree_code orig_code = gimple_assign_rhs_code (c->cand_stmt); > - unsigned i; > + int i; > > i = incr_vec_index (increment); > > /* Only process profitable increments. Nothing useful can be done > to a cast or copy. */ > - if (profitable_increment_p (i) > + if (i >= 0 > + && profitable_increment_p (i) > && orig_code != MODIFY_EXPR > && orig_code != NOP_EXPR) > { > @@ -3378,6 +3391,8 @@ analyze_candidates_and_replace (void) > length = count_candidates (c); > if (!length) > continue; > + if (length > MAX_INCR_VEC_LEN) > + length = MAX_INCR_VEC_LEN; > > /* Construct an array of increments for this candidate chain. */ > incr_vec = XNEWVEC (incr_info, length); > > >
On 05/07/2013 07:22 AM, Bill Schmidt wrote: > This handles the unlikely case where there are many different increments > associated with a group of related SLSR candidates, which could result > in poor performance when doing linear searches of the increment vector. > The size of the increment vector is limited to a reasonable constant, > and increments that do not appear in the increment vector are not > processed. > > Bootstrapped and tested on powerpc64-unknown-linux-gnu with no new > regressions. Ok for trunk? > > Thanks, > Bill > > > 2013-05-06 Bill Schmidt <wschmidt@linux.vnet.ibm.com> > > * gimple-ssa-strength-reduction.c (MAX_INCR_VEC_LEN): New constant. > (incr_vec_index): Return -1 if increment not found. > (create_add_on_incoming_edge): Assert if increment not found. > (record_increment): Limit number of increments recorded. > (all_phi_incrs_profitable): Return false if an increment not found. > (replace_profitable_candidates): Don't process increments that were > not recorded. > (analyze_candidates_and_replace): Limit size of incr_vec. BTW, I'd be interested to know if anyone has poked at the SH port to see if SLSR eliminates the need for reload_cse_move2add? Who does SH stuff these days? jeff
Index: gcc/gimple-ssa-strength-reduction.c =================================================================== --- gcc/gimple-ssa-strength-reduction.c (revision 198680) +++ gcc/gimple-ssa-strength-reduction.c (working copy) @@ -366,9 +366,11 @@ static struct obstack chain_obstack; /* An array INCR_VEC of incr_infos is used during analysis of related candidates having an SSA name for a stride. INCR_VEC_LEN describes - its current length. */ + its current length. MAX_INCR_VEC_LEN is used to avoid costly + pathological cases. */ static incr_info_t incr_vec; static unsigned incr_vec_len; +const int MAX_INCR_VEC_LEN = 16; /* For a chain of candidates with unknown stride, indicates whether or not we must generate pointer arithmetic when replacing statements. */ @@ -1960,9 +1962,11 @@ replace_unconditional_candidate (slsr_cand_t c) replace_mult_candidate (c, gimple_assign_lhs (basis->cand_stmt), bump); } -/* Return the index in the increment vector of the given INCREMENT. */ +/* Return the index in the increment vector of the given INCREMENT, + or -1 if not found. The latter can occur if more than + MAX_INCR_VEC_LEN increments have been found. */ -static inline unsigned +static inline int incr_vec_index (double_int increment) { unsigned i; @@ -1970,8 +1974,10 @@ incr_vec_index (double_int increment) for (i = 0; i < incr_vec_len && increment != incr_vec[i].incr; i++) ; - gcc_assert (i < incr_vec_len); - return i; + if (i < incr_vec_len) + return i; + else + return -1; } /* Create a new statement along edge E to add BASIS_NAME to the product @@ -2015,9 +2021,10 @@ create_add_on_incoming_edge (slsr_cand_t c, tree b } else { - unsigned i; + int i; bool negate_incr = (!address_arithmetic_p && increment.is_negative ()); i = incr_vec_index (negate_incr ? -increment : increment); + gcc_assert (i >= 0); if (incr_vec[i].initializer) { @@ -2323,7 +2330,7 @@ record_increment (slsr_cand_t c, double_int increm } } - if (!found) + if (!found && incr_vec_len < MAX_INCR_VEC_LEN - 1) { /* The first time we see an increment, create the entry for it. If this is the root candidate which doesn't have a basis, set @@ -3025,7 +3032,7 @@ all_phi_incrs_profitable (slsr_cand_t c, gimple ph } else { - unsigned j; + int j; slsr_cand_t arg_cand = base_cand_from_table (arg); double_int increment = arg_cand->index - basis->index; @@ -3041,14 +3048,19 @@ all_phi_incrs_profitable (slsr_cand_t c, gimple ph print_gimple_stmt (dump_file, phi, 0, 0); fputs (" increment: ", dump_file); dump_double_int (dump_file, increment, false); - fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost); - if (profitable_increment_p (j)) - fputs (" Replacing...\n", dump_file); - else - fputs (" Not replaced.\n", dump_file); + if (j < 0) + fprintf (dump_file, + "\n Not replaced; incr_vec overflow.\n"); + else { + fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost); + if (profitable_increment_p (j)) + fputs (" Replacing...\n", dump_file); + else + fputs (" Not replaced.\n", dump_file); + } } - if (!profitable_increment_p (j)) + if (j < 0 || !profitable_increment_p (j)) return false; } } @@ -3268,13 +3280,14 @@ replace_profitable_candidates (slsr_cand_t c) { double_int increment = cand_abs_increment (c); enum tree_code orig_code = gimple_assign_rhs_code (c->cand_stmt); - unsigned i; + int i; i = incr_vec_index (increment); /* Only process profitable increments. Nothing useful can be done to a cast or copy. */ - if (profitable_increment_p (i) + if (i >= 0 + && profitable_increment_p (i) && orig_code != MODIFY_EXPR && orig_code != NOP_EXPR) { @@ -3378,6 +3391,8 @@ analyze_candidates_and_replace (void) length = count_candidates (c); if (!length) continue; + if (length > MAX_INCR_VEC_LEN) + length = MAX_INCR_VEC_LEN; /* Construct an array of increments for this candidate chain. */ incr_vec = XNEWVEC (incr_info, length);