[PATCH] Handle GIMPLE_ASSIGNs with different vuse in gimple_equal_p

[PATCH] Handle GIMPLE_ASSIGNs with different vuse in gimple_equal_p

[Tom de Vries]

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

Richard,

Consider the test-case test.c:
...
int z;
int x;

void
f (int c, int d)
{
   if (c)
     z = 5;
   else
     {
       if (d)
	x = 4;
       z = 5;
     }
}
...

Atm, we don't tail-merge the 'z = 5' blocks, because gimple_equal_p returns 
false for the 'z = 5' statements. The relevant code is this:
...
       if (TREE_CODE (lhs1) != SSA_NAME
           && TREE_CODE (lhs2) != SSA_NAME)
         return (vn_valueize (gimple_vdef (s1))
                 == vn_valueize (gimple_vdef (s2)));
...
The vdefs of the 'z = 5' statements are different, because the incoming vuses 
are different.

This patch handles GIMPLE_ASSIGNs with different vuse in gimple_equal_p, by 
doing a structural comparison.

Bootstrapped and regtested on x86_64.

OK for trunk?

Thanks,
- Tom

2013-11-06  Tom de Vries  <tom@codesourcery.com>

	* tree-ssa-tail-merge.c (gimple_equal_p): Add test for structural
	equality for GIMPLE_ASSIGN.

	* gcc.dg/tail-merge-store.c: New test.

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

diff --git a/gcc/testsuite/gcc.dg/tail-merge-store.c b/gcc/testsuite/gcc.dg/tail-merge-store.c
new file mode 100644
index 0000000..1aefbdc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tail-merge-store.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-tail-merge -fdump-tree-pre" } */
+
+int z;
+int x;
+
+void
+f (int c, int d)
+{
+  if (c)
+    z = 5;
+  else
+    {
+      if (d)
+	x = 4;
+      z = 5;
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "duplicate of" 1 "pre"} } */
+/* { dg-final { scan-tree-dump-times "z = 5" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
index 98b5882..43516a7 100644
--- a/gcc/tree-ssa-tail-merge.c
+++ b/gcc/tree-ssa-tail-merge.c
@@ -1173,8 +1173,47 @@ gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
       lhs2 = gimple_get_lhs (s2);
       if (TREE_CODE (lhs1) != SSA_NAME
 	  && TREE_CODE (lhs2) != SSA_NAME)
-	return (vn_valueize (gimple_vdef (s1))
-		== vn_valueize (gimple_vdef (s2)));
+	{
+	  /* If the vdef is the same, it's the same statement.  */
+	  if (vn_valueize (gimple_vdef (s1))
+	      == vn_valueize (gimple_vdef (s2)))
+	    return true;
+
+	  /* If the vdef is not the same but the vuse is the same, it's not the
+	     same stmt.  */
+	  if (vn_valueize (gimple_vuse (s1))
+	      == vn_valueize (gimple_vuse (s2)))
+	    return false;
+	  /* If the vdef is not the same and the vuse is not the same, it might be
+	     same stmt.  */
+
+	  /* Test for structural equality.  */
+	  if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s1)
+	      || (gimple_assign_nontemporal_move_p (s1)
+		  != gimple_assign_nontemporal_move_p (s2)))
+	    return false;
+
+	  if (!operand_equal_p (lhs1, lhs2, 0))
+	    return false;
+
+	  t1 = gimple_assign_rhs1 (s1);
+	  t2 = gimple_assign_rhs1 (s2);
+	  if (!gimple_operand_equal_value_p (t1, t2))
+	    return false;
+
+	  t1 = gimple_assign_rhs2 (s1);
+	  t2 = gimple_assign_rhs2 (s2);
+	  if (!gimple_operand_equal_value_p (t1, t2))
+	    return false;
+
+	  t1 = gimple_assign_rhs3 (s1);
+	  t2 = gimple_assign_rhs3 (s2);
+	  if (!gimple_operand_equal_value_p (t1, t2))
+	    return false;
+
+	  /* Same structure.  */
+	  return true;
+	}
       else if (TREE_CODE (lhs1) == SSA_NAME
 	       && TREE_CODE (lhs2) == SSA_NAME)
 	return vn_valueize (lhs1) == vn_valueize (lhs2);

Re: [PATCH] Handle GIMPLE_ASSIGNs with different vuse in gimple_equal_p

[Bernhard Reutner-Fischer]

On Sat, Nov 09, 2013 at 05:30:00PM +0100, Tom de Vries wrote:
>Richard,
>
>Consider the test-case test.c:
>...
>int z;
>int x;
>
>void
>f (int c, int d)
>{
>  if (c)
>    z = 5;
>  else
>    {
>      if (d)
>	x = 4;
>      z = 5;
>    }
>}
>...
>
>Atm, we don't tail-merge the 'z = 5' blocks, because gimple_equal_p
>returns false for the 'z = 5' statements. The relevant code is this:
>...
>      if (TREE_CODE (lhs1) != SSA_NAME
>          && TREE_CODE (lhs2) != SSA_NAME)
>        return (vn_valueize (gimple_vdef (s1))
>                == vn_valueize (gimple_vdef (s2)));
>...
>The vdefs of the 'z = 5' statements are different, because the
>incoming vuses are different.
>
>This patch handles GIMPLE_ASSIGNs with different vuse in
>gimple_equal_p, by doing a structural comparison.
>
>Bootstrapped and regtested on x86_64.
>
>OK for trunk?
>
>Thanks,
>- Tom
>
>2013-11-06  Tom de Vries  <tom@codesourcery.com>
>
>	* tree-ssa-tail-merge.c (gimple_equal_p): Add test for structural
>	equality for GIMPLE_ASSIGN.
>
>	* gcc.dg/tail-merge-store.c: New test.

>diff --git a/gcc/testsuite/gcc.dg/tail-merge-store.c b/gcc/testsuite/gcc.dg/tail-merge-store.c
>new file mode 100644
>index 0000000..1aefbdc
>--- /dev/null
>+++ b/gcc/testsuite/gcc.dg/tail-merge-store.c
>@@ -0,0 +1,22 @@
>+/* { dg-do compile } */
>+/* { dg-options "-O2 -ftree-tail-merge -fdump-tree-pre" } */
>+
>+int z;
>+int x;
>+
>+void
>+f (int c, int d)
>+{
>+  if (c)
>+    z = 5;
>+  else
>+    {
>+      if (d)
>+	x = 4;
>+      z = 5;
>+    }
>+}
>+
>+/* { dg-final { scan-tree-dump-times "duplicate of" 1 "pre"} } */
>+/* { dg-final { scan-tree-dump-times "z = 5" 1 "pre"} } */
>+/* { dg-final { cleanup-tree-dump "pre" } } */
>diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
>index 98b5882..43516a7 100644
>--- a/gcc/tree-ssa-tail-merge.c
>+++ b/gcc/tree-ssa-tail-merge.c
>@@ -1173,8 +1173,47 @@ gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
>       lhs2 = gimple_get_lhs (s2);
>       if (TREE_CODE (lhs1) != SSA_NAME
> 	  && TREE_CODE (lhs2) != SSA_NAME)
>-	return (vn_valueize (gimple_vdef (s1))
>-		== vn_valueize (gimple_vdef (s2)));
>+	{
>+	  /* If the vdef is the same, it's the same statement.  */
>+	  if (vn_valueize (gimple_vdef (s1))
>+	      == vn_valueize (gimple_vdef (s2)))
>+	    return true;
>+
>+	  /* If the vdef is not the same but the vuse is the same, it's not the
>+	     same stmt.  */
>+	  if (vn_valueize (gimple_vuse (s1))
>+	      == vn_valueize (gimple_vuse (s2)))
>+	    return false;
>+	  /* If the vdef is not the same and the vuse is not the same, it might be
>+	     same stmt.  */
>+
>+	  /* Test for structural equality.  */
>+	  if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s1)

typo, second one should be s2.
thanks,

>+	      || (gimple_assign_nontemporal_move_p (s1)
>+		  != gimple_assign_nontemporal_move_p (s2)))
>+	    return false;
>+
>+	  if (!operand_equal_p (lhs1, lhs2, 0))
>+	    return false;
>+
>+	  t1 = gimple_assign_rhs1 (s1);
>+	  t2 = gimple_assign_rhs1 (s2);
>+	  if (!gimple_operand_equal_value_p (t1, t2))
>+	    return false;
>+
>+	  t1 = gimple_assign_rhs2 (s1);
>+	  t2 = gimple_assign_rhs2 (s2);
>+	  if (!gimple_operand_equal_value_p (t1, t2))
>+	    return false;
>+
>+	  t1 = gimple_assign_rhs3 (s1);
>+	  t2 = gimple_assign_rhs3 (s2);
>+	  if (!gimple_operand_equal_value_p (t1, t2))
>+	    return false;
>+
>+	  /* Same structure.  */
>+	  return true;
>+	}
>       else if (TREE_CODE (lhs1) == SSA_NAME
> 	       && TREE_CODE (lhs2) == SSA_NAME)
> 	return vn_valueize (lhs1) == vn_valueize (lhs2);

Re: [PATCH] Handle GIMPLE_ASSIGNs with different vuse in gimple_equal_p

[Richard Biener]

On Sat, 9 Nov 2013, Tom de Vries wrote:

> Richard,
> 
> Consider the test-case test.c:
> ...
> int z;
> int x;
> 
> void
> f (int c, int d)
> {
>   if (c)
>     z = 5;
>   else
>     {
>       if (d)
> 	x = 4;
>       z = 5;
>     }
> }
> ...
> 
> Atm, we don't tail-merge the 'z = 5' blocks, because gimple_equal_p returns
> false for the 'z = 5' statements. The relevant code is this:
> ...
>       if (TREE_CODE (lhs1) != SSA_NAME
>           && TREE_CODE (lhs2) != SSA_NAME)
>         return (vn_valueize (gimple_vdef (s1))
>                 == vn_valueize (gimple_vdef (s2)));
> ...
> The vdefs of the 'z = 5' statements are different, because the incoming vuses
> are different.
> 
> This patch handles GIMPLE_ASSIGNs with different vuse in gimple_equal_p, by
> doing a structural comparison.
> 
> Bootstrapped and regtested on x86_64.
> 
> OK for trunk?

Comments inline


diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
index 98b5882..43516a7 100644
--- a/gcc/tree-ssa-tail-merge.c
+++ b/gcc/tree-ssa-tail-merge.c
@@ -1173,8 +1173,47 @@ gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
       lhs2 = gimple_get_lhs (s2);
       if (TREE_CODE (lhs1) != SSA_NAME
 	  && TREE_CODE (lhs2) != SSA_NAME)
-	return (vn_valueize (gimple_vdef (s1))
-		== vn_valueize (gimple_vdef (s2)));
+	{
+	  /* If the vdef is the same, it's the same statement.  */
+	  if (vn_valueize (gimple_vdef (s1))
+	      == vn_valueize (gimple_vdef (s2)))
+	    return true;
+
+	  /* If the vdef is not the same but the vuse is the same, it's not the
+	     same stmt.  */
+	  if (vn_valueize (gimple_vuse (s1))
+	      == vn_valueize (gimple_vuse (s2)))
+	    return false;

What's the logic behind this?  We want to use VN to get more "positive"
results - doing a negative early out looks suspicious to me ...

+	  /* If the vdef is not the same and the vuse is not the same, it might be
+	     same stmt.  */
+
+	  /* Test for structural equality.  */
+	  if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s1)

s2

+	      || (gimple_assign_nontemporal_move_p (s1)
+		  != gimple_assign_nontemporal_move_p (s2)))

I don't think we should care (it'll be false - a later pass sets it,
it's an optimization hint, not a correctness issue).  More interesting
would be to assert that has_volatile_ops is the same if the operands
turned out to be the same.

+	    return false;
+
+	  if (!operand_equal_p (lhs1, lhs2, 0))
+	    return false;
+
+	  t1 = gimple_assign_rhs1 (s1);
+	  t2 = gimple_assign_rhs1 (s2);
+	  if (!gimple_operand_equal_value_p (t1, t2))
+	    return false;
+
+	  t1 = gimple_assign_rhs2 (s1);
+	  t2 = gimple_assign_rhs2 (s2);
+	  if (!gimple_operand_equal_value_p (t1, t2))
+	    return false;
+
+	  t1 = gimple_assign_rhs3 (s1);
+	  t2 = gimple_assign_rhs3 (s2);
+	  if (!gimple_operand_equal_value_p (t1, t2))
+	    return false;

  for (i = 1; i < gimple_num_ops (s1); ++i)
    t1 = gimple_op (s1, i);
    ...

but I think you should only compare rhs1 and thus only handle
GIMPLE_ASSIGN_SINGLEs this way - the others have a SSA name
lhs.

That makes the whole thing just

      if (TREE_CODE (lhs1) != SSA_NAME
          && TREE_CODE (lhs2) != SSA_NAME)
        {
           if (vn_valueize (gimple_vdef (s1))
               == vn_valueize (gimple_vdef (s2)))
	     return true;
           return operand_equal_p (lhs1, lhs2, 0)
               && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
                                                 gimple_assign_rhs2 (s2));
        }

Ok with doing it this way.

Thanks,
Richard.

+	  /* Same structure.  */
+	  return true;
+	}
       else if (TREE_CODE (lhs1) == SSA_NAME
 	       && TREE_CODE (lhs2) == SSA_NAME)
 	return vn_valueize (lhs1) == vn_valueize (lhs2);

Re: [PATCH] Handle GIMPLE_ASSIGNs with different vuse in gimple_equal_p

[Tom de Vries]

On 11/11/13 10:50, Richard Biener wrote:
> On Sat, 9 Nov 2013, Tom de Vries wrote:
>> Bootstrapped and regtested on x86_64.
>>
>> OK for trunk?
> 
> Comments inline
> 
> 
> diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
> index 98b5882..43516a7 100644
> --- a/gcc/tree-ssa-tail-merge.c
> +++ b/gcc/tree-ssa-tail-merge.c
> @@ -1173,8 +1173,47 @@ gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
>        lhs2 = gimple_get_lhs (s2);
>        if (TREE_CODE (lhs1) != SSA_NAME
>  	  && TREE_CODE (lhs2) != SSA_NAME)
> -	return (vn_valueize (gimple_vdef (s1))
> -		== vn_valueize (gimple_vdef (s2)));
> +	{
> +	  /* If the vdef is the same, it's the same statement.  */
> +	  if (vn_valueize (gimple_vdef (s1))
> +	      == vn_valueize (gimple_vdef (s2)))
> +	    return true;
> +
> +	  /* If the vdef is not the same but the vuse is the same, it's not the
> +	     same stmt.  */
> +	  if (vn_valueize (gimple_vuse (s1))
> +	      == vn_valueize (gimple_vuse (s2)))
> +	    return false;
> 

Richard,

> What's the logic behind this?
> We want to use VN to get more "positive"
> results

We can use it to get both positive and negative results faster.

> - doing a negative early out looks suspicious to me ...
> 

If the vdefs are the same, the VN has concluded that the statements are the
same. We have a positive early out.

If the vdefs are not the same, the VN has concluded that the statements are
different. But if the vuses are the same, the VN has concluded that the
statements are different because of structural difference. Which means there's
no sense in us repeating the structural comparison. We have a negative early out.

If the vdefs are not the same, the VN has concluded that the statements are
different. But if the vuses are different, the VN may have concluded that the
statements are different because of the different vuses. So it still makes sense
to try structural comparison.

> +	  /* If the vdef is not the same and the vuse is not the same, it might be
> +	     same stmt.  */
> +
> +	  /* Test for structural equality.  */
> +	  if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s1)
> 
> s2
> 
> +	      || (gimple_assign_nontemporal_move_p (s1)
> +		  != gimple_assign_nontemporal_move_p (s2)))
> 
> I don't think we should care (it'll be false - a later pass sets it,
> it's an optimization hint, not a correctness issue).  More interesting
> would be to assert that has_volatile_ops is the same if the operands
> turned out to be the same.
> 

OK.

> +	    return false;
> +
> +	  if (!operand_equal_p (lhs1, lhs2, 0))
> +	    return false;
> +
> +	  t1 = gimple_assign_rhs1 (s1);
> +	  t2 = gimple_assign_rhs1 (s2);
> +	  if (!gimple_operand_equal_value_p (t1, t2))
> +	    return false;
> +
> +	  t1 = gimple_assign_rhs2 (s1);
> +	  t2 = gimple_assign_rhs2 (s2);
> +	  if (!gimple_operand_equal_value_p (t1, t2))
> +	    return false;
> +
> +	  t1 = gimple_assign_rhs3 (s1);
> +	  t2 = gimple_assign_rhs3 (s2);
> +	  if (!gimple_operand_equal_value_p (t1, t2))
> +	    return false;
> 
>   for (i = 1; i < gimple_num_ops (s1); ++i)
>     t1 = gimple_op (s1, i);
>     ...
> 
> but I think you should only compare rhs1 and thus only handle
> GIMPLE_ASSIGN_SINGLEs this way - the others have a SSA name
> lhs.
> 

I see.

> That makes the whole thing just
> 
>       if (TREE_CODE (lhs1) != SSA_NAME
>           && TREE_CODE (lhs2) != SSA_NAME)
>         {
>            if (vn_valueize (gimple_vdef (s1))
>                == vn_valueize (gimple_vdef (s2)))
> 	     return true;
>            return operand_equal_p (lhs1, lhs2, 0)
>                && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
>                                                  gimple_assign_rhs2 (s2));
>         }
> 
> Ok with doing it this way.

I'll retest and checkin like this, unless you agree about the early out, which I
still think is a good idea, although the structural test is now much smaller.

Thanks,
- Tom

> 
> Thanks,
> Richard.
> 
> +	  /* Same structure.  */
> +	  return true;
> +	}
>        else if (TREE_CODE (lhs1) == SSA_NAME
>  	       && TREE_CODE (lhs2) == SSA_NAME)
>  	return vn_valueize (lhs1) == vn_valueize (lhs2);
> 

Re: [PATCH] Handle GIMPLE_ASSIGNs with different vuse in gimple_equal_p

[Richard Biener]

On Mon, 11 Nov 2013, Tom de Vries wrote:

> On 11/11/13 10:50, Richard Biener wrote:
> > On Sat, 9 Nov 2013, Tom de Vries wrote:
> >> Bootstrapped and regtested on x86_64.
> >>
> >> OK for trunk?
> > 
> > Comments inline
> > 
> > 
> > diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
> > index 98b5882..43516a7 100644
> > --- a/gcc/tree-ssa-tail-merge.c
> > +++ b/gcc/tree-ssa-tail-merge.c
> > @@ -1173,8 +1173,47 @@ gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
> >        lhs2 = gimple_get_lhs (s2);
> >        if (TREE_CODE (lhs1) != SSA_NAME
> >  	  && TREE_CODE (lhs2) != SSA_NAME)
> > -	return (vn_valueize (gimple_vdef (s1))
> > -		== vn_valueize (gimple_vdef (s2)));
> > +	{
> > +	  /* If the vdef is the same, it's the same statement.  */
> > +	  if (vn_valueize (gimple_vdef (s1))
> > +	      == vn_valueize (gimple_vdef (s2)))
> > +	    return true;
> > +
> > +	  /* If the vdef is not the same but the vuse is the same, it's not the
> > +	     same stmt.  */
> > +	  if (vn_valueize (gimple_vuse (s1))
> > +	      == vn_valueize (gimple_vuse (s2)))
> > +	    return false;
> > 
> 
> Richard,
> 
> > What's the logic behind this?
> > We want to use VN to get more "positive"
> > results
> 
> We can use it to get both positive and negative results faster.

I can get a negative result for free: "false" ;)

VN proves equivalency it doesn't prove non-equivalency - that's
simply its conservative fallback.

> > - doing a negative early out looks suspicious to me ...
> > 
> 
> If the vdefs are the same, the VN has concluded that the statements are the
> same. We have a positive early out.
> 
> If the vdefs are not the same, the VN has concluded that the statements are
> different. But if the vuses are the same, the VN has concluded that the
> statements are different because of structural difference. Which means there's
> no sense in us repeating the structural comparison. We have a negative early out.

Well, see above - it merely failed to prove equivalency, it didn't
actually conclude they are different.
 
> If the vdefs are not the same, the VN has concluded that the statements are
> different. But if the vuses are different, the VN may have concluded that the
> statements are different because of the different vuses. So it still makes sense
> to try structural comparison.
> 
> > +	  /* If the vdef is not the same and the vuse is not the same, it might be
> > +	     same stmt.  */
> > +
> > +	  /* Test for structural equality.  */
> > +	  if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s1)
> > 
> > s2
> > 
> > +	      || (gimple_assign_nontemporal_move_p (s1)
> > +		  != gimple_assign_nontemporal_move_p (s2)))
> > 
> > I don't think we should care (it'll be false - a later pass sets it,
> > it's an optimization hint, not a correctness issue).  More interesting
> > would be to assert that has_volatile_ops is the same if the operands
> > turned out to be the same.
> > 
> 
> OK.
> 
> > +	    return false;
> > +
> > +	  if (!operand_equal_p (lhs1, lhs2, 0))
> > +	    return false;
> > +
> > +	  t1 = gimple_assign_rhs1 (s1);
> > +	  t2 = gimple_assign_rhs1 (s2);
> > +	  if (!gimple_operand_equal_value_p (t1, t2))
> > +	    return false;
> > +
> > +	  t1 = gimple_assign_rhs2 (s1);
> > +	  t2 = gimple_assign_rhs2 (s2);
> > +	  if (!gimple_operand_equal_value_p (t1, t2))
> > +	    return false;
> > +
> > +	  t1 = gimple_assign_rhs3 (s1);
> > +	  t2 = gimple_assign_rhs3 (s2);
> > +	  if (!gimple_operand_equal_value_p (t1, t2))
> > +	    return false;
> > 
> >   for (i = 1; i < gimple_num_ops (s1); ++i)
> >     t1 = gimple_op (s1, i);
> >     ...
> > 
> > but I think you should only compare rhs1 and thus only handle
> > GIMPLE_ASSIGN_SINGLEs this way - the others have a SSA name
> > lhs.
> > 
> 
> I see.
> 
> > That makes the whole thing just
> > 
> >       if (TREE_CODE (lhs1) != SSA_NAME
> >           && TREE_CODE (lhs2) != SSA_NAME)
> >         {
> >            if (vn_valueize (gimple_vdef (s1))
> >                == vn_valueize (gimple_vdef (s2)))
> > 	     return true;
> >            return operand_equal_p (lhs1, lhs2, 0)
> >                && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
> >                                                  gimple_assign_rhs2 (s2));
> >         }
> > 
> > Ok with doing it this way.
> 
> I'll retest and checkin like this, unless you agree about the early out, which I
> still think is a good idea, although the structural test is now much smaller.

I think the early out is premature.

Richard.

Re: [PATCH] Handle GIMPLE_ASSIGNs with different vuse in gimple_equal_p

[Tom de Vries]

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

On 11-11-13 14:17, Richard Biener wrote:
> On Mon, 11 Nov 2013, Tom de Vries wrote:
>
>> On 11/11/13 10:50, Richard Biener wrote:
>>> On Sat, 9 Nov 2013, Tom de Vries wrote:
>>>> Bootstrapped and regtested on x86_64.
>>>>
>>>> OK for trunk?
>>>
>>> Comments inline
>>>
>>>
>>> diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
>>> index 98b5882..43516a7 100644
>>> --- a/gcc/tree-ssa-tail-merge.c
>>> +++ b/gcc/tree-ssa-tail-merge.c
>>> @@ -1173,8 +1173,47 @@ gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
>>>         lhs2 = gimple_get_lhs (s2);
>>>         if (TREE_CODE (lhs1) != SSA_NAME
>>>   	  && TREE_CODE (lhs2) != SSA_NAME)
>>> -	return (vn_valueize (gimple_vdef (s1))
>>> -		== vn_valueize (gimple_vdef (s2)));
>>> +	{
>>> +	  /* If the vdef is the same, it's the same statement.  */
>>> +	  if (vn_valueize (gimple_vdef (s1))
>>> +	      == vn_valueize (gimple_vdef (s2)))
>>> +	    return true;
>>> +
>>> +	  /* If the vdef is not the same but the vuse is the same, it's not the
>>> +	     same stmt.  */
>>> +	  if (vn_valueize (gimple_vuse (s1))
>>> +	      == vn_valueize (gimple_vuse (s2)))
>>> +	    return false;
>>>
>>
>> Richard,
>>
>>> What's the logic behind this?
>>> We want to use VN to get more "positive"
>>> results
>>
>> We can use it to get both positive and negative results faster.
>
> I can get a negative result for free: "false" ;)
>

Richard,

Indeed. But perhaps we could regard the question at hand from the perspective of 
both compilation effect and compilation speed ;)

> VN proves equivalency it doesn't prove non-equivalency - that's
> simply its conservative fallback.
>

Of course.

>>> - doing a negative early out looks suspicious to me ...
>>>
>>
>> If the vdefs are the same, the VN has concluded that the statements are the
>> same. We have a positive early out.
>>
>> If the vdefs are not the same, the VN has concluded that the statements are
>> different. But if the vuses are the same, the VN has concluded that the
>> statements are different because of structural difference. Which means there's
>> no sense in us repeating the structural comparison. We have a negative early out.
>
> Well, see above - it merely failed to prove equivalency, it didn't
> actually conclude they are different.
>

You're right, sloppy formulation on my part.

My question is, if VN has tried to prove equality of vdefs, and failed,
in what scenario could a structural comparison still prove them equal?

In case the vuses are not proven equal, there's an obvious reason why the vdefs 
are not proven equal, and structural comparison might indeed prove them equal.

But if the vuses are proven equal, that's not the reason why the vdefs are not 
proven equal. In which case it's hard for me to understand how a trivial 
structural check would beat VN.

I've browsed the VN code a bit and tried to construct examples where structural 
comparison beats VN, but did not manage.

I've also done a non-bootstrap build with attached patch, and a complete 
testrun, and was not able to trigger the assert.

So if you have any hunch about such a scenario, please let me know.

Thanks,
- Tom

>> If the vdefs are not the same, the VN has concluded that the statements are
>> different. But if the vuses are different, the VN may have concluded that the
>> statements are different because of the different vuses. So it still makes sense
>> to try structural comparison.
>>
>>> +	  /* If the vdef is not the same and the vuse is not the same, it might be
>>> +	     same stmt.  */
>>> +
>>> +	  /* Test for structural equality.  */
>>> +	  if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s1)
>>>
>>> s2
>>>
>>> +	      || (gimple_assign_nontemporal_move_p (s1)
>>> +		  != gimple_assign_nontemporal_move_p (s2)))
>>>
>>> I don't think we should care (it'll be false - a later pass sets it,
>>> it's an optimization hint, not a correctness issue).  More interesting
>>> would be to assert that has_volatile_ops is the same if the operands
>>> turned out to be the same.
>>>
>>
>> OK.
>>
>>> +	    return false;
>>> +
>>> +	  if (!operand_equal_p (lhs1, lhs2, 0))
>>> +	    return false;
>>> +
>>> +	  t1 = gimple_assign_rhs1 (s1);
>>> +	  t2 = gimple_assign_rhs1 (s2);
>>> +	  if (!gimple_operand_equal_value_p (t1, t2))
>>> +	    return false;
>>> +
>>> +	  t1 = gimple_assign_rhs2 (s1);
>>> +	  t2 = gimple_assign_rhs2 (s2);
>>> +	  if (!gimple_operand_equal_value_p (t1, t2))
>>> +	    return false;
>>> +
>>> +	  t1 = gimple_assign_rhs3 (s1);
>>> +	  t2 = gimple_assign_rhs3 (s2);
>>> +	  if (!gimple_operand_equal_value_p (t1, t2))
>>> +	    return false;
>>>
>>>    for (i = 1; i < gimple_num_ops (s1); ++i)
>>>      t1 = gimple_op (s1, i);
>>>      ...
>>>
>>> but I think you should only compare rhs1 and thus only handle
>>> GIMPLE_ASSIGN_SINGLEs this way - the others have a SSA name
>>> lhs.
>>>
>>
>> I see.
>>
>>> That makes the whole thing just
>>>
>>>        if (TREE_CODE (lhs1) != SSA_NAME
>>>            && TREE_CODE (lhs2) != SSA_NAME)
>>>          {
>>>             if (vn_valueize (gimple_vdef (s1))
>>>                 == vn_valueize (gimple_vdef (s2)))
>>> 	     return true;
>>>             return operand_equal_p (lhs1, lhs2, 0)
>>>                 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
>>>                                                   gimple_assign_rhs2 (s2));
>>>          }
>>>
>>> Ok with doing it this way.
>>
>> I'll retest and checkin like this, unless you agree about the early out, which I
>> still think is a good idea, although the structural test is now much smaller.
>
> I think the early out is premature.
>
> Richard.
>


