Optimize statements created by if-conversion

Hi,

For the following minloc loop (which I am trying to vectorize):

  for (i = 0; i < N; i++)
    if (arr[i] < limit)
      {
        pos = i + 1;
        limit = arr[i];
      }

if-conversion generates

  # pos_22 = PHI <pos_1(8), 1(3)>
  # i_23 = PHI <prephitmp.8_2(8), 0(3)>
  # limit_24 = PHI <limit_4(8), 1.28e+2(3)>
  limit_10 = arr[i_23];
  pos_11 = i_23 + 1;
  pretmp.7_3 = i_23 + 1;
  pos_1 = [cond_expr] limit_10 >= limit_24 ? pos_22 : pos_11;
  limit_4 = [cond_expr] limit_10 >= limit_24 ? limit_24 : limit_10;
  prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11;
  if (prephitmp.8_2 < n_9(D))
    goto <bb 8>;
  else
    goto <bb 9>;


For

prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11;

then and else clauses are equivalent, so

prephitmp.8_2 = pretmp.7_3;

should be enough.


Does the following patch make sense? (Meanwhile, I only tested it with
vectorizer testsuite).

Thanks,
Ira

ChangeLog:

      * tree-if-conv.c (replace_phi_with_cond_gimple_assign_stmt):
      If then and else clauses are equivalent, use one of them as a
      rhs.

   new_stmt = gimple_build_assign (PHI_RESULT (phi), rhs);

On Tue, Jun 29, 2010 at 10:03 AM, Ira Rosen <IRAR@il.ibm.com> wrote:
>
> Hi,
>
> For the following minloc loop (which I am trying to vectorize):
>
>  for (i = 0; i < N; i++)
>    if (arr[i] < limit)
>      {
>        pos = i + 1;
>        limit = arr[i];
>      }
>
> if-conversion generates
>
>  # pos_22 = PHI <pos_1(8), 1(3)>
>  # i_23 = PHI <prephitmp.8_2(8), 0(3)>
>  # limit_24 = PHI <limit_4(8), 1.28e+2(3)>
>  limit_10 = arr[i_23];
>  pos_11 = i_23 + 1;
>  pretmp.7_3 = i_23 + 1;
>  pos_1 = [cond_expr] limit_10 >= limit_24 ? pos_22 : pos_11;
>  limit_4 = [cond_expr] limit_10 >= limit_24 ? limit_24 : limit_10;
>  prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11;
>  if (prephitmp.8_2 < n_9(D))
>    goto <bb 8>;
>  else
>    goto <bb 9>;
>
>
> For
>
> prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11;
>
> then and else clauses are equivalent, so
>
> prephitmp.8_2 = pretmp.7_3;
>
> should be enough.
>
>
> Does the following patch make sense? (Meanwhile, I only tested it with
> vectorizer testsuite).

Can you provide a complete testcase?  PRE should have recognized
the equivalecy already.

Richard.

> Thanks,
> Ira
>
> ChangeLog:
>
>      * tree-if-conv.c (replace_phi_with_cond_gimple_assign_stmt):
>      If then and else clauses are equivalent, use one of them as a
>      rhs.
>
> Index: tree-if-conv.c
> ===================================================================
> --- tree-if-conv.c      (revision 161484)
> +++ tree-if-conv.c      (working copy)
> @@ -925,6 +925,8 @@ replace_phi_with_cond_gimple_assign_stmt
>   basic_block bb;
>   tree rhs;
>   tree arg;
> +  gimple def_stmt0, def_stmt1;
> +  enum tree_code code;
>
>   gcc_assert (gimple_code (phi) == GIMPLE_PHI
>              && gimple_phi_num_args (phi) == 2);
> @@ -949,9 +951,35 @@ replace_phi_with_cond_gimple_assign_stmt
>          arg_1 = gimple_phi_arg_def (phi, 1);
>        }
>
> -      /* Build new RHS using selected condition and arguments.  */
> -      rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
> -                   unshare_expr (cond), arg_0, arg_1);
> +      if (TREE_CODE (arg_0) == SSA_NAME && TREE_CODE (arg_1) == SSA_NAME
> +          && (def_stmt0 = SSA_NAME_DEF_STMT (arg_0))
> +          && (def_stmt1 = SSA_NAME_DEF_STMT (arg_1))
> +          && is_gimple_assign (def_stmt0)
> +          && is_gimple_assign (def_stmt1)
> +          && (code = gimple_assign_rhs_code (def_stmt0))
> +             == gimple_assign_rhs_code (def_stmt1)
> +          && ((get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS
> +               && operand_equal_p (gimple_assign_rhs1 (def_stmt0),
> +                                   gimple_assign_rhs1 (def_stmt1), 0))
> +              || (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS
> +                  && operand_equal_p (gimple_assign_rhs1 (def_stmt0),
> +                                      gimple_assign_rhs1 (def_stmt1), 0)
> +                  && operand_equal_p (gimple_assign_rhs2 (def_stmt0),
> +                                      gimple_assign_rhs2 (def_stmt1), 0))
> +              || (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS
> +                  && operand_equal_p (gimple_assign_rhs1 (def_stmt0),
> +                                      gimple_assign_rhs1 (def_stmt1), 0)
> +                  && operand_equal_p (gimple_assign_rhs2 (def_stmt0),
> +                                      gimple_assign_rhs2 (def_stmt1), 0)
> +                  && operand_equal_p (gimple_assign_rhs3 (def_stmt0),
> +                                      gimple_assign_rhs3 (def_stmt1),
> 0))))
> +        /* Since then and else parts are equivalent, make RHS to be one of
> +           them.  */
> +        rhs = arg_0;
> +      else
> +        /* Build new RHS using selected condition and arguments.  */
> +        rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
> +                     unshare_expr (cond), arg_0, arg_1);
>     }
>
>   new_stmt = gimple_build_assign (PHI_RESULT (phi), rhs);
>
>

Richard Guenther <richard.guenther@gmail.com> wrote on 29/06/2010 12:46:52
PM:

> On Tue, Jun 29, 2010 at 10:03 AM, Ira Rosen <IRAR@il.ibm.com> wrote:
> >
> > Hi,
> >
> > For the following minloc loop (which I am trying to vectorize):
> >
> >  for (i = 0; i < N; i++)
> >    if (arr[i] < limit)
> >      {
> >        pos = i + 1;
> >        limit = arr[i];
> >      }
> >
> > if-conversion generates
> >
> >  # pos_22 = PHI <pos_1(8), 1(3)>
> >  # i_23 = PHI <prephitmp.8_2(8), 0(3)>
> >  # limit_24 = PHI <limit_4(8), 1.28e+2(3)>
> >  limit_10 = arr[i_23];
> >  pos_11 = i_23 + 1;
> >  pretmp.7_3 = i_23 + 1;
> >  pos_1 = [cond_expr] limit_10 >= limit_24 ? pos_22 : pos_11;
> >  limit_4 = [cond_expr] limit_10 >= limit_24 ? limit_24 : limit_10;
> >  prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 :
pos_11;
> >  if (prephitmp.8_2 < n_9(D))
> >    goto <bb 8>;
> >  else
> >    goto <bb 9>;
> >
> >
> > For
> >
> > prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11;
> >
> > then and else clauses are equivalent, so
> >
> > prephitmp.8_2 = pretmp.7_3;
> >
> > should be enough.
> >
> >
> > Does the following patch make sense? (Meanwhile, I only tested it with
> > vectorizer testsuite).
>
> Can you provide a complete testcase?  PRE should have recognized
> the equivalecy already.

(See attached file: test.c)

Thanks,
Ira

>
> Richard.
>
> > Thanks,
> > Ira
> >
> > ChangeLog:
> >
> >      * tree-if-conv.c (replace_phi_with_cond_gimple_assign_stmt):
> >      If then and else clauses are equivalent, use one of them as a
> >      rhs.
> >
> > Index: tree-if-conv.c
> > ===================================================================
> > --- tree-if-conv.c      (revision 161484)
> > +++ tree-if-conv.c      (working copy)
> > @@ -925,6 +925,8 @@ replace_phi_with_cond_gimple_assign_stmt
> >   basic_block bb;
> >   tree rhs;
> >   tree arg;
> > +  gimple def_stmt0, def_stmt1;
> > +  enum tree_code code;
> >
> >   gcc_assert (gimple_code (phi) == GIMPLE_PHI
> >              && gimple_phi_num_args (phi) == 2);
> > @@ -949,9 +951,35 @@ replace_phi_with_cond_gimple_assign_stmt
> >          arg_1 = gimple_phi_arg_def (phi, 1);
> >        }
> >
> > -      /* Build new RHS using selected condition and arguments.  */
> > -      rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
> > -                   unshare_expr (cond), arg_0, arg_1);
> > +      if (TREE_CODE (arg_0) == SSA_NAME && TREE_CODE (arg_1) ==
SSA_NAME
> > +          && (def_stmt0 = SSA_NAME_DEF_STMT (arg_0))
> > +          && (def_stmt1 = SSA_NAME_DEF_STMT (arg_1))
> > +          && is_gimple_assign (def_stmt0)
> > +          && is_gimple_assign (def_stmt1)
> > +          && (code = gimple_assign_rhs_code (def_stmt0))
> > +             == gimple_assign_rhs_code (def_stmt1)
> > +          && ((get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS
> > +               && operand_equal_p (gimple_assign_rhs1 (def_stmt0),
> > +                                   gimple_assign_rhs1 (def_stmt1), 0))
> > +              || (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS
> > +                  && operand_equal_p (gimple_assign_rhs1 (def_stmt0),
> > +                                      gimple_assign_rhs1 (def_stmt1),
0)
> > +                  && operand_equal_p (gimple_assign_rhs2 (def_stmt0),
> > +                                      gimple_assign_rhs2 (def_stmt1),
0))
> > +              || (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS
> > +                  && operand_equal_p (gimple_assign_rhs1 (def_stmt0),
> > +                                      gimple_assign_rhs1 (def_stmt1),
0)
> > +                  && operand_equal_p (gimple_assign_rhs2 (def_stmt0),
> > +                                      gimple_assign_rhs2 (def_stmt1),
0)
> > +                  && operand_equal_p (gimple_assign_rhs3 (def_stmt0),
> > +                                      gimple_assign_rhs3 (def_stmt1),
> > 0))))
> > +        /* Since then and else parts are equivalent, make RHS to be
one of
> > +           them.  */
> > +        rhs = arg_0;
> > +      else
> > +        /* Build new RHS using selected condition and arguments.  */
> > +        rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
> > +                     unshare_expr (cond), arg_0, arg_1);
> >     }
> >
> >   new_stmt = gimple_build_assign (PHI_RESULT (phi), rhs);
> >
> >

On Tue, Jun 29, 2010 at 11:58 AM, Ira Rosen <IRAR@il.ibm.com> wrote:
>
>
>
> Richard Guenther <richard.guenther@gmail.com> wrote on 29/06/2010 12:46:52
> PM:
>
>> On Tue, Jun 29, 2010 at 10:03 AM, Ira Rosen <IRAR@il.ibm.com> wrote:
>> >
>> > Hi,
>> >
>> > For the following minloc loop (which I am trying to vectorize):
>> >
>> >  for (i = 0; i < N; i++)
>> >    if (arr[i] < limit)
>> >      {
>> >        pos = i + 1;
>> >        limit = arr[i];
>> >      }
>> >
>> > if-conversion generates
>> >
>> >  # pos_22 = PHI <pos_1(8), 1(3)>
>> >  # i_23 = PHI <prephitmp.8_2(8), 0(3)>
>> >  # limit_24 = PHI <limit_4(8), 1.28e+2(3)>
>> >  limit_10 = arr[i_23];
>> >  pos_11 = i_23 + 1;
>> >  pretmp.7_3 = i_23 + 1;
>> >  pos_1 = [cond_expr] limit_10 >= limit_24 ? pos_22 : pos_11;
>> >  limit_4 = [cond_expr] limit_10 >= limit_24 ? limit_24 : limit_10;
>> >  prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 :
> pos_11;
>> >  if (prephitmp.8_2 < n_9(D))
>> >    goto <bb 8>;
>> >  else
>> >    goto <bb 9>;
>> >
>> >
>> > For
>> >
>> > prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11;
>> >
>> > then and else clauses are equivalent, so
>> >
>> > prephitmp.8_2 = pretmp.7_3;
>> >
>> > should be enough.
>> >
>> >
>> > Does the following patch make sense? (Meanwhile, I only tested it with
>> > vectorizer testsuite).
>>
>> Can you provide a complete testcase?  PRE should have recognized
>> the equivalecy already.
>
> (See attached file: test.c)

So the reason is our heuristic in PRE to not introduce new IVs:

Found partial redundancy for expression {plus_expr,i_24,1} (0005)
Skipping insertion of phi for partial redundancy: Looks like an
induction variable
Inserted pretmp.4_2 = i_13 + 1;
 in predecessor 8
Found partial redundancy for expression {plus_expr,i_24,1} (0005)
Inserted pretmp.4_22 = i_24 + 1;
 in predecessor 7
Created phi prephitmp.5_21 = PHI <pretmp.4_22(7), pos_11(4)>
 in block 5
Found partial redundancy for expression {plus_expr,i_24,1} (0005)
Skipping insertion of phi for partial redundancy: Looks like an
induction variable
Replaced i_24 + 1 with prephitmp.5_21 in i_13 = i_24 + 1;
Removing unnecessary insertion:pretmp.4_2 = i_13 + 1;

we do not want to insert into block 3, so we are left with

<bb 3>:
  # pos_23 = PHI <pos_1(8), 1(2)>
  # i_24 = PHI <i_13(8), 0(2)>
  # limit_25 = PHI <limit_4(8), 1.28e+2(2)>
  limit_9 = arr[i_24];
  D.3841_10 = limit_9 < limit_25;
  if (D.3841_10 != 0)
    goto <bb 4>;
  else
    goto <bb 7>;

<bb 7>:
  pretmp.4_22 = i_24 + 1;
  goto <bb 5>;

<bb 4>:
  pos_11 = i_24 + 1;

<bb 5>:
  # pos_1 = PHI <pos_23(7), pos_11(4)>
  # limit_4 = PHI <limit_25(7), limit_9(4)>
  # prephitmp.5_21 = PHI <pretmp.4_22(7), pos_11(4)>
  i_13 = prephitmp.5_21;

where there is no full redundancy for i_24 + 1 now (that is,
we did some useless half-way PRE because of that IV
heuristic ...).

Can you file a bug about this, too?  It should be fixed in
PRE, not worked around in if-conversion.

Thanks,
Richard.