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

[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

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

[dnovillo at google dot com]

------- Comment #1 from dnovillo at google dot com  2008-12-09 20:22 -------
Subject: Re:  New: copy-propagation doesn't 
        handle cycles

On Tue, Dec 9, 2008 at 14:53, rguenth at gcc dot gnu dot org
<gcc-bugzilla@gcc.gnu.org> wrote:
>        {
> -         phi_val.value = arg;
> +         phi_val.value = arg_val->value;
>          continue;
>        }

This looks OK.

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

We don't want to propagate using get_last_copy_of here.  The reason
now escapes me, but it should be documented in the code.  It was
related to phi-cycles, but it's been a long time.


Diego.


-- 


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

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

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2008-12-09 20:45 -------
Thanks.  Mine then.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-12-09 20:45:20
               date|                            |


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

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

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2008-12-10 17:53 -------
Subject: Bug 38458

Author: rguenth
Date: Wed Dec 10 17:51:52 2008
New Revision: 142654

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=142654
Log:
2008-12-10  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/38458
        * tree-ssa-copy.c (copy_prop_visit_phi_node): For the first
        argument use the arguments copy-of value.

Modified:
    branches/alias-improvements/gcc/ChangeLog.alias
    branches/alias-improvements/gcc/tree-ssa-copy.c


-- 


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

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

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2009-03-28 12:54 -------
Subject: Bug 38458

Author: rguenth
Date: Sat Mar 28 12:54:14 2009
New Revision: 145185

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=145185
Log:
2009-03-28  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/38458
        * tree-ssa-copy.c (copy_prop_visit_phi_node): For the first
        argument use the arguments copy-of value.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-copy.c


-- 


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

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

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2009-03-28 12:55 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.5.0


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