On Fri, Aug 18, 2017 at 8:36 PM, Bill Schmidt
<wschm...@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 <wschm...@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
>
