(This patch is for the bug 58728:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58728)
As in the bug report, consider the following loop:
int foo(unsigned int n)
{
if (n != 0)
if (n != 1)
if (n != 2)
if (n != 3)
if (n != 4)
return ++n;
return n;
}
The range test optimization should be able to merge all those five
conditions into one in reassoc pass, but I fails to do so. The reason
is that the phi arg of n is replaced by the constant it compares to in
case of == or != comparisons (in vrp pass). GCC checks there is no
side effect on n between any two neighboring conditions by examining
if they defined the same phi arg in the join node. But as the phi arg
is replace by a constant, the check fails.
This patch deals with this situation by considering the existence of
== or != comparisons, which is attached below (a text file is also
attached with proper tabs). Bootstrap and make check both get passed.
Any comment?
thanks,
Cong
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8a38316..9247222 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2013-10-31 Cong Hou <co...@google.com>
+
+ PR tree-optimization/58728
+ * tree-ssa-reassoc.c (suitable_cond_bb): Consider the situtation
+ that ==/!= comparisons between a variable and a constant may lead
+ to that the later phi arg of the variable is substitued by the
+ constant from prior passes, during range test optimization.
+
2013-10-14 David Malcolm <dmalc...@redhat.com>
* dumpfile.h (gcc::dump_manager): New class, to hold state
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 075d071..44a5e70 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2013-10-31 Cong Hou <co...@google.com>
+
+ PR tree-optimization/58728
+ * gcc.dg/tree-ssa/pr58728: New test.
+
2013-10-14 Tobias Burnus <bur...@net-b.de>
PR fortran/58658
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c
new file mode 100644
index 0000000..312aebc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
+
+int foo (unsigned int n)
+{
+ if (n != 0)
+ if (n != 1)
+ return ++n;
+ return n;
+}
+
+int bar (unsigned int n)
+{
+ if (n == 0)
+ ;
+ else if (n == 1)
+ ;
+ else
+ return ++n;
+ return n;
+}
+
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests" 2
"reassoc1" } } */
+/* { dg-final { cleanup-tree-dump "reassoc1" } } */
diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 6859518..bccf99f 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -2426,11 +2426,70 @@ suitable_cond_bb (basic_block bb, basic_block
test_bb, basic_block *other_bb,
for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple phi = gsi_stmt (gsi);
+ tree phi_arg = gimple_phi_arg_def (phi, e->dest_idx);
+ tree phi_arg2 = gimple_phi_arg_def (phi, e2->dest_idx);
+
/* If both BB and TEST_BB end with GIMPLE_COND, all PHI arguments
corresponding to BB and TEST_BB predecessor must be the same. */
- if (!operand_equal_p (gimple_phi_arg_def (phi, e->dest_idx),
- gimple_phi_arg_def (phi, e2->dest_idx), 0))
- {
+ if (!operand_equal_p (phi_arg, phi_arg2, 0))
+ {
+ /* If the condition in BB or TEST_BB is an NE or EQ comparison like
+ if (n != N) or if (n == N), it is possible that the corresponding
+ def of n in the phi function is replaced by N. We should still allow
+ range test optimization in this case. */
+
+ tree lhs = NULL, rhs = NULL,
+ lhs2 = NULL, rhs2 = NULL;
+ bool is_eq_expr = is_cond && (gimple_cond_code (stmt) == NE_EXPR
+ || gimple_cond_code (stmt) == EQ_EXPR)
+ && TREE_CODE (phi_arg) == INTEGER_CST;
+
+ if (is_eq_expr)
+ {
+ lhs = gimple_cond_lhs (stmt);
+ rhs = gimple_cond_rhs (stmt);
+
+ if (operand_equal_p (lhs, phi_arg, 0))
+ {
+ tree t = lhs;
+ lhs = rhs;
+ rhs = t;
+ }
+ if (operand_equal_p (rhs, phi_arg, 0)
+ && operand_equal_p (lhs, phi_arg2, 0))
+ continue;
+ }
+
+ gimple stmt2 = last_stmt (test_bb);
+ bool is_eq_expr2 = gimple_code (stmt2) == GIMPLE_COND
+ && (gimple_cond_code (stmt2) == NE_EXPR
+ || gimple_cond_code (stmt2) == EQ_EXPR)
+ && TREE_CODE (phi_arg2) == INTEGER_CST;
+
+ if (is_eq_expr2)
+ {
+ lhs2 = gimple_cond_lhs (stmt2);
+ rhs2 = gimple_cond_rhs (stmt2);
+
+ if (operand_equal_p (lhs2, phi_arg2, 0))
+ {
+ tree t = lhs2;
+ lhs2 = rhs2;
+ rhs2 = t;
+ }
+ if (operand_equal_p (rhs2, phi_arg2, 0)
+ && operand_equal_p (lhs2, phi_arg, 0))
+ continue;
+ }
+
+ if (is_eq_expr && is_eq_expr2)
+ {
+ if (operand_equal_p (rhs, phi_arg, 0)
+ && operand_equal_p (rhs2, phi_arg2, 0)
+ && operand_equal_p (lhs, lhs2, 0))
+ continue;
+ }
+
/* Otherwise, if one of the blocks doesn't end with GIMPLE_COND,
one of the PHIs should have the lhs of the last stmt in
that block as PHI arg and that PHI should have 0 or 1
@@ -2438,21 +2497,16 @@ suitable_cond_bb (basic_block bb, basic_block
test_bb, basic_block *other_bb,
considered. */
if (!is_cond)
{
- if (gimple_phi_arg_def (phi, e->dest_idx)
- == gimple_assign_lhs (stmt)
- && (integer_zerop (gimple_phi_arg_def (phi, e2->dest_idx))
- || integer_onep (gimple_phi_arg_def (phi,
- e2->dest_idx))))
+ if (phi_arg == gimple_assign_lhs (stmt)
+ && (integer_zerop (phi_arg2) || integer_onep (phi_arg2)))
continue;
}
else
{
gimple test_last = last_stmt (test_bb);
if (gimple_code (test_last) != GIMPLE_COND
- && gimple_phi_arg_def (phi, e2->dest_idx)
- == gimple_assign_lhs (test_last)
- && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx))
- || integer_onep (gimple_phi_arg_def (phi, e->dest_idx))))
+ && phi_arg2 == gimple_assign_lhs (test_last)
+ && (integer_zerop (phi_arg) || integer_onep (phi_arg)))
continue;
}
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8a38316..9247222 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2013-10-31 Cong Hou <co...@google.com>
+
+ PR tree-optimization/58728
+ * tree-ssa-reassoc.c (suitable_cond_bb): Consider the situtation
+ that ==/!= comparisons between a variable and a constant may lead
+ to that the later phi arg of the variable is substitued by the
+ constant from prior passes, during range test optimization.
+
2013-10-14 David Malcolm <dmalc...@redhat.com>
* dumpfile.h (gcc::dump_manager): New class, to hold state
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 075d071..44a5e70 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2013-10-31 Cong Hou <co...@google.com>
+
+ PR tree-optimization/58728
+ * gcc.dg/tree-ssa/pr58728: New test.
+
2013-10-14 Tobias Burnus <bur...@net-b.de>
PR fortran/58658
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c
new file mode 100644
index 0000000..312aebc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
+
+int foo (unsigned int n)
+{
+ if (n != 0)
+ if (n != 1)
+ return ++n;
+ return n;
+}
+
+int bar (unsigned int n)
+{
+ if (n == 0)
+ ;
+ else if (n == 1)
+ ;
+ else
+ return ++n;
+ return n;
+}
+
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests" 2 "reassoc1" } }
*/
+/* { dg-final { cleanup-tree-dump "reassoc1" } } */
diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 6859518..bccf99f 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -2426,11 +2426,70 @@ suitable_cond_bb (basic_block bb, basic_block test_bb,
basic_block *other_bb,
for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple phi = gsi_stmt (gsi);
+ tree phi_arg = gimple_phi_arg_def (phi, e->dest_idx);
+ tree phi_arg2 = gimple_phi_arg_def (phi, e2->dest_idx);
+
/* If both BB and TEST_BB end with GIMPLE_COND, all PHI arguments
corresponding to BB and TEST_BB predecessor must be the same. */
- if (!operand_equal_p (gimple_phi_arg_def (phi, e->dest_idx),
- gimple_phi_arg_def (phi, e2->dest_idx), 0))
- {
+ if (!operand_equal_p (phi_arg, phi_arg2, 0))
+ {
+ /* If the condition in BB or TEST_BB is an NE or EQ comparison like
+ if (n != N) or if (n == N), it is possible that the corresponding
+ def of n in the phi function is replaced by N. We should still allow
+ range test optimization in this case. */
+
+ tree lhs = NULL, rhs = NULL,
+ lhs2 = NULL, rhs2 = NULL;
+ bool is_eq_expr = is_cond && (gimple_cond_code (stmt) == NE_EXPR
+ || gimple_cond_code (stmt) == EQ_EXPR)
+ && TREE_CODE (phi_arg) == INTEGER_CST;
+
+ if (is_eq_expr)
+ {
+ lhs = gimple_cond_lhs (stmt);
+ rhs = gimple_cond_rhs (stmt);
+
+ if (operand_equal_p (lhs, phi_arg, 0))
+ {
+ tree t = lhs;
+ lhs = rhs;
+ rhs = t;
+ }
+ if (operand_equal_p (rhs, phi_arg, 0)
+ && operand_equal_p (lhs, phi_arg2, 0))
+ continue;
+ }
+
+ gimple stmt2 = last_stmt (test_bb);
+ bool is_eq_expr2 = gimple_code (stmt2) == GIMPLE_COND
+ && (gimple_cond_code (stmt2) == NE_EXPR
+ || gimple_cond_code (stmt2) == EQ_EXPR)
+ && TREE_CODE (phi_arg2) == INTEGER_CST;
+
+ if (is_eq_expr2)
+ {
+ lhs2 = gimple_cond_lhs (stmt2);
+ rhs2 = gimple_cond_rhs (stmt2);
+
+ if (operand_equal_p (lhs2, phi_arg2, 0))
+ {
+ tree t = lhs2;
+ lhs2 = rhs2;
+ rhs2 = t;
+ }
+ if (operand_equal_p (rhs2, phi_arg2, 0)
+ && operand_equal_p (lhs2, phi_arg, 0))
+ continue;
+ }
+
+ if (is_eq_expr && is_eq_expr2)
+ {
+ if (operand_equal_p (rhs, phi_arg, 0)
+ && operand_equal_p (rhs2, phi_arg2, 0)
+ && operand_equal_p (lhs, lhs2, 0))
+ continue;
+ }
+
/* Otherwise, if one of the blocks doesn't end with GIMPLE_COND,
one of the PHIs should have the lhs of the last stmt in
that block as PHI arg and that PHI should have 0 or 1
@@ -2438,21 +2497,16 @@ suitable_cond_bb (basic_block bb, basic_block test_bb,
basic_block *other_bb,
considered. */
if (!is_cond)
{
- if (gimple_phi_arg_def (phi, e->dest_idx)
- == gimple_assign_lhs (stmt)
- && (integer_zerop (gimple_phi_arg_def (phi, e2->dest_idx))
- || integer_onep (gimple_phi_arg_def (phi,
- e2->dest_idx))))
+ if (phi_arg == gimple_assign_lhs (stmt)
+ && (integer_zerop (phi_arg2) || integer_onep (phi_arg2)))
continue;
}
else
{
gimple test_last = last_stmt (test_bb);
if (gimple_code (test_last) != GIMPLE_COND
- && gimple_phi_arg_def (phi, e2->dest_idx)
- == gimple_assign_lhs (test_last)
- && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx))
- || integer_onep (gimple_phi_arg_def (phi, e->dest_idx))))
+ && phi_arg2 == gimple_assign_lhs (test_last)
+ && (integer_zerop (phi_arg) || integer_onep (phi_arg)))
continue;
}
