Re: [PATCH] Fix for PR52009 - Another missed tail merging opportunity

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

On 31/01/12 22:05, Tom de Vries wrote:
> Richard,
> 

Sorry, with patch this time.

> this patch fixes PR52009.
> 
> Consider this test-case:
> ...
> int z;
> 
> void
> foo (int y)
> {
>   if (y == 6)
>     z = 5;
>   else
>     z = 5;
> }
> ...
> 
> Currently, compiling with -O2 gives us this representation at pr51879-7.c.094t.pre:
> ...
>   # BLOCK 3 freq:1991
>   # PRED: 2 [19.9%]  (true,exec)
>   # .MEMD.1710_4 = VDEF <.MEMD.1710_3(D)>
>   zD.1702 = 5;
>   goto <bb 5>;
>   # SUCC: 5 [100.0%]  (fallthru,exec)
> 
>   # BLOCK 4 freq:8009
>   # PRED: 2 [80.1%]  (false,exec)
>   # .MEMD.1710_5 = VDEF <.MEMD.1710_3(D)>
>   zD.1702 = 5;
>   # SUCC: 5 [100.0%]  (fallthru,exec)
> 
>   # BLOCK 5 freq:10000
>   # PRED: 3 [100.0%]  (fallthru,exec) 4 [100.0%]  (fallthru,exec)
>   # .MEMD.1710_2 = PHI <.MEMD.1710_4(3), .MEMD.1710_5(4)>
>   # VUSE <.MEMD.1710_2>
>   return;
> ...
> 
> Blocks 3 and 4 are not tail-merged.
> 
> The patch allows the example to be tail-merged by:
> - value numbering .MEMD.1710_4 and .MEMD.1710_5 equal
> - comparing gimple_vdef value numbers for assignments during tail-merge
> 
> Bootstrapped and reg-tested on x86_64.
> 
> OK for stage1?
> 
> Thanks,
> - Tom
> 
> 2012-01-31  Tom de Vries  <tom@codesourcery.com>
> 
> 	PR tree-optimization/52009
> 	* tree-ssa-tail-merge.c (gimple_equal_p): For GIMPLE_ASSIGN, compare
> 	value numbers of gimple_vdef.
> 	* tree-ssa-sccvn.h (struct vn_reference_s): Add vdef field.
> 	(vn_reference_insert): Add vdef parameter to prototype.
> 	* tree-ssa-sccvn.c (copy_reference_ops_from_ref): Handle MODIFY_EXPR.
> 	(vn_reference_insert): Add and handle vdef parameter.
> 	(visit_reference_op_load): Add argument to vn_reference_insert call.
> 	(visit_reference_op_store): Find value number of vdef of store.  Insert
> 	value number of vdef of store.
> 
> 	* gcc.dg/pr51879-7.c: New test.

Index: gcc/tree-ssa-tail-merge.c
===================================================================
--- gcc/tree-ssa-tail-merge.c (revision 183325)
+++ gcc/tree-ssa-tail-merge.c (working copy)
@@ -1087,6 +1087,14 @@ gimple_equal_p (same_succ same_succ, gim
     case GIMPLE_ASSIGN:
       lhs1 = gimple_get_lhs (s1);
       lhs2 = gimple_get_lhs (s2);
+      if (gimple_vdef (s1))
+	{
+	  if (vn_valueize (gimple_vdef (s1)) != vn_valueize (gimple_vdef (s2)))
+	    return false;
+	  if (TREE_CODE (lhs1) != SSA_NAME
+	      && TREE_CODE (lhs2) != SSA_NAME)
+	    return true;
+	}
       return (TREE_CODE (lhs1) == SSA_NAME
 	      && TREE_CODE (lhs2) == SSA_NAME
 	      && vn_valueize (lhs1) == vn_valueize (lhs2));
Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c (revision 183325)
+++ gcc/tree-ssa-sccvn.c (working copy)
@@ -624,6 +624,9 @@ copy_reference_ops_from_ref (tree ref, V
 
       switch (temp.opcode)
 	{
+	case MODIFY_EXPR:
+	  temp.op0 = TREE_OPERAND (ref, 1);
+	  break;	  
 	case MEM_REF:
 	  /* The base address gets its own vn_reference_op_s structure.  */
 	  temp.op0 = TREE_OPERAND (ref, 1);
@@ -740,6 +743,7 @@ copy_reference_ops_from_ref (tree ref, V
       VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
 
       if (REFERENCE_CLASS_P (ref)
+	  || TREE_CODE (ref) == MODIFY_EXPR
 	  || (TREE_CODE (ref) == ADDR_EXPR
 	      && !is_gimple_min_invariant (ref)))
 	ref = TREE_OPERAND (ref, 0);
@@ -1928,7 +1932,7 @@ vn_reference_lookup (tree op, tree vuse,
    RESULT, and return the resulting reference structure we created.  */
 
 vn_reference_t
-vn_reference_insert (tree op, tree result, tree vuse)
+vn_reference_insert (tree op, tree result, tree vuse, tree vdef)
 {
   void **slot;
   vn_reference_t vr1;
@@ -1944,6 +1948,7 @@ vn_reference_insert (tree op, tree resul
   vr1->set = get_alias_set (op);
   vr1->hashcode = vn_reference_compute_hash (vr1);
   vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
+  vr1->vdef = vdef;
 
   slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
 				   INSERT);
@@ -2725,7 +2730,7 @@ visit_reference_op_load (tree lhs, tree
   else
     {
       changed = set_ssa_val_to (lhs, lhs);
-      vn_reference_insert (op, lhs, last_vuse);
+      vn_reference_insert (op, lhs, last_vuse, NULL_TREE);
     }
 
   return changed;
@@ -2739,8 +2744,11 @@ static bool
 visit_reference_op_store (tree lhs, tree op, gimple stmt)
 {
   bool changed = false;
-  tree result;
+  vn_reference_t vnresult = NULL;
+  tree result, assign;
   bool resultsame = false;
+  tree vuse = gimple_vuse (stmt);
+  tree vdef = gimple_vdef (stmt);
 
   /* First we want to lookup using the *vuses* from the store and see
      if there the last store to this location with the same address
@@ -2758,7 +2766,7 @@ visit_reference_op_store (tree lhs, tree
      Otherwise, the vdefs for the store are used when inserting into
      the table, since the store generates a new memory state.  */
 
-  result = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_NOWALK, NULL);
+  result = vn_reference_lookup (lhs, vuse, VN_NOWALK, NULL);
 
   if (result)
     {
@@ -2771,8 +2779,17 @@ visit_reference_op_store (tree lhs, tree
 
   if (!result || !resultsame)
     {
-      tree vdef;
+      assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op);
+      vn_reference_lookup (assign, vuse, VN_NOWALK, &vnresult);
+      if (vnresult)
+	{
+	  VN_INFO (vdef)->use_processed = true;
+	  return set_ssa_val_to (vdef, vnresult->vdef);
+	}
+    }
 
+  if (!result || !resultsame)
+    {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file, "No store match\n");
@@ -2784,7 +2801,7 @@ visit_reference_op_store (tree lhs, tree
 	}
       /* Have to set value numbers before insert, since insert is
 	 going to valueize the references in-place.  */
-      if ((vdef = gimple_vdef (stmt)))
+      if (vdef)
 	{
 	  VN_INFO (vdef)->use_processed = true;
 	  changed |= set_ssa_val_to (vdef, vdef);
@@ -2793,23 +2810,22 @@ visit_reference_op_store (tree lhs, tree
       /* Do not insert structure copies into the tables.  */
       if (is_gimple_min_invariant (op)
 	  || is_gimple_reg (op))
-        vn_reference_insert (lhs, op, vdef);
+        vn_reference_insert (lhs, op, vdef, NULL);
+
+      assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op);
+      vn_reference_insert (assign, lhs, vuse, vdef);
     }
   else
     {
       /* We had a match, so value number the vdef to have the value
 	 number of the vuse it came from.  */
-      tree def, use;
 
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "Store matched earlier value,"
 		 "value numbering store vdefs to matching vuses.\n");
 
-      def = gimple_vdef (stmt);
-      use = gimple_vuse (stmt);
-
-      VN_INFO (def)->use_processed = true;
-      changed |= set_ssa_val_to (def, SSA_VAL (use));
+      VN_INFO (vdef)->use_processed = true;
+      changed |= set_ssa_val_to (vdef, SSA_VAL (vuse));
     }
 
   return changed;
Index: gcc/tree-ssa-sccvn.h
===================================================================
--- gcc/tree-ssa-sccvn.h (revision 183325)
+++ gcc/tree-ssa-sccvn.h (working copy)
@@ -110,6 +110,7 @@ typedef struct vn_reference_s
   tree type;
   VEC (vn_reference_op_s, heap) *operands;
   tree result;
+  tree vdef;
 } *vn_reference_t;
 typedef const struct vn_reference_s *const_vn_reference_t;
 
@@ -199,7 +200,7 @@ tree vn_reference_lookup_pieces (tree, a
 				 VEC (vn_reference_op_s, heap) *,
 				 vn_reference_t *, vn_lookup_kind);
 tree vn_reference_lookup (tree, tree, vn_lookup_kind, vn_reference_t *);
-vn_reference_t vn_reference_insert (tree, tree, tree);
+vn_reference_t vn_reference_insert (tree, tree, tree, tree);
 vn_reference_t vn_reference_insert_pieces (tree, alias_set_type, tree,
 					   VEC (vn_reference_op_s, heap) *,
 					   tree, unsigned int);
Index: gcc/testsuite/gcc.dg/pr51879-7.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/pr51879-7.c (revision 0)
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre" } */
+
+int bar (int);
+
+int z;
+
+void
+foo (int y)
+{
+  if (y == 6)
+    z = 5;
+  else
+    z = 5;
+}
+
+/* { dg-final { scan-tree-dump-times "z = 5" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */