Patchwork Handling == or != comparisons that may affect range test optimization.

login
register
mail settings
Submitter Cong Hou
Date Nov. 1, 2013, 12:03 a.m.
Message ID <CAK=A3=2=9GqGSA4AqAYkMuuZ7YqT11uRbSRr7woGuW=xZRXeBA@mail.gmail.com>
Download mbox | patch
Permalink /patch/287686/
State New
Headers show

Comments

Cong Hou - Nov. 1, 2013, 12:03 a.m.
(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




      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  <congh@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  <dmalcolm@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  <congh@google.com>
+
+	PR tree-optimization/58728
+	* gcc.dg/tree-ssa/pr58728: New test.
+
 2013-10-14  Tobias Burnus  <burnus@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;
 	    }
Jeff Law - Nov. 5, 2013, 8:23 p.m.
On 10/31/13 18:03, Cong Hou wrote:
> (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?

+	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;
+	  }

Can you factor those two hunks of nearly identical code into a single 
function and call it twice?  I'm also curious if you really need the 
code to swap lhs/rhs.  When can the LHS of a cond be an integer 
constant?  Don't we canonicalize it as <ssa_name> <COND> <constant>?

I'd probably write the ChangeLog as:

	* tree-ssa-reassoc.c (suitable_cond_bb): Handle constant PHI
	operands resulting from propagation of edge equivalences.


I'm also curious -- did this code show up in a particular benchmark, if 
so, which one?

jeff
Jakub Jelinek - Nov. 5, 2013, 8:53 p.m.
On Tue, Nov 05, 2013 at 01:23:00PM -0700, Jeff Law wrote:
> On 10/31/13 18:03, Cong Hou wrote:
> >(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.

I can't reproduce this, at least not on x86_64-linux with -O2,
the ifcombine pass already merges those.

	Jakub
Cong Hou - Nov. 5, 2013, 9:35 p.m.
It seems there are some changes in GCC. But if you change the type of
n into signed int, the issue appears again:


int foo(int n)
{
   if (n != 0)
   if (n != 1)
   if (n != 2)
   if (n != 3)
   if (n != 4)
     return ++n;
   return n;
}

Also, ifcombine also suffers from the same issue here.


thanks,
Cong


On Tue, Nov 5, 2013 at 12:53 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Tue, Nov 05, 2013 at 01:23:00PM -0700, Jeff Law wrote:
>> On 10/31/13 18:03, Cong Hou wrote:
>> >(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.
>
> I can't reproduce this, at least not on x86_64-linux with -O2,
> the ifcombine pass already merges those.
>
>         Jakub
Cong Hou - Nov. 5, 2013, 10 p.m.
On Tue, Nov 5, 2013 at 12:23 PM, Jeff Law <law@redhat.com> wrote:
> On 10/31/13 18:03, Cong Hou wrote:
>>
>> (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?
>
>
> +       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;
> +         }
>
> Can you factor those two hunks of nearly identical code into a single
> function and call it twice?  I'm also curious if you really need the code to
> swap lhs/rhs.  When can the LHS of a cond be an integer constant?  Don't we
> canonicalize it as <ssa_name> <COND> <constant>?


I was not aware that the comparison between a variable and a constant
will always be canonicalized as <ssa_name> <COND> <constant>. Then I
will remove the swap, and as the code is much smaller, I think it may
not be necessary to create a function for them.


>
> I'd probably write the ChangeLog as:
>
>         * tree-ssa-reassoc.c (suitable_cond_bb): Handle constant PHI
>         operands resulting from propagation of edge equivalences.
>
>

OK, much better than mine ;)


> I'm also curious -- did this code show up in a particular benchmark, if so,
> which one?

I didn't find this problem from any benchmark, but from another
concern about loop upper bound estimation. Look at the following code:

int foo(unsigned int n, int r)
{
  int i;
  if (n > 0)
    if (n < 4)
    {
      do {
         --n;
         r *= 2;
      } while (n > 0);
    }
  return r+n;
}


In order to get the upper bound of the loop in this function, GCC
traverses conditions n<4 and n>0 separately and tries to get any
useful information. But as those two conditions cannot be combined
into one due to this issue (note that n>0 will be transformed into
n!=0), when GCC sees n<4, it will consider the possibility that n may
be equal to 0, in which case the upper bound is UINT_MAX. If those two
conditions can be combined into one, which is n-1<=2, then we can get
the correct upper bound of the loop.


thanks,
Cong

>
> jeff
Jeff Law - Nov. 5, 2013, 10:16 p.m.
On 11/05/13 15:00, Cong Hou wrote:
>>
>> Can you factor those two hunks of nearly identical code into a single
>> function and call it twice?  I'm also curious if you really need the code to
>> swap lhs/rhs.  When can the LHS of a cond be an integer constant?  Don't we
>> canonicalize it as <ssa_name> <COND> <constant>?
>
>
> I was not aware that the comparison between a variable and a constant
> will always be canonicalized as <ssa_name> <COND> <constant>. Then I
> will remove the swap, and as the code is much smaller, I think it may
> not be necessary to create a function for them.
Hmm, looking at is_gimple_condexpr, it appears to accept both forms:

/*  Return true if T is a GIMPLE condition.  */

bool
is_gimple_condexpr (tree t)
{
   return (is_gimple_val (t) || (COMPARISON_CLASS_P (t)
                                 && !tree_could_throw_p (t)
                                 && is_gimple_val (TREE_OPERAND (t, 0))
                                 && is_gimple_val (TREE_OPERAND (t, 1))));
}


Sigh.  So you probably still need to handle both forms :(


>
> I didn't find this problem from any benchmark, but from another
> concern about loop upper bound estimation. Look at the following code:
>
> int foo(unsigned int n, int r)
> {
>    int i;
>    if (n > 0)
>      if (n < 4)
>      {
>        do {
>           --n;
>           r *= 2;
>        } while (n > 0);
>      }
>    return r+n;
> }
>
>
> In order to get the upper bound of the loop in this function, GCC
> traverses conditions n<4 and n>0 separately and tries to get any
> useful information. But as those two conditions cannot be combined
> into one due to this issue (note that n>0 will be transformed into
> n!=0), when GCC sees n<4, it will consider the possibility that n may
> be equal to 0, in which case the upper bound is UINT_MAX. If those two
> conditions can be combined into one, which is n-1<=2, then we can get
> the correct upper bound of the loop.
Ah.  Ok. Thanks.

jeff

Patch

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  <congh@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  <dmalcolm@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  <congh@google.com>
+
+ PR tree-optimization/58728
+ * gcc.dg/tree-ssa/pr58728: New test.
+
 2013-10-14  Tobias Burnus  <burnus@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