This is the mail archive of the
`gcc-patches@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Richard Biener <richard dot guenther at gmail dot com>*To*: Bill Schmidt <wschmidt at linux dot vnet dot ibm dot com>*Cc*: GCC Patches <gcc-patches at gcc dot gnu dot org>*Date*: Mon, 21 Aug 2017 09:44:03 +0200*Subject*: Re: [PATCH] Fix PR81488*Authentication-results*: sourceware.org; auth=none*References*: <4f565124-02ef-f1af-36d1-5c16f6cb502a@linux.vnet.ibm.com>

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 >

**References**:**[PATCH] Fix PR81488***From:*Bill Schmidt

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |