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

[Richard Guenther <richard dot guenther at gmail dot 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.  "

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