Fix PR87473 (SLSR ICE on hidden basis)

Hi,

This patch addresses SLSR bug PR87473.  The underlying problem here is that
create_add_on_incoming_edge contains code to handle a phi_arg that is equal
to the base expression of the PHI candidate, where the increment assigned to
the incoming arc should be zero minus the index expression of the hidden
basis; but several other places in SLSR processing need to handle the same
case, and fail to do so.  As a result, the code to replace the PHI basis
attempts to use an initializing statement that was never created in the first
place, and we ICE.  This patch adds the necessary logic in four parts of the
code to ensure we handle this consistently throughout.

This error survived this long because the typical case when accessing the
hidden basis is for the index of the hidden basis to be zero.  For such a
case we don't need an initializing statement, and the ICE doesn't trigger.
The test case provided with the PR is a counter-example where the hidden
basis has an index of 2.

For the four functions fixed here, each identified the case of interest,
but just didn't do anything when that case arose.  I've reorganized the
code in each case to always execute the relevant logic, but change what's
done for the specific situation of the "pass-through" PHI argument.  This
makes the diffs a little hard to read, unfortunately.

During the investigation I noticed that we are dealing with a degenerate PHI,
introduced by the loopinit pass, that we would be better off optimizing away
sooner:

 <bb 5> [local count: 14598063]:
  # qz_1 = PHI <qz_3(4)>
  # jl_22 = PHI <jl_6(4)>
  _8 = (unsigned int) jl_22;
  _13 = _8 * _15;
  qz_11 = (int) _13;

The assignment to _8 should just use jl_6 in place of jl_22.  This would
greatly simplify SLSR's job, since PHI-free code is handled much more
straightforwardly than code that involves conditional updates.  We go through
at least 30 passes without having this cleaned up, and I expect other passes
than SLSR would perhaps be hamstrung by this as well.  Any recommendations?

Bootstrapped and tested on powerpc64le-linux-gnu with no regressions.  I've
added the test case from the bugzilla to the torture tests.  Is this okay for
trunk, and after a suitable period, to GCC 7 and 8 also?

Thanks!
Bill


[gcc]

2018-10-12  Bill Schmidt  <wschmidt@linux.ibm.com>

	PR tree-optimization/87473
	* gimple-ssa-strength-reduction.c (record_phi_increments_1): For
	phi arguments identical to the base expression of the phi
	candidate, record a phi-adjust increment of zero minus the index
	expression of the hidden basis.
	(phi_incr_cost_1): For phi arguments identical to the base
	expression of the phi candidate, the difference to compare against
	the increment is zero minus the index expression of the hidden
	basis, and there is no potential savings from replacing the (phi)
	statement.
	(ncd_with_phi): For phi arguments identical to the base expression
	of the phi candidate, the difference to compare against the
	increment is zero minus the index expression of the hidden basis.
	(all_phi_incrs_profitable_1): For phi arguments identical to the
	base expression of the phi candidate, the increment to be checked
	for profitability is zero minus the index expression of the hidden
	basis.

[gcc/testsuite]

2018-10-12  Bill Schmidt  <wschmidt@linux.ibm.com>

	PR tree-optimization/87473
	* gcc.c-torture/compile/pr87473.c: New file.

On Fri, Oct 12, 2018 at 10:01 PM Bill Schmidt <wschmidt@linux.ibm.com> wrote:
>
> Hi,
>
> This patch addresses SLSR bug PR87473.  The underlying problem here is that
> create_add_on_incoming_edge contains code to handle a phi_arg that is equal
> to the base expression of the PHI candidate, where the increment assigned to
> the incoming arc should be zero minus the index expression of the hidden
> basis; but several other places in SLSR processing need to handle the same
> case, and fail to do so.  As a result, the code to replace the PHI basis
> attempts to use an initializing statement that was never created in the first
> place, and we ICE.  This patch adds the necessary logic in four parts of the
> code to ensure we handle this consistently throughout.
>
> This error survived this long because the typical case when accessing the
> hidden basis is for the index of the hidden basis to be zero.  For such a
> case we don't need an initializing statement, and the ICE doesn't trigger.
> The test case provided with the PR is a counter-example where the hidden
> basis has an index of 2.
>
> For the four functions fixed here, each identified the case of interest,
> but just didn't do anything when that case arose.  I've reorganized the
> code in each case to always execute the relevant logic, but change what's
> done for the specific situation of the "pass-through" PHI argument.  This
> makes the diffs a little hard to read, unfortunately.
>
> During the investigation I noticed that we are dealing with a degenerate PHI,
> introduced by the loopinit pass, that we would be better off optimizing away
> sooner:
>
>  <bb 5> [local count: 14598063]:
>   # qz_1 = PHI <qz_3(4)>
>   # jl_22 = PHI <jl_6(4)>
>   _8 = (unsigned int) jl_22;
>   _13 = _8 * _15;
>   qz_11 = (int) _13;
>
> The assignment to _8 should just use jl_6 in place of jl_22.  This would
> greatly simplify SLSR's job, since PHI-free code is handled much more
> straightforwardly than code that involves conditional updates.  We go through
> at least 30 passes without having this cleaned up, and I expect other passes
> than SLSR would perhaps be hamstrung by this as well.  Any recommendations?

Without more context these are likely loop-closed PHIs.  It's probaby DOM
after loop that gets rid of them currently but a cheaper way would be to
propagate them out in pass_tree_loop_done.  Note that IIRC there are some
other passes rewriting things into loop-closed SSA form that might expose
such degenerate PHIs as well (a quick look shows invariant motion, both
VRP and EVRP should eventually propagate them out during their propagation
step and EVRP shouldn't even need loop-closed SSA?).

So some

  FOR_EACH_LOOP ()
     exits = get_loop_exit_edges ();
     for-each-edge (exits)
       if (single_pred_p (exit->dest))
         for-each-phi (exit->dest)
            propagate ()

in tree-loop-done should do the trick.

> Bootstrapped and tested on powerpc64le-linux-gnu with no regressions.  I've
> added the test case from the bugzilla to the torture tests.  Is this okay for
> trunk, and after a suitable period, to GCC 7 and 8 also?

OK for trunk and branches after a while.

Richard.

> Thanks!
> Bill
>
>
> [gcc]
>
> 2018-10-12  Bill Schmidt  <wschmidt@linux.ibm.com>
>
>         PR tree-optimization/87473
>         * gimple-ssa-strength-reduction.c (record_phi_increments_1): For
>         phi arguments identical to the base expression of the phi
>         candidate, record a phi-adjust increment of zero minus the index
>         expression of the hidden basis.
>         (phi_incr_cost_1): For phi arguments identical to the base
>         expression of the phi candidate, the difference to compare against
>         the increment is zero minus the index expression of the hidden
>         basis, and there is no potential savings from replacing the (phi)
>         statement.
>         (ncd_with_phi): For phi arguments identical to the base expression
>         of the phi candidate, the difference to compare against the
>         increment is zero minus the index expression of the hidden basis.
>         (all_phi_incrs_profitable_1): For phi arguments identical to the
>         base expression of the phi candidate, the increment to be checked
>         for profitability is zero minus the index expression of the hidden
>         basis.
>
> [gcc/testsuite]
>
> 2018-10-12  Bill Schmidt  <wschmidt@linux.ibm.com>
>
>         PR tree-optimization/87473
>         * gcc.c-torture/compile/pr87473.c: New file.
>
>
> Index: gcc/gimple-ssa-strength-reduction.c
> ===================================================================
> --- gcc/gimple-ssa-strength-reduction.c (revision 265112)
> +++ gcc/gimple-ssa-strength-reduction.c (working copy)
> @@ -2779,17 +2779,23 @@ record_phi_increments_1 (slsr_cand_t basis, gimple
>    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 (!operand_equal_p (arg, phi_cand->base_expr, 0))
> +      if (gimple_code (arg_def) == GIMPLE_PHI)
> +       record_phi_increments_1 (basis, arg_def);
> +      else
>         {
> -         gimple *arg_def = SSA_NAME_DEF_STMT (arg);
> +         widest_int diff;
>
> -         if (gimple_code (arg_def) == GIMPLE_PHI)
> -           record_phi_increments_1 (basis, arg_def);
> +         if (operand_equal_p (arg, phi_cand->base_expr, 0))
> +           {
> +             diff = -basis->index;
> +             record_increment (phi_cand, diff, PHI_ADJUST);
> +           }
>           else
>             {
>               slsr_cand_t arg_cand = base_cand_from_table (arg);
> -             widest_int diff = arg_cand->index - basis->index;
> +             diff = arg_cand->index - basis->index;
>               record_increment (arg_cand, diff, PHI_ADJUST);
>             }
>         }
> @@ -2864,29 +2870,43 @@ phi_incr_cost_1 (slsr_cand_t c, const widest_int &
>    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 (!operand_equal_p (arg, phi_cand->base_expr, 0))
> +      if (gimple_code (arg_def) == GIMPLE_PHI)
>         {
> -         gimple *arg_def = SSA_NAME_DEF_STMT (arg);
> -
> -         if (gimple_code (arg_def) == GIMPLE_PHI)
> +         int feeding_savings = 0;
> +         tree feeding_var = gimple_phi_result (arg_def);
> +         cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings);
> +         if (uses_consumed_by_stmt (feeding_var, phi))
> +           *savings += feeding_savings;
> +       }
> +      else
> +       {
> +         widest_int diff;
> +         slsr_cand_t arg_cand;
> +
> +         /* When the PHI argument is just a pass-through to the base
> +            expression of the hidden basis, the difference is zero minus
> +            the index of the basis.  There is no potential savings by
> +            eliminating a statement in this case.  */
> +         if (operand_equal_p (arg, phi_cand->base_expr, 0))
>             {
> -             int feeding_savings = 0;
> -             tree feeding_var = gimple_phi_result (arg_def);
> -             cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings);
> -             if (uses_consumed_by_stmt (feeding_var, phi))
> -               *savings += feeding_savings;
> +             arg_cand = (slsr_cand_t)NULL;
> +             diff = -basis->index;
>             }
>           else
>             {
> -             slsr_cand_t arg_cand = base_cand_from_table (arg);
> -             widest_int diff = arg_cand->index - basis->index;
> -
> -             if (incr == diff)
> +             arg_cand = base_cand_from_table (arg);
> +             diff = arg_cand->index - basis->index;
> +           }
> +
> +         if (incr == diff)
> +           {
> +             tree basis_lhs = gimple_assign_lhs (basis->cand_stmt);
> +             cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs)));
> +             if (arg_cand)
>                 {
> -                 tree basis_lhs = gimple_assign_lhs (basis->cand_stmt);
>                   tree lhs = gimple_assign_lhs (arg_cand->cand_stmt);
> -                 cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs)));
>                   if (uses_consumed_by_stmt (lhs, phi))
>                     *savings += stmt_cost (arg_cand->cand_stmt, true);
>                 }
> @@ -3228,23 +3248,26 @@ ncd_with_phi (slsr_cand_t c, const widest_int &inc
>    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 (!operand_equal_p (arg, phi_cand->base_expr, 0))
> +      if (gimple_code (arg_def) == GIMPLE_PHI)
> +       ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd, where);
> +      else
>         {
> -         gimple *arg_def = SSA_NAME_DEF_STMT (arg);
> +         widest_int diff;
>
> -         if (gimple_code (arg_def) == GIMPLE_PHI)
> -           ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd,
> -                               where);
> -         else
> +         if (operand_equal_p (arg, phi_cand->base_expr, 0))
> +           diff = -basis->index;
> +         else
>             {
>               slsr_cand_t arg_cand = base_cand_from_table (arg);
> -             widest_int diff = arg_cand->index - basis->index;
> -             basic_block pred = gimple_phi_arg_edge (phi, i)->src;
> -
> -             if ((incr == diff) || (!address_arithmetic_p && incr == -diff))
> -               ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where);
> +             diff = arg_cand->index - basis->index;
>             }
> +
> +         basic_block pred = gimple_phi_arg_edge (phi, i)->src;
> +
> +         if ((incr == diff) || (!address_arithmetic_p && incr == -diff))
> +           ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where);
>         }
>      }
>
> @@ -3515,51 +3538,53 @@ all_phi_incrs_profitable_1 (slsr_cand_t c, gphi *p
>         return false;
>
>        tree arg = gimple_phi_arg_def (phi, i);
> +      gimple *arg_def = SSA_NAME_DEF_STMT (arg);
>
> -      if (!operand_equal_p (arg, phi_cand->base_expr, 0))
> +      if (gimple_code (arg_def) == GIMPLE_PHI)
>         {
> -         gimple *arg_def = SSA_NAME_DEF_STMT (arg);
> +         if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def), spread)
> +             || *spread > MAX_SPREAD)
> +           return false;
> +       }
> +      else
> +       {
> +         int j;
> +         widest_int increment;
>
> -         if (gimple_code (arg_def) == GIMPLE_PHI)
> -           {
> -             if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def),
> -                                              spread)
> -                 || *spread > MAX_SPREAD)
> -               return false;
> -           }
> +         if (operand_equal_p (arg, phi_cand->base_expr, 0))
> +           increment = -basis->index;
>           else
>             {
> -             int j;
>               slsr_cand_t arg_cand = base_cand_from_table (arg);
> -             widest_int increment = arg_cand->index - basis->index;
> +             increment = arg_cand->index - basis->index;
> +           }
>
> -             if (!address_arithmetic_p && wi::neg_p (increment))
> -               increment = -increment;
> +         if (!address_arithmetic_p && wi::neg_p (increment))
> +           increment = -increment;
>
> -             j = incr_vec_index (increment);
> +         j = incr_vec_index (increment);
>
> -             if (dump_file && (dump_flags & TDF_DETAILS))
> -               {
> -                 fprintf (dump_file, "  Conditional candidate %d, phi: ",
> -                          c->cand_num);
> -                 print_gimple_stmt (dump_file, phi, 0);
> -                 fputs ("    increment: ", dump_file);
> -                 print_decs (increment, dump_file);
> -                 if (j < 0)
> -                   fprintf (dump_file,
> -                            "\n  Not replaced; incr_vec overflow.\n");
> -                 else {
> -                   fprintf (dump_file, "\n    cost: %d\n", incr_vec[j].cost);
> -                   if (profitable_increment_p (j))
> -                     fputs ("  Replacing...\n", dump_file);
> -                   else
> -                     fputs ("  Not replaced.\n", dump_file);
> -                 }
> -               }
> +         if (dump_file && (dump_flags & TDF_DETAILS))
> +           {
> +             fprintf (dump_file, "  Conditional candidate %d, phi: ",
> +                      c->cand_num);
> +             print_gimple_stmt (dump_file, phi, 0);
> +             fputs ("    increment: ", dump_file);
> +             print_decs (increment, dump_file);
> +             if (j < 0)
> +               fprintf (dump_file,
> +                        "\n  Not replaced; incr_vec overflow.\n");
> +             else {
> +               fprintf (dump_file, "\n    cost: %d\n", incr_vec[j].cost);
> +               if (profitable_increment_p (j))
> +                 fputs ("  Replacing...\n", dump_file);
> +               else
> +                 fputs ("  Not replaced.\n", dump_file);
> +             }
> +           }
>
> -             if (j < 0 || !profitable_increment_p (j))
> -               return false;
> -           }
> +         if (j < 0 || !profitable_increment_p (j))
> +           return false;
>         }
>      }
>
> Index: gcc/testsuite/gcc.c-torture/compile/pr87473.c
> ===================================================================
> --- gcc/testsuite/gcc.c-torture/compile/pr87473.c       (nonexistent)
> +++ gcc/testsuite/gcc.c-torture/compile/pr87473.c       (working copy)
> @@ -0,0 +1,19 @@
> +/* PR87473: SLSR ICE on hidden basis with |increment| > 1.  */
> +/* { dg-additional-options "-fno-tree-ch" } */
> +
> +void
> +t6 (int qz, int wh)
> +{
> +  int jl = wh;
> +
> +  while (1.0 / 0 < 1)
> +    {
> +      qz = wh * (wh + 2);
> +
> +      while (wh < 1)
> +        jl = 0;
> +    }
> +
> +  while (qz < 1)
> +    qz = jl * wh;
> +}
>

On 10/15/18 3:02 AM, Richard Biener wrote:
> On Fri, Oct 12, 2018 at 10:01 PM Bill Schmidt <wschmidt@linux.ibm.com> wrote:
>>
>> Hi,
>>
>> This patch addresses SLSR bug PR87473.  The underlying problem here is that
>> create_add_on_incoming_edge contains code to handle a phi_arg that is equal
>> to the base expression of the PHI candidate, where the increment assigned to
>> the incoming arc should be zero minus the index expression of the hidden
>> basis; but several other places in SLSR processing need to handle the same
>> case, and fail to do so.  As a result, the code to replace the PHI basis
>> attempts to use an initializing statement that was never created in the first
>> place, and we ICE.  This patch adds the necessary logic in four parts of the
>> code to ensure we handle this consistently throughout.
>>
>> This error survived this long because the typical case when accessing the
>> hidden basis is for the index of the hidden basis to be zero.  For such a
>> case we don't need an initializing statement, and the ICE doesn't trigger.
>> The test case provided with the PR is a counter-example where the hidden
>> basis has an index of 2.
>>
>> For the four functions fixed here, each identified the case of interest,
>> but just didn't do anything when that case arose.  I've reorganized the
>> code in each case to always execute the relevant logic, but change what's
>> done for the specific situation of the "pass-through" PHI argument.  This
>> makes the diffs a little hard to read, unfortunately.
>>
>> During the investigation I noticed that we are dealing with a degenerate PHI,
>> introduced by the loopinit pass, that we would be better off optimizing away
>> sooner:
>>
>>  <bb 5> [local count: 14598063]:
>>   # qz_1 = PHI <qz_3(4)>
>>   # jl_22 = PHI <jl_6(4)>
>>   _8 = (unsigned int) jl_22;
>>   _13 = _8 * _15;
>>   qz_11 = (int) _13;
>>
>> The assignment to _8 should just use jl_6 in place of jl_22.  This would
>> greatly simplify SLSR's job, since PHI-free code is handled much more
>> straightforwardly than code that involves conditional updates.  We go through
>> at least 30 passes without having this cleaned up, and I expect other passes
>> than SLSR would perhaps be hamstrung by this as well.  Any recommendations?
> 
> Without more context these are likely loop-closed PHIs.  It's probaby DOM
> after loop that gets rid of them currently but a cheaper way would be to
> propagate them out in pass_tree_loop_done.  Note that IIRC there are some
> other passes rewriting things into loop-closed SSA form that might expose
> such degenerate PHIs as well (a quick look shows invariant motion, both
> VRP and EVRP should eventually propagate them out during their propagation
> step and EVRP shouldn't even need loop-closed SSA?).
There's phi_only_cprop which can deal with this stuff very fast.  It
creates a worklist of degenerate PHIs, propagates them away, adding
anything that becomes a degenerate (including normal statements) to the
worklist.  We typically run it after the dom/vrp or vrp/dom pass pairs
because threading tends to create lots of these degenerates.


The question I would answer is where does the PHI first appear and when
does it become a degenerate?

jeff