[Bug c/42142] New: GCC 4.5 doesn't compile a certain quicksort implementation correctly when optimizing with -O1 or higher

[Bug c/42142] New: GCC 4.5 doesn't compile a certain quicksort implementation correctly when optimizing with -O1 or higher

[maister at archlinux dot us]

I have a reproducible test case which shows that GCC 4.5 (20091112) doesn't
compile a certain quicksort implementation correctly. It runs fine, but the
sorting is plain wrong when trying to optimize with -O1 or higher. There might
be something wrong with the quicksort implementation itself, but it compiles
and runs fine when not optimizing anything with GCC 4.5. It also runs, and
executes correctly on 4.3 and 4.4 with all optimizations applied.

The code in question is here:
http://pastebin.com/m270ad2a5


Output when compiling with
   gcc-4.5 -o qsort qsort.c -O

http://pastebin.com/m44c8f6f2


Output with
   gcc-4.5 -o qsort qsort.c

http://pastebin.com/m6ee486a0


Output with
   gcc-4.4 -o qsort qsort.c $CRAZYSTUFF_HERE

http://pastebin.com/m78d55249


-- 
           Summary: GCC 4.5 doesn't compile a certain quicksort
                    implementation correctly when optimizing with -O1 or
                    higher
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: maister at archlinux dot us
  GCC host triplet: x86_64-unknown-linux-gnu


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

[Bug c/42142] GCC 4.5 doesn't compile a certain quicksort implementation correctly when optimizing with -O1 or higher

[maister at archlinux dot us]

------- Comment #1 from maister at archlinux dot us  2009-11-22 12:14 -------
Created an attachment (id=19080)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19080&action=view)
The sorting test case


-- 


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

[Bug c/42142] GCC 4.5 doesn't compile a certain quicksort implementation correctly when optimizing with -O1 or higher

[maister at archlinux dot us]

------- Comment #3 from maister at archlinux dot us  2009-11-22 12:15 -------
Created an attachment (id=19082)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19082&action=view)
Output with gcc-4.5, no optimization


-- 


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

[Bug c/42142] GCC 4.5 doesn't compile a certain quicksort implementation correctly when optimizing with -O1 or higher

[maister at archlinux dot us]

------- Comment #2 from maister at archlinux dot us  2009-11-22 12:15 -------
Created an attachment (id=19081)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19081&action=view)
Output with gcc-4.5 and -O


-- 


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

[Bug c/42142] GCC 4.5 doesn't compile a certain quicksort implementation correctly when optimizing with -O1 or higher

[maister at archlinux dot us]

------- Comment #4 from maister at archlinux dot us  2009-11-22 12:15 -------
Created an attachment (id=19083)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19083&action=view)
Output from gcc-4.4 with lots of optimizations


-- 


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

[Bug tree-optimization/42142] GCC 4.5 doesn't compile a certain quicksort implementation correctly when optimizing with -O1 or higher

[paolo dot carlini at oracle dot com]

------- Comment #5 from paolo dot carlini at oracle dot com  2009-11-23 12:40 -------
Richard, can you have a look to this one? First blush, I don't see anything
wrong with the code...


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/42142] GCC 4.5 doesn't compile a certain quicksort implementation correctly when optimizing with -O1 or higher

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2009-11-23 13:10 -------
==29953== Conditional jump or move depends on uninitialised value(s)
==29953==    at 0x400671: sort (qsort.c:16)
==29953==    by 0x40079F: main (qsort.c:45)

qsort.c.034t.cddce1 deletes the store to end[i+1].

I will investigate further.  Partially reduced testcase:

extern void abort (void);

void __attribute__((noinline,noclone))
sort(int *arr, int elements)
{
  int piv, beg[10] = {}, end[10] = {}, i=0, L, R ;
  beg[0]=0; end[0]=elements;
  while (i>=0)
    {
      L=beg[i]; R=end[i]-1;
      if (L<R)
        {
          piv=arr[L];
          if (i==9)
            abort ();

          while (L<R)
            {
              while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R];
              while (arr[L]<=piv && L<R) L++; if (L<R) arr[R--]=arr[L];
            }
          arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L;
        }
        {
          i--;
        }
    }
}

