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

[Tom de Vries <Tom_deVries at mentor dot com>]

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.

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)