The following code compiled with GCC 4.7.1 on amd64 (I haven't tested x86) crashes Valgrind 3.8.1:

int main()
{
    unsigned char value;
    unsigned char result = __sync_fetch_and_add( &value, 1 );

    return 0;
}

Result:

==24468== Memcheck, a memory error detector
==24468== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==24468== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==24468== Command: ./a.out
==24468== 
vex amd64->IR: unhandled instruction bytes: 0xF0 0xF 0xC0 0x45 0xFE 0x88 0x45 0xFF
vex amd64->IR:   REX=0 REX.W=0 REX.R=0 REX.X=0 REX.B=0
vex amd64->IR:   VEX=0 VEX.L=0 VEX.nVVVV=0x0 ESC=0F
vex amd64->IR:   PFX.66=0 PFX.F2=0 PFX.F3=0
==24468== valgrind: Unrecognised instruction at address 0x4004b5.
==24468==    at 0x4004B5: main (in /tmp/a.out)
(...)

Reproducible: Always

Steps to Reproduce:
1. Save the code as test.c
2. Run: gcc test.c && valgrind ./a.out