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

login
register
mail settings
Submitter Kai Tietz
Date July 1, 2011, 11:44 a.m.
Message ID <2017997593.883643.1309520672925.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com>
Download mbox | patch
Permalink /patch/102899/
State New
Headers show

Comments

Kai Tietz - July 1, 2011, 11:44 a.m.
----- Original Message -----
From: "Richard Guenther" <richard.guenther@gmail.com>
To: "Kai Tietz" <ktietz@redhat.com>
Cc: gcc-patches@gcc.gnu.org
Sent: Thursday, June 30, 2011 1:36:13 PM
Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns

On Wed, Jun 29, 2011 at 3:00 PM, Kai Tietz <ktietz@redhat.com> wrote:
> ----- Original Message -----
> From: "Kai Tietz" <ktietz@redhat.com>
> To: "Richard Guenther" <richard.guenther@gmail.com>
> Cc: gcc-patches@gcc.gnu.org
> Sent: Wednesday, June 29, 2011 1:33:30 PM
> Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns
>
> ----- Original Message -----
> From: "Richard Guenther" <richard.guenther@gmail.com>
> To: "Kai Tietz" <ktietz@redhat.com>
> Cc: gcc-patches@gcc.gnu.org
> Sent: Wednesday, June 29, 2011 12:14:10 PM
> Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns
>
> On Tue, Jun 28, 2011 at 5:05 PM, Kai Tietz <ktietz@redhat.com> wrote:
>> Hello,
>>
>> this patch implements the X op !X patterns within tree-ssa-forwprop.c without using here const-fold routines.  Additionally it does some trivial folding for X op X.  Implementation
>> also looks through [(type)] X op [(type)] !X, if type of X is integral and precision is suitable
>> for operation.
>>
>> ChangeLog gcc/
>>
>> 2011-06-28  Kai Tietz  <ktietz@redhat.com>
>>
>>        * tree-ssa-forwprop.c (operand_precision_onep): New
>>        function.
>>        (find_possible_not_expr_argument): Likewise.
>>        (simplify_bitwise_binary_1): Likewise.
>>        (simplify_bitwise_binary): Use simplify_bitwise_binary_1
>>        for detecting various X op !X optimizations.
>>
>> ChangeLog gcc/testsuite
>>
>> 2011-06-28  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 languages plus Ada and Obj-C for x86_64-pc-linux-gnu. Ok for apply?
>
> I can't follow the code in find_possible_not_expr_argument or its uses
> at all.  Please try to produce patches that look more obvious in what
> they are doing - don't try to solve every testcase you can come up with
> in a single patch.  Especially don't write functions like
> find_possible_not_expr_argument which seems to have evolved a lot
> after you wrote the overall function comment.
>
> Thanks,
> Richard.
>
>> Regards,
>> Kai
>>
>
> Well, I added some comments to these functions and renamed the find_possible_not_expr_argument function to detect_not_expr_operand, which hits its use better.
> The cause for this function is, that there are more then one variant of expressing a logical-not and all of them are used.
> This routine simply tries to detect different variants used for not. Eg ~X == !X and (X ^ 1) == !X for integral type of X with precision one. For X with integral type, (X == 0) == !X.
>
> The folding for the three different bitwise-operations is pretty easy and it makes sense to implement them at once.  I see here no good point to separate them into different patches.  To separate them might even lead to questions about abstracting some code-pieces out of the main function.
> I didn't added testcases for all variants I am aware now. Just those, which are now handled.
>
> So hope you can read and understand logic of patch better by updated patch.
>
> Regards,
> Kai
>
> I found that in version I've sent there is an unclosed comment.  So here is updated patch, which additionally simplify some code to ease reading.

Ok, I'm going to comment on a few things in the patch.

+/* Checks if expression has type of one-bit precision, or is result of
+   a known boolean expression.  */
+static bool
+operand_precision_onep (tree expr)
+{
+  enum tree_code code;
+  gimple def_stmt;
+
+  do
+    {
+      code = TREE_CODE (expr);
+      if (!INTEGRAL_TYPE_P (TREE_TYPE (expr)))
+	return false;
+      if (TYPE_PRECISION (TREE_TYPE (expr)) == 1)
+	return true;
+      if (code != SSA_NAME)
+	break;
+      def_stmt = SSA_NAME_DEF_STMT (expr);
+      if (!def_stmt || !is_gimple_assign (def_stmt))
+	break;
+      code = gimple_assign_rhs_code (def_stmt);
+      if (!CONVERT_EXPR_CODE_P (code))
+	break;
+      expr = gimple_assign_rhs1 (def_stmt);
+    }
+  while (CONVERT_EXPR_CODE_P (code));
+
+  if (code == TRUTH_NOT_EXPR || TREE_CODE_CLASS (code) == tcc_comparison)
+    return true;
+  return false;
+}

Please don't do arbitrary deep lookups like this.  Instead this
function should be

bool
truth_valued_ssa_name_p (tree name)
{
  tree type = TREE_TYPE (name);
  gimple def_stmt;

  if (!INTEGRAL_TYPE_P (type))
    return false;
  if (TREE_CODE (type) == BOOLEAN_TYPE
      || TYPE_PRECISION (type) == 1)
    return true;

  def_stmt = SSA_NAME_DEF_STMT (name);
  if (is_gimple_assign (def_stmt))
    return truth_value_p (gimple_assign_rhs_code (def_stmt));
  return false;
}

+static tree
+detect_not_expr_operand (tree name, tree *nexpr)

same, don't do arbitrary deep lookups.  Do simple matches by
enumerating them.  The code is not followable or easily verifiable
for correctness.  Look at how all the code in fold-const.c is written - it's
very easy to follow what is matched and what is produced.  This is not
at all the case for your code.

Richard.

> Regards,
> Kai
>

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?

Regards,
Kai
Richard Guenther - July 1, 2011, 12:53 p.m.
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.  "

+  /* 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?

+/* 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.

+  def = SSA_NAME_DEF_STMT (name);
+  if (!def || !is_gimple_assign (def))
+    return NULL_TREE;
+

def is never NULL.

+  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

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

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

What about NE_EXPR?

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.

There is also EQ/NE_EXPR with op2 == 1, which at least
for truth-valued op1 can be handled as well.

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

+  /* 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.

+  /* 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
>
Kai Tietz - July 1, 2011, 1:43 p.m.
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
Kai Tietz - July 1, 2011, 1:57 p.m.
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.

Regards,
Kai
Kai Tietz - July 2, 2011, 8:59 a.m.
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

Patch

Index: gcc-head/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc-head.orig/gcc/tree-ssa-forwprop.c
+++ gcc-head/gcc/tree-ssa-forwprop.c
@@ -1602,6 +1602,179 @@  simplify_builtin_call (gimple_stmt_itera
   return false;
 }
 
+/* Checks if expression has type of one-bit precision, or is a known
+   truth-value pression.  */
+static bool
+truth_valued_ssa_name (tree name)
+{
+  gimple def;
+  tree type = TREE_TYPE (name);
+
+  if (!INTEGRAL_TYPE_P (type))
+    return false;
+  /* 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;
+  def = SSA_NAME_DEF_STMT (name);
+  if (is_gimple_assign (def))
+    return truth_value_p (gimple_assign_rhs_code (def));
+  return false;
+}
+
+/* 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)
+{
+  tree op1, op2;
+  enum tree_code code;
+  gimple def;
+
+  /* If name has none-intergal type, or isn't a SSA_NAME, then
+     return.  */
+  if (TREE_CODE (name) != SSA_NAME
+      || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
+    return NULL_TREE;
+  def = SSA_NAME_DEF_STMT (name);
+  if (!def || !is_gimple_assign (def))
+    return NULL_TREE;
+
+  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))
+	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;
+      if (integer_zerop (op2))
+	return op1;
+      else if (integer_zerop (op1))
+	return op2;
+      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;
+    }
+
+  return NULL_TREE;
+}
+
+/* Try to optimize patterns X & not(X) -> zero, X | not(X) -> one, and
+   X ^ not(X) -> one, if type of X is valid for this.
+   Additional handle the variants X & X -> X, X | X -> X, and X ^ X -> zero.
+
+   See for detected not-patterns the detect_not_expr_operand function.  */
+static tree
+simplify_bitwise_binary_1 (enum tree_code code, tree arg1,
+			   tree arg2)
+{
+  tree a1not, a2not;
+  tree op = NULL_TREE;
+
+  /* If CODE isn't a bitwise binary operation, return NULL_TREE.  */
+  if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
+      && code != BIT_XOR_EXPR)
+    return NULL_TREE;
+
+  /* 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;
+    }
+  /* 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;
+
+  /* Do we have case not(X) op not(X)?  */
+  if (a1not && a2not)
+    {
+      /* Check if operands not(ARG1) and not(ARG2) are equal and
+	 fold them if so.  */
+      if (operand_equal_p (a1not, a2not, 0))
+	{
+	  /* !X & !X -> !X, and !X | i!X -> !X.  */
+	  if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+	    return arg1;
+	  /* !X ^ !X -> 0.  */
+	  return integer_zero_node;
+	}
+      return NULL_TREE;
+    }
+
+  if (a2not)
+    {
+      /* X equal to Y for X op not(Y)  */
+      if (operand_equal_p (arg1, a2not, 0))
+        op = arg1;
+    }
+  if (!op && a1not)
+    {
+      /* X equal to Y for not(X) op Y  */
+      if (operand_equal_p (arg2, a1not, 0))
+        op = arg2;
+    }
+  /* No match, return NULL_TREE.  */
+  if (!op)
+    return NULL_TREE;
+
+  /* X & not(X) -> 0.  */
+  if (code == BIT_AND_EXPR)
+    return integer_zero_node;
+  else if (code == BIT_IOR_EXPR)
+    {
+      /* X | not(X) -> 1, if X is truth-valued.  */
+      if (truth_valued_ssa_name (op))
+	return integer_one_node;
+
+      /* ??? Otherwise result is (X != 0 ? X : 1).  not handled.  */
+    }
+  else if (code == BIT_XOR_EXPR)
+    {
+      /* X ^ not(X) -> 1, if X is truth-valued.  */
+      if (truth_valued_ssa_name (op))
+	return integer_one_node;
+
+      /* ??? Otherwise result is (X != 0 ? X : 1.  not handled.  */
+    }
+  return NULL_TREE;
+}
+
 /* Simplify bitwise binary operations.
    Return true if a transformation applied, otherwise return false.  */
 
@@ -1768,7 +1941,31 @@  simplify_bitwise_binary (gimple_stmt_ite
       update_stmt (stmt);
       return true;
     }
+  /* Try simple folding for X op !X, and X op X.  */
+  res = simplify_bitwise_binary_1 (code, arg1, arg2);
+  if (res != NULL_TREE && TREE_CODE (res) == INTEGER_CST)
+    {
+      res = fold_convert_loc (gimple_location (stmt),
+			      TREE_TYPE (arg1), res);
+      gimple_assign_set_rhs_from_tree (gsi, res);
+      update_stmt (gsi_stmt (*gsi));
+      return true;
+    }
+  else if (res)
+    {
+      if (!useless_type_conversion_p (TREE_TYPE (arg1), TREE_TYPE (res)))
+	{
+	  res = force_gimple_operand_gsi (gsi, res, true, NULL_TREE, true,
+					  GSI_SAME_STMT);
 
+	  gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
+					    res, NULL_TREE, NULL_TREE);
+	}
+      else
+	gimple_assign_set_rhs_from_tree (gsi, res);
+      update_stmt (gsi_stmt (*gsi));
+      return true;
+    }
   return false;
 }
 
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand1a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand1a.c
@@ -0,0 +1,13 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (char a, unsigned short b)
+{
+  return (a & !a) | (b & !b);
+}
+
+/* As long as comparisons aren't boolified and casts from boolean-types
+   aren't preserved, the folding of  X & !X to zero fails.  */
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand2a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand2a.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a)
+{
+  return (!a & 1) != (a == 0);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand3a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand3a.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (short a)
+{
+  return (!a & 1) != ((a == 0) & 1);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand4a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand4a.c
@@ -0,0 +1,13 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (unsigned char a, _Bool b)
+{
+  return (!a & a) | (b & !b);
+}
+
+/* As long as comparisons aren't boolified and casts from boolean-types
+   aren't preserved, the folding of  X & !X to zero fails.  */
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand5a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand5a.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (long a, unsigned long b)
+{
+  return (a & (a == 0)) | (b & !b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand6a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand6a.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (unsigned long a, long b)
+{
+  return (a & !a) | (b & (b == 0));
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notor1.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notor1.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (_Bool a, _Bool b)
+{
+  return (a | !a) | (!b | b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notor2.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notor2.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (_Bool a, _Bool b)
+{
+  return (a | (a == 0)) | ((b ^ 1) | b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notxor1.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notxor1.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (_Bool a, _Bool b)
+{
+  return (a ^ !a) | (!b ^ b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notxor2.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notxor2.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (_Bool a, _Bool b)
+{
+  return (a ^ (a == 0)) | ((b == 0) ^ b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */