Re: [PATCH] Fix PR81488

[Richard Biener <richard dot guenther at gmail dot 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
>