optimization/863: wrong optimization of STL's find() algorithm by g++

[reichelt at igpm dot rwth-aachen dot de]

>Number:         863
>Category:       optimization
>Synopsis:       wrong optimization of STL's find() algorithm by g++
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          wrong-code
>Submitter-Id:   net
>Arrival-Date:   Tue Nov 21 17:06:00 PST 2000
>Closed-Date:
>Last-Modified:
>Originator:     Volker Reichelt
>Release:        gcc 2.97 20001106
>Organization:
>Environment:
Reading specs from /usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.97/specs
Configured with: 
gcc version 2.97 20001106 (experimental)

SuSE Linux 6.0, running kernel 2.2.12 with SMP enabled
on a Gigabyte dual Pentium II board (233 MHz)
>Description:
The following program is looking for a specific element
in a simple array. It uses the find() algorithm of the STL
(I just instantiated the template by hand, since the
template stuff has nothing to do with the bug).
The program is in fact looking for the first element, so it
should return 1 (true). This is indeed the case if I
compile it without optimization. However, with -O1 the
program returns 0 (false).
There seems to be something wrong with the optimization
of the for-loop since the bug only occurs for "Size" larger
than 3.


struct Data { int x, y, z; };

inline bool operator == ( const Data &d1, const Data &d2 )
  { return d1.x==d2.x; }

Data* find ( Data* first, Data* last, const Data& val )
{
  for ( int i = (last - first) >> 2; i>0 ; --i) {
    if (*first == val) return first;
    ++first;

    if (*first == val) return first;
    ++first;

    if (*first == val) return first;
    ++first;

    if (*first == val) return first;
    ++first;
  }

  switch(last - first) {
  case 3:
    if (*first == val) return first;
    ++first;
  case 2:
    if (*first == val) return first;
    ++first;
  case 1:
    if (*first == val) return first;
    ++first;
  case 0:
  default:
    return last;
  }
}

int main()
{
  enum { Size=4 };
  Data DataList[Size];

  for ( int i=0; i<Size; ++i )
    { DataList[i].x=0; DataList[i].y=0; DataList[i].z=0; }

  return find(DataList+0,DataList+Size,DataList[0])!=DataList+Size;
}
>How-To-Repeat:
g++ -O1 bug.cpp; a.out; echo $?
>Fix:

>Release-Note:
>Audit-Trail:
>Unformatted: