[Bug tree-optimization/47265] New: [4.6 Regression] Error: SSA name in freelist but still referenced

[Bug tree-optimization/47265] New: [4.6 Regression] Error: SSA name in freelist but still referenced

[d.g.gorbachev at gmail dot com]

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

           Summary: [4.6 Regression] Error: SSA name in freelist but still
                    referenced
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: d.g.gorbachev@gmail.com


With GCC 4.6.0 20110108 (experimental):

===================== foo.c ====================
struct S {
  char a[3];
  char b[3];
};

void bar(char *dst, const char *src, unsigned n)
{
  while (n--)
    *dst++ = *src ? *src++ : ' ';
}

void foo(struct S *s)
{
  bar(s->a, s->b, 3);
}
================================================

$ gcc -S -O3 foo.c
foo.c: In function 'foo':
foo.c:12:6: error: SSA name in freelist but still referenced
D.1961_2
cc1: note: in statement
src_19 = [cond_expr] D.1974_11 != 0 ? src_20 : D.1961_2;

foo.c:12:6: internal compiler error: verify_stmts failed
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[hjl.tools at gmail dot com]

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

H.J. Lu <hjl.tools at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.01.12 14:21:03
                 CC|                            |matz at gcc dot gnu.org
   Target Milestone|---                         |4.6.0
     Ever Confirmed|0                           |1

--- Comment #1 from H.J. Lu <hjl.tools at gmail dot com> 2011-01-12 14:21:03 UTC ---
It is caused by revision 163998:

http://gcc.gnu.org/ml/gcc-cvs/2010-09/msg00290.html

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[matz at gcc dot gnu.org]

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

Michael Matz <matz at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

--- Comment #2 from Michael Matz <matz at gcc dot gnu.org> 2011-01-12 17:20:00 UTC ---
The underlying problem is that tree-ssa-forwprop.c recursively calls itself
on the same statement, updating it in the process.  That destroys the 
imm_use iterator for the outer iteration, making us miss on imm-use.
The definition then is removed (under the assumption that all imm-uses
are changed), leaving a stale reference to an SSA name in the free list.

In detail here's what happens, the situation at first:

  src_2 = &s_1(D)->b;
  src_20 = src_2 + 1;
  src_19 = [cond_expr] iftmp.0_11 != 0 ? src_20 : src_2;

forward_propagate_addr_expr (src_2) iterates over the imm-uses of src_2.
(1)
The first is the def of src_20, which itself is a pointer addition.
forward_propagate_addr_expr_1 happily tries to look through that one
calling forward_propagate_addr_expr recursively on src_20.  The imm-use
list of src_20 also contains statement src_19, which is now updated via
update_stmt.  Unfortunately that will clobber the iterator at (1)
to not contain the src_19 statement anymore.  So when returning the
outer loop on imm-uses(src_2) will now exit as if all imm-uses were
handled.

Caller will remove def(src_2), leaving us with:

  src_20 = &MEM[(void *)s_1(D) + 4B];
  src_19 = [cond_expr] iftmp.0_11 != 0 ? src_20 : src_2;

Boom.  Triggered by my patch perhaps, but latent problem.

The underlying problem is statements that can be reached over multiple
distinct paths of def-use chains.

I'll experiment with totally removing the recursion, it possibly isn't
necessary anymore since MEMREF because looking through type-casts and
the like isn't necessary.  And of course as this one shows it's simply
not correct to recurse on forward_propagate_addr_expr, at least as long
as the destination statement has more than one operand

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |zsojka at seznam dot cz

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-01-25 09:50:52 UTC ---
*** Bug 47443 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-01-25 10:10:30 UTC ---
Alternative solution would be to remember the count of imm uses before doing
FOR_EACH_IMM_USE and if the loop does not iterate that many times, return
conservatively that not all uses have been seen.

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-01-25 10:27:41 UTC ---
Actually, there is a far easier fix.  Either add
  if (all && !has_zero_uses (name))
    all = false;
to the end of forward_propagate_addr_expr, or we could iterate some more,
either like this:
--- gcc/tree-ssa-forwprop.c.jj     2011-01-15 11:26:42.000000000 +0100
+++ gcc/tree-ssa-forwprop.c 2011-01-25 11:22:02.828495766 +0100
@@ -1061,6 +1061,8 @@ forward_propagate_addr_expr (tree name, 
   bool all = true;
   bool single_use_p = has_single_use (name);

+  do
+  {
   FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
     {
       bool result;
@@ -1113,6 +1115,7 @@ forward_propagate_addr_expr (tree name, 
          gsi_remove (&gsi, true);
        }
     }
+  } while (all && !has_zero_uses (name));

   return all;
 }

or say just once or say 4 times:
  int i;
  for (i = 0; i < 4; i++)
    {
      FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
        {
          ...
        }
      if (!all || has_zero_uses (name))
        return all;
    }
  return false;

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-01-25 10:47:29 UTC ---
(In reply to comment #5)
> Actually, there is a far easier fix.  Either add
>   if (all && !has_zero_uses (name))
>     all = false;
> to the end of forward_propagate_addr_expr, or we could iterate some more,
> either like this:
> --- gcc/tree-ssa-forwprop.c.jj     2011-01-15 11:26:42.000000000 +0100
> +++ gcc/tree-ssa-forwprop.c 2011-01-25 11:22:02.828495766 +0100
> @@ -1061,6 +1061,8 @@ forward_propagate_addr_expr (tree name, 
>    bool all = true;
>    bool single_use_p = has_single_use (name);
> 
> +  do
> +  {
>    FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
>      {
>        bool result;
> @@ -1113,6 +1115,7 @@ forward_propagate_addr_expr (tree name, 
>           gsi_remove (&gsi, true);
>         }
>      }
> +  } while (all && !has_zero_uses (name));
> 
>    return all;
>  }
> 
> or say just once or say 4 times:
>   int i;
>   for (i = 0; i < 4; i++)
>     {
>       FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
>         {
>           ...
>         }
>       if (!all || has_zero_uses (name))
>         return all;
>     }
>   return false;

Or simply

  return all && has_zero_uses (name);

?

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[matz at gcc dot gnu.org]

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

--- Comment #7 from Michael Matz <matz at gcc dot gnu.org> 2011-01-25 12:58:33 UTC ---
FWIW removing the second recursive call doesn't regress the testsuite.

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-01-25 13:19:35 UTC ---
Have you gathered statistics how much less does forwprop propagate though?
I'm ATM running an instrumented bootstrap/regtest to see how many replacement
hits result from the iterations, if iteration proves not to be worthwhile, I'd
say just the return all && has_zero_uses (name); change would be safest for
4.6.

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[jakub at gcc dot gnu.org]

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

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-01-25 19:51:02 UTC ---
Author: jakub
Date: Tue Jan 25 19:50:56 2011
New Revision: 169250

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=169250
Log:
    PR tree-optimization/47265
    PR tree-optimization/47443
    * tree-ssa-forwprop.c (forward_propagate_addr_expr): Return false
    if name still has some uses.

    * gcc.c-torture/compile/pr47265.c: New test.
    * gcc.dg/pr47443.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/compile/pr47265.c
    trunk/gcc/testsuite/gcc.dg/pr47443.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-forwprop.c

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-01-25 23:53:13 UTC ---
Fixed.

[Bug tree-optimization/47265] [4.6 Regression] Error: SSA name in freelist but still referenced

[dnovillo at gcc dot gnu.org]

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

--- Comment #11 from Diego Novillo <dnovillo at gcc dot gnu.org> 2011-02-02 17:47:39 UTC ---
Author: dnovillo
Date: Wed Feb  2 17:47:35 2011
New Revision: 169589

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=169589
Log:
    PR tree-optimization/47265
    PR tree-optimization/47443
    * tree-ssa-forwprop.c (forward_propagate_addr_expr): Return false
    if name still has some uses.

    * gcc.c-torture/compile/pr47265.c: New test.
    * gcc.dg/pr47443.c: New test.

Added:
    branches/google/integration/gcc/testsuite/gcc.c-torture/compile/pr47265.c
    branches/google/integration/gcc/testsuite/gcc.dg/pr47443.c
Modified:
    branches/google/integration/gcc/ChangeLog
    branches/google/integration/gcc/testsuite/ChangeLog
    branches/google/integration/gcc/tree-ssa-forwprop.c