-bash-3.00$ gcc -v
Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-libgcj-multifile --enable-languages=c,c++,objc,java,f95,ada --enable-java-awt=gtk --with-java-home=/usr/lib/jvm/java-1.4.2-gcj-1.4.2.0/jre --host=i386-redhat-linux
Thread model: posix
gcc version 4.0.1 20050727 (Red Hat 4.0.1-5)

The program below produces incorrect results with -O2 and higher, which
I've deduced is due to the combined options -fcse-follow-jumps -fforce-mem

#include <stdlib.h>
#include <stdio.h>
 
typedef unsigned long Word_t;
 
typedef struct {
  unsigned char type;
  unsigned char color;
  unsigned char left;
  unsigned char right;
} cell;
 
//possible cell types
#define WIDTH 3
 
typedef cell bstate[WIDTH]; // borderstate
 
void wordtostate(Word_t s, int bump, bstate state)
{
  char stack[WIDTH];
  int sp,i,type,leftcolor=0;
  cell *sti;
                                                                                
  for (sti = &state[i = sp = 0]; i < WIDTH; sti++, i++) {
    sti->type = type = (s >> (3*i)) & 7;
    sti->left = sti->right = i;
    sti->color = leftcolor ^ 1; // assume opposite color
    if (type & 2) {
      sti->right = state[sti->left = stack[--sp]].right;
      state[sti->left].right = state[sti->right].left = i;
      sti->color ^= (sti->left == i-1); // check color assumption
    }
    if (type & 1)
      stack[sp++] = i;
    leftcolor = sti->color;
  }
}
 
int main()
{
  bstate state;
  Word_t s = 0675;
 
  wordtostate(s, 0, state);
  printf("%s\n", state[1].color ? "OK" : "BUG");
  return 0;
}