Message ID | 4f565124-02ef-f1af-36d1-5c16f6cb502a@linux.vnet.ibm.com |
---|---|
State | New |
Headers | show |
On Fri, Aug 18, 2017 at 8:36 PM, Bill Schmidt <wschmidt@linux.vnet.ibm.com> wrote: > Hi, > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81488 reports a problem with SLSR where > too many memory resources are required to complete SLSR processing of conditional > candidates. The code in question contains large trees of PHI dependencies that must > be examined in order to find all candidates for replacement. Not only are the > dependency chains deep, but many PHIs contain duplicate source operands arriving by > different paths, and SLSR isn't currently smart enough to avoid tracing them more > than once. This leads to exponential behavior and a bad ending. > > Even removing the exponential behavior is not sufficient to fix the problem. The > dependencies are just too complex. So it is also necessary to put a limit on how > much time we want to spend examining PHI nodes before giving up. I've arbitrarily > chosen 16 as the maximum number of PHI nodes to visit for each candidate, which > seems likely to be sufficient in most cases. > > A side benefit of removing the exponential behavior is better accuracy in making > cost-model decisions. With tracing through the same PHI dependencies more than > once, the insertion (+) and replacement (-) costs are overcounted. This should > now be improved. > > The original bug went latent on the trunk after it was reported, but I was able > to reproduce with an older revision and verify that the following patch fixes > the problem. I've also bootstrapped and tested it on powerpc64le-linux-gnu with > no regressions. Is this ok for trunk? Ok. Thanks, Richard. > Thanks, > Bill > > > 2017-08-18 Bill Schmidt <wschmidt@linux.vnet.ibm.com> > > PR tree-optimization/81488 > * gimple-ssa-strength-reduction (struct slsr_cand_d): Add visited > and cached_basis fields. > (MAX_SPREAD): New constant. > (alloc_cand_and_find_basis): Initialize new fields. > (clear_visited): New function. > (create_phi_basis_1): Rename from create_phi_basis, set visited > and cached_basis fields. > (create_phi_basis): New wrapper function. > (phi_add_costs_1): Rename from phi_add_costs, add spread > parameter, set visited field, short-circuit when limits reached. > (phi_add_costs): New wrapper function. > (record_phi_increments_1): Rename from record_phi_increments, set > visited field. > (record_phi_increments): New wrapper function. > (phi_incr_cost_1): Rename from phi_incr_cost, set visited field. > (phi_incr_cost): New wrapper function. > (all_phi_incrs_profitable_1): Rename from > all_phi_incrs_profitable, set visited field. > (all_phi_incrs_profitable): New wrapper function. > > > Index: gcc/gimple-ssa-strength-reduction.c > =================================================================== > --- gcc/gimple-ssa-strength-reduction.c (revision 251159) > +++ gcc/gimple-ssa-strength-reduction.c (working copy) > @@ -281,6 +281,14 @@ struct slsr_cand_d > /* Savings that can be expected from eliminating dead code if this > candidate is replaced. */ > int dead_savings; > + > + /* For PHI candidates, use a visited flag to keep from processing the > + same PHI twice from multiple paths. */ > + int visited; > + > + /* We sometimes have to cache a phi basis with a phi candidate to > + avoid processing it twice. Valid only if visited==1. */ > + tree cached_basis; > }; > > typedef struct slsr_cand_d slsr_cand, *slsr_cand_t; > @@ -369,7 +377,11 @@ enum count_phis_status > DONT_COUNT_PHIS = 0, > COUNT_PHIS = 1 > }; > - > + > +/* Constrain how many PHI nodes we will visit for a conditional > + candidate (depth and breadth). */ > +const int MAX_SPREAD = 16; > + > /* Pointer map embodying a mapping from statements to candidates. */ > static hash_map<gimple *, slsr_cand_t> *stmt_cand_map; > > @@ -671,6 +683,8 @@ alloc_cand_and_find_basis (enum cand_kind kind, gi > c->sibling = 0; > c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0; > c->dead_savings = savings; > + c->visited = 0; > + c->cached_basis = NULL_TREE; > > cand_vec.safe_push (c); > > @@ -2317,19 +2331,33 @@ create_add_on_incoming_edge (slsr_cand_t c, tree b > return lhs; > } > > -/* Given a candidate C with BASIS_NAME being the LHS of C's basis which > - is hidden by the phi node FROM_PHI, create a new phi node in the same > - block as FROM_PHI. The new phi is suitable for use as a basis by C, > - with its phi arguments representing conditional adjustments to the > - hidden basis along conditional incoming paths. Those adjustments are > - made by creating add statements (and sometimes recursively creating > - phis) along those incoming paths. LOC is the location to attach to > - the introduced statements. KNOWN_STRIDE is true iff C's stride is a > - constant. */ > +/* Clear the visited field for a tree of PHI candidates. */ > > +static void > +clear_visited (gphi *phi) > +{ > + unsigned i; > + slsr_cand_t phi_cand = *stmt_cand_map->get (phi); > + > + if (phi_cand->visited) > + { > + phi_cand->visited = 0; > + > + for (i = 0; i < gimple_phi_num_args (phi); i++) > + { > + tree arg = gimple_phi_arg_def (phi, i); > + gimple *arg_def = SSA_NAME_DEF_STMT (arg); > + if (gimple_code (arg_def) == GIMPLE_PHI) > + clear_visited (as_a <gphi *> (arg_def)); > + } > + } > +} > + > +/* Recursive helper function for create_phi_basis. */ > + > static tree > -create_phi_basis (slsr_cand_t c, gimple *from_phi, tree basis_name, > - location_t loc, bool known_stride) > +create_phi_basis_1 (slsr_cand_t c, gimple *from_phi, tree basis_name, > + location_t loc, bool known_stride) > { > int i; > tree name, phi_arg; > @@ -2340,6 +2368,10 @@ static tree > slsr_cand_t phi_cand = *stmt_cand_map->get (from_phi); > auto_vec<tree> phi_args (nargs); > > + if (phi_cand->visited) > + return phi_cand->cached_basis; > + phi_cand->visited = 1; > + > /* Process each argument of the existing phi that represents > conditionally-executed add candidates. */ > for (i = 0; i < nargs; i++) > @@ -2367,8 +2399,8 @@ static tree > process it in the same fashion to ensure that all basis > adjustments are made along its incoming edges. */ > if (gimple_code (arg_def) == GIMPLE_PHI) > - feeding_def = create_phi_basis (c, arg_def, basis_name, > - loc, known_stride); > + feeding_def = create_phi_basis_1 (c, arg_def, basis_name, > + loc, known_stride); > else > { > slsr_cand_t arg_cand = base_cand_from_table (arg); > @@ -2403,9 +2435,31 @@ static tree > print_gimple_stmt (dump_file, phi, 0); > } > > + phi_cand->cached_basis = name; > return name; > } > > +/* Given a candidate C with BASIS_NAME being the LHS of C's basis which > + is hidden by the phi node FROM_PHI, create a new phi node in the same > + block as FROM_PHI. The new phi is suitable for use as a basis by C, > + with its phi arguments representing conditional adjustments to the > + hidden basis along conditional incoming paths. Those adjustments are > + made by creating add statements (and sometimes recursively creating > + phis) along those incoming paths. LOC is the location to attach to > + the introduced statements. KNOWN_STRIDE is true iff C's stride is a > + constant. */ > + > +static tree > +create_phi_basis (slsr_cand_t c, gimple *from_phi, tree basis_name, > + location_t loc, bool known_stride) > +{ > + tree retval = create_phi_basis_1 (c, from_phi, basis_name, loc, > + known_stride); > + gcc_assert (retval); > + clear_visited (as_a <gphi *> (from_phi)); > + return retval; > +} > + > /* Given a candidate C whose basis is hidden by at least one intervening > phi, introduce a matching number of new phis to represent its basis > adjusted by conditional increments along possible incoming paths. Then > @@ -2429,6 +2483,7 @@ replace_conditional_candidate (slsr_cand_t c) > loc = gimple_location (c->cand_stmt); > name = create_phi_basis (c, lookup_cand (c->def_phi)->cand_stmt, > basis_name, loc, KNOWN_STRIDE); > + > /* Replace C with an add of the new basis phi and a constant. */ > widest_int bump = c->index * wi::to_widest (c->stride); > > @@ -2435,19 +2490,22 @@ replace_conditional_candidate (slsr_cand_t c) > replace_mult_candidate (c, name, bump); > } > > -/* Compute the expected costs of inserting basis adjustments for > - candidate C with phi-definition PHI. The cost of inserting > - one adjustment is given by ONE_ADD_COST. If PHI has arguments > - which are themselves phi results, recursively calculate costs > - for those phis as well. */ > +/* Recursive helper function for phi_add_costs. SPREAD is a measure of > + how many PHI nodes we have visited at this point in the tree walk. */ > > static int > -phi_add_costs (gimple *phi, slsr_cand_t c, int one_add_cost) > +phi_add_costs_1 (gimple *phi, slsr_cand_t c, int one_add_cost, int *spread) > { > unsigned i; > int cost = 0; > slsr_cand_t phi_cand = *stmt_cand_map->get (phi); > > + if (phi_cand->visited) > + return 0; > + > + phi_cand->visited = 1; > + (*spread)++; > + > /* If we work our way back to a phi that isn't dominated by the hidden > basis, this isn't a candidate for replacement. Indicate this by > returning an unreasonably high cost. It's not easy to detect > @@ -2469,7 +2527,12 @@ static int > gimple *arg_def = SSA_NAME_DEF_STMT (arg); > > if (gimple_code (arg_def) == GIMPLE_PHI) > - cost += phi_add_costs (arg_def, c, one_add_cost); > + { > + cost += phi_add_costs_1 (arg_def, c, one_add_cost, spread); > + > + if (cost >= COST_INFINITE || *spread > MAX_SPREAD) > + return COST_INFINITE; > + } > else > { > slsr_cand_t arg_cand = base_cand_from_table (arg); > @@ -2483,6 +2546,20 @@ static int > return cost; > } > > +/* Compute the expected costs of inserting basis adjustments for > + candidate C with phi-definition PHI. The cost of inserting > + one adjustment is given by ONE_ADD_COST. If PHI has arguments > + which are themselves phi results, recursively calculate costs > + for those phis as well. */ > + > +static int > +phi_add_costs (gimple *phi, slsr_cand_t c, int one_add_cost) > +{ > + int spread = 0; > + int retval = phi_add_costs_1 (phi, c, one_add_cost, &spread); > + clear_visited (as_a <gphi *> (phi)); > + return retval; > +} > /* For candidate C, each sibling of candidate C, and each dependent of > candidate C, determine whether the candidate is dependent upon a > phi that hides its basis. If not, replace the candidate unconditionally. > @@ -2648,18 +2725,18 @@ record_increment (slsr_cand_t c, widest_int increm > } > } > > -/* Given phi statement PHI that hides a candidate from its BASIS, find > - the increments along each incoming arc (recursively handling additional > - phis that may be present) and record them. These increments are the > - difference in index between the index-adjusting statements and the > - index of the basis. */ > +/* Recursive helper function for record_phi_increments. */ > > static void > -record_phi_increments (slsr_cand_t basis, gimple *phi) > +record_phi_increments_1 (slsr_cand_t basis, gimple *phi) > { > unsigned i; > slsr_cand_t phi_cand = *stmt_cand_map->get (phi); > > + if (phi_cand->visited) > + return; > + phi_cand->visited = 1; > + > for (i = 0; i < gimple_phi_num_args (phi); i++) > { > tree arg = gimple_phi_arg_def (phi, i); > @@ -2669,7 +2746,7 @@ static void > gimple *arg_def = SSA_NAME_DEF_STMT (arg); > > if (gimple_code (arg_def) == GIMPLE_PHI) > - record_phi_increments (basis, arg_def); > + record_phi_increments_1 (basis, arg_def); > else > { > slsr_cand_t arg_cand = base_cand_from_table (arg); > @@ -2680,6 +2757,19 @@ static void > } > } > > +/* Given phi statement PHI that hides a candidate from its BASIS, find > + the increments along each incoming arc (recursively handling additional > + phis that may be present) and record them. These increments are the > + difference in index between the index-adjusting statements and the > + index of the basis. */ > + > +static void > +record_phi_increments (slsr_cand_t basis, gimple *phi) > +{ > + record_phi_increments_1 (basis, phi); > + clear_visited (as_a <gphi *> (phi)); > +} > + > /* Determine how many times each unique increment occurs in the set > of candidates rooted at C's parent, recording the data in the > increment vector. For each unique increment I, if an initializer > @@ -2717,15 +2807,11 @@ record_increments (slsr_cand_t c) > record_increments (lookup_cand (c->dependent)); > } > > -/* Add up and return the costs of introducing add statements that > - require the increment INCR on behalf of candidate C and phi > - statement PHI. Accumulate into *SAVINGS the potential savings > - from removing existing statements that feed PHI and have no other > - uses. */ > +/* Recursive helper function for phi_incr_cost. */ > > static int > -phi_incr_cost (slsr_cand_t c, const widest_int &incr, gimple *phi, > - int *savings) > +phi_incr_cost_1 (slsr_cand_t c, const widest_int &incr, gimple *phi, > + int *savings) > { > unsigned i; > int cost = 0; > @@ -2732,6 +2818,10 @@ static int > slsr_cand_t basis = lookup_cand (c->basis); > slsr_cand_t phi_cand = *stmt_cand_map->get (phi); > > + if (phi_cand->visited) > + return 0; > + phi_cand->visited = 1; > + > for (i = 0; i < gimple_phi_num_args (phi); i++) > { > tree arg = gimple_phi_arg_def (phi, i); > @@ -2744,7 +2834,7 @@ static int > { > int feeding_savings = 0; > tree feeding_var = gimple_phi_result (arg_def); > - cost += phi_incr_cost (c, incr, arg_def, &feeding_savings); > + cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings); > if (uses_consumed_by_stmt (feeding_var, phi)) > *savings += feeding_savings; > } > @@ -2768,6 +2858,21 @@ static int > return cost; > } > > +/* Add up and return the costs of introducing add statements that > + require the increment INCR on behalf of candidate C and phi > + statement PHI. Accumulate into *SAVINGS the potential savings > + from removing existing statements that feed PHI and have no other > + uses. */ > + > +static int > +phi_incr_cost (slsr_cand_t c, const widest_int &incr, gimple *phi, > + int *savings) > +{ > + int retval = phi_incr_cost_1 (c, incr, phi, savings); > + clear_visited (as_a <gphi *> (phi)); > + return retval; > +} > + > /* Return the first candidate in the tree rooted at C that has not > already been replaced, favoring siblings over dependents. */ > > @@ -3309,16 +3414,21 @@ insert_initializers (slsr_cand_t c) > } > } > > -/* Return TRUE iff all required increments for candidates feeding PHI > - are profitable (and legal!) to replace on behalf of candidate C. */ > +/* Recursive helper function for all_phi_incrs_profitable. */ > > static bool > -all_phi_incrs_profitable (slsr_cand_t c, gphi *phi) > +all_phi_incrs_profitable_1 (slsr_cand_t c, gphi *phi, int *spread) > { > unsigned i; > slsr_cand_t basis = lookup_cand (c->basis); > slsr_cand_t phi_cand = *stmt_cand_map->get (phi); > > + if (phi_cand->visited) > + return true; > + > + phi_cand->visited = 1; > + (*spread)++; > + > /* If the basis doesn't dominate the PHI (including when the PHI is > in the same block as the basis), we won't be able to create a PHI > using the basis here. */ > @@ -3346,7 +3456,9 @@ static bool > > if (gimple_code (arg_def) == GIMPLE_PHI) > { > - if (!all_phi_incrs_profitable (c, as_a <gphi *> (arg_def))) > + if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def), > + spread) > + || *spread > MAX_SPREAD) > return false; > } > else > @@ -3388,6 +3500,18 @@ static bool > return true; > } > > +/* Return TRUE iff all required increments for candidates feeding PHI > + are profitable (and legal!) to replace on behalf of candidate C. */ > + > +static bool > +all_phi_incrs_profitable (slsr_cand_t c, gphi *phi) > +{ > + int spread = 0; > + bool retval = all_phi_incrs_profitable_1 (c, phi, &spread); > + clear_visited (phi); > + return retval; > +} > + > /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of > type TO_TYPE, and insert it in front of the statement represented > by candidate C. Use *NEW_VAR to create the new SSA name. Return >
Index: gcc/gimple-ssa-strength-reduction.c =================================================================== --- gcc/gimple-ssa-strength-reduction.c (revision 251159) +++ gcc/gimple-ssa-strength-reduction.c (working copy) @@ -281,6 +281,14 @@ struct slsr_cand_d /* Savings that can be expected from eliminating dead code if this candidate is replaced. */ int dead_savings; + + /* For PHI candidates, use a visited flag to keep from processing the + same PHI twice from multiple paths. */ + int visited; + + /* We sometimes have to cache a phi basis with a phi candidate to + avoid processing it twice. Valid only if visited==1. */ + tree cached_basis; }; typedef struct slsr_cand_d slsr_cand, *slsr_cand_t; @@ -369,7 +377,11 @@ enum count_phis_status DONT_COUNT_PHIS = 0, COUNT_PHIS = 1 }; - + +/* Constrain how many PHI nodes we will visit for a conditional + candidate (depth and breadth). */ +const int MAX_SPREAD = 16; + /* Pointer map embodying a mapping from statements to candidates. */ static hash_map<gimple *, slsr_cand_t> *stmt_cand_map; @@ -671,6 +683,8 @@ alloc_cand_and_find_basis (enum cand_kind kind, gi c->sibling = 0; c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0; c->dead_savings = savings; + c->visited = 0; + c->cached_basis = NULL_TREE; cand_vec.safe_push (c); @@ -2317,19 +2331,33 @@ create_add_on_incoming_edge (slsr_cand_t c, tree b return lhs; } -/* Given a candidate C with BASIS_NAME being the LHS of C's basis which - is hidden by the phi node FROM_PHI, create a new phi node in the same - block as FROM_PHI. The new phi is suitable for use as a basis by C, - with its phi arguments representing conditional adjustments to the - hidden basis along conditional incoming paths. Those adjustments are - made by creating add statements (and sometimes recursively creating - phis) along those incoming paths. LOC is the location to attach to - the introduced statements. KNOWN_STRIDE is true iff C's stride is a - constant. */ +/* Clear the visited field for a tree of PHI candidates. */ +static void +clear_visited (gphi *phi) +{ + unsigned i; + slsr_cand_t phi_cand = *stmt_cand_map->get (phi); + + if (phi_cand->visited) + { + phi_cand->visited = 0; + + for (i = 0; i < gimple_phi_num_args (phi); i++) + { + tree arg = gimple_phi_arg_def (phi, i); + gimple *arg_def = SSA_NAME_DEF_STMT (arg); + if (gimple_code (arg_def) == GIMPLE_PHI) + clear_visited (as_a <gphi *> (arg_def)); + } + } +} + +/* Recursive helper function for create_phi_basis. */ + static tree -create_phi_basis (slsr_cand_t c, gimple *from_phi, tree basis_name, - location_t loc, bool known_stride) +create_phi_basis_1 (slsr_cand_t c, gimple *from_phi, tree basis_name, + location_t loc, bool known_stride) { int i; tree name, phi_arg; @@ -2340,6 +2368,10 @@ static tree slsr_cand_t phi_cand = *stmt_cand_map->get (from_phi); auto_vec<tree> phi_args (nargs); + if (phi_cand->visited) + return phi_cand->cached_basis; + phi_cand->visited = 1; + /* Process each argument of the existing phi that represents conditionally-executed add candidates. */ for (i = 0; i < nargs; i++) @@ -2367,8 +2399,8 @@ static tree process it in the same fashion to ensure that all basis adjustments are made along its incoming edges. */ if (gimple_code (arg_def) == GIMPLE_PHI) - feeding_def = create_phi_basis (c, arg_def, basis_name, - loc, known_stride); + feeding_def = create_phi_basis_1 (c, arg_def, basis_name, + loc, known_stride); else { slsr_cand_t arg_cand = base_cand_from_table (arg); @@ -2403,9 +2435,31 @@ static tree print_gimple_stmt (dump_file, phi, 0); } + phi_cand->cached_basis = name; return name; } +/* Given a candidate C with BASIS_NAME being the LHS of C's basis which + is hidden by the phi node FROM_PHI, create a new phi node in the same + block as FROM_PHI. The new phi is suitable for use as a basis by C, + with its phi arguments representing conditional adjustments to the + hidden basis along conditional incoming paths. Those adjustments are + made by creating add statements (and sometimes recursively creating + phis) along those incoming paths. LOC is the location to attach to + the introduced statements. KNOWN_STRIDE is true iff C's stride is a + constant. */ + +static tree +create_phi_basis (slsr_cand_t c, gimple *from_phi, tree basis_name, + location_t loc, bool known_stride) +{ + tree retval = create_phi_basis_1 (c, from_phi, basis_name, loc, + known_stride); + gcc_assert (retval); + clear_visited (as_a <gphi *> (from_phi)); + return retval; +} + /* Given a candidate C whose basis is hidden by at least one intervening phi, introduce a matching number of new phis to represent its basis adjusted by conditional increments along possible incoming paths. Then @@ -2429,6 +2483,7 @@ replace_conditional_candidate (slsr_cand_t c) loc = gimple_location (c->cand_stmt); name = create_phi_basis (c, lookup_cand (c->def_phi)->cand_stmt, basis_name, loc, KNOWN_STRIDE); + /* Replace C with an add of the new basis phi and a constant. */ widest_int bump = c->index * wi::to_widest (c->stride); @@ -2435,19 +2490,22 @@ replace_conditional_candidate (slsr_cand_t c) replace_mult_candidate (c, name, bump); } -/* Compute the expected costs of inserting basis adjustments for - candidate C with phi-definition PHI. The cost of inserting - one adjustment is given by ONE_ADD_COST. If PHI has arguments - which are themselves phi results, recursively calculate costs - for those phis as well. */ +/* Recursive helper function for phi_add_costs. SPREAD is a measure of + how many PHI nodes we have visited at this point in the tree walk. */ static int -phi_add_costs (gimple *phi, slsr_cand_t c, int one_add_cost) +phi_add_costs_1 (gimple *phi, slsr_cand_t c, int one_add_cost, int *spread) { unsigned i; int cost = 0; slsr_cand_t phi_cand = *stmt_cand_map->get (phi); + if (phi_cand->visited) + return 0; + + phi_cand->visited = 1; + (*spread)++; + /* If we work our way back to a phi that isn't dominated by the hidden basis, this isn't a candidate for replacement. Indicate this by returning an unreasonably high cost. It's not easy to detect @@ -2469,7 +2527,12 @@ static int gimple *arg_def = SSA_NAME_DEF_STMT (arg); if (gimple_code (arg_def) == GIMPLE_PHI) - cost += phi_add_costs (arg_def, c, one_add_cost); + { + cost += phi_add_costs_1 (arg_def, c, one_add_cost, spread); + + if (cost >= COST_INFINITE || *spread > MAX_SPREAD) + return COST_INFINITE; + } else { slsr_cand_t arg_cand = base_cand_from_table (arg); @@ -2483,6 +2546,20 @@ static int return cost; } +/* Compute the expected costs of inserting basis adjustments for + candidate C with phi-definition PHI. The cost of inserting + one adjustment is given by ONE_ADD_COST. If PHI has arguments + which are themselves phi results, recursively calculate costs + for those phis as well. */ + +static int +phi_add_costs (gimple *phi, slsr_cand_t c, int one_add_cost) +{ + int spread = 0; + int retval = phi_add_costs_1 (phi, c, one_add_cost, &spread); + clear_visited (as_a <gphi *> (phi)); + return retval; +} /* For candidate C, each sibling of candidate C, and each dependent of candidate C, determine whether the candidate is dependent upon a phi that hides its basis. If not, replace the candidate unconditionally. @@ -2648,18 +2725,18 @@ record_increment (slsr_cand_t c, widest_int increm } } -/* Given phi statement PHI that hides a candidate from its BASIS, find - the increments along each incoming arc (recursively handling additional - phis that may be present) and record them. These increments are the - difference in index between the index-adjusting statements and the - index of the basis. */ +/* Recursive helper function for record_phi_increments. */ static void -record_phi_increments (slsr_cand_t basis, gimple *phi) +record_phi_increments_1 (slsr_cand_t basis, gimple *phi) { unsigned i; slsr_cand_t phi_cand = *stmt_cand_map->get (phi); + if (phi_cand->visited) + return; + phi_cand->visited = 1; + for (i = 0; i < gimple_phi_num_args (phi); i++) { tree arg = gimple_phi_arg_def (phi, i); @@ -2669,7 +2746,7 @@ static void gimple *arg_def = SSA_NAME_DEF_STMT (arg); if (gimple_code (arg_def) == GIMPLE_PHI) - record_phi_increments (basis, arg_def); + record_phi_increments_1 (basis, arg_def); else { slsr_cand_t arg_cand = base_cand_from_table (arg); @@ -2680,6 +2757,19 @@ static void } } +/* Given phi statement PHI that hides a candidate from its BASIS, find + the increments along each incoming arc (recursively handling additional + phis that may be present) and record them. These increments are the + difference in index between the index-adjusting statements and the + index of the basis. */ + +static void +record_phi_increments (slsr_cand_t basis, gimple *phi) +{ + record_phi_increments_1 (basis, phi); + clear_visited (as_a <gphi *> (phi)); +} + /* Determine how many times each unique increment occurs in the set of candidates rooted at C's parent, recording the data in the increment vector. For each unique increment I, if an initializer @@ -2717,15 +2807,11 @@ record_increments (slsr_cand_t c) record_increments (lookup_cand (c->dependent)); } -/* Add up and return the costs of introducing add statements that - require the increment INCR on behalf of candidate C and phi - statement PHI. Accumulate into *SAVINGS the potential savings - from removing existing statements that feed PHI and have no other - uses. */ +/* Recursive helper function for phi_incr_cost. */ static int -phi_incr_cost (slsr_cand_t c, const widest_int &incr, gimple *phi, - int *savings) +phi_incr_cost_1 (slsr_cand_t c, const widest_int &incr, gimple *phi, + int *savings) { unsigned i; int cost = 0; @@ -2732,6 +2818,10 @@ static int slsr_cand_t basis = lookup_cand (c->basis); slsr_cand_t phi_cand = *stmt_cand_map->get (phi); + if (phi_cand->visited) + return 0; + phi_cand->visited = 1; + for (i = 0; i < gimple_phi_num_args (phi); i++) { tree arg = gimple_phi_arg_def (phi, i); @@ -2744,7 +2834,7 @@ static int { int feeding_savings = 0; tree feeding_var = gimple_phi_result (arg_def); - cost += phi_incr_cost (c, incr, arg_def, &feeding_savings); + cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings); if (uses_consumed_by_stmt (feeding_var, phi)) *savings += feeding_savings; } @@ -2768,6 +2858,21 @@ static int return cost; } +/* Add up and return the costs of introducing add statements that + require the increment INCR on behalf of candidate C and phi + statement PHI. Accumulate into *SAVINGS the potential savings + from removing existing statements that feed PHI and have no other + uses. */ + +static int +phi_incr_cost (slsr_cand_t c, const widest_int &incr, gimple *phi, + int *savings) +{ + int retval = phi_incr_cost_1 (c, incr, phi, savings); + clear_visited (as_a <gphi *> (phi)); + return retval; +} + /* Return the first candidate in the tree rooted at C that has not already been replaced, favoring siblings over dependents. */ @@ -3309,16 +3414,21 @@ insert_initializers (slsr_cand_t c) } } -/* Return TRUE iff all required increments for candidates feeding PHI - are profitable (and legal!) to replace on behalf of candidate C. */ +/* Recursive helper function for all_phi_incrs_profitable. */ static bool -all_phi_incrs_profitable (slsr_cand_t c, gphi *phi) +all_phi_incrs_profitable_1 (slsr_cand_t c, gphi *phi, int *spread) { unsigned i; slsr_cand_t basis = lookup_cand (c->basis); slsr_cand_t phi_cand = *stmt_cand_map->get (phi); + if (phi_cand->visited) + return true; + + phi_cand->visited = 1; + (*spread)++; + /* If the basis doesn't dominate the PHI (including when the PHI is in the same block as the basis), we won't be able to create a PHI using the basis here. */ @@ -3346,7 +3456,9 @@ static bool if (gimple_code (arg_def) == GIMPLE_PHI) { - if (!all_phi_incrs_profitable (c, as_a <gphi *> (arg_def))) + if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def), + spread) + || *spread > MAX_SPREAD) return false; } else @@ -3388,6 +3500,18 @@ static bool return true; } +/* Return TRUE iff all required increments for candidates feeding PHI + are profitable (and legal!) to replace on behalf of candidate C. */ + +static bool +all_phi_incrs_profitable (slsr_cand_t c, gphi *phi) +{ + int spread = 0; + bool retval = all_phi_incrs_profitable_1 (c, phi, &spread); + clear_visited (phi); + return retval; +} + /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of type TO_TYPE, and insert it in front of the statement represented by candidate C. Use *NEW_VAR to create the new SSA name. Return