You probably meant -march=i686 not -mtune=i686. The arch setting
controls the instruction set available, while the tune setting only
controls choice of instructions within that set and scheduling. Without
any arch option specified the default is 386, the lowest common
denominator. The 386 did not have the cmpxchg instruction necessary to
implement the atomic compare and swap operation.
It's not a compile time error because when a suitable instruction isn't
available the compiler emits a call to a library function instead, as in
theory it is possible to implement atomic operations with aid from the
kernel or operating system if the cpu doesn't support it as a single
instruction. In this case since cmpxchg is available for the 486 and
later architectures there's really no point in doing this and there's so
such implementation, hence the link error.
Brian