* tree-ssa-dom.c (record_dominating_conditions): New function.

	(dom_opt_finalize_block, get_eq_expr_value): Use it.

	* gcc.dg/tree-ssa/20040624-1.c: New test.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@83597 138bc75d-0d04-0410-961f-82ee72b054a4

4 files changed, 207 insertions, 0 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d50d7f061b5..9876fc878ae 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,8 @@
+2004-06-24  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-dom.c (record_dominating_conditions): New function.
+	(dom_opt_finalize_block, get_eq_expr_value): Use it.
+
 2004-06-24  Richard Sandiford  <rsandifo@redhat.com>
 
 	* calls.c (shift_returned_value): Fix handling of non-integer
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 07f99b51338..f7acf36ee0b 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2004-06-24  Jeff Law  <law@redhat.com>
+
+	* gcc.dg/tree-ssa/20040624-1.c: New test.
+
 2004-06-24  Richard Sandiford  <rsandifo@redhat.com>
 
 	* gcc.c-torture/compile/20040624-1.c: New test.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/20040624-1.c b/gcc/testsuite/gcc.dg/tree-ssa/20040624-1.c
new file mode 100644
index 00000000000..54f37433d95
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/20040624-1.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-dom1" } */
+  
+void bar1 (void);
+void bar2 (void);
+
+void
+foo (unsigned int a, unsigned int b)
+{
+  if (a >= b)
+    bar1 ();
+  else if (a <= b)
+    bar2 ();
+}
+
+/* The second conditional is redundant since we know it must be
+   true (to reach the second condition we know a < b via the first
+   conditional.  */
+
+/* { dg-final { scan-tree-dump-times "if " 1 "dom1" } } */
+
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 2be24ae1c8d..a4151423cf3 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -226,6 +226,7 @@ static hashval_t avail_expr_hash (const void *);
 static int avail_expr_eq (const void *, const void *);
 static void htab_statistics (FILE *, htab_t);
 static void record_cond (tree, tree, varray_type *);
+static void record_dominating_conditions (tree, varray_type *);
 static void record_const_or_copy (tree, tree, varray_type *);
 static void record_equality (tree, tree, varray_type *);
 static tree update_rhs_and_lookup_avail_expr (tree, tree, varray_type *,
@@ -1228,6 +1229,7 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
 	  if (TREE_CODE_CLASS (cond_code) == '<')
 	    {
 	      record_cond (cond, boolean_true_node, &bd->avail_exprs);
+	      record_dominating_conditions (cond, &bd->avail_exprs);
 	      record_cond (inverted, boolean_false_node, &bd->avail_exprs);
 	    }
 	  else if (cond_code == SSA_NAME)
@@ -1257,6 +1259,7 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
 	    {
 	      record_cond (cond, boolean_false_node, &bd->avail_exprs);
 	      record_cond (inverted, boolean_true_node, &bd->avail_exprs);
+	      record_dominating_conditions (inverted, &bd->avail_exprs);
 	    }
 	  else if (cond_code == SSA_NAME)
 	    record_const_or_copy (cond, boolean_false_node,
@@ -1606,6 +1609,178 @@ record_cond (tree cond, tree value, varray_type *block_avail_exprs_p)
     free (element);
 }
 
+/* COND is a condition which is known to be true.   Record variants of
+   COND which must also be true.
+
+   For example, if a < b is true, then a <= b must also be true.  */
+
+static void
+record_dominating_conditions (tree cond, varray_type *block_avail_exprs_p)
+{
+  switch (TREE_CODE (cond))
+    {
+    case LT_EXPR:
+      record_cond (build2 (LE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (ORDERED_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (NE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (LTGT_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      break;
+
+    case GT_EXPR:
+      record_cond (build2 (GE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (ORDERED_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (NE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (LTGT_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      break;
+
+    case GE_EXPR:
+    case LE_EXPR:
+      record_cond (build2 (ORDERED_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      break;
+
+    case EQ_EXPR:
+      record_cond (build2 (ORDERED_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (LE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (GE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      break;
+
+    case UNORDERED_EXPR:
+      record_cond (build2 (NE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (UNLE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (UNGE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (UNEQ_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (UNLT_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (UNGT_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      break;
+
+    case UNLT_EXPR:
+      record_cond (build2 (UNLE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (NE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      break;
+
+    case UNGT_EXPR:
+      record_cond (build2 (UNGE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (NE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      break;
+
+    case UNEQ_EXPR:
+      record_cond (build2 (UNLE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (UNGE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      break;
+
+    case LTGT_EXPR:
+      record_cond (build2 (NE_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+      record_cond (build2 (ORDERED_EXPR, boolean_type_node,
+			   TREE_OPERAND (cond, 0),
+			   TREE_OPERAND (cond, 1)),
+		   boolean_true_node,
+		   block_avail_exprs_p);
+
+    default:
+      break;
+    }
+}
+
 /* A helper function for record_const_or_copy and record_equality.
    Do the work of recording the value and undo info.  */
 
@@ -3044,6 +3219,7 @@ get_eq_expr_value (tree if_stmt,
 	  if (true_arm)
 	    {
 	      record_cond (cond, boolean_true_node, block_avail_exprs_p);
+	      record_dominating_conditions (cond, block_avail_exprs_p);
 	      record_cond (inverted, boolean_false_node, block_avail_exprs_p);
 
 	      if (TREE_CONSTANT (op1))
@@ -3062,6 +3238,7 @@ get_eq_expr_value (tree if_stmt,
 	    {
 
 	      record_cond (inverted, boolean_true_node, block_avail_exprs_p);
+	      record_dominating_conditions (inverted, block_avail_exprs_p);
 	      record_cond (cond, boolean_false_node, block_avail_exprs_p);
 
 	      if (TREE_CONSTANT (op1))