[-- Attachment #2: tail-merge-neg-out-early.patch --]
[-- Type: text/x-patch, Size: 1358 bytes --]

commit ccc270253d3dac27f297919d6a7c253a23cc9827
Author: Tom de Vries <tom@codesourcery.com>
Date:   Mon Nov 11 21:23:47 2013 +0100

    Add neg_early_out assert

diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
index b1bc783..2d1b187 100644
--- a/gcc/tree-ssa-tail-merge.c
+++ b/gcc/tree-ssa-tail-merge.c
@@ -1243,15 +1243,26 @@ gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
       if (TREE_CODE (lhs1) != SSA_NAME
 	  && TREE_CODE (lhs2) != SSA_NAME)
 	{
+	  bool equal, neg_early_out;
+
 	  /* If the vdef is the same, it's the same statement.  */
 	  if (vn_valueize (gimple_vdef (s1))
 	      == vn_valueize (gimple_vdef (s2)))
 	    return true;
 
+	  neg_early_out = (vn_valueize (gimple_vuse (s1))
+			   == vn_valueize (gimple_vuse (s2)));
+
 	  /* Test for structural equality.  */
-	  return (operand_equal_p (lhs1, lhs2, 0)
-		  && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
-						   gimple_assign_rhs1 (s2)));
+	  equal = (operand_equal_p (lhs1, lhs2, 0)
+		   && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
+						    gimple_assign_rhs1 (s2)));
+
+	  /* Assert that neg_early_out implies !equal.	*/
+	  /* A implies B == ! (A && !B)*/
+	  gcc_assert (!(neg_early_out && equal));
+
+	  return equal;
 	}
       else if (TREE_CODE (lhs1) == SSA_NAME
 	       && TREE_CODE (lhs2) == SSA_NAME)

Re: [PATCH] Handle GIMPLE_ASSIGNs with different vuse in gimple_equal_p

[Richard Biener]

On 11/12/13 2:03 PM, Tom de Vries wrote:
> On 11-11-13 14:17, Richard Biener wrote:
>> On Mon, 11 Nov 2013, Tom de Vries wrote:
>>
>>> On 11/11/13 10:50, Richard Biener wrote:
>>>> On Sat, 9 Nov 2013, Tom de Vries wrote:
>>>>> Bootstrapped and regtested on x86_64.
>>>>>
>>>>> OK for trunk?
>>>>
>>>> Comments inline
>>>>
>>>>
>>>> diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
>>>> index 98b5882..43516a7 100644
>>>> --- a/gcc/tree-ssa-tail-merge.c
>>>> +++ b/gcc/tree-ssa-tail-merge.c
>>>> @@ -1173,8 +1173,47 @@ gimple_equal_p (same_succ same_succ, gimple
>>>> s1, gimple s2)
>>>>         lhs2 = gimple_get_lhs (s2);
>>>>         if (TREE_CODE (lhs1) != SSA_NAME
>>>>         && TREE_CODE (lhs2) != SSA_NAME)
>>>> -    return (vn_valueize (gimple_vdef (s1))
>>>> -        == vn_valueize (gimple_vdef (s2)));
>>>> +    {
>>>> +      /* If the vdef is the same, it's the same statement.  */
>>>> +      if (vn_valueize (gimple_vdef (s1))
>>>> +          == vn_valueize (gimple_vdef (s2)))
>>>> +        return true;
>>>> +
>>>> +      /* If the vdef is not the same but the vuse is the same, it's
>>>> not the
>>>> +         same stmt.  */
>>>> +      if (vn_valueize (gimple_vuse (s1))
>>>> +          == vn_valueize (gimple_vuse (s2)))
>>>> +        return false;
>>>>
>>>
>>> Richard,
>>>
>>>> What's the logic behind this?
>>>> We want to use VN to get more "positive"
>>>> results
>>>
>>> We can use it to get both positive and negative results faster.
>>
>> I can get a negative result for free: "false" ;)
>>
> 
> Richard,
> 
> Indeed. But perhaps we could regard the question at hand from the
> perspective of both compilation effect and compilation speed ;)
> 
>> VN proves equivalency it doesn't prove non-equivalency - that's
>> simply its conservative fallback.
>>
> 
> Of course.
> 
>>>> - doing a negative early out looks suspicious to me ...
>>>>
>>>
>>> If the vdefs are the same, the VN has concluded that the statements
>>> are the
>>> same. We have a positive early out.
>>>
>>> If the vdefs are not the same, the VN has concluded that the
>>> statements are
>>> different. But if the vuses are the same, the VN has concluded that the
>>> statements are different because of structural difference. Which
>>> means there's
>>> no sense in us repeating the structural comparison. We have a
>>> negative early out.
>>
>> Well, see above - it merely failed to prove equivalency, it didn't
>> actually conclude they are different.
>>
> 
> You're right, sloppy formulation on my part.
> 
> My question is, if VN has tried to prove equality of vdefs, and failed,
> in what scenario could a structural comparison still prove them equal?
> 
> In case the vuses are not proven equal, there's an obvious reason why
> the vdefs are not proven equal, and structural comparison might indeed
> prove them equal.
> 
> But if the vuses are proven equal, that's not the reason why the vdefs
> are not proven equal. In which case it's hard for me to understand how a
> trivial structural check would beat VN.
> 
> I've browsed the VN code a bit and tried to construct examples where
> structural comparison beats VN, but did not manage.
> 
> I've also done a non-bootstrap build with attached patch, and a complete
> testrun, and was not able to trigger the assert.
> 
> So if you have any hunch about such a scenario, please let me know.

I don't - just relying on the value-number for virtual operands always
makes me nervous.

I'm fine with the early out, it just looks odd to me (the compile-time
effect should be minimal).

Richard.

> Thanks,
> - Tom
> 
>>> If the vdefs are not the same, the VN has concluded that the
>>> statements are
>>> different. But if the vuses are different, the VN may have concluded
>>> that the
>>> statements are different because of the different vuses. So it still
>>> makes sense
>>> to try structural comparison.
>>>
>>>> +      /* If the vdef is not the same and the vuse is not the same,
>>>> it might be
>>>> +         same stmt.  */
>>>> +
>>>> +      /* Test for structural equality.  */
>>>> +      if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s1)
>>>>
>>>> s2
>>>>
>>>> +          || (gimple_assign_nontemporal_move_p (s1)
>>>> +          != gimple_assign_nontemporal_move_p (s2)))
>>>>
>>>> I don't think we should care (it'll be false - a later pass sets it,
>>>> it's an optimization hint, not a correctness issue).  More interesting
>>>> would be to assert that has_volatile_ops is the same if the operands
>>>> turned out to be the same.
>>>>
>>>
>>> OK.
>>>
>>>> +        return false;
>>>> +
>>>> +      if (!operand_equal_p (lhs1, lhs2, 0))
>>>> +        return false;
>>>> +
>>>> +      t1 = gimple_assign_rhs1 (s1);
>>>> +      t2 = gimple_assign_rhs1 (s2);
>>>> +      if (!gimple_operand_equal_value_p (t1, t2))
>>>> +        return false;
>>>> +
>>>> +      t1 = gimple_assign_rhs2 (s1);
>>>> +      t2 = gimple_assign_rhs2 (s2);
>>>> +      if (!gimple_operand_equal_value_p (t1, t2))
>>>> +        return false;
>>>> +
>>>> +      t1 = gimple_assign_rhs3 (s1);
>>>> +      t2 = gimple_assign_rhs3 (s2);
>>>> +      if (!gimple_operand_equal_value_p (t1, t2))
>>>> +        return false;
>>>>
>>>>    for (i = 1; i < gimple_num_ops (s1); ++i)
>>>>      t1 = gimple_op (s1, i);
>>>>      ...
>>>>
>>>> but I think you should only compare rhs1 and thus only handle
>>>> GIMPLE_ASSIGN_SINGLEs this way - the others have a SSA name
>>>> lhs.
>>>>
>>>
>>> I see.
>>>
>>>> That makes the whole thing just
>>>>
>>>>        if (TREE_CODE (lhs1) != SSA_NAME
>>>>            && TREE_CODE (lhs2) != SSA_NAME)
>>>>          {
>>>>             if (vn_valueize (gimple_vdef (s1))
>>>>                 == vn_valueize (gimple_vdef (s2)))
>>>>          return true;
>>>>             return operand_equal_p (lhs1, lhs2, 0)
>>>>                 && gimple_operand_equal_value_p (gimple_assign_rhs1
>>>> (s1),
>>>>                                                   gimple_assign_rhs2
>>>> (s2));
>>>>          }
>>>>
>>>> Ok with doing it this way.
>>>
>>> I'll retest and checkin like this, unless you agree about the early
>>> out, which I
>>> still think is a good idea, although the structural test is now much
>>> smaller.
>>
>> I think the early out is premature.
>>
>> Richard.
>>
>