Re: [PATCH] Fix PR81488

[Richard Biener]

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

[PATCH] Fix PR81488

[Bill Schmidt]

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?

Thanks,
Bill


2017-08-18  Bill Schmidt  

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 *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,