Patchwork Fix for PR51879 - Missed tail merging with non-const/pure calls

login
register
mail settings
Submitter Tom de Vries
Date July 5, 2012, 4:44 p.m.
Message ID <4FF5C478.2030007@mentor.com>
Download mbox | patch
Permalink /patch/169223/
State New
Headers show

Comments

Tom de Vries - July 5, 2012, 4:44 p.m.
On 03/05/12 12:21, Richard Guenther wrote:
> On Wed, May 2, 2012 at 4:06 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> On 27/04/12 11:01, Richard Guenther wrote:
>> <SNIP>
>>>>>>> I see you do not handle
>> <SNIP>
>>>>>>> struct S { int i; };
>>>>>>> struct S foo (void);
>>>>>>> struct S bar (void)
>>>>>>> {
>>>>>>>   struct S s1, s2;
>>>>>>>   if (...)
>>>>>>>    s = foo ();
>>>>>>>   else
>>>>>>>    s = foo ();
>>>>>>>
>>>>>>> because the calls have a LHS that is not an SSA name.
>>>>>>
>>>>>> Indeed, the gvn patch handles this example conservatively, and tree-tail-merge
>>>>>> fails to optimize this test-case:
>>>>>> ...
>>>>>> struct S { int i; };
>>>>>> extern struct S foo (void);
>>>>>> extern int foo2 (void);
>>>>>> struct S s;
>>>>>> int bar (int c) {
>>>>>>  int r;
>>>>>>  if (c)
>>>>>>    {
>>>>>>      s = foo ();
>>>>>>      r = foo2 ();
>>>>>>    }
>>>>>>  else
>>>>>>    {
>>>>>>      s = foo ();
>>>>>>      r = foo2 ();
>>>>>>    }
>>>>>>  return r;
>>>>>> }
>>>>>> ...
>>>>>>
>>>>>> A todo.
>>>>>>
>> <SNIP>
>>>>>> bootstrapped and reg-tested on x86_64 (ada inclusive).
>>>>>>
>>>>>> Is this patch ok, or is the todo required?
>>>>>
>>>>> No, you can followup with that.
>>>>>
>>
>> Richard,
>>
>> here is the follow-up patch, which adds value numbering of a call for which the
>> lhs is not an SSA_NAME.
>>
>> The only thing I ended up using from the patch in
>> http://gcc.gnu.org/ml/gcc-patches/2012-01/msg01731.html was the idea of using
>> MODIFY_EXPR.
>>
>> I don't include any handling of MODIFY_EXPR in create_component_ref_by_pieces_1
>> because I don't think it will trigger with PRE.
>>
>> bootstrapped and reg-tested on x86_64.
>>
>> Ok for trunk?
> 
> Hmm, I wonder why
> 
>           if (!gimple_call_internal_p (stmt)
>               && (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST)
>                   /* If the call has side effects, subsequent calls won't have
>                      the same incoming vuse, so it's save to assume
>                      equality.  */
>                   || gimple_has_side_effects (stmt)))
> 
> works - I realize you added the gimple_has_side_effects () call - but
> if you consider ECF_LOOPING_CONST_OR_PURE functions, which
> have no VDEF, then it's odd how the comment applies.  And together
> both tests turn out to let all calls pass.
> 

Richard,

You're right, this is not correct. The test for gimple_has_side_effect should be
a test for gimple_vdef.
A ECF_LOOPING_CONST_OR_PURE function will be rejected by the updated condition.

I fixed this in the patch, and added comments describing both the const/pure
clause, and the vdef clause.

I also removed the comment 'We should handle stores from calls' since this patch
implements that.

> +  tree lhs = gimple_call_lhs (call);
> +
> +  if (lhs && TREE_CODE (lhs) != SSA_NAME)
> +    {
> +      memset (&temp, 0, sizeof (temp));
> +      temp.opcode = MODIFY_EXPR;
> +      temp.type = TREE_TYPE (lhs);
> +      temp.op0 = lhs;
> +      temp.off = -1;
> +      VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
> +    }
> 
> this deserves a comment

Done.

> - you are adding the extra operand solely for
> the purpose of hashing.  You are also not doing a good job identifying
> common calls.  Consider
> 
> if ()
>  *p = foo ();
> else
>  *q = foo ();
> 
> where p and q are value-numbered the same.  You fail to properly
> commonize the blocks.  That is because valueization of the ops
> of the call does not work for arbitrarily complex operands - see
> how we handle call operands.  Instead you should probably use
> copy_reference_ops_from_ref on the lhs, similar to call operands.
> 

If p and q are value numbered, it means they're SSA_NAMEs, and that means
they're not handled by this patch which is only about handling calls for which
the lhs is not an SSA_NAME.

This example is handled by the patch I posted for pr52009. I reposted the patch
and added this test-case (http://gcc.gnu.org/ml/gcc-patches/2012-07/msg00155.html).

So I'm not using copy_reference_ops_from_ref on the lhs, since it's not an SSA_NAME.

> Using MODIFY_EXPR as toplevel code for the vn_reference is going to
> indeed disable PRE for them, likewise any other call handling in VN.
> 
> Otherwise the idea looks ok - can you change the patch like above
> and add a testcase with an equal-VNed indirect store?
> 

I updated the patch as indicated in my comments, and added the test-case to the
patch for pr52009.

Bootstrapped and reg-tested on x86_64 (ada inclusive).

OK for trunk?

Thanks,
- Tom

2012-07-05  Tom de Vries  <tom@codesourcery.com>

	* tree-ssa-sccvn.c (copy_reference_ops_from_call)
	(visit_reference_op_call): Handle case that lhs is not an SSA_NAME.
	(visit_use): Also call visit_reference_op_call for calls with a vdef.
	
	* gcc.dg/pr51879-16.c: New test.
	* gcc.dg/pr51879-17.c: Same.
Richard Guenther - July 6, 2012, 8:58 a.m.
On Thu, Jul 5, 2012 at 6:44 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 03/05/12 12:21, Richard Guenther wrote:
>> On Wed, May 2, 2012 at 4:06 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>> On 27/04/12 11:01, Richard Guenther wrote:
>>> <SNIP>
>>>>>>>> I see you do not handle
>>> <SNIP>
>>>>>>>> struct S { int i; };
>>>>>>>> struct S foo (void);
>>>>>>>> struct S bar (void)
>>>>>>>> {
>>>>>>>>   struct S s1, s2;
>>>>>>>>   if (...)
>>>>>>>>    s = foo ();
>>>>>>>>   else
>>>>>>>>    s = foo ();
>>>>>>>>
>>>>>>>> because the calls have a LHS that is not an SSA name.
>>>>>>>
>>>>>>> Indeed, the gvn patch handles this example conservatively, and tree-tail-merge
>>>>>>> fails to optimize this test-case:
>>>>>>> ...
>>>>>>> struct S { int i; };
>>>>>>> extern struct S foo (void);
>>>>>>> extern int foo2 (void);
>>>>>>> struct S s;
>>>>>>> int bar (int c) {
>>>>>>>  int r;
>>>>>>>  if (c)
>>>>>>>    {
>>>>>>>      s = foo ();
>>>>>>>      r = foo2 ();
>>>>>>>    }
>>>>>>>  else
>>>>>>>    {
>>>>>>>      s = foo ();
>>>>>>>      r = foo2 ();
>>>>>>>    }
>>>>>>>  return r;
>>>>>>> }
>>>>>>> ...
>>>>>>>
>>>>>>> A todo.
>>>>>>>
>>> <SNIP>
>>>>>>> bootstrapped and reg-tested on x86_64 (ada inclusive).
>>>>>>>
>>>>>>> Is this patch ok, or is the todo required?
>>>>>>
>>>>>> No, you can followup with that.
>>>>>>
>>>
>>> Richard,
>>>
>>> here is the follow-up patch, which adds value numbering of a call for which the
>>> lhs is not an SSA_NAME.
>>>
>>> The only thing I ended up using from the patch in
>>> http://gcc.gnu.org/ml/gcc-patches/2012-01/msg01731.html was the idea of using
>>> MODIFY_EXPR.
>>>
>>> I don't include any handling of MODIFY_EXPR in create_component_ref_by_pieces_1
>>> because I don't think it will trigger with PRE.
>>>
>>> bootstrapped and reg-tested on x86_64.
>>>
>>> Ok for trunk?
>>
>> Hmm, I wonder why
>>
>>           if (!gimple_call_internal_p (stmt)
>>               && (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST)
>>                   /* If the call has side effects, subsequent calls won't have
>>                      the same incoming vuse, so it's save to assume
>>                      equality.  */
>>                   || gimple_has_side_effects (stmt)))
>>
>> works - I realize you added the gimple_has_side_effects () call - but
>> if you consider ECF_LOOPING_CONST_OR_PURE functions, which
>> have no VDEF, then it's odd how the comment applies.  And together
>> both tests turn out to let all calls pass.
>>
>
> Richard,
>
> You're right, this is not correct. The test for gimple_has_side_effect should be
> a test for gimple_vdef.
> A ECF_LOOPING_CONST_OR_PURE function will be rejected by the updated condition.
>
> I fixed this in the patch, and added comments describing both the const/pure
> clause, and the vdef clause.
>
> I also removed the comment 'We should handle stores from calls' since this patch
> implements that.
>
>> +  tree lhs = gimple_call_lhs (call);
>> +
>> +  if (lhs && TREE_CODE (lhs) != SSA_NAME)
>> +    {
>> +      memset (&temp, 0, sizeof (temp));
>> +      temp.opcode = MODIFY_EXPR;
>> +      temp.type = TREE_TYPE (lhs);
>> +      temp.op0 = lhs;
>> +      temp.off = -1;
>> +      VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
>> +    }
>>
>> this deserves a comment
>
> Done.
>
>> - you are adding the extra operand solely for
>> the purpose of hashing.  You are also not doing a good job identifying
>> common calls.  Consider
>>
>> if ()
>>  *p = foo ();
>> else
>>  *q = foo ();
>>
>> where p and q are value-numbered the same.  You fail to properly
>> commonize the blocks.  That is because valueization of the ops
>> of the call does not work for arbitrarily complex operands - see
>> how we handle call operands.  Instead you should probably use
>> copy_reference_ops_from_ref on the lhs, similar to call operands.
>>
>
> If p and q are value numbered, it means they're SSA_NAMEs, and that means
> they're not handled by this patch which is only about handling calls for which
> the lhs is not an SSA_NAME.
>
> This example is handled by the patch I posted for pr52009. I reposted the patch
> and added this test-case (http://gcc.gnu.org/ml/gcc-patches/2012-07/msg00155.html).
>
> So I'm not using copy_reference_ops_from_ref on the lhs, since it's not an SSA_NAME.
>
>> Using MODIFY_EXPR as toplevel code for the vn_reference is going to
>> indeed disable PRE for them, likewise any other call handling in VN.
>>
>> Otherwise the idea looks ok - can you change the patch like above
>> and add a testcase with an equal-VNed indirect store?
>>
>
> I updated the patch as indicated in my comments, and added the test-case to the
> patch for pr52009.
>
> Bootstrapped and reg-tested on x86_64 (ada inclusive).
>
> OK for trunk?

Ok.

Thanks,
Richard.

> Thanks,
> - Tom
>
> 2012-07-05  Tom de Vries  <tom@codesourcery.com>
>
>         * tree-ssa-sccvn.c (copy_reference_ops_from_call)
>         (visit_reference_op_call): Handle case that lhs is not an SSA_NAME.
>         (visit_use): Also call visit_reference_op_call for calls with a vdef.
>
>         * gcc.dg/pr51879-16.c: New test.
>         * gcc.dg/pr51879-17.c: Same.

Patch

Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c (revision 189007)
+++ gcc/tree-ssa-sccvn.c (working copy)
@@ -942,6 +942,20 @@  copy_reference_ops_from_call (gimple cal
 {
   vn_reference_op_s temp;
   unsigned i;
+  tree lhs = gimple_call_lhs (call);
+
+  /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
+     different.  By adding the lhs here in the vector, we ensure that the
+     hashcode is different, guaranteeing a different value number.  */
+  if (lhs && TREE_CODE (lhs) != SSA_NAME)
+    {
+      memset (&temp, 0, sizeof (temp));
+      temp.opcode = MODIFY_EXPR;
+      temp.type = TREE_TYPE (lhs);
+      temp.op0 = lhs;
+      temp.off = -1;
+      VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
+    }
 
   /* Copy the type, opcode, function being called and static chain.  */
   memset (&temp, 0, sizeof (temp));
@@ -2628,6 +2642,10 @@  visit_reference_op_call (tree lhs, gimpl
   tree vuse = gimple_vuse (stmt);
   tree vdef = gimple_vdef (stmt);
 
+  /* Non-ssa lhs is handled in copy_reference_ops_from_call.  */
+  if (lhs && TREE_CODE (lhs) != SSA_NAME)
+    lhs = NULL_TREE;
+
   vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
   vr1.operands = valueize_shared_reference_ops_from_call (stmt);
   vr1.type = gimple_expr_type (stmt);
@@ -3408,18 +3426,20 @@  visit_use (tree use)
 		}
 	    }
 
-	  /* ???  We should handle stores from calls.  */
 	  if (!gimple_call_internal_p (stmt)
-	      && (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST)
-		  /* If the call has side effects, subsequent calls won't have
-		     the same incoming vuse, so it's save to assume
-		     equality.  */
-		  || gimple_has_side_effects (stmt))
-	      && ((lhs && TREE_CODE (lhs) == SSA_NAME)
-		  || (!lhs && gimple_vdef (stmt))))
-	    {
-	      changed = visit_reference_op_call (lhs, stmt);
-	    }
+	      && (/* Calls to the same function with the same vuse
+		     and the same operands do not necessarily return the same
+		     value, unless they're pure or const.  */
+		  gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST)
+		  /* If calls have a vdef, subsequent calls won't have
+		     the same incoming vuse.  So, if 2 calls with vdef have the
+		     same vuse, we know they're not subsequent.
+		     We can value number 2 calls to the same function with the
+		     same vuse and the same operands which are not subsequent
+		     the same, because there is no code in the program that can
+		     compare the 2 values.  */
+		  || gimple_vdef (stmt)))
+	    changed = visit_reference_op_call (lhs, stmt);
 	  else
 	    changed = defs_to_varying (stmt);
 	}
