This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch 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 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.
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.
>> ? ? ? 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