PATCH: fix PR tree-optimization/39874

PATCH: fix PR tree-optimization/39874

[Sandra Loosemore]

[-- Attachment #1: Type: text/plain, Size: 2323 bytes --]

This patch adds some more sophisticated logic for simplifying logical AND and OR 
expressions to fix PR39874, one of the sub-cases of PR28685.

The test case illustrates the problem:

void func();
void test(char *signature)
{
   char ch = signature[0];
   if (ch == 15 || ch == 3)
   {
     if (ch == 15) func();
   }
}

Here, the ifcombine pass was being too stupid to optimize away the outer "if" 
because it was relying on combine_comparisons only to detect when it can do 
that.  So, the basic idea of my patch is to provide better logic for optimizing 
logical ANDs and ORs in the ifcombine pass.  I recently added a patch to 
tree_ssa_reassoc that also used combine_comparisons for a similar purpose to fix 
another one of the PR28685 sub-cases, and my new functions can apply there as well.

This patch didn't really start out being quite this complicated, but once I got 
started I figured I might as well add all the usual boolean identities and 
comparison simplifications.  Much of this duplicates simplifications that are 
performed on trees in fold-const.c, but my code deals with gimple 
representations and simplifications that can be performed by copy-propagating 
SSA variables.  (E.g., in the example above, the "ch == 15" expression is 
PRE'ed coming into the ifcombine pass.)

This patch passed 3-stage bootstrap and testing on native x86_64 Linux.  I also 
tested on ARM Linux, and ran SPEC benchmarks on ARM to make sure this wasn't 
accidentally un-optimizing something else.  OK to check in?

-Sandra


2010-05-31  Sandra Loosemore  <sandra@codesourcery.com>

	PR tree-optimization/39874
	PR middle-end/28685

	gcc/
	* gimple.h (maybe_fold_and_comparisons, maybe_fold_or_comparisons):
	Declare.
	* gimple-fold.c (canonicalize_bool, same_bool_comparison_p,
	same_bool_result_p): New.
	(and_var_with_comparison, and_var_with_comparison_1,
	and_comparisons_1, and_comparisons, maybe_fold_and_comparisons): New.
	(or_var_with_comparison, or_var_with_comparison_1,
	or_comparisons_1, or_comparisons, maybe_fold_or_comparisons): New.
	* tree-ssa-reassoc.c (eliminate_redundant_comparison): Use
	maybe_fold_and_comparisons or maybe_fold_or_comparisons instead
	of combine_comparisons.
	* tree-ssa-ifcombine.c (ifcombine_ifandif, ifcombine_iforif): Likewise.

	gcc/testsuite/
	* gcc.dg/pr39874.c: New file.

[-- Attachment #2: pr39874.patch --]
[-- Type: text/x-patch, Size: 41071 bytes --]

Index: gimple.h
===================================================================
--- gimple.h	(revision 159188)
+++ gimple.h	(working copy)
@@ -4798,6 +4798,9 @@ tree maybe_fold_offset_to_address (locat
 tree maybe_fold_stmt_addition (location_t, tree, tree, tree);
 tree get_symbol_constant_value (tree);
 bool may_propagate_address_into_dereference (tree, tree);
-
+extern tree maybe_fold_and_comparisons (enum tree_code, tree, tree, 
+					enum tree_code, tree, tree);
+extern tree maybe_fold_or_comparisons (enum tree_code, tree, tree,
+				       enum tree_code, tree, tree);
 
 #endif  /* GCC_GIMPLE_H */
Index: gimple-fold.c
===================================================================
--- gimple-fold.c	(revision 159188)
+++ gimple-fold.c	(working copy)
@@ -1594,3 +1594,1050 @@ fold_stmt_inplace (gimple stmt)
   return changed;
 }
 
+/* Canonicalize and possibly invert the boolean EXPR; return NULL_TREE 
+   if EXPR is null or we don't know how.
+   If non-null, the result always has boolean type.  */
+
+static tree
+canonicalize_bool (tree expr, bool invert)
+{
+  if (!expr)
+    return NULL_TREE;
+  else if (invert)
+    {
+      if (integer_nonzerop (expr))
+	return boolean_false_node;
+      else if (integer_zerop (expr))
+	return boolean_true_node;
+      else if (TREE_CODE (expr) == SSA_NAME)
+	return fold_build2 (EQ_EXPR, boolean_type_node, expr,
+			    fold_convert (TREE_TYPE (expr), integer_zero_node));
+      else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
+	return fold_build2 (invert_tree_comparison (TREE_CODE (expr), false),
+			    boolean_type_node,
+			    TREE_OPERAND (expr, 0),
+			    TREE_OPERAND (expr, 1));
+      else
+	return NULL_TREE;
+    }
+  else
+    {
+      if (TREE_TYPE (expr) == boolean_type_node)
+	return expr;
+      if (integer_nonzerop (expr))
+	return boolean_true_node;
+      else if (integer_zerop (expr))
+	return boolean_false_node;
+      else if (TREE_CODE (expr) == SSA_NAME)
+	return fold_build2 (NE_EXPR, boolean_type_node, expr,
+			    fold_convert (TREE_TYPE (expr), integer_zero_node));
+      else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
+	return fold_build2 (TREE_CODE (expr),
+			    boolean_type_node,
+			    TREE_OPERAND (expr, 0),
+			    TREE_OPERAND (expr, 1));
+      else
+	return NULL_TREE;
+    }
+}
+
+/* Check to see if a boolean expression OP0 is logically equivalent to the
+   comparison (OP1 CODE OP2).  Check for various identities involving
+   SSA_NAMEs.  */
+
+static bool
+same_bool_comparison_p (const_tree op0, enum tree_code code,
+			const_tree op1, const_tree op2)
+{
+  gimple s;
+
+  /* The obvious case.  */
+  if (TREE_CODE (op0) == code
+      && operand_equal_p (TREE_OPERAND (op0, 0), op1, 0)
+      && operand_equal_p (TREE_OPERAND (op0, 1), op2, 0))
+    return true;
+
+  /* Check for comparing (name, name != 0) and the case where op0
+     is an SSA_NAME with a definition matching the comparison.  */
+  if (TREE_CODE (op0) == SSA_NAME
+      && TREE_TYPE (op0) == boolean_type_node)
+    {
+      if (operand_equal_p (op0, op1, 0))
+	return ((code == NE_EXPR && integer_zerop (op2))
+		|| (code == EQ_EXPR && integer_nonzerop (op2)));
+      if (is_gimple_assign (s = SSA_NAME_DEF_STMT (op0)))
+	{
+	  if (gimple_assign_rhs_code (s) == code
+	      && operand_equal_p (gimple_assign_rhs1 (s), op1, 0)
+	      && operand_equal_p (gimple_assign_rhs2 (s), op2, 0))
+	    return true;
+	}
+    }
+
+  /* If op1 is of the form (name != 0) or (name == 0), and the definition
+     of name is a comparison, recurse.  */
+  if (TREE_CODE (op1) == SSA_NAME
+      && TREE_TYPE (op1) == boolean_type_node
+      && is_gimple_assign (s = SSA_NAME_DEF_STMT (op1))
+      && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
+    {
+      enum tree_code c = gimple_assign_rhs_code (s);
+      if ((c == NE_EXPR && integer_zerop (op2))
+	  || (c == EQ_EXPR && integer_nonzerop (op2)))
+	return same_bool_comparison_p (op0, c,
+				       gimple_assign_rhs1 (s),
+				       gimple_assign_rhs2 (s));
+      if ((c == EQ_EXPR && integer_zerop (op2))
+	  || (c == NE_EXPR && integer_nonzerop (op2)))
+	return same_bool_comparison_p (op0,
+				       invert_tree_comparison (c, false),
+				       gimple_assign_rhs1 (s),
+				       gimple_assign_rhs2 (s));
+    }
+  return false;
+}
+
+/* Check to see if two boolean expressions OP1 and OP2 are logically
+   equivalent.  */
+
+static bool
+same_bool_result_p (const_tree op1, const_tree op2)
+{
+  /* Simple cases first.  */
+  if (op1 == op2)
+    return true;
+  if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op2) == INTEGER_CST)
+    return operand_equal_p (op1, op2, 0);
+
+  /* Check the cases where at least one of the operands is a comparison.
+     These are a bit smarter than operand_equal_p in that they apply some
+     identifies on SSA_NAMEs.  */
+  if (TREE_CODE_CLASS (TREE_CODE (op2)) == tcc_comparison
+      && same_bool_comparison_p (op1, TREE_CODE (op2),
+				 TREE_OPERAND (op2, 0),
+				 TREE_OPERAND (op2, 1)))
+    return true;
+  if (TREE_CODE_CLASS (TREE_CODE (op1)) == tcc_comparison
+      && same_bool_comparison_p (op2, TREE_CODE (op1),
+				 TREE_OPERAND (op1, 0),
+				 TREE_OPERAND (op1, 1)))
+    return true;
+
+  /* Default case.  */
+  return operand_equal_p (op1, op2, 0);
+}
+
+/* Forward declarations for some mutually recursive functions.  */
+
+static tree
+and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
+		   enum tree_code code2, tree op2a, tree op2b);
+static tree
+and_var_with_comparison (tree var, bool invert,
+			 enum tree_code code2, tree op2a, tree op2b);
+static tree
+and_var_with_comparison_1 (gimple stmt, 
+			   enum tree_code code2, tree op2a, tree op2b);
+static tree
+or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
+		  enum tree_code code2, tree op2a, tree op2b);
+static tree
+or_var_with_comparison (tree var, bool invert,
+			enum tree_code code2, tree op2a, tree op2b);
+static tree
+or_var_with_comparison_1 (gimple stmt, 
+			  enum tree_code code2, tree op2a, tree op2b);
+
+/* Helper function for and_comparisons_1:  try to simplify the AND of the
+   ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
+   If INVERT is true, invert the value of the VAR before doing the AND.
+   Return NULL_EXPR if we can't simplify this to a single expression.  */
+
+static tree
+and_var_with_comparison (tree var, bool invert,
+			 enum tree_code code2, tree op2a, tree op2b)
+{
+  tree t;
+  gimple stmt = SSA_NAME_DEF_STMT (var);
+
+  /* We can only deal with variables whose definitions are assignments.  */
+  if (!is_gimple_assign (stmt))
+    return NULL_TREE;
+  
+  /* If we have an inverted comparison, apply DeMorgan's law and rewrite
+     !var AND (op2a code2 op2b) => !(var OR !(op2a code2 op2b))
+     Then we only have to consider the simpler non-inverted cases.  */
+  if (invert)
+    t = or_var_with_comparison_1 (stmt, 
+				  invert_tree_comparison (code2, false),
+				  op2a, op2b);
+  else
+    t = and_var_with_comparison_1 (stmt, code2, op2a, op2b);
+  return canonicalize_bool (t, invert);
+}
+
+/* Try to simplify the AND of the ssa variable defined by the assignment
+   STMT with the comparison specified by (OP2A CODE2 OP2B).
+   Return NULL_EXPR if we can't simplify this to a single expression.  */
+
+static tree
+and_var_with_comparison_1 (gimple stmt,
+			   enum tree_code code2, tree op2a, tree op2b)
+{
+  tree var = gimple_assign_lhs (stmt);
+  tree true_test_var = NULL_TREE;
+  tree false_test_var = NULL_TREE;
+  enum tree_code innercode = gimple_assign_rhs_code (stmt);
+
+  /* Check for identities like (var AND (var == 0)) => false.  */
+  if (TREE_CODE (op2a) == SSA_NAME && TREE_TYPE (var) == boolean_type_node)
+    {
+      if ((code2 == NE_EXPR && integer_zerop (op2b))
+	  || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
+	{
+	  true_test_var = op2a;
+	  if (var == true_test_var)
+	    return var;
+	}
+      else if ((code2 == EQ_EXPR && integer_zerop (op2b))
+	       || (code2 == NE_EXPR && integer_nonzerop (op2b)))
+	{
+	  false_test_var = op2a;
+	  if (var == false_test_var)
+	    return boolean_false_node;
+	}
+    }
+
+  /* If the definition is a comparison, recurse on it.  */
+  if (TREE_CODE_CLASS (innercode) == tcc_comparison)
+    {
+      tree t = and_comparisons_1 (innercode,
+				  gimple_assign_rhs1 (stmt),
+				  gimple_assign_rhs2 (stmt),
+				  code2,
+				  op2a,
+				  op2b);
+      if (t)
+	return t;
+    }
+
+  /* If the definition is an AND or OR expression, we may be able to
+     simplify by reassociating.  */
+  if (innercode == TRUTH_AND_EXPR
+      || innercode == TRUTH_OR_EXPR
+      || (TREE_TYPE (var) == boolean_type_node
+	  && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR)))
+    {
+      tree inner1 = gimple_assign_rhs1 (stmt);
+      tree inner2 = gimple_assign_rhs2 (stmt);
+      gimple s;
+      tree t;
+      tree partial = NULL_TREE;
+      bool is_and = (innercode == TRUTH_AND_EXPR || innercode == BIT_AND_EXPR);
+      
+      /* Check for boolean identities that don't require recursive examination
+	 of inner1/inner2:
+	 inner1 AND (inner1 AND inner2) => inner1 AND inner2 => var
+	 inner1 AND (inner1 OR inner2) => inner1
+	 !inner1 AND (inner1 AND inner2) => false
+	 !inner1 AND (inner1 OR inner2) => !inner1 AND inner2
+         Likewise for similar cases involving inner2.  */
+      if (inner1 == true_test_var)
+	return (is_and ? var : inner1);
+      else if (inner2 == true_test_var)
+	return (is_and ? var : inner2);
+      else if (inner1 == false_test_var)
+	return (is_and
+		? boolean_false_node
+		: and_var_with_comparison (inner2, false, code2, op2a, op2b));
+      else if (inner2 == false_test_var)
+	return (is_and
+		? boolean_false_node
+		: and_var_with_comparison (inner1, false, code2, op2a, op2b));
+
+      /* Next, redistribute/reassociate the AND across the inner tests.
+	 Compute the first partial result, (inner1 AND (op2a code op2b))  */
+      if (TREE_CODE (inner1) == SSA_NAME
+	  && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
+	  && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
+	  && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
+					      gimple_assign_rhs1 (s),
+					      gimple_assign_rhs2 (s),
+					      code2, op2a, op2b)))
+	{
+	  /* Handle the AND case, where we are reassociating:
+	     (inner1 AND inner2) AND (op2a code2 op2b)
+	     => (t AND inner2)
+	     If the partial result t is a constant, we win.  Otherwise
+	     continue on to try reassociating with the other inner test.  */
+	  if (is_and)
+	    {
+	      if (integer_onep (t))
+		return inner2;
+	      else if (integer_zerop (t))
+		return boolean_false_node;
+	    }
+
+	  /* Handle the OR case, where we are redistributing:
+	     (inner1 OR inner2) AND (op2a code2 op2b)
+	     => (t OR (inner2 AND (op2a code2 op2b)))  */
+	  else
+	    {
+	      if (integer_onep (t))
+		return boolean_true_node;
+	      else
+		/* Save partial result for later.  */
+		partial = t;
+	    }
+	}
+      
+      /* Compute the second partial result, (inner2 AND (op2a code op2b)) */
+      if (TREE_CODE (inner2) == SSA_NAME
+	  && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
+	  && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
+	  && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
+					      gimple_assign_rhs1 (s),
+					      gimple_assign_rhs2 (s),
+					      code2, op2a, op2b)))
+	{
+	  /* Handle the AND case, where we are reassociating:
+	     (inner1 AND inner2) AND (op2a code2 op2b)
+	     => (inner1 AND t)  */
+	  if (is_and)
+	    {
+	      if (integer_onep (t))
+		return inner1;
+	      else if (integer_zerop (t))
+		return boolean_false_node;
+	    }
+
+	  /* Handle the OR case. where we are redistributing:
+	     (inner1 OR inner2) AND (op2a code2 op2b)
+	     => (t OR (inner1 AND (op2a code2 op2b)))
+	     => (t OR partial)  */
+	  else
+	    {
+	      if (integer_onep (t))
+		return boolean_true_node;
+	      else if (partial)
+		{
+		  /* We already got a simplification for the other
+		     operand to the redistributed OR expression.  The
+		     interesting case is when at least one is false.
+		     Or, if both are the same, we can apply the identity
+		     (x OR x) == x.  */
+		  if (integer_zerop (partial))
+		    return t;
+		  else if (integer_zerop (t))
+		    return partial;
+		  else if (same_bool_result_p (t, partial))
+		    return t;
+		}
+	    }
+	}
+    }
+  return NULL_TREE;
+}
+
+/* Try to simplify the AND of two comparisons defined by
+   (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
+   If this can be done without constructing an intermediate value,
+   return the resulting tree; otherwise NULL_TREE is returned.
+   This function is deliberately asymmetric as it recurses on SSA_DEFs
+   in the first comparison but not the second.  */
+
+static tree
+and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
+		   enum tree_code code2, tree op2a, tree op2b)
+{
+  /* First check for ((x CODE1 y) AND (x CODE2 y)).  */
+  if (operand_equal_p (op1a, op2a, 0)
+      && operand_equal_p (op1b, op2b, 0))
+    {
+      tree t = combine_comparisons (UNKNOWN_LOCATION,
+				    TRUTH_ANDIF_EXPR, code1, code2,
+				    boolean_type_node, op1a, op1b);
+      if (t)
+	return t;
+    }
+
+  /* Likewise the swapped case of the above.  */
+  if (operand_equal_p (op1a, op2b, 0)
+      && operand_equal_p (op1b, op2a, 0))
+    {
+      tree t = combine_comparisons (UNKNOWN_LOCATION,
+				    TRUTH_ANDIF_EXPR, code1,
+				    swap_tree_comparison (code2),
+				    boolean_type_node, op1a, op1b);
+      if (t)
+	return t;
+    }
+
+  /* If both comparisons are of the same value against constants, we might
+     be able to merge them.  */
+  if (operand_equal_p (op1a, op2a, 0)
+      && TREE_CODE (op1b) == INTEGER_CST
+      && TREE_CODE (op2b) == INTEGER_CST)
+    {
+      int cmp = tree_int_cst_compare (op1b, op2b);
+
+      /* If we have (op1a == op1b), we should either be able to
+	 return that or FALSE, depending on whether the constant op1b
+	 also satisfies the other comparison against op2b.  */
+      if (code1 == EQ_EXPR)
+	{
+	  bool done = true;
+	  bool val;
+	  switch (code2)
+	    {
+	    case EQ_EXPR: val = (cmp == 0); break;
+	    case NE_EXPR: val = (cmp != 0); break;
+	    case LT_EXPR: val = (cmp < 0); break;
+	    case GT_EXPR: val = (cmp > 0); break;
+	    case LE_EXPR: val = (cmp <= 0); break;
+	    case GE_EXPR: val = (cmp >= 0); break;
+	    default: done = false;
+	    }
+	  if (done)
+	    {
+	      if (val)
+		return fold_build2 (code1, boolean_type_node, op1a, op1b);
+	      else
+		return boolean_false_node;
+	    }
+	}
+      /* Likewise if the second comparison is an == comparison.  */
+      else if (code2 == EQ_EXPR)
+	{
+	  bool done = true;
+	  bool val;
+	  switch (code1)
+	    {
+	    case EQ_EXPR: val = (cmp == 0); break;
+	    case NE_EXPR: val = (cmp != 0); break;
+	    case LT_EXPR: val = (cmp > 0); break;
+	    case GT_EXPR: val = (cmp < 0); break;
+	    case LE_EXPR: val = (cmp >= 0); break;
+	    case GE_EXPR: val = (cmp <= 0); break;
+	    default: done = false;
+	    }
+	  if (done)
+	    {
+	      if (val)
+		return fold_build2 (code2, boolean_type_node, op2a, op2b);
+	      else
+		return boolean_false_node;
+	    }
+	}
+
+      /* Same business with inequality tests.  */
+      else if (code1 == NE_EXPR)
+	{
+	  bool val;
+	  switch (code2)
+	    {
+	    case EQ_EXPR: val = (cmp != 0); break;
+	    case NE_EXPR: val = (cmp == 0); break;
+	    case LT_EXPR: val = (cmp >= 0); break;
+	    case GT_EXPR: val = (cmp <= 0); break;
+	    case LE_EXPR: val = (cmp > 0); break;
+	    case GE_EXPR: val = (cmp < 0); break;
+	    default:
+	      val = false;
+	    }
+	  if (val)
+	    return fold_build2 (code2, boolean_type_node, op2a, op2b);
+	}
+      else if (code2 == NE_EXPR)
+	{
+	  bool val;
+	  switch (code1)
+	    {
+	    case EQ_EXPR: val = (cmp == 0); break;
+	    case NE_EXPR: val = (cmp != 0); break;
+	    case LT_EXPR: val = (cmp <= 0); break;
+	    case GT_EXPR: val = (cmp >= 0); break;
+	    case LE_EXPR: val = (cmp < 0); break;
+	    case GE_EXPR: val = (cmp > 0); break;
+	    default:
+	      val = false;
+	    }
+	  if (val)
+	    return fold_build2 (code1, boolean_type_node, op1a, op1b);
+	}
+
+      /* Chose the more restrictive of two < or <= comparisons.  */
+      else if ((code1 == LT_EXPR || code1 == LE_EXPR)
+	       && (code2 == LT_EXPR || code2 == LE_EXPR))
+	{
+	  if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
+	    return fold_build2 (code1, boolean_type_node, op1a, op1b);
+	  else
+	    return fold_build2 (code2, boolean_type_node, op2a, op2b);
+	}
+
+      /* Likewise chose the more restrictive of two > or >= comparisons.  */
+      else if ((code1 == GT_EXPR || code1 == GE_EXPR)
+	       && (code2 == GT_EXPR || code2 == GE_EXPR))
+	{
+	  if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
+	    return fold_build2 (code1, boolean_type_node, op1a, op1b);
+	  else
+	    return fold_build2 (code2, boolean_type_node, op2a, op2b);
+	}
+
+      /* Check for singleton ranges.  */
+      else if (cmp == 0
+	       && ((code1 == LE_EXPR && code2 == GE_EXPR)
+		   || (code1 == GE_EXPR && code2 == LE_EXPR)))
+	return fold_build2 (EQ_EXPR, boolean_type_node, op1a, op2b);
+
+      /* Check for disjoint ranges. */
+      else if (cmp <= 0
+	       && (code1 == LT_EXPR || code1 == LE_EXPR)
+	       && (code2 == GT_EXPR || code2 == GE_EXPR))
+	return boolean_false_node;
+      else if (cmp >= 0
+	       && (code1 == GT_EXPR || code1 == GE_EXPR)
+	       && (code2 == LT_EXPR || code2 == LE_EXPR))
+	return boolean_false_node;
+    }
+
+  /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
+     NAME's definition is a truth value.  See if there are any simplifications
+     that can be done against the NAME's definition.  */
+  if (TREE_CODE (op1a) == SSA_NAME
+      && (code1 == NE_EXPR || code1 == EQ_EXPR)
+      && (integer_zerop (op1b) || integer_onep (op1b)))
+    {
+      bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
+		     || (code1 == NE_EXPR && integer_onep (op1b)));
+      gimple stmt = SSA_NAME_DEF_STMT (op1a);
+      switch (gimple_code (stmt))
+	{
+	case GIMPLE_ASSIGN:
+	  /* Try to simplify by copy-propagating the definition.  */
+	  return and_var_with_comparison (op1a, invert, code2, op2a, op2b);
+
+	case GIMPLE_PHI:
+	  /* If every argument to the PHI produces the same result when
+	     ANDed with the second comparison, we win.
+	     Do not do this unless the type is bool since we need a bool
+	     result here anyway.  */
+	  if (TREE_TYPE (op1a) == boolean_type_node)
+	    {
+	      tree result = NULL_TREE;
+	      unsigned i;
+	      for (i = 0; i < gimple_phi_num_args (stmt); i++)
+		{
+		  tree arg = gimple_phi_arg_def (stmt, i);
+		  
+		  /* If this PHI has itself as an argument, ignore it.
+		     If all the other args produce the same result,
+		     we're still OK.  */
+		  if (arg == gimple_phi_result (stmt))
+		    continue;
+		  else if (TREE_CODE (arg) == INTEGER_CST)
+		    {
+		      if (invert ? integer_nonzerop (arg) : integer_zerop (arg))
+			{
+			  if (!result)
+			    result = boolean_false_node;
+			  else if (!integer_zerop (result))
+			    return NULL_TREE;
+			}
+		      else if (!result)
+			result = fold_build2 (code2, boolean_type_node,
+					      op2a, op2b);
+		      else if (!same_bool_comparison_p (result,
+							code2, op2a, op2b))
+			return NULL_TREE;
+		    }
+		  else if (TREE_CODE (arg) == SSA_NAME)
+		    {
+		      tree temp = and_var_with_comparison (arg, invert,
+							   code2, op2a, op2b);
+		      if (!temp)
+			return NULL_TREE;
+		      else if (!result)
+			result = temp;
+		      else if (!same_bool_result_p (result, temp))
+			return NULL_TREE;
+		    }
+		  else
+		    return NULL_TREE;
+		}
+	      return result;
+	    }
+
+	default:
+	  break;
+	}
+    }
+  return NULL_TREE;
+}
+
+/* Try to simplify the AND of two comparisons, specified by
+   (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
+   If this can be simplified to a single expression (without requiring
+   introducing more SSA variables to hold intermediate values),
+   return the resulting tree.  Otherwise return NULL_TREE.
+   If the result expression is non-null, it has boolean type.  */
+
+tree
+maybe_fold_and_comparisons (enum tree_code code1, tree op1a, tree op1b,
+			    enum tree_code code2, tree op2a, tree op2b)
+{
+  tree t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
+  if (t)
+    return t;
+  else
+    return and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+}
+
+/* Helper function for or_comparisons_1:  try to simplify the OR of the
+   ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
+   If INVERT is true, invert the value of VAR before doing the OR.
+   Return NULL_EXPR if we can't simplify this to a single expression.  */
+
+static tree
+or_var_with_comparison (tree var, bool invert,
+			enum tree_code code2, tree op2a, tree op2b)
+{
+  tree t;
+  gimple stmt = SSA_NAME_DEF_STMT (var);
+
+  /* We can only deal with variables whose definitions are assignments.  */
+  if (!is_gimple_assign (stmt))
+    return NULL_TREE;
+  
+  /* If we have an inverted comparison, apply DeMorgan's law and rewrite
+     !var OR (op2a code2 op2b) => !(var AND !(op2a code2 op2b))
+     Then we only have to consider the simpler non-inverted cases.  */
+  if (invert)
+    t = and_var_with_comparison_1 (stmt, 
+				   invert_tree_comparison (code2, false),
+				   op2a, op2b);
+  else
+    t = or_var_with_comparison_1 (stmt, code2, op2a, op2b);
+  return canonicalize_bool (t, invert);
+}
+
+/* Try to simplify the OR of the ssa variable defined by the assignment
+   STMT with the comparison specified by (OP2A CODE2 OP2B).
+   Return NULL_EXPR if we can't simplify this to a single expression.  */
+
+static tree
+or_var_with_comparison_1 (gimple stmt,
+			  enum tree_code code2, tree op2a, tree op2b)
+{
+  tree var = gimple_assign_lhs (stmt);
+  tree true_test_var = NULL_TREE;
+  tree false_test_var = NULL_TREE;
+  enum tree_code innercode = gimple_assign_rhs_code (stmt);
+
+  /* Check for identities like (var OR (var != 0)) => true .  */
+  if (TREE_CODE (op2a) == SSA_NAME && TREE_TYPE (var) == boolean_type_node)
+    {
+      if ((code2 == NE_EXPR && integer_zerop (op2b))
+	  || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
+	{
+	  true_test_var = op2a;
+	  if (var == true_test_var)
+	    return var;
+	}
+      else if ((code2 == EQ_EXPR && integer_zerop (op2b))
+	       || (code2 == NE_EXPR && integer_nonzerop (op2b)))
+	{
+	  false_test_var = op2a;
+	  if (var == false_test_var)
+	    return boolean_true_node;
+	}
+    }
+
+  /* If the definition is a comparison, recurse on it.  */
+  if (TREE_CODE_CLASS (innercode) == tcc_comparison)
+    {
+      tree t = or_comparisons_1 (innercode,
+				 gimple_assign_rhs1 (stmt),
+				 gimple_assign_rhs2 (stmt),
+				 code2,
+				 op2a,
+				 op2b);
+      if (t)
+	return t;
+    }
+  
+  /* If the definition is an AND or OR expression, we may be able to
+     simplify by reassociating.  */
+  if (innercode == TRUTH_AND_EXPR
+      || innercode == TRUTH_OR_EXPR
+      || (TREE_TYPE (var) == boolean_type_node
+	  && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR)))
+    {
+      tree inner1 = gimple_assign_rhs1 (stmt);
+      tree inner2 = gimple_assign_rhs2 (stmt);
+      gimple s;
+      tree t;
+      tree partial = NULL_TREE;
+      bool is_or = (innercode == TRUTH_OR_EXPR || innercode == BIT_IOR_EXPR);
+      
+      /* Check for boolean identities that don't require recursive examination
+	 of inner1/inner2:
+	 inner1 OR (inner1 OR inner2) => inner1 OR inner2 => var
+	 inner1 OR (inner1 AND inner2) => inner1
+	 !inner1 OR (inner1 OR inner2) => true
+	 !inner1 OR (inner1 AND inner2) => !inner1 OR inner2
+      */
+      if (inner1 == true_test_var)
+	return (is_or ? var : inner1);
+      else if (inner2 == true_test_var)
+	return (is_or ? var : inner2);
+      else if (inner1 == false_test_var)
+	return (is_or
+		? boolean_true_node
+		: or_var_with_comparison (inner2, false, code2, op2a, op2b));
+      else if (inner2 == false_test_var)
+	return (is_or
+		? boolean_true_node
+		: or_var_with_comparison (inner1, false, code2, op2a, op2b));
+      
+      /* Next, redistribute/reassociate the OR across the inner tests.
+	 Compute the first partial result, (inner1 OR (op2a code op2b))  */
+      if (TREE_CODE (inner1) == SSA_NAME
+	  && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
+	  && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
+	  && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
+					     gimple_assign_rhs1 (s),
+					     gimple_assign_rhs2 (s),
+					     code2, op2a, op2b)))
+	{
+	  /* Handle the OR case, where we are reassociating:
+	     (inner1 OR inner2) OR (op2a code2 op2b)
+	     => (t OR inner2)
+	     If the partial result t is a constant, we win.  Otherwise
+	     continue on to try reassociating with the other inner test.  */
+	  if (innercode == TRUTH_OR_EXPR)
+	    {
+	      if (integer_onep (t))
+		return boolean_true_node;
+	      else if (integer_zerop (t))
+		return inner2;
+	    }
+	  
+	  /* Handle the AND case, where we are redistributing:
+	     (inner1 AND inner2) OR (op2a code2 op2b)
+	     => (t AND (inner2 OR (op2a code op2b)))  */
+	  else
+	    {
+	      if (integer_zerop (t))
+		return boolean_false_node;
+	      else
+		/* Save partial result for later.  */
+		partial = t;
+	    }
+	}
+      
+      /* Compute the second partial result, (inner2 OR (op2a code op2b)) */
+      if (TREE_CODE (inner2) == SSA_NAME
+	  && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
+	  && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
+	  && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
+					     gimple_assign_rhs1 (s),
+					     gimple_assign_rhs2 (s),
+					     code2, op2a, op2b)))
+	{
+	  /* Handle the OR case, where we are reassociating:
+	     (inner1 OR inner2) OR (op2a code2 op2b)
+	     => (inner1 OR t)  */
+	  if (innercode == TRUTH_OR_EXPR)
+	    {
+	      if (integer_zerop (t))
+		return inner1;
+	      else if (integer_onep (t))
+		return boolean_true_node;
+	    }
+	  
+	  /* Handle the AND case, where we are redistributing:
+	     (inner1 AND inner2) OR (op2a code2 op2b)
+	     => (t AND (inner1 OR (op2a code2 op2b)))
+	     => (t AND partial)  */
+	  else 
+	    {
+	      if (integer_zerop (t))
+		return boolean_false_node;
+	      else if (partial)
+		{
+		  /* We already got a simplification for the other
+		     operand to the redistributed AND expression.  The
+		     interesting case is when at least one is true.
+		     Or, if both are the same, we can apply the identity
+		     (x AND x) == true.  */
+		  if (integer_onep (partial))
+		    return t;
+		  else if (integer_onep (t))
+		    return partial;
+		  else if (same_bool_result_p (t, partial))
+		    return boolean_true_node;
+		}
+	    }
+	}
+    }
+  return NULL_TREE;
+}
+
+/* Try to simplify the OR of two comparisons defined by
+   (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
+   If this can be done without constructing an intermediate value,
+   return the resulting tree; otherwise NULL_TREE is returned.
+   This function is deliberately asymmetric as it recurses on SSA_DEFs
+   in the first comparison but not the second.  */
+
+static tree
+or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
+		  enum tree_code code2, tree op2a, tree op2b)
+{
+  /* First check for ((x CODE1 y) OR (x CODE2 y)).  */
+  if (operand_equal_p (op1a, op2a, 0)
+      && operand_equal_p (op1b, op2b, 0))
+    {
+      tree t = combine_comparisons (UNKNOWN_LOCATION,
+				    TRUTH_ORIF_EXPR, code1, code2,
+				    boolean_type_node, op1a, op1b);
+      if (t)
+	return t;
+    }
+
+  /* Likewise the swapped case of the above.  */
+  if (operand_equal_p (op1a, op2b, 0)
+      && operand_equal_p (op1b, op2a, 0))
+    {
+      tree t = combine_comparisons (UNKNOWN_LOCATION,
+				    TRUTH_ORIF_EXPR, code1,
+				    swap_tree_comparison (code2),
+				    boolean_type_node, op1a, op1b);
+      if (t)
+	return t;
+    }
+
+  /* If both comparisons are of the same value against constants, we might
+     be able to merge them.  */
+  if (operand_equal_p (op1a, op2a, 0)
+      && TREE_CODE (op1b) == INTEGER_CST
+      && TREE_CODE (op2b) == INTEGER_CST)
+    {
+      int cmp = tree_int_cst_compare (op1b, op2b);
+
+      /* If we have (op1a != op1b), we should either be able to
+	 return that or TRUE, depending on whether the constant op1b
+	 also satisfies the other comparison against op2b.  */
+      if (code1 == NE_EXPR)
+	{
+	  bool done = true;
+	  bool val;
+	  switch (code2)
+	    {
+	    case EQ_EXPR: val = (cmp == 0); break;
+	    case NE_EXPR: val = (cmp != 0); break;
+	    case LT_EXPR: val = (cmp < 0); break;
+	    case GT_EXPR: val = (cmp > 0); break;
+	    case LE_EXPR: val = (cmp <= 0); break;
+	    case GE_EXPR: val = (cmp >= 0); break;
+	    default: done = false;
+	    }
+	  if (done)
+	    {
+	      if (val)
+		return boolean_true_node;
+	      else
+		return fold_build2 (code1, boolean_type_node, op1a, op1b);
+	    }
+	}
+      /* Likewise if the second comparison is a != comparison.  */
+      else if (code2 == NE_EXPR)
+	{
+	  bool done = true;
+	  bool val;
+	  switch (code1)
+	    {
+	    case EQ_EXPR: val = (cmp == 0); break;
+	    case NE_EXPR: val = (cmp != 0); break;
+	    case LT_EXPR: val = (cmp > 0); break;
+	    case GT_EXPR: val = (cmp < 0); break;
+	    case LE_EXPR: val = (cmp >= 0); break;
+	    case GE_EXPR: val = (cmp <= 0); break;
+	    default: done = false;
+	    }
+	  if (done)
+	    {
+	      if (val)
+		return boolean_true_node;
+	      else
+		return fold_build2 (code2, boolean_type_node, op2a, op2b);
+	    }
+	}
+
+      /* See if an equality test is redundant with the other comparison.  */
+      else if (code1 == EQ_EXPR)
+	{
+	  bool val;
+	  switch (code2)
+	    {
+	    case EQ_EXPR: val = (cmp == 0); break;
+	    case NE_EXPR: val = (cmp != 0); break;
+	    case LT_EXPR: val = (cmp < 0); break;
+	    case GT_EXPR: val = (cmp > 0); break;
+	    case LE_EXPR: val = (cmp <= 0); break;
+	    case GE_EXPR: val = (cmp >= 0); break;
+	    default:
+	      val = false;
+	    }
+	  if (val)
+	    return fold_build2 (code2, boolean_type_node, op2a, op2b);
+	}
+      else if (code2 == EQ_EXPR)
+	{
+	  bool val;
+	  switch (code1)
+	    {
+	    case EQ_EXPR: val = (cmp == 0); break;
+	    case NE_EXPR: val = (cmp != 0); break;
+	    case LT_EXPR: val = (cmp > 0); break;
+	    case GT_EXPR: val = (cmp < 0); break;
+	    case LE_EXPR: val = (cmp >= 0); break;
+	    case GE_EXPR: val = (cmp <= 0); break;
+	    default:
+	      val = false;
+	    }
+	  if (val)
+	    return fold_build2 (code1, boolean_type_node, op1a, op1b);
+	}
+
+      /* Chose the less restrictive of two < or <= comparisons.  */
+      else if ((code1 == LT_EXPR || code1 == LE_EXPR)
+	       && (code2 == LT_EXPR || code2 == LE_EXPR))
+	{
+	  if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
+	    return fold_build2 (code2, boolean_type_node, op2a, op2b);
+	  else
+	    return fold_build2 (code1, boolean_type_node, op1a, op1b);
+	}
+
+      /* Likewise chose the less restrictive of two > or >= comparisons.  */
+      else if ((code1 == GT_EXPR || code1 == GE_EXPR)
+	       && (code2 == GT_EXPR || code2 == GE_EXPR))
+	{
+	  if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
+	    return fold_build2 (code2, boolean_type_node, op2a, op2b);
+	  else
+	    return fold_build2 (code1, boolean_type_node, op1a, op1b);
+	}
+
+      /* Check for singleton ranges.  */
+      else if (cmp == 0
+	       && ((code1 == LT_EXPR && code2 == GT_EXPR)
+		   || (code1 == GT_EXPR && code2 == LT_EXPR)))
+	return fold_build2 (NE_EXPR, boolean_type_node, op1a, op2b);
+
+      /* Check for less/greater pairs that don't restrict the range at all.  */
+      else if (cmp >= 0
+	       && (code1 == LT_EXPR || code1 == LE_EXPR)
+	       && (code2 == GT_EXPR || code2 == GE_EXPR))
+	return boolean_true_node;
+      else if (cmp <= 0
+	       && (code1 == GT_EXPR || code1 == GE_EXPR)
+	       && (code2 == LT_EXPR || code2 == LE_EXPR))
+	return boolean_true_node;
+    }
+
+  /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
+     NAME's definition is a truth value.  See if there are any simplifications
+     that can be done against the NAME's definition.  */
+  if (TREE_CODE (op1a) == SSA_NAME
+      && (code1 == NE_EXPR || code1 == EQ_EXPR)
+      && (integer_zerop (op1b) || integer_onep (op1b)))
+    {
+      bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
+		     || (code1 == NE_EXPR && integer_onep (op1b)));
+      gimple stmt = SSA_NAME_DEF_STMT (op1a);
+      switch (gimple_code (stmt))
+	{
+	case GIMPLE_ASSIGN:
+	  /* Try to simplify by copy-propagating the definition.  */
+	  return or_var_with_comparison (op1a, invert, code2, op2a, op2b);
+
+	case GIMPLE_PHI:
+	  /* If every argument to the PHI produces the same result when
+	     ORed with the second comparison, we win.
+	     Do not do this unless the type is bool since we need a bool
+	     result here anyway.  */
+	  if (TREE_TYPE (op1a) == boolean_type_node)
+	    {
+	      tree result = NULL_TREE;
+	      unsigned i;
+	      for (i = 0; i < gimple_phi_num_args (stmt); i++)
+		{
+		  tree arg = gimple_phi_arg_def (stmt, i);
+		  
+		  /* If this PHI has itself as an argument, ignore it.
+		     If all the other args produce the same result,
+		     we're still OK.  */
+		  if (arg == gimple_phi_result (stmt))
+		    continue;
+		  else if (TREE_CODE (arg) == INTEGER_CST)
+		    {
+		      if (invert ? integer_zerop (arg) : integer_nonzerop (arg))
+			{
+			  if (!result)
+			    result = boolean_true_node;
+			  else if (!integer_onep (result))
+			    return NULL_TREE;
+			}
+		      else if (!result)
+			result = fold_build2 (code2, boolean_type_node,
+					      op2a, op2b);
+		      else if (!same_bool_comparison_p (result,
+							code2, op2a, op2b))
+			return NULL_TREE;
+		    }
+		  else if (TREE_CODE (arg) == SSA_NAME)
+		    {
+		      tree temp = or_var_with_comparison (arg, invert,
+							  code2, op2a, op2b);
+		      if (!temp)
+			return NULL_TREE;
+		      else if (!result)
+			result = temp;
+		      else if (!same_bool_result_p (result, temp))
+			return NULL_TREE;
+		    }
+		  else
+		    return NULL_TREE;
+		}
+	      return result;
+	    }
+
+	default:
+	  break;
+	}
+    }
+  return NULL_TREE;
+}
+
+/* Try to simplify the OR of two comparisons, specified by
+   (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
+   If this can be simplified to a single expression (without requiring
+   introducing more SSA variables to hold intermediate values),
+   return the resulting tree.  Otherwise return NULL_TREE.
+   If the result expression is non-null, it has boolean type.  */
+
+tree
+maybe_fold_or_comparisons (enum tree_code code1, tree op1a, tree op1b,
+			   enum tree_code code2, tree op2a, tree op2b)
+{
+  tree t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
+  if (t)
+    return t;
+  else
+    return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+}
Index: tree-ssa-reassoc.c
===================================================================
--- tree-ssa-reassoc.c	(revision 159189)
+++ tree-ssa-reassoc.c	(working copy)
@@ -1262,23 +1262,26 @@ eliminate_redundant_comparison (enum tre
       rcode = gimple_assign_rhs_code (def2);
       if (TREE_CODE_CLASS (rcode) != tcc_comparison)
 	continue;
-      if (operand_equal_p (op1, gimple_assign_rhs1 (def2), 0)
-	  && operand_equal_p (op2, gimple_assign_rhs2 (def2), 0))
-	;
-      else if (operand_equal_p (op1, gimple_assign_rhs2 (def2), 0)
-	       && operand_equal_p (op2, gimple_assign_rhs1 (def2), 0))
-	rcode = swap_tree_comparison (rcode);
-      else
-	continue;
 
       /* If we got here, we have a match.  See if we can combine the
 	 two comparisons.  */
-      t = combine_comparisons (UNKNOWN_LOCATION,
-			       (opcode == BIT_IOR_EXPR
-				? TRUTH_OR_EXPR : TRUTH_AND_EXPR),
-			       lcode, rcode, TREE_TYPE (curr->op), op1, op2);
+      if (opcode == BIT_IOR_EXPR)
+	t = maybe_fold_or_comparisons (lcode, op1, op2,
+				       rcode, gimple_assign_rhs1 (def2),
+				       gimple_assign_rhs2 (def2));
+      else
+	t = maybe_fold_and_comparisons (lcode, op1, op2,
+					rcode, gimple_assign_rhs1 (def2),
+					gimple_assign_rhs2 (def2));
       if (!t)
 	continue;
+
+      /* maybe_fold_and_comparisons and maybe_fold_or_comparisons
+	 always give us a boolean_type_node value back.  If the original
+	 BIT_AND_EXPR or BIT_IOR_EXPR was of a wider integer type,
+	 we need to convert.  */
+      t = fold_convert (TREE_TYPE (curr->op), t);
+
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file, "Equivalence: ");
@@ -1304,7 +1307,7 @@ eliminate_redundant_comparison (enum tre
 	  VEC_ordered_remove (operand_entry_t, *ops, currindex);
 	  add_to_ops_vec (ops, t);
 	}
-      else if (TREE_CODE (t) != lcode)
+      else if (!operand_equal_p (t, curr->op, 0))
 	{
 	  tree tmpvar;
 	  gimple sum;
Index: tree-ssa-ifcombine.c
===================================================================
--- tree-ssa-ifcombine.c	(revision 159188)
+++ tree-ssa-ifcombine.c	(working copy)
@@ -366,21 +366,16 @@ ifcombine_ifandif (basic_block inner_con
 
   /* See if we have two comparisons that we can merge into one.  */
   else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
-	   && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison
-	   && operand_equal_p (gimple_cond_lhs (inner_cond),
-			       gimple_cond_lhs (outer_cond), 0)
-	   && operand_equal_p (gimple_cond_rhs (inner_cond),
-			       gimple_cond_rhs (outer_cond), 0))
+	   && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
     {
-      enum tree_code code1 = gimple_cond_code (inner_cond);
-      enum tree_code code2 = gimple_cond_code (outer_cond);
       tree t;
 
-      if (!(t = combine_comparisons (UNKNOWN_LOCATION,
-	      			     TRUTH_ANDIF_EXPR, code1, code2,
-				     boolean_type_node,
-				     gimple_cond_lhs (outer_cond),
-				     gimple_cond_rhs (outer_cond))))
+      if (!(t = maybe_fold_and_comparisons (gimple_cond_code (inner_cond),
+					    gimple_cond_lhs (inner_cond),
+					    gimple_cond_rhs (inner_cond),
+					    gimple_cond_code (outer_cond),
+					    gimple_cond_lhs (outer_cond),
+					    gimple_cond_rhs (outer_cond))))
 	return false;
       t = canonicalize_cond_expr_cond (t);
       if (!t)
@@ -518,22 +513,17 @@ ifcombine_iforif (basic_block inner_cond
   /* See if we have two comparisons that we can merge into one.
      This happens for C++ operator overloading where for example
      GE_EXPR is implemented as GT_EXPR || EQ_EXPR.  */
-  else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
-	   && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison
-	   && operand_equal_p (gimple_cond_lhs (inner_cond),
-			       gimple_cond_lhs (outer_cond), 0)
-	   && operand_equal_p (gimple_cond_rhs (inner_cond),
-			       gimple_cond_rhs (outer_cond), 0))
+    else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
+	   && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
     {
-      enum tree_code code1 = gimple_cond_code (inner_cond);
-      enum tree_code code2 = gimple_cond_code (outer_cond);
       tree t;
 
-      if (!(t = combine_comparisons (UNKNOWN_LOCATION,
-	      			     TRUTH_ORIF_EXPR, code1, code2,
-				     boolean_type_node,
-				     gimple_cond_lhs (outer_cond),
-				     gimple_cond_rhs (outer_cond))))
+      if (!(t = maybe_fold_or_comparisons (gimple_cond_code (inner_cond),
+					   gimple_cond_lhs (inner_cond),
+					   gimple_cond_rhs (inner_cond),
+					   gimple_cond_code (outer_cond),
+					   gimple_cond_lhs (outer_cond),
+					   gimple_cond_rhs (outer_cond))))
 	return false;
       t = canonicalize_cond_expr_cond (t);
       if (!t)
Index: testsuite/gcc.dg/pr39874.c
===================================================================
--- testsuite/gcc.dg/pr39874.c	(revision 0)
+++ testsuite/gcc.dg/pr39874.c	(revision 0)
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" }  */
+
+extern void func();
+
+void test1(char *signature)
+{
+  char ch = signature[0];
+  if (ch == 15 || ch == 3)
+  {
+    if (ch == 15) func();
+  }
+}
+
+
+void test2(char *signature)
+{
+  char ch = signature[0];
+  if (ch == 15 || ch == 3)
+  {
+    if (ch > 14) func();
+  }
+}
+
+/* { dg-final { scan-tree-dump-times " == 15" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-not " == 3" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
+
+

Re: PATCH: fix PR tree-optimization/39874

[Richard Guenther]

On Tue, Jun 1, 2010 at 2:32 AM, Sandra Loosemore
<sandra@codesourcery.com> wrote:
> This patch adds some more sophisticated logic for simplifying logical AND
> and OR expressions to fix PR39874, one of the sub-cases of PR28685.
>
> The test case illustrates the problem:
>
> void func();
> void test(char *signature)
> {
>  char ch = signature[0];
>  if (ch == 15 || ch == 3)
>  {
>    if (ch == 15) func();
>  }
> }
>
> Here, the ifcombine pass was being too stupid to optimize away the outer
> "if" because it was relying on combine_comparisons only to detect when it
> can do that.  So, the basic idea of my patch is to provide better logic for
> optimizing logical ANDs and ORs in the ifcombine pass.  I recently added a
> patch to tree_ssa_reassoc that also used combine_comparisons for a similar
> purpose to fix another one of the PR28685 sub-cases, and my new functions
> can apply there as well.
>
> This patch didn't really start out being quite this complicated, but once I
> got started I figured I might as well add all the usual boolean identities
> and comparison simplifications.  Much of this duplicates simplifications
> that are performed on trees in fold-const.c, but my code deals with gimple
> representations and simplifications that can be performed by
> copy-propagating SSA variables.  (E.g., in the example above, the "ch == 15"
> expression is PRE'ed coming into the ifcombine pass.)
>
> This patch passed 3-stage bootstrap and testing on native x86_64 Linux.  I
> also tested on ARM Linux, and ran SPEC benchmarks on ARM to make sure this
> wasn't accidentally un-optimizing something else.  OK to check in?

+                           fold_convert (TREE_TYPE (expr), integer_zero_node));

use build_int_cst (TREE_TYPE (expr), 0).

+/* Check to see if a boolean expression OP0 is logically equivalent to the
+   comparison (OP1 CODE OP2).  Check for various identities involving
+   SSA_NAMEs.  */
+
+static bool
+same_bool_comparison_p (const_tree op0, enum tree_code code,
+                       const_tree op1, const_tree op2)

I think op0 is an unfortunate name, 'expr' would be better.

+      if (is_gimple_assign (s = SSA_NAME_DEF_STMT (op0)))
+       {

please move the assignment before the if ().

+  /* If op1 is of the form (name != 0) or (name == 0), and the definition
+     of name is a comparison, recurse.  */
+  if (TREE_CODE (op1) == SSA_NAME
+      && TREE_TYPE (op1) == boolean_type_node
+      && is_gimple_assign (s = SSA_NAME_DEF_STMT (op1))

likewise.

Instead of testing for equality to boolean_type_node please
replace the checks with a check for TREE_CODE (TREE_TYPE (op1)) == BOOLEAN_TYPE.

+  if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op2) == INTEGER_CST)
+    return operand_equal_p (op1, op2, 0);

tree_int_cst_equal ()

you fall back to operand_equal_p later, so why not do that test
here first like

  if (operand_equal_p (op1, op2, 0))
    return true;

and fall back to return false?

+      if ((code2 == NE_EXPR && integer_zerop (op2b))
+         || (code2 == EQ_EXPR && integer_nonzerop (op2b)))

I see this pattern in multiple places - as you check for
BOOLEAN_TYPE on var and later do an equality comparison
with op2a you know that that also has BOOLEAN_TYPE and
thus we should have canonicalized bool == 1 to plain bool
by fold.

+      /* maybe_fold_and_comparisons and maybe_fold_or_comparisons
+        always give us a boolean_type_node value back.  If the original
+        BIT_AND_EXPR or BIT_IOR_EXPR was of a wider integer type,
+        we need to convert.  */
+      t = fold_convert (TREE_TYPE (curr->op), t);

guard this with if (!useless_type_conversion_p (TREE_TYPE (curr->op),
TREE_TYPE (t))

Overall the patch is large and it feels like it duplicates a lot of
code from fold-const (but indeed in a better way, without building
trees all the time).  Please give others the chance to review it (I
know I get distracted after a while when looking at large patches like
this ... ;)).

Thus - the patch is ok if nobody dares to give it another look within a week.

Thanks,
Richard.

> -Sandra
>
>
> 2010-05-31  Sandra Loosemore  <sandra@codesourcery.com>
>
>        PR tree-optimization/39874
>        PR middle-end/28685
>
>        gcc/
>        * gimple.h (maybe_fold_and_comparisons, maybe_fold_or_comparisons):
>        Declare.
>        * gimple-fold.c (canonicalize_bool, same_bool_comparison_p,
>        same_bool_result_p): New.
>        (and_var_with_comparison, and_var_with_comparison_1,
>        and_comparisons_1, and_comparisons, maybe_fold_and_comparisons): New.
>        (or_var_with_comparison, or_var_with_comparison_1,
>        or_comparisons_1, or_comparisons, maybe_fold_or_comparisons): New.
>        * tree-ssa-reassoc.c (eliminate_redundant_comparison): Use
>        maybe_fold_and_comparisons or maybe_fold_or_comparisons instead
>        of combine_comparisons.
>        * tree-ssa-ifcombine.c (ifcombine_ifandif, ifcombine_iforif):
> Likewise.
>
>        gcc/testsuite/
>        * gcc.dg/pr39874.c: New file.
>

Re: PATCH: fix PR tree-optimization/39874

[NightStrike]

On Tue, Jun 1, 2010 at 7:30 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Tue, Jun 1, 2010 at 2:32 AM, Sandra Loosemore
> <sandra@codesourcery.com> wrote:
>> This patch adds some more sophisticated logic for simplifying logical AND
>> and OR expressions to fix PR39874, one of the sub-cases of PR28685.
>>
>> The test case illustrates the problem:
>>
>> void func();
>> void test(char *signature)
>> {
>>  char ch = signature[0];
>>  if (ch == 15 || ch == 3)
>>  {
>>    if (ch == 15) func();
>>  }
>> }
>>
>> Here, the ifcombine pass was being too stupid to optimize away the outer
>> "if" because it was relying on combine_comparisons only to detect when it
>> can do that.  So, the basic idea of my patch is to provide better logic for
>> optimizing logical ANDs and ORs in the ifcombine pass.  I recently added a
>> patch to tree_ssa_reassoc that also used combine_comparisons for a similar
>> purpose to fix another one of the PR28685 sub-cases, and my new functions
>> can apply there as well.
>>
>> This patch didn't really start out being quite this complicated, but once I
>> got started I figured I might as well add all the usual boolean identities
>> and comparison simplifications.  Much of this duplicates simplifications
>> that are performed on trees in fold-const.c, but my code deals with gimple
>> representations and simplifications that can be performed by
>> copy-propagating SSA variables.  (E.g., in the example above, the "ch == 15"
>> expression is PRE'ed coming into the ifcombine pass.)
>>
>> This patch passed 3-stage bootstrap and testing on native x86_64 Linux.  I
>> also tested on ARM Linux, and ran SPEC benchmarks on ARM to make sure this
>> wasn't accidentally un-optimizing something else.  OK to check in?
>
> +                           fold_convert (TREE_TYPE (expr), integer_zero_node));
>
> use build_int_cst (TREE_TYPE (expr), 0).
>
> +/* Check to see if a boolean expression OP0 is logically equivalent to the
> +   comparison (OP1 CODE OP2).  Check for various identities involving
> +   SSA_NAMEs.  */
> +
> +static bool
> +same_bool_comparison_p (const_tree op0, enum tree_code code,
> +                       const_tree op1, const_tree op2)
>
> I think op0 is an unfortunate name, 'expr' would be better.
>
> +      if (is_gimple_assign (s = SSA_NAME_DEF_STMT (op0)))
> +       {
>
> please move the assignment before the if ().
>
> +  /* If op1 is of the form (name != 0) or (name == 0), and the definition
> +     of name is a comparison, recurse.  */
> +  if (TREE_CODE (op1) == SSA_NAME
> +      && TREE_TYPE (op1) == boolean_type_node
> +      && is_gimple_assign (s = SSA_NAME_DEF_STMT (op1))
>
> likewise.
>
> Instead of testing for equality to boolean_type_node please
> replace the checks with a check for TREE_CODE (TREE_TYPE (op1)) == BOOLEAN_TYPE.
>
> +  if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op2) == INTEGER_CST)
> +    return operand_equal_p (op1, op2, 0);
>
> tree_int_cst_equal ()
>
> you fall back to operand_equal_p later, so why not do that test
> here first like
>
>  if (operand_equal_p (op1, op2, 0))
>    return true;
>
> and fall back to return false?
>
> +      if ((code2 == NE_EXPR && integer_zerop (op2b))
> +         || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
>
> I see this pattern in multiple places - as you check for
> BOOLEAN_TYPE on var and later do an equality comparison
> with op2a you know that that also has BOOLEAN_TYPE and
> thus we should have canonicalized bool == 1 to plain bool
> by fold.
>
> +      /* maybe_fold_and_comparisons and maybe_fold_or_comparisons
> +        always give us a boolean_type_node value back.  If the original
> +        BIT_AND_EXPR or BIT_IOR_EXPR was of a wider integer type,
> +        we need to convert.  */
> +      t = fold_convert (TREE_TYPE (curr->op), t);
>
> guard this with if (!useless_type_conversion_p (TREE_TYPE (curr->op),
> TREE_TYPE (t))
>
> Overall the patch is large and it feels like it duplicates a lot of
> code from fold-const (but indeed in a better way, without building
> trees all the time).  Please give others the chance to review it (I
> know I get distracted after a while when looking at large patches like
> this ... ;)).
>
> Thus - the patch is ok if nobody dares to give it another look within a week.
>
> Thanks,
> Richard.
>
>> -Sandra
>>
>>
>> 2010-05-31  Sandra Loosemore  <sandra@codesourcery.com>
>>
>>        PR tree-optimization/39874
>>        PR middle-end/28685
>>
>>        gcc/
>>        * gimple.h (maybe_fold_and_comparisons, maybe_fold_or_comparisons):
>>        Declare.
>>        * gimple-fold.c (canonicalize_bool, same_bool_comparison_p,
>>        same_bool_result_p): New.
>>        (and_var_with_comparison, and_var_with_comparison_1,
>>        and_comparisons_1, and_comparisons, maybe_fold_and_comparisons): New.
>>        (or_var_with_comparison, or_var_with_comparison_1,
>>        or_comparisons_1, or_comparisons, maybe_fold_or_comparisons): New.
>>        * tree-ssa-reassoc.c (eliminate_redundant_comparison): Use
>>        maybe_fold_and_comparisons or maybe_fold_or_comparisons instead
>>        of combine_comparisons.
>>        * tree-ssa-ifcombine.c (ifcombine_ifandif, ifcombine_iforif):
>> Likewise.
>>
>>        gcc/testsuite/
>>        * gcc.dg/pr39874.c: New file.
>>
>

Ping
PR: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39874

Re: PATCH: fix PR tree-optimization/39874

[H.J. Lu]

On Mon, May 31, 2010 at 5:32 PM, Sandra Loosemore
<sandra@codesourcery.com> wrote:
> This patch adds some more sophisticated logic for simplifying logical AND
> and OR expressions to fix PR39874, one of the sub-cases of PR28685.
>
> The test case illustrates the problem:
>
> void func();
> void test(char *signature)
> {
>  char ch = signature[0];
>  if (ch == 15 || ch == 3)
>  {
>    if (ch == 15) func();
>  }
> }
>
> Here, the ifcombine pass was being too stupid to optimize away the outer
> "if" because it was relying on combine_comparisons only to detect when it
> can do that.  So, the basic idea of my patch is to provide better logic for
> optimizing logical ANDs and ORs in the ifcombine pass.  I recently added a
> patch to tree_ssa_reassoc that also used combine_comparisons for a similar
> purpose to fix another one of the PR28685 sub-cases, and my new functions
> can apply there as well.
>
> This patch didn't really start out being quite this complicated, but once I
> got started I figured I might as well add all the usual boolean identities
> and comparison simplifications.  Much of this duplicates simplifications
> that are performed on trees in fold-const.c, but my code deals with gimple
> representations and simplifications that can be performed by
> copy-propagating SSA variables.  (E.g., in the example above, the "ch == 15"
> expression is PRE'ed coming into the ifcombine pass.)
>
> This patch passed 3-stage bootstrap and testing on native x86_64 Linux.  I
> also tested on ARM Linux, and ran SPEC benchmarks on ARM to make sure this
> wasn't accidentally un-optimizing something else.  OK to check in?
>
> -Sandra
>
>
> 2010-05-31  Sandra Loosemore  <sandra@codesourcery.com>
>
>        PR tree-optimization/39874
>        PR middle-end/28685
>
>        gcc/
>        * gimple.h (maybe_fold_and_comparisons, maybe_fold_or_comparisons):
>        Declare.
>        * gimple-fold.c (canonicalize_bool, same_bool_comparison_p,
>        same_bool_result_p): New.
>        (and_var_with_comparison, and_var_with_comparison_1,
>        and_comparisons_1, and_comparisons, maybe_fold_and_comparisons): New.
>        (or_var_with_comparison, or_var_with_comparison_1,
>        or_comparisons_1, or_comparisons, maybe_fold_or_comparisons): New.
>        * tree-ssa-reassoc.c (eliminate_redundant_comparison): Use
>        maybe_fold_and_comparisons or maybe_fold_or_comparisons instead
>        of combine_comparisons.
>        * tree-ssa-ifcombine.c (ifcombine_ifandif, ifcombine_iforif):
> Likewise.
>

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46909


-- 
H.J.