Fix PR85712 (SLSR cleanup of alternative interpretations)

Message ID 875f0508-ae57-1cb1-f7c3-41aa6561f75a@linux.ibm.com
State New
Headers show
Series
  • Fix PR85712 (SLSR cleanup of alternative interpretations)
Related show

Commit Message

Bill Schmidt May 22, 2018, 9:37 p.m.
Hi,

PR85712 shows where an existing test case fails in the SLSR pass because
the code is flawed that cleans up alternative interpretations (CAND_ADD 
versus CAND_MULT, for example) after a replacement.  This patch fixes the
flaw by ensuring that we always visit all interpretations, not just
subsequent ones in the next_interp chain.  I found six occurrences of
this mistake in the code.

Bootstrapped and tested on powerpc64le-linux-gnu with no regressions.
No new test case is added since the failure occurs on an existing test
in the test suite.  Is this okay for trunk, and for backports to all
supported branches after some burn-in time?

Thanks,
Bill


2018-05-22  Bill Schmidt  <wschmidt@linux.ibm.com>

	* gimple-ssa-strength-reduction.c (struct slsr_cand_d): Add
	first_interp field.
	(alloc_cand_and_find_basis): Initialize first_interp field.
	(slsr_process_mul): Modify first_interp field.
	(slsr_process_add): Likewise.
	(slsr_process_cast): Modify first_interp field for each new
	interpretation.
	(slsr_process_copy): Likewise.
	(dump_candidate): Dump first_interp field.
	(replace_mult_candidate): Process all interpretations, not just
	subsequent ones.
	(replace_rhs_if_not_dup): Likewise.
	(replace_one_candidate): Likewise.

Comments

Richard Biener May 23, 2018, 9:32 a.m. | #1
On Tue, May 22, 2018 at 11:37 PM Bill Schmidt <wschmidt@linux.ibm.com>
wrote:

> Hi,


> PR85712 shows where an existing test case fails in the SLSR pass because

> the code is flawed that cleans up alternative interpretations (CAND_ADD

> versus CAND_MULT, for example) after a replacement.  This patch fixes the

> flaw by ensuring that we always visit all interpretations, not just

> subsequent ones in the next_interp chain.  I found six occurrences of

> this mistake in the code.


> Bootstrapped and tested on powerpc64le-linux-gnu with no regressions.

> No new test case is added since the failure occurs on an existing test

> in the test suite.  Is this okay for trunk, and for backports to all

> supported branches after some burn-in time?


OK and Yes for the backports.

Thanks,
Richard.

> Thanks,

> Bill



> 2018-05-22  Bill Schmidt  <wschmidt@linux.ibm.com>


>          * gimple-ssa-strength-reduction.c (struct slsr_cand_d): Add

>          first_interp field.

>          (alloc_cand_and_find_basis): Initialize first_interp field.

>          (slsr_process_mul): Modify first_interp field.

>          (slsr_process_add): Likewise.

>          (slsr_process_cast): Modify first_interp field for each new

>          interpretation.

>          (slsr_process_copy): Likewise.

>          (dump_candidate): Dump first_interp field.

>          (replace_mult_candidate): Process all interpretations, not just

>          subsequent ones.

>          (replace_rhs_if_not_dup): Likewise.

>          (replace_one_candidate): Likewise.


> Index: gcc/gimple-ssa-strength-reduction.c

> ===================================================================

> --- gcc/gimple-ssa-strength-reduction.c (revision 260484)

> +++ gcc/gimple-ssa-strength-reduction.c (working copy)

> @@ -266,6 +266,10 @@ struct slsr_cand_d

>        of a statement.  */

>     cand_idx next_interp;


> +  /* Index of the first candidate record in a chain for the same

> +     statement.  */

> +  cand_idx first_interp;

> +

>     /* Index of the basis statement S0, if any, in the candidate vector.

  */
>     cand_idx basis;


> @@ -686,6 +690,7 @@ alloc_cand_and_find_basis (enum cand_kind kind, gi

>     c->kind = kind;

>     c->cand_num = cand_vec.length () + 1;

>     c->next_interp = 0;

> +  c->first_interp = c->cand_num;

>     c->dependent = 0;

>     c->sibling = 0;

>     c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0;

> @@ -1261,6 +1266,7 @@ slsr_process_mul (gimple *gs, tree rhs1, tree rhs2

>           is the stride and RHS2 is the base expression.  */

>         c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed);

>         c->next_interp = c2->cand_num;

> +      c2->first_interp = c->cand_num;

>       }

>     else if (TREE_CODE (rhs2) == INTEGER_CST)

>       {

> @@ -1498,7 +1504,10 @@ slsr_process_add (gimple *gs, tree rhs1, tree rhs2

>          {

>            c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed);

>            if (c)

> -           c->next_interp = c2->cand_num;

> +           {

> +             c->next_interp = c2->cand_num;

> +             c2->first_interp = c->cand_num;

> +           }

>            else

>              add_cand_for_stmt (gs, c2);

>          }

> @@ -1621,6 +1630,8 @@ slsr_process_cast (gimple *gs, tree rhs1, bool spe


>     if (base_cand && base_cand->kind != CAND_PHI)

>       {

> +      slsr_cand_t first_cand = NULL;

> +

>         while (base_cand)

>          {

>            /* Propagate all data from the base candidate except the type,

> @@ -1635,6 +1646,12 @@ slsr_process_cast (gimple *gs, tree rhs1, bool spe

>                                           base_cand->index,

base_cand->stride,
>                                           ctype, base_cand->stride_type,

>                                           savings);

> +         if (!first_cand)

> +           first_cand = c;

> +

> +         if (first_cand != c)

> +           c->first_interp = first_cand->cand_num;

> +

>            if (base_cand->next_interp)

>              base_cand = lookup_cand (base_cand->next_interp);

>            else

> @@ -1657,6 +1674,7 @@ slsr_process_cast (gimple *gs, tree rhs1, bool spe

>         c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0,

>                                        integer_one_node, ctype, sizetype,

0);
>         c->next_interp = c2->cand_num;

> +      c2->first_interp = c->cand_num;

>       }


>     /* Add the first (or only) interpretation to the statement-candidate

> @@ -1681,6 +1699,8 @@ slsr_process_copy (gimple *gs, tree rhs1, bool spe


>     if (base_cand && base_cand->kind != CAND_PHI)

>       {

> +      slsr_cand_t first_cand = NULL;

> +

>         while (base_cand)

>          {

>            /* Propagate all data from the base candidate.  */

> @@ -1693,6 +1713,12 @@ slsr_process_copy (gimple *gs, tree rhs1, bool spe

>                                           base_cand->index,

base_cand->stride,
>                                           base_cand->cand_type,

>                                           base_cand->stride_type, savings);

> +         if (!first_cand)

> +           first_cand = c;

> +

> +         if (first_cand != c)

> +           c->first_interp = first_cand->cand_num;

> +

>            if (base_cand->next_interp)

>              base_cand = lookup_cand (base_cand->next_interp);

>            else

> @@ -1717,6 +1743,7 @@ slsr_process_copy (gimple *gs, tree rhs1, bool spe

>                                        integer_one_node, TREE_TYPE (rhs1),

>                                        sizetype, 0);

>         c->next_interp = c2->cand_num;

> +      c2->first_interp = c->cand_num;

>       }


>     /* Add the first (or only) interpretation to the statement-candidate

> @@ -1887,8 +1914,9 @@ dump_candidate (slsr_cand_t c)

>     print_generic_expr (dump_file, c->cand_type);

>     fprintf (dump_file, "\n     basis: %d  dependent: %d  sibling: %d\n",

>             c->basis, c->dependent, c->sibling);

> -  fprintf (dump_file, "     next-interp: %d  dead-savings: %d\n",

> -          c->next_interp, c->dead_savings);

> +  fprintf (dump_file,

> +          "     next-interp: %d  first-interp: %d  dead-savings: %d\n",

> +          c->next_interp, c->first_interp, c->dead_savings);

>     if (c->def_phi)

>       fprintf (dump_file, "     phi:  %d\n", c->def_phi);

>     fputs ("\n", dump_file);

> @@ -2147,14 +2175,13 @@ replace_mult_candidate (slsr_cand_t c, tree basis_

>         tree lhs = gimple_assign_lhs (c->cand_stmt);

>         gassign *copy_stmt = gimple_build_assign (lhs, basis_name);

>         gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

> -      slsr_cand_t cc = c;

> +      slsr_cand_t cc = lookup_cand (c->first_interp);

>         gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));

>         gsi_replace (&gsi, copy_stmt, false);

> -      c->cand_stmt = copy_stmt;

> -      while (cc->next_interp)

> +      while (cc)

>          {

> -         cc = lookup_cand (cc->next_interp);

>            cc->cand_stmt = copy_stmt;

> +         cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>          }

>         if (dump_file && (dump_flags & TDF_DETAILS))

>          stmt_to_print = copy_stmt;

> @@ -2181,14 +2208,13 @@ replace_mult_candidate (slsr_cand_t c, tree basis_

>         else

>          {

>            gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

> -         slsr_cand_t cc = c;

> +         slsr_cand_t cc = lookup_cand (c->first_interp);

>            gimple_assign_set_rhs_with_ops (&gsi, code, basis_name,

bump_tree);
>            update_stmt (gsi_stmt (gsi));

> -         c->cand_stmt = gsi_stmt (gsi);

> -         while (cc->next_interp)

> +         while (cc)

>              {

> -             cc = lookup_cand (cc->next_interp);

>                cc->cand_stmt = gsi_stmt (gsi);

> +             cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>              }

>            if (dump_file && (dump_flags & TDF_DETAILS))

>              stmt_to_print = gsi_stmt (gsi);

> @@ -3597,14 +3623,13 @@ replace_rhs_if_not_dup (enum tree_code new_code, t

>                || !operand_equal_p (new_rhs2, old_rhs1, 0))))

>       {

>         gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

> -      slsr_cand_t cc = c;

> +      slsr_cand_t cc = lookup_cand (c->first_interp);

>         gimple_assign_set_rhs_with_ops (&gsi, new_code, new_rhs1,

new_rhs2);
>         update_stmt (gsi_stmt (gsi));

> -      c->cand_stmt = gsi_stmt (gsi);

> -      while (cc->next_interp)

> +      while (cc)

>          {

> -         cc = lookup_cand (cc->next_interp);

>            cc->cand_stmt = gsi_stmt (gsi);

> +         cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>          }


>         if (dump_file && (dump_flags & TDF_DETAILS))

> @@ -3709,14 +3734,13 @@ replace_one_candidate (slsr_cand_t c, unsigned i,

>            || !operand_equal_p (rhs2, orig_rhs2, 0))

>          {

>            gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

> -         slsr_cand_t cc = c;

> +         slsr_cand_t cc = lookup_cand (c->first_interp);

>            gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, basis_name,

rhs2);
>            update_stmt (gsi_stmt (gsi));

> -          c->cand_stmt = gsi_stmt (gsi);

> -         while (cc->next_interp)

> +         while (cc)

>              {

> -             cc = lookup_cand (cc->next_interp);

>                cc->cand_stmt = gsi_stmt (gsi);

> +             cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>              }


>            if (dump_file && (dump_flags & TDF_DETAILS))

> @@ -3736,14 +3760,13 @@ replace_one_candidate (slsr_cand_t c, unsigned i,

>          {

>            gassign *copy_stmt = gimple_build_assign (lhs, basis_name);

>            gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

> -         slsr_cand_t cc = c;

> +         slsr_cand_t cc = lookup_cand (c->first_interp);

>            gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));

>            gsi_replace (&gsi, copy_stmt, false);

> -         c->cand_stmt = copy_stmt;

> -         while (cc->next_interp)

> +         while (cc)

>              {

> -             cc = lookup_cand (cc->next_interp);

>                cc->cand_stmt = copy_stmt;

> +             cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>              }


>            if (dump_file && (dump_flags & TDF_DETAILS))

> @@ -3753,14 +3776,13 @@ replace_one_candidate (slsr_cand_t c, unsigned i,

>          {

>            gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

>            gassign *cast_stmt = gimple_build_assign (lhs, NOP_EXPR,

basis_name);
> -         slsr_cand_t cc = c;

> +         slsr_cand_t cc = lookup_cand (c->first_interp);

>            gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));

>            gsi_replace (&gsi, cast_stmt, false);

> -         c->cand_stmt = cast_stmt;

> -         while (cc->next_interp)

> +         while (cc)

>              {

> -             cc = lookup_cand (cc->next_interp);

>                cc->cand_stmt = cast_stmt;

> +             cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>              }


>            if (dump_file && (dump_flags & TDF_DETAILS))
Bill Schmidt May 23, 2018, 1:27 p.m. | #2
On May 23, 2018, at 4:32 AM, Richard Biener <richard.guenther@gmail.com> wrote:
> 

> On Tue, May 22, 2018 at 11:37 PM Bill Schmidt <wschmidt@linux.ibm.com>

> wrote:

> 

>> Hi,

> 

>> PR85712 shows where an existing test case fails in the SLSR pass because

>> the code is flawed that cleans up alternative interpretations (CAND_ADD

>> versus CAND_MULT, for example) after a replacement.  This patch fixes the

>> flaw by ensuring that we always visit all interpretations, not just

>> subsequent ones in the next_interp chain.  I found six occurrences of

>> this mistake in the code.

> 

>> Bootstrapped and tested on powerpc64le-linux-gnu with no regressions.

>> No new test case is added since the failure occurs on an existing test

>> in the test suite.  Is this okay for trunk, and for backports to all

>> supported branches after some burn-in time?

> 

> OK and Yes for the backports.


Thanks, committed to trunk as r260608.  Will do backports next week.

Bill
> 

> Thanks,

> Richard.

> 

>> Thanks,

>> Bill

> 

> 

>> 2018-05-22  Bill Schmidt  <wschmidt@linux.ibm.com>

> 

>>         * gimple-ssa-strength-reduction.c (struct slsr_cand_d): Add

>>         first_interp field.

>>         (alloc_cand_and_find_basis): Initialize first_interp field.

>>         (slsr_process_mul): Modify first_interp field.

>>         (slsr_process_add): Likewise.

>>         (slsr_process_cast): Modify first_interp field for each new

>>         interpretation.

>>         (slsr_process_copy): Likewise.

>>         (dump_candidate): Dump first_interp field.

>>         (replace_mult_candidate): Process all interpretations, not just

>>         subsequent ones.

>>         (replace_rhs_if_not_dup): Likewise.

>>         (replace_one_candidate): Likewise.

> 

>> Index: gcc/gimple-ssa-strength-reduction.c

>> ===================================================================

>> --- gcc/gimple-ssa-strength-reduction.c (revision 260484)

>> +++ gcc/gimple-ssa-strength-reduction.c (working copy)

>> @@ -266,6 +266,10 @@ struct slsr_cand_d

>>       of a statement.  */

>>    cand_idx next_interp;

> 

>> +  /* Index of the first candidate record in a chain for the same

>> +     statement.  */

>> +  cand_idx first_interp;

>> +

>>    /* Index of the basis statement S0, if any, in the candidate vector.

>  */

>>    cand_idx basis;

> 

>> @@ -686,6 +690,7 @@ alloc_cand_and_find_basis (enum cand_kind kind, gi

>>    c->kind = kind;

>>    c->cand_num = cand_vec.length () + 1;

>>    c->next_interp = 0;

>> +  c->first_interp = c->cand_num;

>>    c->dependent = 0;

>>    c->sibling = 0;

>>    c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0;

>> @@ -1261,6 +1266,7 @@ slsr_process_mul (gimple *gs, tree rhs1, tree rhs2

>>          is the stride and RHS2 is the base expression.  */

>>        c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed);

>>        c->next_interp = c2->cand_num;

>> +      c2->first_interp = c->cand_num;

>>      }

>>    else if (TREE_CODE (rhs2) == INTEGER_CST)

>>      {

>> @@ -1498,7 +1504,10 @@ slsr_process_add (gimple *gs, tree rhs1, tree rhs2

>>         {

>>           c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed);

>>           if (c)

>> -           c->next_interp = c2->cand_num;

>> +           {

>> +             c->next_interp = c2->cand_num;

>> +             c2->first_interp = c->cand_num;

>> +           }

>>           else

>>             add_cand_for_stmt (gs, c2);

>>         }

>> @@ -1621,6 +1630,8 @@ slsr_process_cast (gimple *gs, tree rhs1, bool spe

> 

>>    if (base_cand && base_cand->kind != CAND_PHI)

>>      {

>> +      slsr_cand_t first_cand = NULL;

>> +

>>        while (base_cand)

>>         {

>>           /* Propagate all data from the base candidate except the type,

>> @@ -1635,6 +1646,12 @@ slsr_process_cast (gimple *gs, tree rhs1, bool spe

>>                                          base_cand->index,

> base_cand->stride,

>>                                          ctype, base_cand->stride_type,

>>                                          savings);

>> +         if (!first_cand)

>> +           first_cand = c;

>> +

>> +         if (first_cand != c)

>> +           c->first_interp = first_cand->cand_num;

>> +

>>           if (base_cand->next_interp)

>>             base_cand = lookup_cand (base_cand->next_interp);

>>           else

>> @@ -1657,6 +1674,7 @@ slsr_process_cast (gimple *gs, tree rhs1, bool spe

>>        c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0,

>>                                       integer_one_node, ctype, sizetype,

> 0);

>>        c->next_interp = c2->cand_num;

>> +      c2->first_interp = c->cand_num;

>>      }

> 

>>    /* Add the first (or only) interpretation to the statement-candidate

>> @@ -1681,6 +1699,8 @@ slsr_process_copy (gimple *gs, tree rhs1, bool spe

> 

>>    if (base_cand && base_cand->kind != CAND_PHI)

>>      {

>> +      slsr_cand_t first_cand = NULL;

>> +

>>        while (base_cand)

>>         {

>>           /* Propagate all data from the base candidate.  */

>> @@ -1693,6 +1713,12 @@ slsr_process_copy (gimple *gs, tree rhs1, bool spe

>>                                          base_cand->index,

> base_cand->stride,

>>                                          base_cand->cand_type,

>>                                          base_cand->stride_type, savings);

>> +         if (!first_cand)

>> +           first_cand = c;

>> +

>> +         if (first_cand != c)

>> +           c->first_interp = first_cand->cand_num;

>> +

>>           if (base_cand->next_interp)

>>             base_cand = lookup_cand (base_cand->next_interp);

>>           else

>> @@ -1717,6 +1743,7 @@ slsr_process_copy (gimple *gs, tree rhs1, bool spe

>>                                       integer_one_node, TREE_TYPE (rhs1),

>>                                       sizetype, 0);

>>        c->next_interp = c2->cand_num;

>> +      c2->first_interp = c->cand_num;

>>      }

> 

>>    /* Add the first (or only) interpretation to the statement-candidate

>> @@ -1887,8 +1914,9 @@ dump_candidate (slsr_cand_t c)

>>    print_generic_expr (dump_file, c->cand_type);

>>    fprintf (dump_file, "\n     basis: %d  dependent: %d  sibling: %d\n",

>>            c->basis, c->dependent, c->sibling);

>> -  fprintf (dump_file, "     next-interp: %d  dead-savings: %d\n",

>> -          c->next_interp, c->dead_savings);

>> +  fprintf (dump_file,

>> +          "     next-interp: %d  first-interp: %d  dead-savings: %d\n",

>> +          c->next_interp, c->first_interp, c->dead_savings);

>>    if (c->def_phi)

>>      fprintf (dump_file, "     phi:  %d\n", c->def_phi);

>>    fputs ("\n", dump_file);

>> @@ -2147,14 +2175,13 @@ replace_mult_candidate (slsr_cand_t c, tree basis_

>>        tree lhs = gimple_assign_lhs (c->cand_stmt);

>>        gassign *copy_stmt = gimple_build_assign (lhs, basis_name);

>>        gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

>> -      slsr_cand_t cc = c;

>> +      slsr_cand_t cc = lookup_cand (c->first_interp);

>>        gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));

>>        gsi_replace (&gsi, copy_stmt, false);

>> -      c->cand_stmt = copy_stmt;

>> -      while (cc->next_interp)

>> +      while (cc)

>>         {

>> -         cc = lookup_cand (cc->next_interp);

>>           cc->cand_stmt = copy_stmt;

>> +         cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>>         }

>>        if (dump_file && (dump_flags & TDF_DETAILS))

>>         stmt_to_print = copy_stmt;

>> @@ -2181,14 +2208,13 @@ replace_mult_candidate (slsr_cand_t c, tree basis_

>>        else

>>         {

>>           gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

>> -         slsr_cand_t cc = c;

>> +         slsr_cand_t cc = lookup_cand (c->first_interp);

>>           gimple_assign_set_rhs_with_ops (&gsi, code, basis_name,

> bump_tree);

>>           update_stmt (gsi_stmt (gsi));

>> -         c->cand_stmt = gsi_stmt (gsi);

>> -         while (cc->next_interp)

>> +         while (cc)

>>             {

>> -             cc = lookup_cand (cc->next_interp);

>>               cc->cand_stmt = gsi_stmt (gsi);

>> +             cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>>             }

>>           if (dump_file && (dump_flags & TDF_DETAILS))

>>             stmt_to_print = gsi_stmt (gsi);

>> @@ -3597,14 +3623,13 @@ replace_rhs_if_not_dup (enum tree_code new_code, t

>>               || !operand_equal_p (new_rhs2, old_rhs1, 0))))

>>      {

>>        gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

>> -      slsr_cand_t cc = c;

>> +      slsr_cand_t cc = lookup_cand (c->first_interp);

>>        gimple_assign_set_rhs_with_ops (&gsi, new_code, new_rhs1,

> new_rhs2);

>>        update_stmt (gsi_stmt (gsi));

>> -      c->cand_stmt = gsi_stmt (gsi);

>> -      while (cc->next_interp)

>> +      while (cc)

>>         {

>> -         cc = lookup_cand (cc->next_interp);

>>           cc->cand_stmt = gsi_stmt (gsi);

>> +         cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>>         }

> 

>>        if (dump_file && (dump_flags & TDF_DETAILS))

>> @@ -3709,14 +3734,13 @@ replace_one_candidate (slsr_cand_t c, unsigned i,

>>           || !operand_equal_p (rhs2, orig_rhs2, 0))

>>         {

>>           gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

>> -         slsr_cand_t cc = c;

>> +         slsr_cand_t cc = lookup_cand (c->first_interp);

>>           gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, basis_name,

> rhs2);

>>           update_stmt (gsi_stmt (gsi));

>> -          c->cand_stmt = gsi_stmt (gsi);

>> -         while (cc->next_interp)

>> +         while (cc)

>>             {

>> -             cc = lookup_cand (cc->next_interp);

>>               cc->cand_stmt = gsi_stmt (gsi);

>> +             cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>>             }

> 

>>           if (dump_file && (dump_flags & TDF_DETAILS))

>> @@ -3736,14 +3760,13 @@ replace_one_candidate (slsr_cand_t c, unsigned i,

>>         {

>>           gassign *copy_stmt = gimple_build_assign (lhs, basis_name);

>>           gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

>> -         slsr_cand_t cc = c;

>> +         slsr_cand_t cc = lookup_cand (c->first_interp);

>>           gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));

>>           gsi_replace (&gsi, copy_stmt, false);

>> -         c->cand_stmt = copy_stmt;

>> -         while (cc->next_interp)

>> +         while (cc)

>>             {

>> -             cc = lookup_cand (cc->next_interp);

>>               cc->cand_stmt = copy_stmt;

>> +             cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>>             }

> 

>>           if (dump_file && (dump_flags & TDF_DETAILS))

>> @@ -3753,14 +3776,13 @@ replace_one_candidate (slsr_cand_t c, unsigned i,

>>         {

>>           gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);

>>           gassign *cast_stmt = gimple_build_assign (lhs, NOP_EXPR,

> basis_name);

>> -         slsr_cand_t cc = c;

>> +         slsr_cand_t cc = lookup_cand (c->first_interp);

>>           gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));

>>           gsi_replace (&gsi, cast_stmt, false);

>> -         c->cand_stmt = cast_stmt;

>> -         while (cc->next_interp)

>> +         while (cc)

>>             {

>> -             cc = lookup_cand (cc->next_interp);

>>               cc->cand_stmt = cast_stmt;

>> +             cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;

>>             }

> 

>>           if (dump_file && (dump_flags & TDF_DETAILS))

>

Patch

Index: gcc/gimple-ssa-strength-reduction.c
===================================================================
--- gcc/gimple-ssa-strength-reduction.c	(revision 260484)
+++ gcc/gimple-ssa-strength-reduction.c	(working copy)
@@ -266,6 +266,10 @@  struct slsr_cand_d
      of a statement.  */
   cand_idx next_interp;
 
+  /* Index of the first candidate record in a chain for the same
+     statement.  */
+  cand_idx first_interp;
+
   /* Index of the basis statement S0, if any, in the candidate vector.  */
   cand_idx basis;
 
@@ -686,6 +690,7 @@  alloc_cand_and_find_basis (enum cand_kind kind, gi
   c->kind = kind;
   c->cand_num = cand_vec.length () + 1;
   c->next_interp = 0;
+  c->first_interp = c->cand_num;
   c->dependent = 0;
   c->sibling = 0;
   c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0;
@@ -1261,6 +1266,7 @@  slsr_process_mul (gimple *gs, tree rhs1, tree rhs2
 	 is the stride and RHS2 is the base expression.  */
       c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed);
       c->next_interp = c2->cand_num;
+      c2->first_interp = c->cand_num;
     }
   else if (TREE_CODE (rhs2) == INTEGER_CST)
     {
@@ -1498,7 +1504,10 @@  slsr_process_add (gimple *gs, tree rhs1, tree rhs2
 	{
 	  c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed);
 	  if (c)
-	    c->next_interp = c2->cand_num;
+	    {
+	      c->next_interp = c2->cand_num;
+	      c2->first_interp = c->cand_num;
+	    }
 	  else
 	    add_cand_for_stmt (gs, c2);
 	}
@@ -1621,6 +1630,8 @@  slsr_process_cast (gimple *gs, tree rhs1, bool spe
 
   if (base_cand && base_cand->kind != CAND_PHI)
     {
+      slsr_cand_t first_cand = NULL;
+
       while (base_cand)
 	{
 	  /* Propagate all data from the base candidate except the type,
@@ -1635,6 +1646,12 @@  slsr_process_cast (gimple *gs, tree rhs1, bool spe
 					 base_cand->index, base_cand->stride,
 					 ctype, base_cand->stride_type,
 					 savings);
+	  if (!first_cand)
+	    first_cand = c;
+
+	  if (first_cand != c)
+	    c->first_interp = first_cand->cand_num;
+
 	  if (base_cand->next_interp)
 	    base_cand = lookup_cand (base_cand->next_interp);
 	  else
@@ -1657,6 +1674,7 @@  slsr_process_cast (gimple *gs, tree rhs1, bool spe
       c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0,
 				      integer_one_node, ctype, sizetype, 0);
       c->next_interp = c2->cand_num;
+      c2->first_interp = c->cand_num;
     }
 
   /* Add the first (or only) interpretation to the statement-candidate
@@ -1681,6 +1699,8 @@  slsr_process_copy (gimple *gs, tree rhs1, bool spe
 
   if (base_cand && base_cand->kind != CAND_PHI)
     {
+      slsr_cand_t first_cand = NULL;
+
       while (base_cand)
 	{
 	  /* Propagate all data from the base candidate.  */
@@ -1693,6 +1713,12 @@  slsr_process_copy (gimple *gs, tree rhs1, bool spe
 					 base_cand->index, base_cand->stride,
 					 base_cand->cand_type,
 					 base_cand->stride_type, savings);
+	  if (!first_cand)
+	    first_cand = c;
+
+	  if (first_cand != c)
+	    c->first_interp = first_cand->cand_num;
+
 	  if (base_cand->next_interp)
 	    base_cand = lookup_cand (base_cand->next_interp);
 	  else
@@ -1717,6 +1743,7 @@  slsr_process_copy (gimple *gs, tree rhs1, bool spe
 				      integer_one_node, TREE_TYPE (rhs1),
 				      sizetype, 0);
       c->next_interp = c2->cand_num;
+      c2->first_interp = c->cand_num;
     }
 
   /* Add the first (or only) interpretation to the statement-candidate
@@ -1887,8 +1914,9 @@  dump_candidate (slsr_cand_t c)
   print_generic_expr (dump_file, c->cand_type);
   fprintf (dump_file, "\n     basis: %d  dependent: %d  sibling: %d\n",
 	   c->basis, c->dependent, c->sibling);
-  fprintf (dump_file, "     next-interp: %d  dead-savings: %d\n",
-	   c->next_interp, c->dead_savings);
+  fprintf (dump_file,
+	   "     next-interp: %d  first-interp: %d  dead-savings: %d\n",
+	   c->next_interp, c->first_interp, c->dead_savings);
   if (c->def_phi)
     fprintf (dump_file, "     phi:  %d\n", c->def_phi);
   fputs ("\n", dump_file);
@@ -2147,14 +2175,13 @@  replace_mult_candidate (slsr_cand_t c, tree basis_
       tree lhs = gimple_assign_lhs (c->cand_stmt);
       gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
       gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
-      slsr_cand_t cc = c;
+      slsr_cand_t cc = lookup_cand (c->first_interp);
       gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
       gsi_replace (&gsi, copy_stmt, false);
-      c->cand_stmt = copy_stmt;
-      while (cc->next_interp)
+      while (cc)
 	{
-	  cc = lookup_cand (cc->next_interp);
 	  cc->cand_stmt = copy_stmt;
+	  cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
 	}
       if (dump_file && (dump_flags & TDF_DETAILS))
 	stmt_to_print = copy_stmt;
@@ -2181,14 +2208,13 @@  replace_mult_candidate (slsr_cand_t c, tree basis_
       else
 	{
 	  gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
-	  slsr_cand_t cc = c;
+	  slsr_cand_t cc = lookup_cand (c->first_interp);
 	  gimple_assign_set_rhs_with_ops (&gsi, code, basis_name, bump_tree);
 	  update_stmt (gsi_stmt (gsi));
-	  c->cand_stmt = gsi_stmt (gsi);
-	  while (cc->next_interp)
+	  while (cc)
 	    {
-	      cc = lookup_cand (cc->next_interp);
 	      cc->cand_stmt = gsi_stmt (gsi);
+	      cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
 	    }
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    stmt_to_print = gsi_stmt (gsi);
@@ -3597,14 +3623,13 @@  replace_rhs_if_not_dup (enum tree_code new_code, t
 	      || !operand_equal_p (new_rhs2, old_rhs1, 0))))
     {
       gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
-      slsr_cand_t cc = c;
+      slsr_cand_t cc = lookup_cand (c->first_interp);
       gimple_assign_set_rhs_with_ops (&gsi, new_code, new_rhs1, new_rhs2);
       update_stmt (gsi_stmt (gsi));
-      c->cand_stmt = gsi_stmt (gsi);
-      while (cc->next_interp)
+      while (cc)
 	{
-	  cc = lookup_cand (cc->next_interp);
 	  cc->cand_stmt = gsi_stmt (gsi);
+	  cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
 	}
 
       if (dump_file && (dump_flags & TDF_DETAILS))
@@ -3709,14 +3734,13 @@  replace_one_candidate (slsr_cand_t c, unsigned i,
 	  || !operand_equal_p (rhs2, orig_rhs2, 0))
 	{
 	  gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
-	  slsr_cand_t cc = c;
+	  slsr_cand_t cc = lookup_cand (c->first_interp);
 	  gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, basis_name, rhs2);
 	  update_stmt (gsi_stmt (gsi));
-          c->cand_stmt = gsi_stmt (gsi);
-	  while (cc->next_interp)
+	  while (cc)
 	    {
-	      cc = lookup_cand (cc->next_interp);
 	      cc->cand_stmt = gsi_stmt (gsi);
+	      cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
 	    }
 
 	  if (dump_file && (dump_flags & TDF_DETAILS))
@@ -3736,14 +3760,13 @@  replace_one_candidate (slsr_cand_t c, unsigned i,
 	{
 	  gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
 	  gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
-	  slsr_cand_t cc = c;
+	  slsr_cand_t cc = lookup_cand (c->first_interp);
 	  gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
 	  gsi_replace (&gsi, copy_stmt, false);
-	  c->cand_stmt = copy_stmt;
-	  while (cc->next_interp)
+	  while (cc)
 	    {
-	      cc = lookup_cand (cc->next_interp);
 	      cc->cand_stmt = copy_stmt;
+	      cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
 	    }
 
 	  if (dump_file && (dump_flags & TDF_DETAILS))
@@ -3753,14 +3776,13 @@  replace_one_candidate (slsr_cand_t c, unsigned i,
 	{
 	  gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
 	  gassign *cast_stmt = gimple_build_assign (lhs, NOP_EXPR, basis_name);
-	  slsr_cand_t cc = c;
+	  slsr_cand_t cc = lookup_cand (c->first_interp);
 	  gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));
 	  gsi_replace (&gsi, cast_stmt, false);
-	  c->cand_stmt = cast_stmt;
-	  while (cc->next_interp)
+	  while (cc)
 	    {
-	      cc = lookup_cand (cc->next_interp);
 	      cc->cand_stmt = cast_stmt;
+	      cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
 	    }
 
 	  if (dump_file && (dump_flags & TDF_DETAILS))