# [tree-optimization] : Improve reassociation pass for bitwise-operations

Message ID CAEwic4bvBefwvVzC5rQ0tVDQHqbcu-keAbpZky4hKGUNdUsOGQ@mail.gmail.com New show

## Commit Message

Kai Tietz Sept. 21, 2011, 1:29 p.m.
Hello,

This revised patch adds support to tree-ssa-reassoc for intial
normalizing of bitwise operation.  So the reassociation pass is able
to have better folding result.
Also it has a final denormalzing of bitwise-operations after
reassociation pass is completed to restore optimized writing.

This patch is a bit huge, but I see here no good point to split it
into smaller pieces due the denormalization and normalization of
bitwise-operation are  bound pretty much to each other.

I added some additional testcases to check also for the denormalization pass.

Normalization transforms the following patterns:

- ~ (X | Y) -> ~X & ~Y
- ~ (X & Y) -> ~X | ~Y
- ~ (X ^ Y) -> ~X ^ Y
- ~ (X ^ CST) -> X ^ CST'; with CST'=~CST
- ~ (X cmp Y) -> X cmp' Y; with cmp' = inverted comparison of cmp
- ((X cmp Y) != 0) -> X cmp Y
- ((X cmp Y) == 0) -> X cmp' Y; with cmp' = inverted comparison of cmp
- ~ (~X) -> X
- (X ! Y) != 0 -> (X != 0) | (Y != 0)
- (X | Y) == 0 -> (X == 0) & (Y == 0)

by this even more complex statments like produced for this code:

int foo (int a, int b, int c, int d)
{
int r1 = a != 0 & c != 0 & b != 0;
int r2 = a == 0 | b != 0 | d == 0;
return (r1 != 0 & r2 == 0);
}

getting in gimple transformed to (as pseudo code)

return (a != 0 & c != 0 & b != 0 & a != 0 & b == 0 & d != 0);

which can be optimized to fixed result of zero.

The de-normalization pass transforms the following patterns

- ~X & ~Y -> ~ (X | Y)
- ~X & CST -> ~ (X | CST'); with CST'=~CST
- ~X | ~Y -> ~ (X & Y)
- ~X | CST -> ~ (X & CST'); with CST'=~CST
- ~X ^ Y -> ~ (X ^ Y)
- ~X ^ CST -> X ^ CST'; with CST'=~CST
- (X != 0) | (Y != 0) -> (X ! Y) != 0
- (X == 0) & (Y == 0) -> (X | Y) == 0
- (X != ~0) | (Y != ~0) -> (X & Y) != ~0
- (X == ~0) & (Y == ~0) -> (X & Y) != ~0

ChangeLog

2011-09-21  Kai Tietz  <ktietz@redhat.com>

declaration and add support for unary-expressions.
(remove_visited_stmt_chain): Add forwarder declaration.
(push_bitwise_op): New helper function.
(remove_bitwise_op): Likewise.
(operate_bitwise_stmt): Likewise.
(repropagate_bitwise): Likewise.
(operate_bitwise_xor_stmt): Likewise.
(make_new_tmp_statement): Likewise.
(expand_not_bitwise_binary): Likewise.
(get_bitwise_single_use_root): Likewise.
(is_bitwise_not): Likewise.
(walk_bitwise_stmt_elems): Likewise.
(expand_cmp_ior): Likewise.
(rebuild_vector_tree): Likewise.
(break_up_bitwise_combined_stmt): Likewise.
(merge_bitwise_compares): Likewise.
(bitwise_ops): New static variable.
(break_up_subtract_bb): Renamed to break_up_expr_bb and
add call to break_up_bitwise_combined_stmt function.
(do_reassoc): Rename break_up_subtract_bb call as break_up_expr_bb.
(init_reassoc): Initialize bitwise_ops vector.
(fini_reassoc): Destroy bitwise_ops vector.
(execute_reassoc): Add call for repropagate_bitwise function.

ChangeLog gcc/testsuite

2011-09-21  Kai Tietz  <ktietz@redhat.com>

* gcc.dg/tree-ssa/reassoc-26.c: New test.
* gcc.dg/tree-ssa/reassoc-27.c: New test.
* gcc.dg/tree-ssa/reassoc-28.c: New test.
* gcc.dg/tree-ssa/reassoc-29.c: New test.
* gcc.dg/tree-ssa/reassoc-30.c: New test.
* gcc.dg/tree-ssa/reassoc-31.c: New test.
* gcc.dg/tree-ssa/reassoc-32.c: New test.
* gcc.dg/tree-ssa/reassoc-33.c: New test.
* gcc.dg/tree-ssa/reassoc-34.c: New test.
* gcc.dg/tree-ssa/reassoc-35.c: New test.

Bootstrapped and regression tested for all languages (including Ada
and Obj-C++) on host x86_64-pc-linux-gnu.
Ok for apply?

Regards,
Kai

## Patch

Index: gcc/gcc/tree-ssa-reassoc.c
===================================================================
--- gcc.orig/gcc/tree-ssa-reassoc.c
+++ gcc/gcc/tree-ssa-reassoc.c
@@ -43,6 +43,10 @@  along with GCC; see the file COPYING3.
#include "target.h"
#include "params.h"

+/* Forwarders.  */
+static gimple build_and_add_sum (tree, tree, tree, enum tree_code);
+static void remove_visited_stmt_chain (tree);
+
/*  This is a simple global reassociation pass.  It is, in part, based
on the LLVM pass of the same name (They do some things more/less
than we do, in different orders, etc).
@@ -50,7 +54,9 @@  along with GCC; see the file COPYING3.
It consists of five steps:

1. Breaking up subtract operations into addition + negate, where
-    it would promote the reassociation of adds.
+    it would promote the reassociation of adds.  Additionally breaking
+    up combined expression made out of boolean-typed bitwise expressions
+    for improving simplification.

2. Left linearization of the expression trees, so that (A+B)+(C+D)
becomes (((A+B)+C)+D), which is easier for us to rewrite later.
@@ -194,7 +200,9 @@  static struct pointer_map_t *operand_ran

/* Forward decls.  */
static long get_rank (tree);
-
+static void push_bitwise_op (tree);
+static void remove_bitwise_op (tree);
+static void operate_bitwise_stmt (gimple, enum tree_code);

/* Bias amount for loop-carried phis.  We want this to be larger than
the depth of any reassociation tree we can see, but not larger than
@@ -556,6 +564,385 @@  get_unary_op (tree name, enum tree_code
return NULL_TREE;
}

+/* Create a temorary register expression with type TYPE, tree code CODE, and
+   operands OP1 and OP2.  If REF_DEF is a valid gimple statement, we use its
+   location for new generated temporary.
+   Function returns left-hand-side of new generated temporary register.  */
+static tree
+make_new_tmp_statement (tree type, enum tree_code code, tree op1, tree op2,
+			gimple ref_def)
+{
+  gimple sum;
+  tree tmpvar = create_tmp_reg (type, NULL);
+  sum = build_and_add_sum (tmpvar, op1, op2, code);
+  if (ref_def)
+    gimple_set_location (sum, gimple_location (ref_def));
+  return gimple_get_lhs (sum);
+}
+
+/* Perfrom on tree LHS with optional definition statement EPXR
+   a logic-not operation.  TYPE is of kind boolean with a 1-bit
+   precision.  */
+static tree
+expand_not_bitwise_binary (tree type, tree lhs, gimple expr)
+{
+  enum tree_code code = ERROR_MARK;
+  tree op1 = NULL, op2 = NULL;
+  gimple s1 = NULL, s2 = NULL;
+
+  if (TREE_CODE (lhs) == INTEGER_CST)
+    return fold_build1 (BIT_NOT_EXPR, type, lhs);
+
+  if (expr && is_gimple_assign (expr))
+    code = gimple_assign_rhs_code (expr);
+
+  /* If statement lhs isn't a single-use statement,
+     we don't want to modify it. So we can do only default-case
+     operation for it.  */
+  if (code != ERROR_MARK && !has_single_use (lhs))
+    code = ERROR_MARK;
+
+  if (TREE_CODE_CLASS (code) == tcc_comparison
+      || code == BIT_XOR_EXPR
+      || code == BIT_AND_EXPR
+      || code == BIT_IOR_EXPR)
+    {
+      op1 = gimple_assign_rhs1 (expr);
+      op2 = gimple_assign_rhs2 (expr);
+    }
+  else if (code == BIT_NOT_EXPR)
+    op1 = gimple_assign_rhs1 (expr);
+  else
+    return make_new_tmp_statement (TREE_TYPE (lhs), BIT_NOT_EXPR,
lhs, NULL_TREE, expr);
+
+  /* ~(~X) -> X.  */
+  if (code == BIT_NOT_EXPR)
+    return op1;
+
+  /* Invert comparison if possible, otherwise fall through to
+     default case.  */
+  else if (TREE_CODE_CLASS (code) == tcc_comparison)
+    {
+      enum tree_code ncode;
+      tree op1type = TREE_TYPE (op1);
+
+      ncode = invert_tree_comparison (code,
+				      HONOR_NANS (TYPE_MODE (op1type)));
+      if (ncode != ERROR_MARK)
+	return make_new_tmp_statement (type, ncode, op1, op2, expr);
+    }
+  /* ~(A & B) -> ~A | ~B.  */
+  else if (code == BIT_AND_EXPR)
+    {
+      if (TREE_CODE (op1) != SSA_NAME
+         || !(s1 = SSA_NAME_DEF_STMT (op1))
+         || !is_gimple_assign (s1)
+         || !has_single_use (op1))
+	s1 = NULL;
+      if (TREE_CODE (op2) != SSA_NAME
+         || !(s2 = SSA_NAME_DEF_STMT (op2))
+         || !is_gimple_assign (s2)
+         || !has_single_use (op2))
+	s2 = NULL;
+
+      /* We have to do inversion in one step to avoid looping.  */
+      op1 = expand_not_bitwise_binary (type, op1, s1);
+      op2 = expand_not_bitwise_binary (type, op2, s2);
+      if (TREE_CODE (op2) == INTEGER_CST && integer_zerop (op2))
+        {
+	  remove_visited_stmt_chain (op2);
+	  return op1;
+	}
+      else if (TREE_CODE (op2) == INTEGER_CST && integer_all_onesp (op2))
+        {
+	  remove_visited_stmt_chain (op1);
+	  return op2;
+	}
+      return make_new_tmp_statement (type, BIT_IOR_EXPR, op1, op2, expr);
+    }
+  /* ~(A | B) -> ~A & ~B.  */
+  else if (code == BIT_IOR_EXPR)
+    {
+      if (TREE_CODE (op1) != SSA_NAME
+         || !(s1 = SSA_NAME_DEF_STMT (op1))
+         || !is_gimple_assign (s1)
+         || !has_single_use (op1))
+	s1 = NULL;
+      if (TREE_CODE (op2) != SSA_NAME
+         || !(s2 = SSA_NAME_DEF_STMT (op2))
+         || !is_gimple_assign (s2)
+         || !has_single_use (op2))
+	s2 = NULL;
+      op1 = expand_not_bitwise_binary (type, op1, s1);
+      op2 = expand_not_bitwise_binary (type, op2, s2);
+      if (TREE_CODE (op2) == INTEGER_CST && integer_zerop (op2))
+        {
+	  remove_visited_stmt_chain (op1);
+	  return op2;
+	}
+      else if (TREE_CODE (op2) == INTEGER_CST && integer_all_onesp (op2))
+        {
+	  remove_visited_stmt_chain (op2);
+	  return op1;
+	}
+      return make_new_tmp_statement (type, BIT_AND_EXPR, op1, op2, expr);
+    }
+  /* ~(A ^ B) -> ~A ^ B.  Handle here special cases for B being
+     an integer constant, or being a logical-not.  */
+  else if (code == BIT_XOR_EXPR)
+    {
+      if (TREE_CODE (op1) != SSA_NAME
+         || !(s1 = SSA_NAME_DEF_STMT (op1))
+         || !is_gimple_assign (s1)
+         || !has_single_use (op1))
+	s1 = NULL;
+      if (TREE_CODE (op2) != SSA_NAME
+         || !(s2 = SSA_NAME_DEF_STMT (op2))
+         || !is_gimple_assign (s2)
+         || !has_single_use (op2))
+	s2 = NULL;
+      if (TREE_CODE (op2) != INTEGER_CST
+	  && (!s2 || gimple_assign_rhs_code (s2) != BIT_NOT_EXPR))
+        op1 = expand_not_bitwise_binary (type, op1, s1);
+      else
+        op2 = expand_not_bitwise_binary (type, op2, s2);
+
+      if (TREE_CODE (op2) == INTEGER_CST && integer_zerop (op2))
+        {
+	  remove_visited_stmt_chain (op2);
+	  return op1;
+	}
+
+      if (TREE_CODE (op2) == INTEGER_CST && integer_all_onesp (op2))
+        {
+	  remove_visited_stmt_chain (op2);
+	  return make_new_tmp_statement (type, BIT_NOT_EXPR, op1, NULL, expr);
+	}
+      return make_new_tmp_statement (type, BIT_XOR_EXPR, op1, op2, expr);
+    }
+
+  if (!types_compatible_p (type, TREE_TYPE (lhs)))
+    abort ();
+
+  /* Default case lhs -> ~lhs  */
+  return make_new_tmp_statement (TREE_TYPE (lhs), BIT_NOT_EXPR, lhs,
+				 NULL_TREE, expr);
+}
+
+/* Helper routine to expand X CODE 0.
+   Cases are
+    (X | Y) == 0 to (X == 0) & (Y == 0)
+    (X | Y) != 0 to (X != 0) | (Y != 0).
+    (X cmp Y) == 0 to (X cmp' Y) with cmp'=invert of cmp.
+    (X cmp Y) != 0 to (X cmp Y).
+
+   The CODE variable can be either NE_EXPR, or EQ_EXPR.  It indicates
+   what expansion is performed.  */
+static tree
+expand_cmp_ior (tree op, tree type, enum tree_code code)
+{
+  tree op1, op2;
+  gimple s = NULL;
+  enum tree_code hcode;
+
+  if (TREE_CODE (op) == INTEGER_CST)
+    {
+      if (code == EQ_EXPR)
+        return fold_convert (type, (integer_zerop (op) ? integer_one_node
+        						: integer_zero_node));
+      return fold_convert (type, (!integer_zerop (op) ? integer_one_node
+						      : integer_zero_node));
+    }
+  if (TREE_CODE (op) != SSA_NAME
+      || !(s = SSA_NAME_DEF_STMT (op))
+      || !is_gimple_assign (s)
+      || !has_single_use (op))
+    return make_new_tmp_statement (type, code, op,
+				   build_zero_cst (TREE_TYPE (op)), s);
+  hcode = gimple_assign_rhs_code (s);
+
+  if (TREE_CODE_CLASS (hcode) != tcc_comparison
+      && hcode != BIT_IOR_EXPR)
+    return make_new_tmp_statement (type, code, op,
+				   build_zero_cst (TREE_TYPE (op)), s);
+
+  op1 = gimple_assign_rhs1 (s);
+  op2 = gimple_assign_rhs2 (s);
+
+  if (TREE_CODE_CLASS (hcode) == tcc_comparison)
+    {
+      tree op1type = TREE_TYPE (op1);
+
+      if (code == EQ_EXPR)
+        {
+	  enum tree_code ncode;
+	  ncode = invert_tree_comparison (hcode,
+					  HONOR_NANS (TYPE_MODE (op1type)));
+	  if (ncode != ERROR_MARK)
+	    return make_new_tmp_statement (type, ncode, op1, op2, s);
+        }
+      else
+        return make_new_tmp_statement (type, hcode, op1, op2, s);
+    }
+  if (hcode == BIT_IOR_EXPR)
+    {
+      op1 = expand_cmp_ior (op1, type, code);
+      op2 = expand_cmp_ior (op2, type, code);
+      return make_new_tmp_statement (type, (code == EQ_EXPR ? BIT_AND_EXPR
+      							    : BIT_IOR_EXPR),
+				     op1, op2, s);
+    }
+  return make_new_tmp_statement (type, code, op,
+				 build_zero_cst (TREE_TYPE (op)), s);
+}
+
+/* Break up statement STMT if it is a combined expressions made out of
+   bitwise operations.  Handle expansion of (A | B) !=/== 0, and ~(A op B).  */
+static bool
+break_up_bitwise_combined_stmt (gimple stmt)
+{
+  tree op1, op2, old_op;
+  gimple op1_def, op2_def;
+  enum tree_code code = gimple_assign_rhs_code (stmt);
+  tree type = TREE_TYPE (gimple_assign_lhs (stmt));
+  gimple_stmt_iterator gsi;
+
+  op1 = gimple_assign_rhs1 (stmt);
+  old_op = op1;
+  op2 = NULL_TREE;
+
+  if (code == EQ_EXPR || code == NE_EXPR)
+    op2 = gimple_assign_rhs2 (stmt);
+
+  /* Check that left-hand operand is a gimple-assignment
+     and has single use.  */
+  if ((code != BIT_NOT_EXPR
+       && code != EQ_EXPR && code != NE_EXPR)
+      || TREE_CODE (op1) != SSA_NAME)
+    return false;
+  op1_def = SSA_NAME_DEF_STMT (op1);
+  if (!op1_def
+      || !is_gimple_assign (op1_def)
+      || !has_single_use (op1))
+    return false;
+
+  if (code == NE_EXPR || code == EQ_EXPR)
+    {
+      tree inner_op1, inner_op2;
+
+      /* Check that operands have integral type and
+         see if it has as second argument a constant zero valued
+         operand.  */
+      if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))
+          || TREE_CODE (op2) != INTEGER_CST
+	  || !integer_zerop (op2))
+	return false;
+
+      /* Check for pattern X | Y == 0 and X | Y != 0  */
+      if (gimple_assign_rhs_code (op1_def) != BIT_IOR_EXPR)
+	return false;
+
+      inner_op1 = gimple_assign_rhs1 (op1_def);
+      inner_op2 = gimple_assign_rhs2 (op1_def);
+
+      /* Expand (X | Y) == 0 -> (X == 0) & (Y == 0)
+         and (X | Y) != 0 -> (X != 0) | (Y != 0)  */
+
+      op1 = expand_cmp_ior (inner_op1, type, code);
+      op2 = expand_cmp_ior (inner_op2, type, code);
+
+      remove_bitwise_op (old_op);
+
+      gsi = gsi_for_stmt (stmt);
+      gimple_assign_set_rhs_with_ops (&gsi, (code == NE_EXPR ? BIT_IOR_EXPR
+							     : BIT_AND_EXPR),
+				      op1, op2);
+      update_stmt (gsi_stmt (gsi));
+      remove_visited_stmt_chain (old_op);
+      push_bitwise_op (gimple_assign_lhs (stmt));
+      return true;
+    }
+  /* Handle expansion for expansion of ~X.  */
+  else if (code == BIT_NOT_EXPR)
+    {
+      enum tree_code inner_code = gimple_assign_rhs_code (op1_def);
+
+      if (inner_code == BIT_NOT_EXPR)
+        {
+	  op1 = gimple_assign_rhs1 (op1_def);
+	  gsi = gsi_for_stmt (stmt);
+	  gimple_assign_set_rhs_from_tree (&gsi, op1);
+	  update_stmt (gsi_stmt (gsi));
+	  remove_visited_stmt_chain (old_op);
+	  push_bitwise_op (gimple_assign_lhs (stmt));
+	  return true;
+	}
+      else if (TREE_CODE_CLASS (inner_code) == tcc_comparison)
+        {
+	  enum tree_code ncode;
+	  tree op1type;
+
+	  op1 = gimple_assign_rhs1 (op1_def);
+	  op2 = gimple_assign_rhs2 (op1_def);
+	  op1type = TREE_TYPE (op1);
+	  ncode = invert_tree_comparison (inner_code,
+					  HONOR_NANS (TYPE_MODE (op1type)));
+	  if (ncode == ERROR_MARK)
+	    return false;
+	  gsi = gsi_for_stmt (stmt);
+	  gimple_assign_set_rhs_with_ops (&gsi, ncode, op1, op2);
+	  update_stmt (gsi_stmt (gsi));
+	  remove_visited_stmt_chain (old_op);
+	  return true;
+	}
+      if (inner_code != BIT_AND_EXPR && inner_code != BIT_IOR_EXPR
+          && inner_code != BIT_XOR_EXPR)
+	return false;
+
+      op1 = gimple_assign_rhs1 (op1_def);
+      op2 = gimple_assign_rhs2 (op1_def);
+
+      op1_def = op2_def = NULL;
+      if (TREE_CODE (op1) != SSA_NAME
+	|| (op1_def = SSA_NAME_DEF_STMT (op1)) == NULL
+	|| !is_gimple_assign (op1_def))
+	op1_def = NULL;
+      if (TREE_CODE (op2) != SSA_NAME
+	|| (op2_def = SSA_NAME_DEF_STMT (op2)) == NULL
+	|| !is_gimple_assign (op2_def))
+	op2_def = NULL;
+      /* Transform as best representation either from
+         ~(X ^ Y) to ~X ^ Y, or from ~(X ^ Y) toX ^ Y.  */
+      if (inner_code == BIT_XOR_EXPR)
+	{
+          if (TREE_CODE (op2) != INTEGER_CST
+	      && (!op2_def || !is_gimple_assign (op2_def)
+	          || !has_single_use (op2)
+	          || gimple_assign_rhs_code (op2_def) != BIT_NOT_EXPR))
+            op1 = expand_not_bitwise_binary (type, op1, op1_def);
+          else
+            op2 = expand_not_bitwise_binary (type, op2, op2_def);
+	}
+      /* Transform ~(X | Y) -> ~X & Y, or ~(X & Y) -> ~X | ~Y.  */
+      else
+	{
+          op1 = expand_not_bitwise_binary (type, op1, op1_def);
+          op2 = expand_not_bitwise_binary (type, op2, op2_def);
+	  inner_code = (inner_code == BIT_AND_EXPR ? BIT_IOR_EXPR
+						   : BIT_AND_EXPR);
+	}
+      gsi = gsi_for_stmt (stmt);
+      gimple_assign_set_rhs_with_ops (&gsi, inner_code, op1, op2);
+      update_stmt (gsi_stmt (gsi));
+      remove_visited_stmt_chain (old_op);
+      push_bitwise_op (gimple_assign_lhs (stmt));
+      return true;
+    }
+
+  return false;
+}
+
/* If CURR and LAST are a pair of ops that OPCODE allows us to
eliminate through equivalences, do so, remove them from OPS, and
return true.  Otherwise, return false.  */
@@ -632,6 +1019,7 @@  eliminate_duplicate_pair (enum tree_code
}

static VEC(tree, heap) *plus_negates;
+static VEC(tree, heap) *bitwise_ops;

/* If OPCODE is PLUS_EXPR, CURR->OP is a negate expression or a bitwise not
expression, look in OPS for a corresponding positive operation to cancel
@@ -1017,8 +1405,8 @@  zero_one_operation (tree *def, enum tree
while (1);
}

-/* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for
-   the result.  Places the statement after the definition of either
+/* Builds one statement performing OP1 OPCODE OP2, OPCODE op1 using TMPVAR
+   for the result.  Places the statement after the definition of either
OP1 or OP2.  Returns the new statement.  */

static gimple
@@ -1037,7 +1425,7 @@  build_and_add_sum (tree tmpvar, tree op1
/* Find an insertion place and insert.  */
if (TREE_CODE (op1) == SSA_NAME)
op1def = SSA_NAME_DEF_STMT (op1);
-  if (TREE_CODE (op2) == SSA_NAME)
+  if (op2 && TREE_CODE (op2) == SSA_NAME)
op2def = SSA_NAME_DEF_STMT (op2);
if ((!op1def || gimple_nop_p (op1def))
&& (!op2def || gimple_nop_p (op2def)))
@@ -2204,6 +2592,758 @@  linearize_expr_tree (VEC(operand_entry_t
}

+/* This function seeks the root assignment-statement of LHS, which
+   is a bitwise-wise expression.  It additional don't walk over
+   none-single-use elements.  */
+static tree
+get_bitwise_single_use_root (tree lhs)
+{
+  gimple user;
+  if (TREE_CODE (lhs) != SSA_NAME
+      || !SSA_NAME_DEF_STMT (lhs)
+      || !is_gimple_assign (SSA_NAME_DEF_STMT (lhs))
+      || !has_single_use (lhs))
+    return lhs;
+  user = get_single_immediate_use (lhs);
+  if (!user)
+    return lhs;
+  do
+    {
+      if (!is_gimple_assign (user))
+        return lhs;
+      switch (gimple_assign_rhs_code (user))
+        {
+	case BIT_NOT_EXPR:
+	case BIT_XOR_EXPR:
+	case BIT_AND_EXPR:
+	case BIT_IOR_EXPR:
+	  break;
+	default:
+	  return lhs;
+	}
+      lhs = gimple_assign_lhs (user);
+    }
+  while ((user = get_single_immediate_use (lhs)) != NULL);
+
+  return lhs;
+}
+
+/* Saves LHS on vector BITWISE_OPS, if it isn't
+   already stored in vector BITWISE_OPS.  */
+static void
+push_bitwise_op (tree lhs)
+{
+  gimple user;
+
+  /* Check if we are on a root-element. */
+  if (has_single_use (lhs)
+      && (user = get_single_immediate_use (lhs)) != NULL
+      && is_gimple_assign (user))
+    {
+      enum tree_code ucode = gimple_assign_rhs_code (user);
+      if (ucode == BIT_AND_EXPR
+	  || ucode == BIT_IOR_EXPR
+	  || ucode == BIT_XOR_EXPR
+	  || ucode == BIT_NOT_EXPR)
+	return;
+    }
+  /* Find root element.  */
+  lhs = get_bitwise_single_use_root (lhs);
+
+  /* Check that LHS is unique in vector BITWISE_OPS.  */
+  if (bitwise_ops != NULL)
+    {
+      unsigned int i = 0;
+      tree x;
+
+      FOR_EACH_VEC_ELT (tree, bitwise_ops, i, x)
+        {
+	  if (x == lhs)
+	    return;
+	}
+    }
+
+  VEC_safe_push (tree, heap, bitwise_ops, lhs);
+}
+
+/* Function removes element LHS from vector
+   BITWISE_OPS.  */
+static void
+remove_bitwise_op (tree lhs)
+{
+  /* Check that LHS is unique in vector BITWISE_OPS.  */
+  if (bitwise_ops != NULL)
+    {
+      unsigned int i = 0;
+      tree x;
+
+      FOR_EACH_VEC_ELT (tree, bitwise_ops, i, x)
+        {
+	  if (x == lhs)
+	    {
+	      VEC_ordered_remove (tree, bitwise_ops, i);
+	      return;
+	    }
+	}
+    }
+}
+
+/* This routine returns TRUE, if LHS is assignment with
+   tree-code BIT_NOT_EXPR.  Otherwise it returns FALSE.  */
+
+static bool
+is_bitwise_not (tree lhs)
+{
+  gimple stmt;
+
+  if (TREE_CODE (lhs) != SSA_NAME)
+    return false;
+  stmt = SSA_NAME_DEF_STMT (lhs);
+  if (!stmt
+      || !is_gimple_assign (stmt))
+    return false;
+
+  return gimple_assign_rhs_code (stmt) == BIT_NOT_EXPR;
+}
+
+/* Helper function to sort statements starting from STMT with tree-code
+   CODE into ORG for none-not-expressions, into NOT for not-expressions,
+   into VCMP Y == 0 for CODE equal to bitwise-or, into VCMP Y != 0 for
+   CODE eual to bitwise-and, and into CST for integral constants. */
+static void
+walk_bitwise_stmt_elems (gimple stmt, enum tree_code code,
+			 VEC(tree, heap) **vcst,
+			 VEC(tree, heap) **vnot,
+			 VEC(tree, heap) **vcmp_zero,
+			 VEC(tree, heap) **vcmp_m1,
+			 VEC(tree, heap) **vexpr)
+{
+  gimple s;
+  tree l;
+
+  l = gimple_assign_rhs1 (stmt);
+  if (TREE_CODE (l) == INTEGER_CST)
+    VEC_safe_push (tree, heap, *vcst, l);
+  else if (TREE_CODE (l) != SSA_NAME
+	   || (s = SSA_NAME_DEF_STMT (l)) == NULL
+	   || !is_gimple_assign (s)
+	   || !has_single_use (l))
+    VEC_safe_push (tree, heap, *vexpr, l);
+  else if (gimple_assign_rhs_code (s) == code)
+    walk_bitwise_stmt_elems (s, code, vcst, vnot, vcmp_zero, vcmp_m1, vexpr);
+  else if (is_bitwise_not (l))
+    VEC_safe_push (tree, heap, *vnot, l);
+  /* (A == 0) & (B == 0) -> (A | B) == 0
+     (A != 0) | (B != 0) -> (A | B) != 0.  */
+  else if (((code == BIT_AND_EXPR
+  	     && gimple_assign_rhs_code (s) == EQ_EXPR)
+  	    || (code == BIT_IOR_EXPR
+  	        && gimple_assign_rhs_code (s) == NE_EXPR))
+  	   && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (s)))
+  	   && TREE_CODE (gimple_assign_rhs2 (s)) == INTEGER_CST
+  	   && integer_zerop (gimple_assign_rhs2 (s)))
+    VEC_safe_push (tree, heap, *vcmp_zero, l);
+  /* (A == -1) & (B == -1) -> (A & B) == -1
+     (A != -1) | (B != -1) -> (A & B) != -1  */
+  else if (((code == BIT_AND_EXPR
+  	     && gimple_assign_rhs_code (s) == EQ_EXPR)
+  	    || (code == BIT_IOR_EXPR
+  	        && gimple_assign_rhs_code (s) == NE_EXPR))
+  	   && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (s)))
+  	   && TREE_CODE (gimple_assign_rhs2 (s)) == INTEGER_CST
+  	   && integer_all_onesp (gimple_assign_rhs2 (s)))
+    VEC_safe_push (tree, heap, *vcmp_m1, l);
+  else
+    {
+      switch (gimple_assign_rhs_code (s))
+	{
+	case BIT_IOR_EXPR:
+	case BIT_AND_EXPR:
+	case BIT_XOR_EXPR:
+	  operate_bitwise_stmt (s, gimple_assign_rhs_code (s));
+	  break;
+	default:
+	  break;
+	}
+
+      VEC_safe_push (tree, heap, *vexpr, l);
+    }
+
+  l = gimple_assign_rhs2 (stmt);
+
+  if (TREE_CODE (l) == INTEGER_CST)
+    {
+      VEC_safe_push (tree, heap, *vcst, l);
+      return;
+    }
+  if (TREE_CODE (l) != SSA_NAME
+      || (s = SSA_NAME_DEF_STMT (l)) == NULL
+      || !is_gimple_assign (s)
+      || !has_single_use (l))
+    VEC_safe_push (tree, heap, *vexpr, l);
+  else if (gimple_assign_rhs_code (s) == code)
+    walk_bitwise_stmt_elems (s, code, vcst, vnot, vcmp_zero, vcmp_m1, vexpr);
+  else if (is_bitwise_not (l))
+    VEC_safe_push (tree, heap, *vnot, l);
+  /* (A == 0) & (B == 0) -> (A | B) == 0
+     (A != 0) | (B != 0) -> (A | B) != 0.  */
+  else if (((code == BIT_AND_EXPR
+  	     && gimple_assign_rhs_code (s) == EQ_EXPR)
+  	    || (code == BIT_IOR_EXPR
+  	        && gimple_assign_rhs_code (s) == NE_EXPR))
+  	   && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (s)))
+  	   && TREE_CODE (gimple_assign_rhs2 (s)) == INTEGER_CST
+  	   && integer_zerop (gimple_assign_rhs2 (s)))
+    VEC_safe_push (tree, heap, *vcmp_zero, l);
+  /* (A == -1) & (B == -1) -> (A & B) == -1
+     (A != -1) | (B != -1) -> (A & B) != -1  */
+  else if (((code == BIT_AND_EXPR
+  	     && gimple_assign_rhs_code (s) == EQ_EXPR)
+  	    || (code == BIT_IOR_EXPR
+  	        && gimple_assign_rhs_code (s) == NE_EXPR))
+  	   && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (s)))
+  	   && TREE_CODE (gimple_assign_rhs2 (s)) == INTEGER_CST
+  	   && integer_all_onesp (gimple_assign_rhs2 (s)))
+    VEC_safe_push (tree, heap, *vcmp_m1, l);
+  else
+    {
+      switch (gimple_assign_rhs_code (s))
+	{
+	case BIT_IOR_EXPR:
+	case BIT_AND_EXPR:
+	case BIT_XOR_EXPR:
+	  operate_bitwise_stmt (s, gimple_assign_rhs_code (s));
+	  break;
+	default:
+	  break;
+	}
+
+      VEC_safe_push (tree, heap, *vexpr, l);
+    }
+}
+
+/* Helper function to rebuild a binary tree of CODE elements
+   from vector VEC.
+   If LASTP is NULL, then all elements
+   are combined and result is returned, otherwise the last
+   element of vector VEC is stored in LASTP and all - but the last -
+   elements are merged and returned.
+   Note: for vector with just one element, this element is returned
+   and LASTP is set to NULL, if provided.
+   If INNER_LEFT is true, the RHS1 operand of VEC element
+   is used, otherwise the VEC element itself is used.  */
+static tree
+rebuild_vector_tree (VEC(tree, heap) *vec,
+		     enum tree_code code, tree *lastp, bool inner_left)
+{
+  gimple s;
+  unsigned int i = 0;
+  tree r = NULL_TREE, x, r2 = NULL_TREE;
+
+  FOR_EACH_VEC_ELT (tree, vec, i, x)
+    {
+      s = SSA_NAME_DEF_STMT (x);
+
+      if (inner_left)
+	x = gimple_assign_rhs1 (s);
+      if (!r)
+        r = x;
+      else if (!r2)
+        r2 = x;
+      else
+        {
+	  r = make_new_tmp_statement (TREE_TYPE (r), code, r, r2, s);
+	  r2 = x;
+	}
+    }
+  if (lastp)
+    *lastp = r2;
+  else if (r && r2)
+    {
+      s = SSA_NAME_DEF_STMT (r);
+      r = make_new_tmp_statement (TREE_TYPE (r), code, r, r2, s);
+    }
+  return r;
+}
+
+/* Sink not-expression out of xor-expression-sequences TCST, NOT, and ORG
+   generated from STMT.
+   Returns TRUE, if statement STMT was modified, otherwise FALSE.  */
+static bool
+operate_bitwise_xor_stmt (gimple stmt, tree tcst, VEC(tree, heap) *vnot,
+			  VEC(tree, heap) *vexpr)
+{
+  gimple_stmt_iterator gsi;
+  unsigned int i = VEC_length (tree, vnot);
+  tree l = NULL_TREE, r = NULL_TREE;
+  bool inv = false;
+
+  /* If the amount of not-expressions is odd, then we have two cases:
+     a) we have a constant, so we can sink one not into integeral constant
+        as ~X ^ CST -> X ^ CST' with CST' = ~CST.
+     b) we need to add to the hole statment a bitwise-not expression.  */
+  if ((i & 1) != 0)
+    {
+      if (tcst)
+        {
+	  tcst = fold_build1 (BIT_NOT_EXPR, TREE_TYPE (tcst), tcst);
+	  /* See if we can eleminate constant.  */
+	  if (integer_zerop (tcst))
+	    tcst = NULL;
+	}
+      else
+        inv = true;
+    }
+
+  if (vnot && vexpr)
+    {
+      l = rebuild_vector_tree (vnot, BIT_XOR_EXPR, NULL, true);
+      r = rebuild_vector_tree (vexpr, BIT_XOR_EXPR, NULL, false);
+      if (tcst)
+        {
+	  l = make_new_tmp_statement (TREE_TYPE (l), BIT_XOR_EXPR, l, r, stmt);
+	  r = tcst;
+	}
+    }
+  else if (vnot)
+    {
+      l = rebuild_vector_tree (vnot, BIT_XOR_EXPR, &r, true);
+      if (tcst)
+        {
+	  if (!r)
+	    r = tcst;
+	  else
+	    {
+	      l = make_new_tmp_statement (TREE_TYPE (l), BIT_XOR_EXPR, l, r, stmt);
+	      r = tcst;
+	    }
+	}
+    }
+  else if (tcst)
+    {
+      l = rebuild_vector_tree (vexpr, BIT_XOR_EXPR, NULL, false);
+      if (l)
+        r = tcst;
+      else
+        {
+	  l = tcst;
+	  r = NULL_TREE;
+	}
+    }
+  else
+    l = rebuild_vector_tree (vexpr, BIT_XOR_EXPR, &r, false);
+
+  if (inv)
+    {
+      if (r)
+        l = make_new_tmp_statement (TREE_TYPE (l), BIT_XOR_EXPR, l, r, stmt);
+      gsi = gsi_for_stmt (stmt);
+      gimple_assign_set_rhs_with_ops (&gsi, BIT_NOT_EXPR, l, NULL_TREE);
+    }
+  else
+    {
+      gsi = gsi_for_stmt (stmt);
+      if (r)
+        gimple_assign_set_rhs_with_ops (&gsi, BIT_XOR_EXPR, l, r);
+      else
+        gimple_assign_set_rhs_from_tree (&gsi, l);
+    }
+  update_stmt (gsi_stmt (gsi));;
+  return true;
+}
+
+/* Helper function to merge:compares
+   If IS_IOR is TRUE. then merge VCMP elements
+   - (X != 0) | (Y != 0) -> (X | Y) != 0
+   - (X == 0) & (Y == 0) -> (X | Y) == 0.
+
+   If IS_IOR is FALSE. then merge VCMP elements
+   - (X != ~0) | (Y != ~0) -> (X & Y) != ~0
+   - (X == ~0) & (Y == ~0) -> (X & Y) == ~0.
+
+   CODE specifies the final compare expression code. It can be either
+   EQ_EXPR, or NE_EXPR.
+
+   If DESTSTMT is not NULL, then final compare instruction
+   gets assigned to it, otherwise an new temporary is used
+   and stored in VEXPR vector.
+
+   Special note:  We try to merge first elements of compatible
+   types, before doing final merge by casting up to widest type.  */
+static void
+merge_bitwise_compares (VEC(tree, heap) **vcmp, VEC(tree, heap) **vexpr,
+			enum tree_code code, gimple deststmt, bool is_ior)
+{
+  unsigned int i;
+  unsigned int len = VEC_length (tree, *vcmp);
+  tree l, r, x, cmp_type = NULL_TREE;
+  VEC(tree, heap) *vtmp = NULL;
+  enum tree_code cmp_code;
+
+  /* If we have just one compare-element, then simply
+     move it to ORG vector and return.  */
+  if (len <= 1)
+    {
+      FOR_EACH_VEC_ELT (tree, *vcmp, i, x)
+        {
+	  VEC_safe_push (tree, heap, *vexpr, x);
+	  VEC_ordered_remove (tree, *vcmp, i);
+	}
+
+      VEC_free (tree, heap, *vcmp);
+      *vcmp = NULL;
+      return;
+    }
+
+  /* First merge all elements with compatible type, and move
+     intermediate result into VTMP vector.  */
+  while (VEC_length (tree, *vcmp) > 0)
+    {
+      cmp_type = NULL_TREE;
+      l = NULL_TREE;
+      for (i = 0; VEC_iterate (tree, (*vcmp), (i), (x));)
+	{
+	  gimple s = SSA_NAME_DEF_STMT (x);
+	  r = gimple_assign_rhs1 (s);
+	  if (!l)
+	    {
+	      l = r;
+	      cmp_type = TREE_TYPE (x);
+	      VEC_ordered_remove (tree, *vcmp, i);
+	    }
+	  else if (types_compatible_p (TREE_TYPE (r), TREE_TYPE (l)))
+	    {
+	      l = make_new_tmp_statement (TREE_TYPE (l),
+					  (is_ior ? BIT_IOR_EXPR
+	  					  : BIT_AND_EXPR), l, r, s);
+	      VEC_ordered_remove (tree, *vcmp, i);
+	    }
+	  else
+	    ++i;
+	}
+      VEC_safe_push (tree, heap, vtmp, l);
+    }
+  VEC_free (tree, heap, *vcmp);
+  *vcmp = NULL;
+
+  /* Now do final merge of all elements in VTMP vector by casting to
+     wider-type.  */
+  l = NULL_TREE;
+  r = NULL_TREE;
+  FOR_EACH_VEC_ELT (tree, vtmp, i, x)
+    {
+      tree type;
+      type = TREE_TYPE (x);
+
+      /* If we handle (X & Y) ==/!= ~0 case, we need
+         to work on signed types.  */
+      if (!is_ior && TYPE_UNSIGNED (type) && VEC_length (vtmp) > 1)
+        {
+	  type = signed_type_for (type);
+	  x = make_new_tmp_statement (type, NOP_EXPR, x, NULL_TREE,
SSA_NAME_DEF_STMT (x));
+	}
+      if (!l)
+        {
+	  l = x;
+	  r = type;
+	}
+      else
+        {
+	  if (TYPE_PRECISION (r) < TYPE_PRECISION (type))
+	    {
+	      l = make_new_tmp_statement (type, NOP_EXPR, l, NULL_TREE,
SSA_NAME_DEF_STMT (x));
+	      r = type;
+	    }
+	  else if (TYPE_PRECISION (r) > TYPE_PRECISION (type)
+	           || !types_compatible_p (r, type))
+	    x = make_new_tmp_statement (r, NOP_EXPR, x, NULL_TREE,
SSA_NAME_DEF_STMT (x));
+	  l = make_new_tmp_statement (r, (is_ior ? BIT_IOR_EXPR
+						 : BIT_AND_EXPR),
+				      l, x, SSA_NAME_DEF_STMT (x));
+	}
+    }
+
+  /* Generate final L != 0, or L == 0 to statement.
+     a) (X == 0) & (Y == 0) -> (X | Y) == 0
+     b) (X != 0) | (Y != 0) -> (X | Y) != 0
+     c) (X == -1) & (Y == -1) -> (X & Y) == -1
+     d) (X != -1) | (Y != -1) -> (X & Y) != -1
+   */
+  cmp_code = (code == BIT_AND_EXPR ? EQ_EXPR : NE_EXPR);
+  if (!deststmt)
+    {
+      tree cst_val = build_zero_cst (TREE_TYPE (l));
+
+      if (!is_ior)
+        cst_val = fold_build1 (BIT_NOT_EXPR, TREE_TYPE (l), cst_val);
+      l = make_new_tmp_statement (cmp_type,
+				  cmp_code, l,
+				  cst_val,
+				  SSA_NAME_DEF_STMT (l));
+      VEC_safe_push (tree, heap, *vexpr, l);
+    }
+  else
+    {
+      gimple_stmt_iterator gsi;
+      tree cst_val = build_zero_cst (TREE_TYPE (l));
+
+      if (!is_ior)
+        cst_val = fold_build1 (BIT_NOT_EXPR, TREE_TYPE (l), cst_val);
+
+      gsi = gsi_for_stmt (deststmt);
+      gimple_assign_set_rhs_with_ops (&gsi, cmp_code, l,
+				      cst_val);
+      update_stmt (deststmt);
+    }
+  VEC_free (tree, heap, vtmp);
+}
+
+/* Sink bitwise-not expression out of bitwise-binary sequence for STMT.  The
+   tree-code of the statement-sequence CODE.
+   Following patterns are used for transformations:
+     ~X and ~Y -> ~(X or Y)
+     ~X or ~Y -> ~(X and Y)
+     ~X xor ~Y -> X xor Y
+     ~X xor Y -> ~(X xor Y)
+     ~X xor CST -> X xor CST' (with CST' = ~CST).
+     (X == 0) and (Y == 0) -> (X | Y) == 0, if X and Y have
+     integral types.
+     (X == -1) and (Y == -1) -> (X & Y) == -1, if X and Y have
+     integral types.
+     (X != 0) or (Y != 0) -> (X | Y) != 0, if X and Y have
+     integral types.
+     (X != -1) or (Y != -1) -> (X & Y) != -1, if X and Y have
+     integral types.
+
+   */
+static void
+operate_bitwise_stmt (gimple stmt, enum tree_code code)
+{
+  unsigned int i = 0;
+  tree x, tcst = NULL_TREE;
+  tree tnot = NULL_TREE, torg = NULL_TREE;
+  tree l, r;
+  gimple_stmt_iterator gsi;
+  VEC(tree, heap) *vcst = NULL;
+  VEC(tree, heap) *vnot = NULL;
+  VEC(tree, heap) *vcmp_zero = NULL;
+  VEC(tree, heap) *vcmp_m1 = NULL;
+  VEC(tree, heap) *vexpr = NULL;
+  enum tree_code icode;
+  bool do_repropagate = false;
+
+  if (gimple_assign_rhs_code (stmt) != code)
+    abort ();
+
+  walk_bitwise_stmt_elems (stmt, code, &vcst, &vnot,
+  			   &vcmp_zero, &vcmp_m1, &vexpr);
+
+  /* There are constants,  */
+  if (VEC_length (tree, vcst) > 1)
+    do_repropagate = true;
+  /* There are comparisons-to-zero,  */
+  else if (VEC_length (tree, vcmp_zero) > 1
+  	   || VEC_length (tree, vcmp_m1) > 1)
+    do_repropagate = true;
+  /* There are not-expressions,  */
+  else if (VEC_length (tree, vnot) > 1)
+    do_repropagate = true;
+  /* If we have (~X & CST), we convert to ~(X | CST') with CST'=~CST.
+     If we have (~X | CST), we convert to ~(X & CST') with CST'=~CST.  */
+  else if (VEC_length (tree, vnot) == 1
+           && VEC_length (tree, vexpr) == 0
+           && VEC_length (tree, vcmp_zero) == 0
+           && VEC_length (tree, vcmp_m1) == 0
+           && VEC_length (tree, vcst) >= 1)
+     do_repropagate = true;
+  /* For xor-expressions we do following conversion:
+     a) (~X ^ CST) -> X ^ CST'; with CST'=~CST.
+     b) (~X ^ Y) -> ~(X ^ Y).  */
+  else if (code == BIT_XOR_EXPR
+  	   && VEC_length (tree, vnot) == 1)
+    do_repropagate = true;
+
+  if (!do_repropagate)
+    {
+      VEC_free (tree, heap, vcst);
+      VEC_free (tree, heap, vnot);
+      VEC_free (tree, heap, vcmp_zero);
+      VEC_free (tree, heap, vcmp_m1);
+      VEC_free (tree, heap, vexpr);
+      return;
+    }
+
+  l = gimple_assign_rhs1 (stmt);
+  r = gimple_assign_rhs2 (stmt);
+
+  /* First combine integral constant bitwise operations.  */
+  FOR_EACH_VEC_ELT (tree, vcst, i, x)
+    {
+      if (!tcst)
+        tcst = x;
+      else
+        tcst = fold_build2 (code, TREE_TYPE (x), tcst, x);
+    }
+  VEC_free (tree, heap, vcst);
+  vcst = NULL;
+
+  /* Do we have only vcmp_zero elements, then directly assign result
+     of combine to final stmt.  */
+  if (!tcst && !vexpr && !vnot && !vcmp_m1)
+    {
+      merge_bitwise_compares (&vcmp_zero, &vexpr, code, stmt, true);
+      remove_visited_stmt_chain (l);
+      remove_visited_stmt_chain (r);
+      return;
+    }
+  /* Do we have only vcmp_m1 elements, then directly assign result
+     of combine to final stmt.  */
+  if (!tcst && !vexpr && !vnot && !vcmp_zero)
+    {
+      merge_bitwise_compares (&vcmp_m1, &vexpr, code, stmt, false);
+      remove_visited_stmt_chain (l);
+      remove_visited_stmt_chain (r);
+      return;
+    }
+
+  merge_bitwise_compares (&vcmp_zero, &vexpr, code, NULL, true);
+  merge_bitwise_compares (&vcmp_m1, &vexpr, code, NULL, false);
+
+  /* If we deal only with constants, assign
+     calculated constant.  */
+  if (tcst && !vnot && !vexpr)
+    {
+      gsi = gsi_for_stmt (stmt);
+      gimple_assign_set_rhs_from_tree (&gsi, tcst);
+      update_stmt (gsi_stmt (gsi));
+      remove_visited_stmt_chain (l);
+      remove_visited_stmt_chain (r);
+      return;
+    }
+
+  if (code == BIT_XOR_EXPR)
+    {
+      operate_bitwise_xor_stmt (stmt, tcst, vnot, vexpr);
+      remove_visited_stmt_chain (l);
+      remove_visited_stmt_chain (r);
+      VEC_free (tree, heap, vnot);
+      VEC_free (tree, heap, vexpr);
+      return;
+    }
+
+  /* See if we can eleminate constant.  */
+  if (tcst
+      && ((code == BIT_AND_EXPR && integer_all_onesp (tcst))
+          || (code == BIT_IOR_EXPR && integer_zerop (tcst))))
+    tcst = NULL;
+
+  /* Propagate bitwise and/or statements.  */
+
+  /* Inverse for binary and/or.  */
+  icode = (code == BIT_IOR_EXPR ? BIT_AND_EXPR : BIT_IOR_EXPR);
+
+  /* Build inverse tree for bitwise-not part.  */
+  if (VEC_length (tree, vnot) > 0)
+    {
+      tnot = rebuild_vector_tree (vnot, icode, NULL, true);
+      torg = rebuild_vector_tree (vexpr, code, NULL, false);
+      if (tnot && !tcst && !torg)
+        {
+	  gsi = gsi_for_stmt (stmt);
+	  gimple_assign_set_rhs_with_ops (&gsi, BIT_NOT_EXPR, tnot, NULL_TREE);
+	  update_stmt (gsi_stmt (gsi));
+	  remove_visited_stmt_chain (l);
+	  remove_visited_stmt_chain (r);
+	  VEC_free (tree, heap, vnot);
+	  VEC_free (tree, heap, vexpr);
+	  return;
+	}
+      if (!tnot)
+	abort ();
+      tnot = make_new_tmp_statement (TREE_TYPE (tnot), BIT_NOT_EXPR, tnot,
+				     NULL_TREE, SSA_NAME_DEF_STMT (tnot));
+      if (torg)
+	{
+	  if (!tcst)
+	    {
+	      gsi = gsi_for_stmt (stmt);
+	      gimple_assign_set_rhs_with_ops (&gsi, code, tnot, torg);
+	      update_stmt (gsi_stmt (gsi));
+	      remove_visited_stmt_chain (l);
+	      remove_visited_stmt_chain (r);
+	      VEC_free (tree, heap, vnot);
+	      VEC_free (tree, heap, vexpr);
+	      return;
+	    }
+	  tnot = make_new_tmp_statement (TREE_TYPE (tnot), code, tnot, torg,
+					 SSA_NAME_DEF_STMT (tnot));
+	}
+      gsi = gsi_for_stmt (stmt);
+      gimple_assign_set_rhs_with_ops (&gsi, code, tnot, tcst);
+      update_stmt (gsi_stmt (gsi));
+      remove_visited_stmt_chain (l);
+      remove_visited_stmt_chain (r);
+      VEC_free (tree, heap, vnot);
+      VEC_free (tree, heap, vexpr);
+      return;
+    }
+  if (!tcst)
+    torg = rebuild_vector_tree (vexpr, code, &tcst, false);
+  else
+    torg = rebuild_vector_tree (vexpr, code, NULL, false);
+  gsi = gsi_for_stmt (stmt);
+  if (tcst)
+    gimple_assign_set_rhs_with_ops (&gsi, code, torg, tcst);
+  else
+    gimple_assign_set_rhs_from_tree (&gsi, torg);
+  update_stmt (gsi_stmt (gsi));
+  remove_visited_stmt_chain (l);
+  remove_visited_stmt_chain (r);
+  VEC_free (tree, heap, vnot);
+  VEC_free (tree, heap, vexpr);
+}
+
+/* Repropagate bitwise-operations back to de-normalized from.
+   ~X op ~Y -> ~(X op' Y).  */
+static void
+repropagate_bitwise (void)
+{
+  unsigned int i = 0;
+  tree x;
+  gimple user;
+  enum tree_code ucode;
+
+  FOR_EACH_VEC_ELT (tree, bitwise_ops, i, x)
+    {
+      gimple stmt;
+      enum tree_code code;
+
+      if (TREE_CODE (x) != SSA_NAME)
+        continue;
+      stmt = SSA_NAME_DEF_STMT (x);
+      if (!stmt || !is_gimple_assign (stmt))
+        continue;
+      code = gimple_assign_rhs_code (stmt);
+      if (code == BIT_NOT_EXPR)
+        continue;
+      if (code != BIT_XOR_EXPR && code != BIT_IOR_EXPR
+          && code != BIT_AND_EXPR)
+        continue;
+      /* Check if we are on a root-element. */
+      if (has_single_use (x)
+          && (user = get_single_immediate_use (x)) != NULL
+          && is_gimple_assign (user))
+        {
+	  ucode = gimple_assign_rhs_code (user);
+	  if (ucode == BIT_AND_EXPR
+	      || ucode == BIT_IOR_EXPR
+	      || ucode == BIT_XOR_EXPR)
+	    continue;
+	}
+      operate_bitwise_stmt (stmt, code);
+    }
+}
+
/* Repropagate the negates back into subtracts, since no other pass
currently does it.  */

@@ -2320,29 +3460,65 @@  can_reassociate_p (tree op)
we want to break up k = t - q, but we won't until we've transformed q
= b - r, which won't be broken up until we transform b = c - d.

+   Break up comparison !=/== 0 operations of bitwise-or operations for
+   being able to optimize within combined conditions.
+   (A | B) != 0 -> (A != 0) || (B != 0)
+   (A | B) == 0 -> (A == 0) && (B != 0)
+
+   Break up logical-not expressions of bitwise boolean-typed and/or/xor
+   operations for being able to optimize wihin combined conditions.
+   ~(A | B) -> ~A | ~B
+   ~(A & B) -> ~A & ~B
+   ~(A ^ B) -> A ^ ~B (special case if B is a constant)
+
En passant, clear the GIMPLE visited flag on every statement.  */

static void
-break_up_subtract_bb (basic_block bb)
+break_up_expr_bb (basic_block bb)
{
gimple_stmt_iterator gsi;
basic_block son;

-  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
{
gimple stmt = gsi_stmt (gsi);
gimple_set_visited (stmt, false);
-
-      if (!is_gimple_assign (stmt)
-	  || !can_reassociate_p (gimple_assign_lhs (stmt)))
+      if (!is_gimple_assign (stmt))
+        {
+	  gsi_next (&gsi);
+	  continue;
+        }
+      if (break_up_bitwise_combined_stmt (stmt))
continue;

+      switch (gimple_assign_rhs_code (stmt))
+        {
+	case BIT_AND_EXPR:
+	case BIT_IOR_EXPR:
+	case BIT_XOR_EXPR:
+	  /* We might want to remember this statement
+	     for repropagation.  */
+	  push_bitwise_op (gimple_assign_lhs (stmt));
+	  break;
+	default:
+	  break;
+	}
+
+      if (!can_reassociate_p (gimple_assign_lhs (stmt)))
+	{
+	  gsi_next (&gsi);
+	  continue;
+	}
+
/* Look for simple gimple subtract operations.  */
if (gimple_assign_rhs_code (stmt) == MINUS_EXPR)
{
if (!can_reassociate_p (gimple_assign_rhs1 (stmt))
|| !can_reassociate_p (gimple_assign_rhs2 (stmt)))
-	    continue;
+	    {
+	      gsi_next (&gsi);
+	      continue;
+	    }

/* Check for a subtract used only in an addition.  If this
is the case, transform it into add of a negate for better
@@ -2354,11 +3530,12 @@  break_up_subtract_bb (basic_block bb)
else if (gimple_assign_rhs_code (stmt) == NEGATE_EXPR
&& can_reassociate_p (gimple_assign_rhs1 (stmt)))
VEC_safe_push (tree, heap, plus_negates, gimple_assign_lhs (stmt));
+      gsi_next (&gsi);
}
for (son = first_dom_son (CDI_DOMINATORS, bb);
son;
son = next_dom_son (CDI_DOMINATORS, son))
-    break_up_subtract_bb (son);
+    break_up_expr_bb (son);
}

/* Reassociate expressions in basic block BB and its post-dominator as
@@ -2524,7 +3701,8 @@  debug_ops_vector (VEC (operand_entry_t,
static void
do_reassoc (void)
{
-  break_up_subtract_bb (ENTRY_BLOCK_PTR);
+  break_up_expr_bb (ENTRY_BLOCK_PTR);
+
reassociate_bb (EXIT_BLOCK_PTR);
}

@@ -2581,6 +3759,7 @@  init_reassoc (void)
free (bbs);
calculate_dominance_info (CDI_POST_DOMINATORS);
plus_negates = NULL;
+  bitwise_ops = NULL;
}

/* Cleanup after the reassociation pass, and print stats if
@@ -2602,6 +3781,7 @@  fini_reassoc (void)
free_alloc_pool (operand_entry_pool);
free (bb_rank);
VEC_free (tree, heap, plus_negates);
+  VEC_free (tree, heap, bitwise_ops);
free_dominance_info (CDI_POST_DOMINATORS);
loop_optimizer_finalize ();
}
@@ -2615,6 +3795,7 @@  execute_reassoc (void)

do_reassoc ();
repropagate_negates ();
+  repropagate_bitwise ();

fini_reassoc ();
return 0;
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-30.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-30.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+  int r1 = a != 0 & c != 0 & b != 0;
+  int r2 = a == 0 | b != 0 | d == 0;
+  return (r1 != 0 & r2 == 0);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-31.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-31.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+  int r1 = a != 0 & c != 0 & b != 0;
+  int r2 = a == 0 | b != 0 | d == 0;
+  return (r1 == 0 | r2 != 0);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-26.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-26.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+  int r1 = (a | b | c) == 0;
+  int r2 = (a | d | c) != 0 | b == 0;
+  return (r1 == 0 | r2 != 0);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-27.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-27.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+  int r1 = a & ~c & b;
+  int r2 = ~a | b | ~d;
+  return (r1 & ~r2);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-28.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-28.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+  int r1 = a & ~c & b;
+  int r2 = ~a | b | ~d;
+  return (~r1 | r2);
+}
+
+/* { dg-final { scan-tree-dump-times "return -1" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-29.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-29.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+  int r1 = ~(a | b | c);
+  int r2 = (a | d | c) | ~b;
+  return (~r1 | r2);
+}
+
+/* { dg-final { scan-tree-dump-times "return -1" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+  return (~a & ~b) ^ (~c | ~d);
+}
+
+int foo2 (int a, int b, int c, int d)
+{
+  return (~a & ~b & ~c & ~d) ^ 0xff;
+}
+
+int foo3 (int a, int b, int c, int d)
+{
+  return ~a ^ b ^ ~c ^ ~d ^ 0xff;
+}
+
+int foo4 (int a, int b, int c, int d)
+{
+  return ~a ^ ~b ^ ~c ^ ~d;
+}
+
+/* { dg-final { scan-tree-dump-times " ~" 0 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+  int r = (a == -1) & (b == -1);
+  int q = (c == -1) & (d == -1);
+  return r & q;
+}
+
+int bar (int a, int b, int c, int d)
+{
+  int r = (a != -1) | (b != -1);
+  int q = (c != -1) | (d != -1);
+  return r | q;
+}
+
+/* { dg-final { scan-tree-dump-times " == -1" 2 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-34.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-34.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, char b, short c, long d)
+{
+  int r = (a == -1) & (b == -1);
+  int q = (c == -1) & (d == -1);
+  return r & q;
+}
+
+int bar (int a, char b, short c, long d)
+{
+  int r = (a != -1) | (b != -1);
+  int q = (c != -1) | (d != -1);
+  return r | q;
+}
+
+/* { dg-final { scan-tree-dump-times " == -1" 2 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-35.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-35.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, unsigned char b, unsigned short c, unsigned long d)
+{
+  unsigned char b1 = ~0;
+  unsigned short c1 = ~0;
+  unsigned long d1 = ~0;
+  int r = (a == -1) & (b == b1);
+  int q = (c == c1) & (d == d1);
+  return r & q;
+}
+
+int bar (int a, unsigned char b, unsigned short c, unsigned long d)
+{
+  unsigned char b1 = ~0;
+  unsigned short c1 = ~0;
+  unsigned long d1 = ~0;
+  int r = (a != -1) | (b != b1);
+  int q = (c != c1) | (d != d1);
+  return r | q;
+}
+
+/* { dg-final { scan-tree-dump-times " == -1" 2 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */