Patchwork [tree-optimization] : 2 of 2: Add denormalization of bitwise-operations to tree-ssa-reassoc pass

login
register
mail settings
Submitter Kai Tietz
Date Oct. 4, 2011, 12:17 p.m.
Message ID <CAEwic4baGd0r-Ax-8n9AYXxXCHdpFHaNtE7TcYOyRW+pdP-0OQ@mail.gmail.com>
Download mbox | patch
Permalink /patch/117608/
State New
Headers show

Comments

Kai Tietz - Oct. 4, 2011, 12:17 p.m.
Hello,

This patch (two of two) adds to tree-ssa-reassociation code for
repropagation of unpacked
bitwise-binary operations - like (X == 0) & (Y == 0), etc.
Also it denormalizes bitwise-not operations on bitwise-binary tree
chains - eg ~X & ~Y -> ~(X | Y).

ChangeLog

2011-10-04  Kai Tietz  <ktietz@redhat.com>

	* tree-ssa-reassoc.c (walk_bitwise_stmt_elems): Helper
	routine to build vectored representation of bitwise-binary tree chain.
	(rebuild_vector_tree): Build out of a vectored tree-chain representation
	a tree-chain.
	(operate_bitwise_xor_stmt): Handle bitwise-xor denormalization.
	(merge_bitwise_compares): Special helper for rebuilding denormalized
	form of comparison to zero list.
	(operate_bitwise_stmt): Handle bitwise-binary denormalization.
	(repropagate_bitwise): New static function.
	(execute_reassoc): Use repropagate_bitwise.


ChangeLog

2011-10-04  Kai Tietz  <ktietz@redhat.com>

	* gcc.dg/tree-ssa/reassoc-32.c: New file.
	* gcc.dg/tree-ssa/reassoc-33.c: New file.
	* gcc.dg/tree-ssa/reassoc-34.c: New file.
	* gcc.dg/tree-ssa/reassoc-35.c: New file.

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
@@ -2658,6 +3113,648 @@  linearize_expr_tree (VEC(operand_entry_t
   add_to_ops_vec (ops, binrhs);
 }

+/* Split up a binary tree-chain of code CODE - starting at STMT - into four
+   different kinds:
+   - vector VCST stores constant values.
+   - vector VNOT stores bitwise-not expressions.
+   - vector VCMP_ZERO stores comparisons to zero.
+   - vector VEXRR stores the remaining rest. */
+
+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) **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, vexpr);
+  else if (gimple_assign_rhs_code (s) == BIT_NOT_EXPR)
+    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);
+  else
+    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, vexpr);
+  else if (gimple_assign_rhs_code (s) == BIT_NOT_EXPR)
+    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);
+  else
+    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 the 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 has value TRUE, then the RHS1 operand of VEC elements
+   are used for combining.  Otherwise the VEC elements itself are 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.  This sequence
+   is made out of VNOT, VEXPR, and TCST.
+   It returns TRUE, if tree-chain PGSI - starting at STMT - was modified,
+   otherwise FALSE.  */
+
+static bool
+operate_bitwise_xor_stmt (gimple_stmt_iterator *pgsi, gimple stmt, tree tcst,
+			  VEC(tree, heap) *vnot,
+			  VEC(tree, heap) *vexpr)
+{
+  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);
+      gimple_assign_set_rhs_with_ops (pgsi, BIT_NOT_EXPR, l, NULL_TREE);
+    }
+  else
+    {
+      if (r)
+        gimple_assign_set_rhs_with_ops (pgsi, BIT_XOR_EXPR, l, r);
+      else
+        gimple_assign_set_rhs_from_tree (pgsi, l);
+    }
+  return true;
+}
+
+/* This function merges:compares
+   It merges VCMP elements
+   - (X != 0) | (Y != 0) -> (X | Y) != 0
+   - (X == 0) & (Y == 0) -> (X | Y) == 0.
+   Additionally it sorts and merges for the new generated left-hand
+   bitwise-or tree-chain the bitwise-not expressions.
+
+   CODE specifies the final compare expression code. It can be either
+   EQ_EXPR, or NE_EXPR.
+
+   If PGSI is not NULL, then final compare instruction
+   gets assigned to the statement it points to.  Otherwise an new
+   temporary is created for the comparison 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.
+   For the bitwise-and case, we need to make sure sign-expansion is
+   done always for type-expansion.  */
+
+static void
+merge_bitwise_compares (VEC(tree, heap) **vcmp, VEC(tree, heap) **vexpr,
+			enum tree_code code, gimple_stmt_iterator *pgsi)
+{
+  unsigned int i;
+  unsigned int len = VEC_length (tree, *vcmp);
+  tree l, r, x, cmp_type = NULL_TREE;
+  VEC(tree, heap) *vtmp = NULL;
+  VEC(tree, heap) *vtmp_not = NULL;
+  enum tree_code cmp_code;
+
+  /* If we have just one compare-element, then simply
+     move it to VEXPR vector and return.  */
+  if (len <= 1)
+    {
+      if (VEC_iterate (tree, (*vcmp), 0, (x)))
+	VEC_safe_push (tree, heap, *vexpr, x);
+
+      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 (TREE_CODE (r) != SSA_NAME
+	      || (s = SSA_NAME_DEF_STMT (r)) == NULL
+	      || !is_gimple_assign (s)
+	      || gimple_assign_rhs_code (s) != BIT_NOT_EXPR)
+	    {
+	      i++;
+	      continue;
+	    }
+	  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),
+					  BIT_AND_EXPR, l, r, s);
+	      VEC_ordered_remove (tree, *vcmp, i);
+	    }
+	  else
+	    ++i;
+	}
+      if (l != NULL_TREE)
+	VEC_safe_push (tree, heap, vtmp_not, l);
+      l = NULL_TREE;
+      for (i = 0; VEC_iterate (tree, (*vcmp), (i), (x));)
+	{
+	  gimple s2;
+	  gimple s = SSA_NAME_DEF_STMT (x);
+	  r = gimple_assign_rhs1 (s);
+	  if (TREE_CODE (r) == SSA_NAME
+	      && (s2 = SSA_NAME_DEF_STMT (r)) != NULL
+	      && is_gimple_assign (s2)
+	      && gimple_assign_rhs_code (s2) == BIT_NOT_EXPR)
+	    {
+	      i++;
+	      continue;
+	    }
+	  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),
+					  BIT_IOR_EXPR, l, r, s);
+	      VEC_ordered_remove (tree, *vcmp, i);
+	    }
+	  else
+	    ++i;
+	}
+      if (l != NULL_TREE)
+        VEC_safe_push (tree, heap, vtmp, l);
+    }
+  VEC_free (tree, heap, *vcmp);
+  *vcmp = NULL;
+
+  /* Combine elements in vector vtmp_not and put them to vtmp.  */
+  l = NULL_TREE;
+  r = NULL_TREE;
+
+  FOR_EACH_VEC_ELT (tree, vtmp_not, i, x)
+    {
+      tree type;
+      type = TREE_TYPE (x);
+
+      if (TYPE_UNSIGNED (type) && VEC_length (tree, vtmp_not) > 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, BIT_AND_EXPR, l, x, SSA_NAME_DEF_STMT (x));
+	}
+    }
+  if (l != NULL_TREE)
+    {
+      l = make_new_tmp_statement (TREE_TYPE (l), BIT_NOT_EXPR, l, NULL_TREE,
+      				  SSA_NAME_DEF_STMT (l));
+      VEC_safe_push (tree, heap, vtmp, l);
+    }
+  VEC_free (tree, heap, vtmp_not);
+  vtmp_not = 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 (!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, BIT_IOR_EXPR, l, x, SSA_NAME_DEF_STMT (x));
+	}
+    }
+
+  /* - (X == 0) & (Y == 0) -> (X | Y) == 0
+     - (X != 0) | (Y != 0) -> (X | Y) != 0
+   */
+  cmp_code = (code == BIT_AND_EXPR ? EQ_EXPR : NE_EXPR);
+
+  if (!pgsi)
+    {
+      l = make_new_tmp_statement (cmp_type,
+				  cmp_code, l,
+				  build_zero_cst (TREE_TYPE (l)),
+				  SSA_NAME_DEF_STMT (l));
+      VEC_safe_push (tree, heap, *vexpr, l);
+    }
+  else
+    gimple_assign_set_rhs_with_ops (pgsi, cmp_code, l,
+				    build_zero_cst (TREE_TYPE (l)));
+  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 bool
+operate_bitwise_stmt (gimple_stmt_iterator *pgsi, gimple stmt, enum
tree_code code)
+{
+  unsigned int i = 0;
+  tree x, tcst = NULL_TREE;
+  tree tnot = NULL_TREE, torg = NULL_TREE;
+  VEC(tree, heap) *vcst = NULL;
+  VEC(tree, heap) *vnot = NULL;
+  VEC(tree, heap) *vcmp_zero = NULL;
+  VEC(tree, heap) *vexpr = NULL;
+  enum tree_code icode;
+  bool do_repropagate = false;
+
+  gcc_assert (gimple_assign_rhs_code (stmt) == code);
+
+  walk_bitwise_stmt_elems (stmt, code, &vcst, &vnot,
+  			   &vcmp_zero, &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)
+    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, 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, vexpr);
+      return false;
+    }
+
+  /* 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)
+    {
+      merge_bitwise_compares (&vcmp_zero, &vexpr, code, pgsi);
+      return true;
+    }
+
+  merge_bitwise_compares (&vcmp_zero, &vexpr, code, NULL);
+
+  /* If we deal only with constants, assign
+     calculated constant.  */
+  if (tcst && !vnot && !vexpr)
+    {
+      gimple_assign_set_rhs_from_tree (pgsi, tcst);
+      return true;
+    }
+
+  if (code == BIT_XOR_EXPR)
+    {
+      operate_bitwise_xor_stmt (pgsi, stmt, tcst, vnot, vexpr);
+      VEC_free (tree, heap, vnot);
+      VEC_free (tree, heap, vexpr);
+      return true;
+    }
+
+  /* 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)
+        {
+	  gimple_assign_set_rhs_with_ops (pgsi, BIT_NOT_EXPR, tnot, NULL_TREE);
+	  VEC_free (tree, heap, vnot);
+	  VEC_free (tree, heap, vexpr);
+	  return true;
+	}
+
+      tnot = make_new_tmp_statement (TREE_TYPE (tnot), BIT_NOT_EXPR, tnot,
+				     NULL_TREE, SSA_NAME_DEF_STMT (tnot));
+      if (torg)
+	{
+	  if (!tcst)
+	    {
+	      gimple_assign_set_rhs_with_ops (pgsi, code, tnot, torg);
+	      VEC_free (tree, heap, vnot);
+	      VEC_free (tree, heap, vexpr);
+	      return true;
+	    }
+	  tnot = make_new_tmp_statement (TREE_TYPE (tnot), code, tnot, torg,
+					 SSA_NAME_DEF_STMT (tnot));
+	}
+      gimple_assign_set_rhs_with_ops (pgsi, code, tnot, tcst);
+      VEC_free (tree, heap, vnot);
+      VEC_free (tree, heap, vexpr);
+      return true;
+    }
+  if (!tcst)
+    torg = rebuild_vector_tree (vexpr, code, &tcst, false);
+  else
+    torg = rebuild_vector_tree (vexpr, code, NULL, false);
+  if (tcst)
+    gimple_assign_set_rhs_with_ops (pgsi, code, torg, tcst);
+  else
+    gimple_assign_set_rhs_from_tree (pgsi, torg);
+  VEC_free (tree, heap, vnot);
+  VEC_free (tree, heap, vexpr);
+  return true;
+}
+
+/* Repropagate bitwise-operations back to de-normalized form.
+   ~X op ~Y -> ~(X op' Y), (X != 0) | (Y != 0) -> (X | Y) != 0,
+   (X == 0) & (Y == 0) -> (X | Y) == 0, and
+   ~X ==/!= 0 -> X ==/!= ~0.  */
+
+static void
+repropagate_bitwise (basic_block bb)
+{
+  gimple_stmt_iterator gsi;
+  basic_block son;
+
+  /* First do combine and bitwise-not sinking.  */
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple sub;
+      gimple stmt = gsi_stmt (gsi);
+      enum tree_code code;
+      tree l, r, lhs;
+
+      if (!is_gimple_assign (stmt))
+	continue;
+
+      code = gimple_assign_rhs_code (stmt);
+      if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
+          && code != BIT_XOR_EXPR)
+        continue;
+
+      /* If user of this statement has same tree-code as this statement and
+         this STMT has single use, then skip the processing for this STMT for
+         performance reasons.  */
+      lhs = gimple_assign_lhs (stmt);
+      if (has_single_use (lhs)
+          && (sub = get_single_immediate_use (lhs)) != NULL
+          && is_gimple_assign (sub)
+          && gimple_assign_rhs_code (sub) == code)
+        continue;
+      l = gimple_assign_rhs1 (stmt);
+      r = gimple_assign_rhs2 (stmt);
+      if (!operate_bitwise_stmt (&gsi, stmt, code))
+        continue;
+      stmt = gsi_stmt (gsi);
+      update_stmt (stmt);
+      remove_stmt_chain (l);
+      remove_stmt_chain (r);
+    }
+
+  /* Now we are doing transformation ~X !=/== CST -> X !=/== ~CST.  */
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple sub;
+      gimple stmt = gsi_stmt (gsi);
+      enum tree_code code;
+      tree l, r;
+
+      if (!is_gimple_assign (stmt))
+	continue;
+
+      code = gimple_assign_rhs_code (stmt);
+      if (code != EQ_EXPR && code != NE_EXPR)
+	continue;
+      l = gimple_assign_rhs1 (stmt);
+      r = gimple_assign_rhs2 (stmt);
+      if (TREE_CODE (l) != SSA_NAME
+          || TREE_CODE (r) != INTEGER_CST
+          || (sub = SSA_NAME_DEF_STMT (l)) == NULL
+          || !is_gimple_assign (sub)
+          || gimple_assign_rhs_code (sub) != BIT_NOT_EXPR
+	  || !INTEGRAL_TYPE_P (TREE_TYPE (l)))
+	continue;
+      gimple_assign_set_rhs_with_ops (&gsi, code, gimple_assign_rhs1 (sub),
+				      fold_build1 (BIT_NOT_EXPR,
+						   TREE_TYPE (l), r));
+      update_stmt (stmt);
+      remove_stmt_chain (l);
+      remove_stmt_chain (r);
+    }
+
+  for (son = first_dom_son (CDI_DOMINATORS, bb);
+       son;
+       son = next_dom_son (CDI_DOMINATORS, son))
+    repropagate_bitwise (son);
+}
+
 /* Repropagate the negates back into subtracts, since no other pass
    currently does it.  */

@@ -3072,6 +4194,7 @@  execute_reassoc (void)

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

   fini_reassoc ();
   return 0;
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,20 @@ 
+/* { 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" 1 "optimized"} } */
+/* { dg-final { scan-tree-dump-times " != -1" 1 "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,20 @@ 
+/* { 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" 1 "optimized"} } */
+/* { dg-final { scan-tree-dump-times " != -1" 1 "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,26 @@ 
+/* { 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" 1 "optimized"} } */
+/* { dg-final { scan-tree-dump-times " != -1" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */