[Bug tree-optimization/38458] New: copy-propagation doesn't handle cycles

[rguenth at gcc dot gnu dot org]

For

# a_1 = PHI <b_1, c_1>
b_1 = a_1;

copy-propagation propagates a_1 into b_1 instead of c_1 into a_1 and b_1.

This is because handling of PHI and copy nodes is different.  Either

Index: tree-ssa-copy.c
===================================================================
--- tree-ssa-copy.c     (revision 142591)
+++ tree-ssa-copy.c     (working copy)
@@ -793,7 +793,7 @@ copy_prop_visit_phi_node (gimple phi)
         memory reference of all the other arguments.  */
       if (phi_val.value == NULL_TREE)
        {
-         phi_val.value = arg;
+         phi_val.value = arg_val->value;
          continue;
        }


or

Index: tree-ssa-copy.c
===================================================================
--- tree-ssa-copy.c     (revision 142591)
+++ tree-ssa-copy.c     (working copy)
@@ -574,8 +574,7 @@ dump_copy_of (FILE *file, tree var)
 static enum ssa_prop_result
 copy_prop_visit_assignment (gimple stmt, tree *result_p)
 {
-  tree lhs, rhs;
-  prop_value_t *rhs_val;
+  tree lhs, rhs, rhs_val;

   lhs = gimple_assign_lhs (stmt);
   rhs = gimple_assign_rhs1 (stmt);
@@ -583,10 +582,12 @@ copy_prop_visit_assignment (gimple stmt,

   gcc_assert (gimple_assign_rhs_code (stmt) == SSA_NAME);

-  rhs_val = get_copy_of_val (rhs);
+  rhs_val = get_last_copy_of (rhs);

   if (TREE_CODE (lhs) == SSA_NAME)
     {
+      bool res;
+
       /* Straight copy between two SSA names.  First, make sure that
         we can propagate the RHS into uses of LHS.  */
       if (!may_propagate_copy (lhs, rhs))
@@ -599,10 +600,15 @@ copy_prop_visit_assignment (gimple stmt,
         This is different from what we do in copy_prop_visit_phi_node.
         In those cases, we are interested in the copy-of chains.  */
       *result_p = lhs;
-      if (set_copy_of_val (*result_p, rhs_val->value))
-       return SSA_PROP_INTERESTING;
-      else
-       return SSA_PROP_NOT_INTERESTING;
+      res = set_copy_of_val (*result_p, rhs_val);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+       {
+         fprintf (dump_file, "\nASSIGN node ");
+         dump_copy_of (dump_file, lhs);
+         fprintf (dump_file, "\n");
+       }
+
+      return res ? SSA_PROP_INTERESTING : SSA_PROP_NOT_INTERESTING;
     }

   return SSA_PROP_VARYING;


fixes this particular case.  Note that phicprop from DOM handles the above
case fine.  I have a testcase only on the alias-improvements branch with
a local patch applied.

Still - is there any fundamental reason to not use last_copy_of for assignments
and not the copy-of the phi arg?

The testcase goes as

PHI  a is copy of c
CPY  b is copy of c
  ... make edge executable
PHI  a is copy of b which is copy of c
CPY  b is not a copy (whoops, because of b in the copy-of chain of a)
PHI  a is not a copy
CPY  b is a copy of a

I don't know if we in general can fixup cycles this way (in the end we
do not want cycles to survive if there are copy-of edges from it, otherwise
we want to have a single representative).  Maybe we need to do SCC
finding first?


-- 
           Summary: copy-propagation doesn't handle cycles
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38458