[Bug tree-optimization/57488] New: [4.9 regression] loop terminates early at -O3

[Bug tree-optimization/57488] New: [4.9 regression] loop terminates early at -O3

[dhazeghi at yahoo dot com]

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

            Bug ID: 57488
           Summary: [4.9 regression] loop terminates early at -O3
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dhazeghi at yahoo dot com

The following code is miscompiled with current gcc trunk at -O3 on x86_64-linux
in both 32 and 64-bit modes.  The innermost loop in foo should execute 48
times, but at -O3 it does not (note the only place 'v' is touched is in that
loop).  I've tried reducing the testcase further, but any perturabation seems
to hide the bug.


$ gcc-trunk -v
gcc version 4.9.0 20130531 (experimental) [trunk revision 199531] (GCC) 
$ gcc-trunk -O2 wrong.c 
$ ./a.out 
0
$ gcc-4.8 -O3 wrong.c 
$ ./a.out 
0
$ gcc-trunk -O3 wrong.c 
$ ./a.out 
24
$

---------------------------------------
int printf(const char *, ...);

int i, j, *pj = &j, **ppj = &pj;
int x, *px = &x;

short s, *ps = &s, k;

unsigned short u, *pu = &u, **ppu = &pu;

char c, *pc = &c;

unsigned char v = 48;

int
bar (int p)
{
    p = k;
    *px = **ppu = i;
    *ppj = &p;
    if (**ppj)
        *pj = p;
    return p;
}

void
foo ()
{
    for (; i <= 3; i++)
        for (; j; j--);

    u ^= bar (*pj);

    for (k = 1; k >= 0; k--)
    {
        int l;
        bar (0);
        for (l = 1; l < 5; l++)
        {
            int m;
            for (m = 6; m; m--)
            {
                v--;
                *ps = *pc;
            }
        }
    }
}

int
main ()
{
    foo ();
    printf ("%d\n", v);
    return 0;
}

[Bug tree-optimization/57488] [4.9 regression] loop terminates early at -O3

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-05-31
                 CC|                            |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r198333.

[Bug tree-optimization/57488] [4.9 regression] loop terminates early at -O3

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
   Target Milestone|---                         |4.9.0

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a look later this week unless somebody beats me here.

[Bug tree-optimization/57488] [4.9 regression] loop terminates early at -O3

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
-fno-tree-partial-pre fixes this, partial PRE figures that v on entry to the
l loop is invariant in the outer loop.  Thus it does

    tem = v;
    for (k = 1; k >= 0; k--)
    {
        int l;
        bar (0);
        v = tem;
        for (l = 1; l < 5; l++)
        {
            int m;
            for (m = 6; m; m--)
            {
                v--;
                *ps = *pc;
            }
        }
    }

effectively cutting the number of decrements in half.

[Bug tree-optimization/57488] [4.9 regression] loop terminates early at -O3

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
The fun thing is that this is a regular partial redundancy but requires
an earlier partial partial redundancy elimination to be performed.

So what happens is that

int v;
void foo (int n)
{
  int i, j;
  for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
      v++;
}

gets transformed to

int v;
void foo (int n)
{
  int i, j;
  for (i = 0; i < n; ++i)
    tem = v;
    for (j = 0; j < n; ++j)
      # PHI <tem, v>
      v = tem + 1;
}

and in the 3rd insert iteration this becomes

int v;
void foo (int n)
{
  int i, j;
  tem2 = v;
  for (i = 0; i < n; ++i)
    # tem2 = PHI <tem2, ...>
    tem = tem2;
    for (j = 0; j < n; ++j)
      # tem = PHI <tem, v>
      v = tem + 1;
}

with ... replaced by the value and representative 'tem' because via the
NEW sets we propagate that down to the latch.

Of course PRE works fine with the above simplified testcase ...

The following speedup patch fixes the bug:

Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c  (revision 200237)
+++ gcc/tree-ssa-pre.c  (working copy)
@@ -3665,6 +3666,12 @@ insert (void)
       if (dump_file && dump_flags & TDF_DETAILS)
        fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
       new_stuff = insert_aux (ENTRY_BLOCK_PTR);
+
+      /* Clear the NEW sets before the next iteration.  We have already
+         fully propagated its contents.  */
+      if (new_stuff)
+       FOR_ALL_BB (bb)
+         bitmap_set_free (NEW_SETS (bb));
     }
   statistics_histogram_event (cfun, "insert iterations", num_iterations);
 }

remains to be seen why ... (I can only think of NEW sets propagated
over backedges requiring a 2nd iteration to make their effect visible)

That said, this bug seems to be latent for a long time.

[Bug tree-optimization/57488] [4.9 regression] loop terminates early at -O3

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Mon Jun 24 10:22:22 2013
New Revision: 200363

URL: http://gcc.gnu.org/viewcvs?rev=200363&root=gcc&view=rev
Log:
2013-06-24  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/57488
    * tree-ssa-pre.c (insert): Clear NEW sets before each iteration.

    * gcc.dg/torture/pr57488.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr57488.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-pre.c

[Bug tree-optimization/57488] [4.9 regression] loop terminates early at -O3

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |su at cs dot ucdavis.edu

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 58830 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/57488] [4.9 regression] loop terminates early at -O3

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Wed Oct 23 11:59:05 2013
New Revision: 203958

URL: http://gcc.gnu.org/viewcvs?rev=203958&root=gcc&view=rev
Log:
2013-10-23  Richard Biener  <rguenther@suse.de>

    Backport from mainline
    2013-06-24  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/57488
    * tree-ssa-pre.c (insert): Clear NEW sets before each iteration.

    * gcc.dg/torture/pr57488.c: New testcase.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/torture/pr57488.c
    branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/torture/pr58830.c
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-ssa-pre.c