This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns
2011/7/1 Kai Tietz <ktietz70@googlemail.com>:
> 2011/7/1 Kai Tietz <ktietz70@googlemail.com>:
>> 2011/7/1 Richard Guenther <richard.guenther@gmail.com>:
>>> On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz <ktietz@redhat.com> wrote:
>>>> Ok, here is reworked patch with adjusted testcase.
>>>>
>>>> ChangeLog gcc/
>>>>
>>>> 2011-07-01 ?Kai Tietz ?<ktietz@redhat.com>
>>>>
>>>> ? ? ? ?* tree-ssa-forwprop.c (truth_valued_ssa): New function.
>>>> ? ? ? ?(detect_not_expr_operand): New function.
>>>> ? ? ? ?(simplify_bitwise_binary_1): New function.
>>>> ? ? ? ?(simplify_bitwise_binary): Use simplify_bitwise_binary_1.
>>>>
>>>> ChangeLog gcc/
>>>>
>>>> 2011-07-01 ?Kai Tietz ?<ktietz@redhat.com>
>>>>
>>>> ? ? ? ?* gcc.dg/binop-notand1a.c: New test.
>>>> ? ? ? ?* gcc.dg/binop-notand2a.c: New test.
>>>> ? ? ? ?* gcc.dg/binop-notand3a.c: New test.
>>>> ? ? ? ?* gcc.dg/binop-notand4a.c: New test.
>>>> ? ? ? ?* gcc.dg/binop-notand5a.c: New test.
>>>> ? ? ? ?* gcc.dg/binop-notand6a.c: New test.
>>>> ? ? ? ?* gcc.dg/binop-notor1.c: New test.
>>>> ? ? ? ?* gcc.dg/binop-notor2.c: New test.
>>>> ? ? ? ?* gcc.dg/binop-notxor1.c: New test.
>>>> ? ? ? ?* gcc.dg/binop-notxor2.c: New test.
>>>>
>>>>
>>>> Bootstrapped and regression tested for all standard languages plus Ada and Obj-C++ for x86_64-pc-linux-gnu. ?Ok for apply?
>>>
>>> (please post patches inline)
>>>
>>> +/* Checks if expression has type of one-bit precision, or is a known
>>> + ? truth-value pression. ?*/
>>> +static bool
>>> +truth_valued_ssa_name (tree name)
>>>
>>> The function comment should refer to each parameter in capital letters.
>>> The comment is also odd, if you consider the function name. ?Better
>>> would be "Return true if the SSA name NAME is of truth-value. ?"
>>
>> Ok
>>
>>> + ?/* Don't check here for BOOLEAN_TYPE as the precision isn't
>>> + ? ? necessarily one and so ~X is not equal to !X. ?*/
>>> + ?if (TYPE_PRECISION (type) == 1)
>>> + ? ?return true;
>>>
>>> Technically correct, but did you run into actual problems without this?
>> Yes, this makes issues. ?See BIT_NOT_EXPR in fold-const. ?It uses LHS type
>> for ~0. ?[*]
>>
>>> +/* Helper routine for simplify_bitwise_binary_1 function.
>>> + ? If a NOT-expression is found, the operand of the NOT-expression is
>>> + ? returned. ?Othewise NULL_TREE is returned.
>>> + ? Detected not-patterns are !X or X == 0 for X with integral type, and
>>> + ? X ^ 1 or ~X for X with integral type with precision of one.
>>> + ? The value of CNT_CASTS is either zero, or one. ? */
>>> +static tree
>>> +detect_not_expr_operand (tree name)
>>>
>>> What's a NOT-expression? ?I'd suggest
>>>
>>> /* For the SSA name NAME return an expression X so that
>>> ? NAME = !X. ?If there is no such X, return NULL_TREE. ?*/
>>>
>>> Then a better name for the function would be lookup_inverted_value.
>> Hmm, we don't look up inverted values in general. May
>> lookup_inverted_truth_value?
>>
>>> + ?def = SSA_NAME_DEF_STMT (name);
>>> + ?if (!def || !is_gimple_assign (def))
>>> + ? ?return NULL_TREE;
>>> +
>>>
>>> def is never NULL.
>> Ok
>>
>>> + ?code = gimple_assign_rhs_code (def);
>>> + ?op1 = gimple_assign_rhs1 (def);
>>> + ?op2 = NULL_TREE;
>>> +
>>> + ?/* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
>>> + ? ? If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, TRUTH_NOT_EXPR,
>>> + ? ? or BIT_NOT_EXPR, then return. ?*/
>>> + ?if (code == EQ_EXPR || code == BIT_XOR_EXPR)
>>> + ? ?op2 = gimple_assign_rhs2 (def);
>>> +
>>> + ?switch (code)
>>> + ? ?{
>>> + ? ?case TRUTH_NOT_EXPR:
>>> + ? ? ?return op1;
>>> + ? ?case BIT_NOT_EXPR:
>>> + ? ? ?if (truth_valued_ssa_name (name))
>>>
>>> op1, not name
>>
>> No, name is right. see [*]
>>
>>> + ? ? ? return op1;
>>> + ? ? ?break;
>>> + ? ?case EQ_EXPR:
>>> + ? ? ?/* Check if we have X == 0 and X has an integral type. ?*/
>>> + ? ? ?if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
>>> + ? ? ? break;
>>>
>>> I think you want this test generally, before the switch.
>> No, no need for this. Just for comparisons I need to check that
>> operands are equal. The type of NAME
>> is always an integral value.
>>
>>> + ? ? ?if (integer_zerop (op2))
>>> + ? ? ? return op1;
>>> + ? ? ?else if (integer_zerop (op1))
>>> + ? ? ? return op2;
>>>
>>> It's always op2 that is 0, no need to test op1.
>> So for comparison constant will be moved always right-hand? ?Ok fine by this.
>>
>>> What about NE_EXPR?
>> Maybe for X != 1 for an truth-valued X. But I never saw this pattern
>> generated. All other cases related to NE_EXPR, which might be an
>> inverted variant aren't trivial and not sure if it is worth checking
>> them here.
>> Eg. (X | Y) != 0 -> (X != 0 | Y != 0) would be the inverted variant of
>> (X == 0 && Y == 0). But those things might be better placed in
>> and/or_comparison folding in gimple-fold.c, isn't it?
>>
>>> If you allow EQ/NE_EXPRs then what this function returns is
>>> not something for which NAME = !X holds but something
>>> for which NAME = X == 0 holds. ?Otherwise you have to
>>> make sure op1 is a truth value.
>> !X is (for integral types) X == (type-x) 0. And this transformation is
>> bijective AFAICS. I don't see the point you mean here.
>>
>>> There is also EQ/NE_EXPR with op2 == 1, which at least
>>> for truth-valued op1 can be handled as well.
>>
>> See comment above. It is true that X != 1 (for truth-valued X) is X ==
>> 0. This might be a special case worth to add, but for X != 0 (for
>> truth-valued X) it isn't. Same as for X == 1 cases. We want to return
>> the argument of the not expression here. So we would need to return
>> for those cases !X.
>>
>>> + ? ? ?break;
>>> + ? ?case BIT_XOR_EXPR:
>>> + ? ? ?/* Check if we have X ^ 1 and X is truth valued. ?*/
>>> + ? ? ?if (integer_onep (op2) && truth_valued_ssa_name (op1))
>>> + ? ? ? return op1;
>>> + ? ? ?break;
>>> + ? ?default:
>>> + ? ? ?break;
>>> + ? ?}
>>>
>>> + ?/* First check if operands ARG1 and ARG2 are equal, if so we
>>> + ? ? won't have a NOT-pattern match. ?Fold these patterns, as
>>> + ? ? we have detected it already. ?*/
>>> + ?if (operand_equal_p (arg1, arg2, 0))
>>> + ? ?{
>>> + ? ? ?/* X & X -> X, and X | X -> X. ?*/
>>> + ? ? ?if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
>>> + ? ? ? ?return arg1;
>>> + ? ? ?/* X ^ X -> 0. ?*/
>>> + ? ? ?return integer_zero_node;
>>> + ? ?}
>>>
>>> gimple_fold catches this already, no reason to do that here.
>> Ok
>>
>>> + ?/* Do we have case not(X) op not(X)? ?*/
>>> + ?if (a1not && a2not)
>>> + ? ?{
>>>
>>> CSE would have handled this, so no reason to check this - you've
>>> done this with the previous operand_equal_p test already.
>> No I didn't. ?As this will match cases like (X ^ 1) & !X (for
>> truth-valued X). We compare here the operand of the not-expression.
>>
>>> + ?/* Get for each operation operand its optional by one integral typed
>>> + ? ? cast stripped argument. And get the not-expression's operand, if
>>> + ? ? argument represents an not-expression. ?*/
>>> + ?a1not = detect_not_expr_operand (arg1);
>>> + ?a2not = detect_not_expr_operand (arg2);
>>> +
>>> + ?/* If there are no not-expressions found, ?return NULL_TREE. */
>>> + ?if (!a1not && !a2not)
>>> + ? ?return NULL_TREE;
>>>
>>> ...
>>>
>>> + ?if (a2not)
>>> + ? ?{
>>> + ? ? ?/* X equal to Y for X op not(Y) ?*/
>>> + ? ? ?if (operand_equal_p (arg1, a2not, 0))
>>> + ? ? ? ?op = arg1;
>>> + ? ?}
>>>
>>> don't need a1not yet
>>>
>>> So I suggest to rewrite this to sth like
>>>
>>> a1not = detect_not_expr_operand (arg1);
>>> if (a1not
>>> ? ?&& operand_equal_p (a1not, arg2, 0))
>>> ?op = arg2;
>>> else if ((a2not = detect_not_expr_operand (arg2))
>>> ? ? ? ? ? && operand_equal_p (arg1, a2not, 0))
>>> ?op = arg1;
>>> else
>>> ? return NULL_TREE;
>>>
>>> ...
>>>
>>> as that is cheaper. ?The ???s below are probably not worth handling.
>>>
>>> Richard.
>>>
>>>> Regards,
>>>> Kai
>>>>
>>>
>>
>> Regards,
>> Kai
>>
>
> To be more correct here about the use of the LHS for ~ X instead of
> using X. If I check X for truth-valued, I would match also things like
> ~(X == 0). But type of the comparison isn't necessarily bool, So I
> would match for code like 'int foo (int c) { return c & ~(c == 0); }'
> and would fold it to zero. But it has for c with value zero the value
> 0, and for c with value not zero the result c.
Sorry, yesterday wasn't my day. Of course I meant sample 'int foo c) {
return c & ~ (c != 0); }'. Its result for c != 0 is (c & 0xfffffffe),
and for c == 0 it is 0.
Kai