Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns

[Kai Tietz <ktietz70@googlemail.com>]

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