int main(int argc, char *argv[])
{
  int table[10];
  int count;

  for (count = 0; count < 10; count++)
    table[count] = 10 - count;

  sort(table, 10);

  for ( count = 0; count < 9; count++ )
    if ( table[count] > table[count+1] )
      abort ();

  return 0;
}


-- 

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         |2009-11-23 13:10:42
               date|                            |


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

[Bug tree-optimization/42142] [4.5 Regression] DCE miscompiles a certain quicksort implementation correctly when optimizing with -O1 or higher

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
            Summary|GCC 4.5 doesn't compile a   |[4.5 Regression] DCE
                   |certain quicksort           |miscompiles a certain
                   |implementation correctly    |quicksort implementation
                   |when optimizing with -O1 or |correctly when optimizing
                   |higher                      |with -O1 or higher
   Target Milestone|---                         |4.5.0


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

[Bug tree-optimization/42142] [4.5 Regression] DCE miscompiles a certain quicksort implementation when optimizing with -O1 or higher

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2009-11-23 13:29 -------
int __attribute__((noinline,noclone))
sort(int L)
{
  int end[2] = { 10, 10, }, i=0, R;
  while (i<2)
    {
      R = end[i];
      if (L<R)
        {
          end[i+1] = 1;
          end[i] = 10;
          ++i;
        }
      else
        break;
    }
  return i;
}
extern void abort (void);
int main()
{
  if (sort (5) != 1)
    abort ();
  return 0;
}


-- 


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

[Bug tree-optimization/42142] [4.5 Regression] DCE miscompiles a certain quicksort implementation when optimizing with -O1 or higher

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2009-11-24 11:57 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/42142] [4.5 Regression] DCE miscompiles a certain quicksort implementation when optimizing with -O1 or higher

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2009-11-24 11:57 -------
Subject: Bug 42142

Author: rguenth
Date: Tue Nov 24 11:57:26 2009
New Revision: 154494

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

        PR tree-optimization/42142
        * tree-ssa-dce.c (mark_aliased_reaching_defs_necessary_1):
        Handle iv-dependent (non-)kills properly.
        (mark_aliased_reaching_defs_necessary): Pass the basic-block
        of the reference statement to mark_aliased_reaching_defs_necessary_1.

        * gcc.c-torture/execute/pr42142.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr42142.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-dce.c


-- 


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

[Bug tree-optimization/42142] [4.5 Regression] DCE miscompiles a certain quicksort implementation when optimizing with -O1 or higher

[hjl at gcc dot gnu dot org]

------- Comment #10 from hjl at gcc dot gnu dot org  2009-12-11 23:39 -------
Subject: Bug 42142

Author: hjl
Date: Fri Dec 11 23:36:24 2009
New Revision: 155184

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155184
Log:
Backport testcases from trunk.

2009-12-11  H.J. Lu  <hongjiu.lu@intel.com>

        Backport from mainline:
        2009-12-11  Dodji Seketeli  <dodji@redhat.com>

        PR c++/42225
        * g++.dg/template/typedef24.C: New test.
        * g++.dg/template/typedef25.C: New test.

        2009-12-11  Dodji Seketeli  <dodji@redhat.com>

        PR c++/42251
        * g++.dg/template/const3.C: New test.

        2009-12-10  Jakub Jelinek  <jakub@redhat.com>

        PR c++/42317
        * g++.dg/opt/dtor2.C: New test.
        * g++.dg/opt/dtor2.h: New file.
        * g++.dg/opt/dtor2-aux.cc: New file.

        2009-12-10  Jan Hubicka  <jh@suse.cz>

        PR middle-end/42110
        * g++.dg/torture/pr42110.C: new file.

        2009-12-07  Jakub Jelinek  <jakub@redhat.com>

        PR debug/42244
        * gcc.dg/debug/pr42244.c: New test.

        2009-12-04  David Daney  <ddaney@caviumnetworks.com>

        PR rtl-optimization/42164
        * gcc.c-torture/compile/pr42164.c: New test.

        2009-12-03  Jason Merrill  <jason@redhat.com>

        PR c++/41611
        * g++.dg/abi/guard2.C: New.

        2009-12-03  Dodji Seketeli  <dodji@redhat.com>

        PR c++/42217
        * g++.dg/other/bitfield4.C: New test.

        2009-12-03  Jakub Jelinek  <jakub@redhat.com>

        PR c++/42256
        * g++.dg/inherit/thunk11.C: New test.
        * g++.dg/inherit/thunk11.h: New file.
        * g++.dg/inherit/thunk11-aux.cc: New file.

        2009-12-01  Martin Jambor  <mjambor@suse.cz>

        PR tree-optimization/42237
        * gcc.c-torture/compile/pr42237.c: New test.

        2009-12-01  Paolo Carlini  <paolo.carlini@oracle.com>

        PR c++/42057
        * g++.dg/parse/crash54.C: New.

        2009-11-30  Martin Jambor  <mjambor@suse.cz>

        PR middle-end/42196
        * gcc.c-torture/compile/pr42196-1.c: New test.
        * gcc.c-torture/compile/pr42196-2.c: New test.
        * gcc.c-torture/compile/pr42196-3.c: New test.

        2009-11-30  Dodji Seketeli  <dodji@redhat.com>

        PR c++/42069
        * g++.dg/template/typedef23.C: New test.

        2009-11-29  H.J. Lu  <hongjiu.lu@intel.com>

        PR tree-optimization/41961
        * g++.dg/tree-ssa/pr41961.C: New.

        2009-11-29  Ira Rosen  <irar@il.ibm.com>

        PR tree-optimization/42193
        * gcc.dg/vect/pr42193.c: New test.

        2009-11-28  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/42183
        * g++.dg/torture/pr42183.C: New testcase.

        2009-11-27  Martin Jambor  <mjambor@suse.cz>

        PR middle-end/42006
        * gcc.c-torture/execute/pr42006.c: New test.

        2009-11-27  Michael Matz  <matz@suse.de>

        PR rtl-optimization/42084
        * gcc.dg/pr42084.c: New test.

        2009-11-27  Michael Matz  <matz@suse.de>

        PR c++/41906
        * g++.dg/tree-ssa/pr41906.C: New testcase.

        2009-11-26  Michael Matz  <matz@suse.de>

        PR tree-optimization/41905
        * g++.dg/tree-ssa/pr41905.C: New testcase.

        2009-11-24  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/42142
        * gcc.c-torture/execute/pr42142.c: New testcase.

        2009-11-24  Martin Jambor  <mjambor@suse.cz>

        PR tree-optimization/42154
        * gcc.c-torture/execute/pr42154.c: New test.

        2009-11-21  Martin Jambor  <mjambor@suse.cz>

        PR middle-end/42025
        * gcc.c-torture/compile/pr42025-1.c: New test.
        * gcc.c-torture/compile/pr42025-2.c: New test.

        2009-11-21  Jakub Jelinek  <jakub@redhat.com>

        PR tree-optimization/42078
        * gcc.dg/pr42078.c: New test.

Added:
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/abi/guard2.C
      - copied unchanged from r155170, trunk/gcc/testsuite/g++.dg/abi/guard2.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/inherit/thunk11-aux.cc
      - copied unchanged from r155170,
trunk/gcc/testsuite/g++.dg/inherit/thunk11-aux.cc
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/inherit/thunk11.C
      - copied unchanged from r155170,
trunk/gcc/testsuite/g++.dg/inherit/thunk11.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/inherit/thunk11.h
      - copied unchanged from r155170,
trunk/gcc/testsuite/g++.dg/inherit/thunk11.h
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/opt/dtor2-aux.cc
      - copied unchanged from r155170,
trunk/gcc/testsuite/g++.dg/opt/dtor2-aux.cc
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/opt/dtor2.C
      - copied unchanged from r155170, trunk/gcc/testsuite/g++.dg/opt/dtor2.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/opt/dtor2.h
      - copied unchanged from r155170, trunk/gcc/testsuite/g++.dg/opt/dtor2.h
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/other/bitfield4.C
      - copied unchanged from r155170,
trunk/gcc/testsuite/g++.dg/other/bitfield4.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/parse/crash54.C
      - copied unchanged from r155172,
trunk/gcc/testsuite/g++.dg/parse/crash54.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/template/const3.C
      - copied unchanged from r155170,
trunk/gcc/testsuite/g++.dg/template/const3.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/template/typedef23.C
      - copied unchanged from r155181,
trunk/gcc/testsuite/g++.dg/template/typedef23.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/template/typedef24.C
      - copied unchanged from r155170,
trunk/gcc/testsuite/g++.dg/template/typedef24.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/template/typedef25.C
      - copied unchanged from r155170,
trunk/gcc/testsuite/g++.dg/template/typedef25.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/torture/pr42110.C
      - copied unchanged from r155170,
trunk/gcc/testsuite/g++.dg/torture/pr42110.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/torture/pr42183.C
      - copied unchanged from r155181,
trunk/gcc/testsuite/g++.dg/torture/pr42183.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/tree-ssa/pr41905.C
      - copied unchanged from r155182,
trunk/gcc/testsuite/g++.dg/tree-ssa/pr41905.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/tree-ssa/pr41906.C
      - copied unchanged from r155182,
trunk/gcc/testsuite/g++.dg/tree-ssa/pr41906.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/tree-ssa/pr41961.C
      - copied unchanged from r155181,
trunk/gcc/testsuite/g++.dg/tree-ssa/pr41961.C
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr42025-1.c
      - copied unchanged from r155182,
trunk/gcc/testsuite/gcc.c-torture/compile/pr42025-1.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr42025-2.c
      - copied unchanged from r155182,
trunk/gcc/testsuite/gcc.c-torture/compile/pr42025-2.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr42164.c
      - copied unchanged from r155170,
trunk/gcc/testsuite/gcc.c-torture/compile/pr42164.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr42196-1.c
      - copied unchanged from r155181,
trunk/gcc/testsuite/gcc.c-torture/compile/pr42196-1.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr42196-2.c
      - copied unchanged from r155181,
trunk/gcc/testsuite/gcc.c-torture/compile/pr42196-2.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr42196-3.c
      - copied unchanged from r155181,
trunk/gcc/testsuite/gcc.c-torture/compile/pr42196-3.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr42237.c
      - copied unchanged from r155171,
trunk/gcc/testsuite/gcc.c-torture/compile/pr42237.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/execute/pr42006.c
      - copied unchanged from r155181,
trunk/gcc/testsuite/gcc.c-torture/execute/pr42006.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/execute/pr42142.c
      - copied unchanged from r155182,
trunk/gcc/testsuite/gcc.c-torture/execute/pr42142.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/execute/pr42154.c
      - copied unchanged from r155182,
trunk/gcc/testsuite/gcc.c-torture/execute/pr42154.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.dg/debug/pr42244.c
      - copied unchanged from r155170,
trunk/gcc/testsuite/gcc.dg/debug/pr42244.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.dg/pr42078.c
      - copied unchanged from r155182, trunk/gcc/testsuite/gcc.dg/pr42078.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.dg/pr42084.c
      - copied unchanged from r155182, trunk/gcc/testsuite/gcc.dg/pr42084.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.dg/vect/pr42193.c
      - copied unchanged from r155181,
trunk/gcc/testsuite/gcc.dg/vect/pr42193.c
Modified:
    branches/gcc-4_4-branch/gcc/testsuite/ChangeLog


-- 


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