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.
Regards,
Kai
