On Tue, Aug 2, 2011 at 4:34 PM, Kai Tietz <[email protected]> wrote:
> 2011/8/2 Richard Guenther <[email protected]>:
>> On Tue, Aug 2, 2011 at 3:14 PM, Kai Tietz <[email protected]> wrote:
>>> 2011/8/2 Richard Guenther <[email protected]>:
>>>> On Tue, Aug 2, 2011 at 12:17 PM, Kai Tietz <[email protected]> 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 <[email protected]>
>>>
>>> * 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 <[email protected]>
>>>
>>> * 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.
>
> Ok
>
>> 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?
>
> Well, in my tests I haven't saw this for Ada. Anyway I added explicit
> checks for one and zero, so range of constant is defined.
> To make code here a bit more easier to readable, I renamed local var
> and added some comment here.
>
>>> + 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.
>
> Hmm, well, I removed it. This folding is done in forwprop IIRC.
>
>>> + 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?
>
> Yes, missed that (and had here a bug). Corrected in patch.
>
>>> +
>>> + }
>>> +
>>> + }
>>>
>>> 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.
>
> Why, if fold_stmt_inplace returns false, comment says nothing was
> changed. So why should be a second update_stmt be necessary? I
> modified that in new patch, but this looks more costy.
Ah, I somehow saw a -update_stmt (stmt); in the previous line. Thus,
you can move the update_stmt after the fold_stmt_inplace but need to
do it unconditionally. fold_stmt is supposed to only look at operands,
not at immediate use information.
Ok with that change.
Thanks,
Richard.
>>> 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
>
>
> So revised patch with same changelog as before ...
>
> Regards,
> Kai
>
> Index: gcc/gcc/gimple.c
> ===================================================================
> --- gcc.orig/gcc/gimple.c
> +++ gcc/gcc/gimple.c
> @@ -3160,7 +3160,9 @@ canonicalize_cond_expr_cond (tree t)
> {
> /* Strip conversions around boolean operations. */
> if (CONVERT_EXPR_P (t)
> - && truth_value_p (TREE_CODE (TREE_OPERAND (t, 0))))
> + && (truth_value_p (TREE_CODE (TREE_OPERAND (t, 0)))
> + || TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0)))
> + == BOOLEAN_TYPE))
> t = TREE_OPERAND (t, 0);
>
> /* For !x use x == 0. */
> 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,47 @@ fold_gimple_assign (gimple_stmt_iterator
> gimple_assign_rhs1 (stmt),
> gimple_assign_rhs2 (stmt));
> }
> + /* Try to canonicalize for boolean-typed X the comparisons
> + X == 0, X == 1, X != 0, and X != 1. */
> + else if (gimple_assign_rhs_code (stmt) == EQ_EXPR
> + || gimple_assign_rhs_code (stmt) == NE_EXPR)
> + {
> + tree lhs = gimple_assign_lhs (stmt);
> + tree op1 = gimple_assign_rhs1 (stmt);
> + tree op2 = gimple_assign_rhs2 (stmt);
> + tree type = TREE_TYPE (op1);
> +
> + /* Check whether the comparison operands are of the same boolean
> + type as the result type is.
> + Check that second operand is an integer-constant with value
> + one or zero. */
> + if (TREE_CODE (op2) == INTEGER_CST
> + && (integer_zerop (op2) || integer_onep (op2))
> + && useless_type_conversion_p (TREE_TYPE (lhs), type))
> + {
> + enum tree_code cmp_code = gimple_assign_rhs_code (stmt);
> + bool is_logical_not = false;
> +
> + /* X == 0 and X != 1 is a logical-not.of X
> + X == 1 and X != 0 is X */
> + if ((cmp_code == EQ_EXPR && integer_zerop (op2))
> + || (cmp_code == NE_EXPR && integer_onep (op2)))
> + is_logical_not = true;
> +
> + if (is_logical_not == false)
> + result = op1;
> + /* Only for one-bit precision typed X the transformation
> + !X -> ~X is valied. */
> + else if (TYPE_PRECISION (type) == 1)
> + result = build1_loc (gimple_location (stmt), BIT_NOT_EXPR,
> + type, op1);
> + /* Otherwise we use !X -> X ^ 1. */
> + else
> + result = build2_loc (gimple_location (stmt), BIT_XOR_EXPR,
> + type, op1, build_int_cst (type, 1));
> +
> + }
> + }
>
> 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);
> + fold_stmt_inplace (stmt);
> + update_stmt (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);
> }
> else
>
