2011/7/1 Kai Tietz <ktiet...@googlemail.com>:
> 2011/7/1 Kai Tietz <ktiet...@googlemail.com>:
>> 2011/7/1 Richard Guenther <richard.guent...@gmail.com>:
>>> On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz <kti...@redhat.com> wrote:
>>>> Ok, here is reworked patch with adjusted testcase.
>>>>
>>>> ChangeLog gcc/
>>>>
>>>> 2011-07-01 Kai Tietz <kti...@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 <kti...@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
