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

[Kai Tietz <ktietz70@googlemail.com>]

Ok, reworked version.  The folding of X op X and !X op !X seems indeed
not being necessary. So function simplifies much.

Bootstrapped and regression tested for all standard languages (plus
Ada and Obj-C++). Ok for apply?

Regards,
Kai

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,129 @@ simplify_builtin_call (gimple_stmt_itera
   return false;
 }

+/* Checks if expression has type of one-bit precision, or is a known
+   truth-valued expression.  */
+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), type);
+  return false;
+}
+
+/* Helper routine for simplify_bitwise_binary_1 function.
+   Return for the SSA name NAME the expression X if it mets condition
+   NAME = !X. Otherwise return NULL_TREE.
+   Detected patterns for NAME = !X are:
+     !X and X == 0 for X with integral type.
+     X ^ 1, X != 1,or ~X for X with integral type with precision of one.  */
+static tree
+lookup_logical_inverted_value (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 (!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 == NE_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;
+      break;
+    case NE_EXPR:
+      /* Check if we have X != 1 and X is a truth-valued.  */
+      if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
+	break;
+      if (integer_onep (op2) && truth_valued_ssa_name (op1))
+	return op1;
+      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;
+}
+
+/* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
+   operations CODE, if one operand has the logically inverted
+   value of the other.  */
+static tree
+simplify_bitwise_binary_1 (enum tree_code code, tree type,
+			   tree arg1, tree arg2)
+{
+  tree anot;
+
+  /* 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
+     return NULL_TREE as this optimization is handled fold_stmt.  */
+  if (arg1 == arg2)
+    return NULL_TREE;
+  /* See if we have in arguments logical-not patterns.  */
+  if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE
+       || anot != arg2)
+      && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE
+	  || anot != arg1))
+    return NULL_TREE;
+
+  /* X & !X -> 0.  */
+  if (code == BIT_AND_EXPR)
+    return fold_convert (type, integer_zero_node);
+  /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued.  */
+  if (truth_valued_ssa_name (anot))
+    return fold_convert (type, 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.  */

@@ -1769,6 +1892,15 @@ simplify_bitwise_binary (gimple_stmt_ite
       return true;
     }

+  /* Try simple folding for X op !X, and X op X.  */
+  res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
+  if (res != NULL_TREE)
+    {
+      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" } } */