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 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