Index: gcc/testsuite/gcc.dg/pr51879-16.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/pr51879-16.c (revision 0)
@@ -0,0 +1,32 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre" } */
+
+struct S {
+  int i;
+};
+
+extern struct S foo (void);
+extern int foo2 (void);
+
+struct S s;
+
+int bar (int c) {
+  int r;
+
+  if (c)
+    {
+      s = foo ();
+      r = foo2 ();
+    }
+  else
+    {
+      s = foo ();
+      r = foo2 ();
+    }
+
+  return r;
+}
+
+/* { dg-final { scan-tree-dump-times "foo \\(" 1 "pre"} } */
+/* { dg-final { scan-tree-dump-times "foo2 \\(" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
Index: gcc/testsuite/gcc.dg/pr51879-17.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/pr51879-17.c (revision 0)
@@ -0,0 +1,32 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre" } */
+
+struct S {
+  int i;
+};
+
+extern struct S foo (void);
+extern int foo2 (void);
+
+struct S s, s2;
+
+int bar (int c) {
+  int r;
+
+  if (c)
+    {
+      s = foo ();
+      r = foo2 ();
+    }
+  else
+    {
+      s2 = foo ();
+      r = foo2 ();
+    }
+
+  return r;
+}
+
+/* { dg-final { scan-tree-dump-times "foo \\(" 2 "pre"} } */
+/* { dg-final { scan-tree-dump-times "foo2 \\(" 2 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */