[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