[tree-optimization] : Avoid !=/== 0/1 comparisons for boolean-typed argument

2011/8/2 Richard Guenther <richard.guenther@gmail.com>:
> On Tue, Aug 2, 2011 at 12:17 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> Hello,
>>
>> this patch removes in forward-propagation useless comparisons X != 0
>> and X != ~0 for boolean-typed X.  For one-bit precision typed X we
>> simplifiy X == 0 (and X != ~0) to ~X, and for X != 0 (and X == ~0) to
>> X.
>> For none one-bit precisione typed X, we simplify here X == 0 -> X ^ 1,
>> and for X != 0 -> X.  We can do this as even for Ada - which has only
>> boolean-type with none-one-bit precision - the truth-value is one.
>
> This isn't a simplification but a canonicalization and thus should be
> done by fold_stmt instead (we are not propagating anything after all).
> In fact, fold_stmt should do parts of this already by means of its
> canonicalizations via fold.

Well, it simplifies and canonicalizes.  But to put this into
gimple-fold looks better.

>> Additionally this patch changes for function
>> forward_propagate_comparison the meaning of true-result.  As this
>> result wasn't used and it is benefitial to use this propagation also
>
> which is a bug - for a true return value we need to set cfg_changed to true.

I addressed this in my updated patch (see below)

>> in second loop in function ssa_forward_propagate_and_combine, it
>> returns true iff statement was altered.  Additionally this function
>> handles now the boolean-typed simplifications.
>
> why call it twice?  How should that be "beneficial"?  I think that
> forward_propagate_into_comparison should instead fold the changed
> statement.

Well, due missing fold_stmt call, there were still none-converted
comparisons. I've added here the call to fold_stmt_inplace, and it
solved the issue.

>> For the hunk in gimple.c for function canonicalize_cond_expr_cond:
>> This change seems to show no real effect, but IMHO it makes sense to
>> add here the check for cast from boolean-type to be consitant.
>
> Probably yes.
>
> Thanks,
> Richard.


2011-08-02  Kai Tietz  <ktietz@redhat.com>

       * gimple.c (canonicalize_cond_expr_cond): Handle cast from boolean-type.
       (ssa_forward_propagate_and_combine): Interprete result of
       forward_propagate_comparison.
       * gcc/gimple-fold.c (fold_gimple_assign): Add canonicalization for
       boolean-typed operands for comparisons.

2011-08-02  Kai Tietz  <ktietz@redhat.com>

        * gcc.dg/tree-ssa/forwprop-15.c: New testcase.

Regression tested and bootstrapped for all languages (including Ada
and Obj-C++).  Ok for apply?

Regards,
Kai

On Tue, Aug 2, 2011 at 3:14 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/8/2 Richard Guenther <richard.guenther@gmail.com>:
>> On Tue, Aug 2, 2011 at 12:17 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>> Hello,
>>>
>>> this patch removes in forward-propagation useless comparisons X != 0
>>> and X != ~0 for boolean-typed X.  For one-bit precision typed X we
>>> simplifiy X == 0 (and X != ~0) to ~X, and for X != 0 (and X == ~0) to
>>> X.
>>> For none one-bit precisione typed X, we simplify here X == 0 -> X ^ 1,
>>> and for X != 0 -> X.  We can do this as even for Ada - which has only
>>> boolean-type with none-one-bit precision - the truth-value is one.
>>
>> This isn't a simplification but a canonicalization and thus should be
>> done by fold_stmt instead (we are not propagating anything after all).
>> In fact, fold_stmt should do parts of this already by means of its
>> canonicalizations via fold.
>
> Well, it simplifies and canonicalizes.  But to put this into
> gimple-fold looks better.
>
>>> Additionally this patch changes for function
>>> forward_propagate_comparison the meaning of true-result.  As this
>>> result wasn't used and it is benefitial to use this propagation also
>>
>> which is a bug - for a true return value we need to set cfg_changed to true.
>
> I addressed this in my updated patch (see below)
>
>>> in second loop in function ssa_forward_propagate_and_combine, it
>>> returns true iff statement was altered.  Additionally this function
>>> handles now the boolean-typed simplifications.
>>
>> why call it twice?  How should that be "beneficial"?  I think that
>> forward_propagate_into_comparison should instead fold the changed
>> statement.
>
> Well, due missing fold_stmt call, there were still none-converted
> comparisons. I've added here the call to fold_stmt_inplace, and it
> solved the issue.
>
>>> For the hunk in gimple.c for function canonicalize_cond_expr_cond:
>>> This change seems to show no real effect, but IMHO it makes sense to
>>> add here the check for cast from boolean-type to be consitant.
>>
>> Probably yes.
>>
>> Thanks,
>> Richard.
>
>
> 2011-08-02  Kai Tietz  <ktietz@redhat.com>
>
>       * gimple.c (canonicalize_cond_expr_cond): Handle cast from boolean-type.
>       (ssa_forward_propagate_and_combine): Interprete result of
>       forward_propagate_comparison.
>       * gcc/gimple-fold.c (fold_gimple_assign): Add canonicalization for
>       boolean-typed operands for comparisons.
>
> 2011-08-02  Kai Tietz  <ktietz@redhat.com>
>
>        * gcc.dg/tree-ssa/forwprop-15.c: New testcase.
>
> Regression tested and bootstrapped for all languages (including Ada
> and Obj-C++).  Ok for apply?

Comments below

> Regards,
> Kai
>
> Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/forwprop-15.c
> ===================================================================
> --- /dev/null
> +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/forwprop-15.c
> @@ -0,0 +1,14 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-forwprop1" }  */
> +
> +_Bool
> +foo (_Bool a, _Bool b, _Bool c
> +{
> +  _Bool r1 = a == 0 & b != 0;
> +  _Bool r2 = b != 0 & c == 0;
> +  return (r1 == 0 & r2 == 0);
> +}
> +
> +/* { dg-final { scan-tree-dump-times " == " 0 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times " != " 0 "forwprop1" } } */
> +/* { dg-final { cleanup-tree-dump "forwprop1" } } */
> Index: gcc/gcc/gimple-fold.c
> ===================================================================
> --- gcc.orig/gcc/gimple-fold.c
> +++ gcc/gcc/gimple-fold.c
> @@ -814,6 +814,34 @@ fold_gimple_assign (gimple_stmt_iterator
>                                             gimple_assign_rhs1 (stmt),
>                                             gimple_assign_rhs2 (stmt));
>        }
> +      else if (gimple_assign_rhs_code (stmt) == EQ_EXPR
> +               || gimple_assign_rhs_code (stmt) == NE_EXPR)
> +        {
> +         tree op1 = gimple_assign_rhs1 (stmt);
> +         tree op2 = gimple_assign_rhs2 (stmt);
> +         tree type = TREE_TYPE (op1);
> +         if (useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
> +                                        type)
> +             && TREE_CODE (op2) == INTEGER_CST)

first check op2, it's cheaper.  put the lhs into a local var to avoid the
excessive long line.

And add a comment what you check here - cost me some 2nd thoguht.
Like

  /* Check whether the comparison operands are of the same boolean
     type as the result type is.  */

> +           {
> +             gimple s;
> +             bool inverted = (gimple_assign_rhs_code (stmt) == EQ_EXPR);
> +             if (!integer_zerop (op2))
> +               inverted = !inverted;

For non-1-precision bools I believe you can have non-1 and non-0 op2.
So you better explicitly check.  The code also isn't too easy to follow,
just enumerating the four cases wouldn't cause too much bloat, no?

> +             if (inverted == false)
> +               result = op1;
> +             else if (TREE_CODE (op1) == SSA_NAME
> +                      && (s = SSA_NAME_DEF_STMT (op1)) != NULL
> +                      && is_gimple_assign (s)
> +                      && gimple_assign_rhs_code (s) == BIT_NOT_EXPR)

You shouldn't do stmt lookups here.

> +               result = gimple_assign_rhs1 (s);
> +            else
> +               result = build1_loc (gimple_location (stmt), BIT_NOT_EXPR, type, op1);

What about the non-1-precision booleans?  You need to generate
op1 ^ 1 here instead, no?

> +
> +           }
> +
> +       }
>
>       if (!result)
>         result = fold_binary_loc (loc, subcode,
> Index: gcc/gcc/tree-ssa-forwprop.c
> ===================================================================
> --- gcc.orig/gcc/tree-ssa-forwprop.c
> +++ gcc/gcc/tree-ssa-forwprop.c
> @@ -469,6 +469,9 @@ forward_propagate_into_comparison (gimpl
>     {
>       gimple_assign_set_rhs_from_tree (gsi, tmp);
>       update_stmt (stmt);
> +      if (fold_stmt_inplace (stmt))
> +        update_stmt (stmt);
> +

No, we need to update_stmt always as we already did change the stmt.

>       if (TREE_CODE (rhs1) == SSA_NAME)
>        cfg_changed |= remove_prop_source_from_use (rhs1);
>       if (TREE_CODE (rhs2) == SSA_NAME)
> @@ -2407,7 +2410,8 @@ ssa_forward_propagate_and_combine (void)
>            }
>          else if (TREE_CODE_CLASS (code) == tcc_comparison)
>            {
> -             forward_propagate_comparison (stmt);
> +             if (forward_propagate_comparison (stmt))
> +               cfg_changed = true;
>              gsi_next (&gsi);

This hunk is ok.

Thanks,
Richard.

>            }
>          else
>

On Tue, Aug 2, 2011 at 6:14 AM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/8/2 Richard Guenther <richard.guenther@gmail.com>:
>> On Tue, Aug 2, 2011 at 12:17 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>> Hello,
>>>
>>> this patch removes in forward-propagation useless comparisons X != 0
>>> and X != ~0 for boolean-typed X.  For one-bit precision typed X we
>>> simplifiy X == 0 (and X != ~0) to ~X, and for X != 0 (and X == ~0) to
>>> X.
>>> For none one-bit precisione typed X, we simplify here X == 0 -> X ^ 1,
>>> and for X != 0 -> X.  We can do this as even for Ada - which has only
>>> boolean-type with none-one-bit precision - the truth-value is one.
>>
>> This isn't a simplification but a canonicalization and thus should be
>> done by fold_stmt instead (we are not propagating anything after all).
>> In fact, fold_stmt should do parts of this already by means of its
>> canonicalizations via fold.
>
> Well, it simplifies and canonicalizes.  But to put this into
> gimple-fold looks better.
>
>>> Additionally this patch changes for function
>>> forward_propagate_comparison the meaning of true-result.  As this
>>> result wasn't used and it is benefitial to use this propagation also
>>
>> which is a bug - for a true return value we need to set cfg_changed to true.
>
> I addressed this in my updated patch (see below)
>
>>> in second loop in function ssa_forward_propagate_and_combine, it
>>> returns true iff statement was altered.  Additionally this function
>>> handles now the boolean-typed simplifications.
>>
>> why call it twice?  How should that be "beneficial"?  I think that
>> forward_propagate_into_comparison should instead fold the changed
>> statement.
>
> Well, due missing fold_stmt call, there were still none-converted
> comparisons. I've added here the call to fold_stmt_inplace, and it
> solved the issue.
>
>>> For the hunk in gimple.c for function canonicalize_cond_expr_cond:
>>> This change seems to show no real effect, but IMHO it makes sense to
>>> add here the check for cast from boolean-type to be consitant.
>>
>> Probably yes.
>>
>> Thanks,
>> Richard.
>
>
> 2011-08-02  Kai Tietz  <ktietz@redhat.com>
>
>       * gimple.c (canonicalize_cond_expr_cond): Handle cast from boolean-type.
>       (ssa_forward_propagate_and_combine): Interprete result of
>       forward_propagate_comparison.
>       * gcc/gimple-fold.c (fold_gimple_assign): Add canonicalization for
>       boolean-typed operands for comparisons.
>
> 2011-08-02  Kai Tietz  <ktietz@redhat.com>
>
>        * gcc.dg/tree-ssa/forwprop-15.c: New testcase.
>
> Regression tested and bootstrapped for all languages (including Ada
> and Obj-C++).  Ok for apply?
>

It caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49947