Implement most AO_fetch_compare_and_swap primitives

* src/atomic_ops.c (AO_fetch_compare_and_swap_emulation): Implement.
* src/atomic_ops.h: Remove FIXME for AO_fetch_compare_and_swap.
* src/atomic_ops/generalize.h (AO_fetch_compare_and_swap_acquire,
AO_fetch_compare_and_swap_release, AO_fetch_compare_and_swap_acquire,
AO_fetch_compare_and_swap_write, AO_fetch_compare_and_swap_read,
AO_fetch_compare_and_swap, AO_fetch_compare_and_swap_full,
AO_fetch_compare_and_swap_release_write,
AO_fetch_compare_and_swap_acquire_read,
AO_fetch_compare_and_swap_dd_acquire_read): Implement; define the
corresponding AO_HAVE_... macro.
* src/atomic_ops/sysdeps/ao_t_is_int.h
(AO_int_fetch_compare_and_swap_full,
AO_int_fetch_compare_and_swap_acquire,
AO_int_fetch_compare_and_swap_release,
AO_int_fetch_compare_and_swap_write,
AO_int_fetch_compare_and_swap_read, AO_int_fetch_compare_and_swap):
Likewise.
* src/atomic_ops/sysdeps/armcc/arm_v6.h (AO_fetch_compare_and_swap):
Likewise.
* src/atomic_ops/sysdeps/emul_cas.h (AO_fetch_compare_and_swap_full):
Likewise.
* src/atomic_ops/sysdeps/gcc/arm.h (AO_fetch_compare_and_swap):
Likewise.
* src/atomic_ops/sysdeps/gcc/hexagon.h (AO_fetch_compare_and_swap):
Likewise.
* src/atomic_ops/sysdeps/gcc/ia64.h
(AO_fetch_compare_and_swap_acquire, AO_fetch_compare_and_swap_release,
AO_char_fetch_compare_and_swap_acquire,
AO_char_fetch_compare_and_swap_release,
AO_short_fetch_compare_and_swap_acquire,
AO_short_fetch_compare_and_swap_release,
AO_int_fetch_compare_and_swap_acquire,
AO_int_fetch_compare_and_swap_release): Likewise.
* src/atomic_ops/sysdeps/gcc/powerpc.h (AO_fetch_compare_and_swap,
AO_fetch_compare_and_swap_acquire, AO_fetch_compare_and_swap_release,
AO_fetch_compare_and_swap_full): Likewise.
* src/atomic_ops/sysdeps/gcc/x86.h (AO_fetch_compare_and_swap_full):
Likewise.
* src/atomic_ops/sysdeps/gcc/x86_64.h
(AO_fetch_compare_and_swap_full): Likewise.
* src/atomic_ops/sysdeps/generic_pthread.h
(AO_fetch_compare_and_swap_full): Likewise.
* src/atomic_ops/sysdeps/hpc/ia64.h
(AO_fetch_compare_and_swap_acquire, AO_fetch_compare_and_swap_release,
AO_char_fetch_compare_and_swap_acquire,
AO_char_fetch_compare_and_swap_release,
AO_short_fetch_compare_and_swap_acquire,
AO_short_fetch_compare_and_swap_release): Likewise.
* src/atomic_ops/sysdeps/icc/ia64.h
(AO_fetch_compare_and_swap_acquire, AO_fetch_compare_and_swap_release,
AO_char_fetch_compare_and_swap_acquire,
AO_char_fetch_compare_and_swap_release,
AO_short_fetch_compare_and_swap_acquire,
AO_short_fetch_compare_and_swap_release,
AO_int_fetch_compare_and_swap_acquire,
AO_int_fetch_compare_and_swap_release): Likewise.
* src/atomic_ops/sysdeps/msftc/common32_defs.h
(AO_fetch_compare_and_swap_full): Likewise.
* src/atomic_ops/sysdeps/msftc/x86_64.h
(AO_fetch_compare_and_swap_full): Likewise.
* src/atomic_ops/sysdeps/sunc/x86.h
(AO_fetch_compare_and_swap_full): Likewise.
* src/atomic_ops/sysdeps/sunc/x86_64.h
(AO_fetch_compare_and_swap_full): Likewise.
* src/atomic_ops/sysdeps/emul_cas.h
(AO_fetch_compare_and_swap_emulation): Declare the function.
* src/atomic_ops/sysdeps/gcc/mips.h: Adjust FIXME.
* src/atomic_ops/sysdeps/gcc/sparc.h: Likewise.
* src/atomic_ops/sysdeps/ibmc/powerpc.h (AO_fetch_compare_and_swap,
AO_fetch_compare_and_swap_acquire, AO_fetch_compare_and_swap_release,
AO_fetch_compare_and_swap_full): Add implementation stub.
* tests/list_atomic.template (list_atomicXX): Add
AO_fetch_compare_and_swapXX call.
* tests/test_atomic_include.template (test_atomicXX): Likewise.

22 files changed, 698 insertions, 31 deletions

diff --git a/src/atomic_ops.c b/src/atomic_ops.c
index bd77bba..fb262b8 100644
--- a/src/atomic_ops.c
+++ b/src/atomic_ops.c
@@ -211,7 +211,26 @@ int AO_compare_and_swap_emulation(volatile AO_t *addr, AO_t old,
   return result;
 }
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_t AO_fetch_compare_and_swap_emulation(volatile AO_t *addr, AO_t old_val,
+                                         AO_t new_val)
+{
+  AO_TS_t *my_lock = AO_locks + AO_HASH(addr);
+  AO_t fetched_val;
+
+# ifndef AO_USE_NO_SIGNALS
+    sigset_t old_sigs;
+    block_all_signals(&old_sigs);
+# endif
+  lock(my_lock);
+  fetched_val = *addr;
+  if (fetched_val == old_val)
+    *addr = new_val;
+  unlock(my_lock);
+# ifndef AO_USE_NO_SIGNALS
+    sigprocmask(SIG_SETMASK, &old_sigs, NULL);
+# endif
+  return fetched_val;
+}
 
 int AO_compare_double_and_swap_double_emulation(volatile AO_double_t *addr,
                                                 AO_t old_val1, AO_t old_val2,
diff --git a/src/atomic_ops.h b/src/atomic_ops.h
index ca3a21a..4a633b9 100644
--- a/src/atomic_ops.h
+++ b/src/atomic_ops.h
@@ -356,7 +356,6 @@
 # else
 #  error Cannot implement AO_compare_and_swap_full on this architecture.
 # endif
-/* FIXME: same for AO_fetch_compare_and_swap */
 #endif /* AO_REQUIRE_CAS && !AO_HAVE_compare_and_swap ... */
 
 /* The most common way to clear a test-and-set location         */
diff --git a/src/atomic_ops/generalize.h b/src/atomic_ops/generalize.h
index 2131685..4cbf0ea 100644
--- a/src/atomic_ops/generalize.h
+++ b/src/atomic_ops/generalize.h
@@ -1053,8 +1053,6 @@
 # endif
 #endif /* AO_HAVE_compare_and_swap_full */
 
-/* FIXME: implement AO_fetch_compare_and_swap */
-
 #if !defined(AO_HAVE_compare_and_swap) \
     && defined(AO_HAVE_compare_and_swap_release)
 # define AO_compare_and_swap(addr,old,new_val) \
@@ -1126,6 +1124,120 @@
 # endif
 #endif /* !AO_NO_DD_ORDERING */
 
+/* AO_fetch_compare_and_swap */
+#if defined(AO_HAVE_fetch_compare_and_swap) && defined(AO_HAVE_nop_full) \
+    && !defined(AO_HAVE_fetch_compare_and_swap_acquire)
+  AO_INLINE AO_t
+  AO_fetch_compare_and_swap_acquire(volatile AO_t *addr, AO_t old_val,
+                                    AO_t new_val)
+  {
+    AO_t result = AO_fetch_compare_and_swap(addr, old_val, new_val);
+    AO_nop_full();
+    return result;
+  }
+# define AO_HAVE_fetch_compare_and_swap_acquire
+#endif
+#if defined(AO_HAVE_fetch_compare_and_swap) && defined(AO_HAVE_nop_full) \
+    && !defined(AO_HAVE_fetch_compare_and_swap_release)
+# define AO_fetch_compare_and_swap_release(addr,old_val,new_val) \
+              (AO_nop_full(), AO_fetch_compare_and_swap(addr,old_val,new_val))
+# define AO_HAVE_fetch_compare_and_swap_release
+#endif
+#if defined(AO_HAVE_fetch_compare_and_swap_full)
+# if !defined(AO_HAVE_fetch_compare_and_swap_release)
+#   define AO_fetch_compare_and_swap_release(addr,old_val,new_val) \
+                        AO_fetch_compare_and_swap_full(addr,old_val,new_val)
+#   define AO_HAVE_fetch_compare_and_swap_release
+# endif
+# if !defined(AO_HAVE_fetch_compare_and_swap_acquire)
+#   define AO_fetch_compare_and_swap_acquire(addr,old_val,new_val) \
+                        AO_fetch_compare_and_swap_full(addr,old_val,new_val)
+#   define AO_HAVE_fetch_compare_and_swap_acquire
+# endif
+# if !defined(AO_HAVE_fetch_compare_and_swap_write)
+#   define AO_fetch_compare_and_swap_write(addr,old_val,new_val) \
+                        AO_fetch_compare_and_swap_full(addr,old_val,new_val)
+#   define AO_HAVE_fetch_compare_and_swap_write
+# endif
+# if !defined(AO_HAVE_fetch_compare_and_swap_read)
+#   define AO_fetch_compare_and_swap_read(addr,old_val,new_val) \
+                        AO_fetch_compare_and_swap_full(addr,old_val,new_val)
+#   define AO_HAVE_fetch_compare_and_swap_read
+# endif
+#endif /* AO_HAVE_fetch_compare_and_swap_full */
+
+#if !defined(AO_HAVE_fetch_compare_and_swap) \
+    && defined(AO_HAVE_fetch_compare_and_swap_release)
+# define AO_fetch_compare_and_swap(addr,old_val,new_val) \
+                AO_fetch_compare_and_swap_release(addr,old_val,new_val)
+# define AO_HAVE_fetch_compare_and_swap
+#endif
+#if !defined(AO_HAVE_fetch_compare_and_swap) \
+    && defined(AO_HAVE_fetch_compare_and_swap_acquire)
+# define AO_fetch_compare_and_swap(addr,old_val,new_val) \
+                AO_fetch_compare_and_swap_acquire(addr,old_val,new_val)
+# define AO_HAVE_fetch_compare_and_swap
+#endif
+#if !defined(AO_HAVE_fetch_compare_and_swap) \
+    && defined(AO_HAVE_fetch_compare_and_swap_write)
+# define AO_fetch_compare_and_swap(addr,old_val,new_val) \
+                AO_fetch_compare_and_swap_write(addr,old_val,new_val)
+# define AO_HAVE_fetch_compare_and_swap
+#endif
+#if !defined(AO_HAVE_fetch_compare_and_swap) \
+    && defined(AO_HAVE_fetch_compare_and_swap_read)
+# define AO_fetch_compare_and_swap(addr,old_val,new_val) \
+                AO_fetch_compare_and_swap_read(addr,old_val,new_val)
+# define AO_HAVE_fetch_compare_and_swap
+#endif
+
+#if defined(AO_HAVE_fetch_compare_and_swap_acquire) \
+    && defined(AO_HAVE_nop_full) \
+    && !defined(AO_HAVE_fetch_compare_and_swap_full)
+# define AO_fetch_compare_and_swap_full(addr,old_val,new_val) \
+      (AO_nop_full(), AO_fetch_compare_and_swap_acquire(addr,old_val,new_val))
+# define AO_HAVE_fetch_compare_and_swap_full
+#endif
+
+#if !defined(AO_HAVE_fetch_compare_and_swap_release_write) \
+    && defined(AO_HAVE_fetch_compare_and_swap_write)
+# define AO_fetch_compare_and_swap_release_write(addr,old_val,new_val) \
+                AO_fetch_compare_and_swap_write(addr,old_val,new_val)
+# define AO_HAVE_fetch_compare_and_swap_release_write
+#endif
+#if !defined(AO_HAVE_fetch_compare_and_swap_release_write) \
+    && defined(AO_HAVE_fetch_compare_and_swap_release)
+# define AO_fetch_compare_and_swap_release_write(addr,old_val,new_val) \
+                AO_fetch_compare_and_swap_release(addr,old_val,new_val)
+# define AO_HAVE_fetch_compare_and_swap_release_write
+#endif
+#if !defined(AO_HAVE_fetch_compare_and_swap_acquire_read) \
+    && defined(AO_HAVE_fetch_compare_and_swap_read)
+# define AO_fetch_compare_and_swap_acquire_read(addr,old_val,new_val) \
+                AO_fetch_compare_and_swap_read(addr,old_val,new_val)
+# define AO_HAVE_fetch_compare_and_swap_acquire_read
+#endif
+#if !defined(AO_HAVE_fetch_compare_and_swap_acquire_read) \
+    && defined(AO_HAVE_fetch_compare_and_swap_acquire)
+# define AO_fetch_compare_and_swap_acquire_read(addr,old_val,new_val) \
+                AO_fetch_compare_and_swap_acquire(addr,old_val,new_val)
+# define AO_HAVE_fetch_compare_and_swap_acquire_read
+#endif
+
+#ifdef AO_NO_DD_ORDERING
+# if defined(AO_HAVE_fetch_compare_and_swap_acquire_read)
+#   define AO_fetch_compare_and_swap_dd_acquire_read(addr,old_val,new_val) \
+                AO_fetch_compare_and_swap_acquire_read(addr,old_val,new_val)
+#   define AO_HAVE_fetch_compare_and_swap_dd_acquire_read
+# endif
+#else
+# if defined(AO_HAVE_fetch_compare_and_swap)
+#   define AO_fetch_compare_and_swap_dd_acquire_read(addr,old_val,new_val) \
+                AO_fetch_compare_and_swap(addr,old_val,new_val)
+#   define AO_HAVE_fetch_compare_and_swap_dd_acquire_read
+# endif
+#endif /* !AO_NO_DD_ORDERING */
+
 #include "generalize-small.h"
 
 /* Compare_double_and_swap_double */
diff --git a/src/atomic_ops/sysdeps/ao_t_is_int.h b/src/atomic_ops/sysdeps/ao_t_is_int.h
index 33d3e4d..b40bc12 100644
--- a/src/atomic_ops/sysdeps/ao_t_is_int.h
+++ b/src/atomic_ops/sysdeps/ao_t_is_int.h
@@ -72,7 +72,49 @@
 # define AO_HAVE_int_compare_and_swap
 #endif
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+/* AO_fetch_compare_and_swap */
+#if defined(AO_HAVE_fetch_compare_and_swap_full) \
+    && !defined(AO_HAVE_int_fetch_compare_and_swap_full)
+# define AO_int_fetch_compare_and_swap_full(addr, old, new_val) \
+       ((int)AO_fetch_compare_and_swap_full((volatile AO_t *)(addr), \
+                                            (AO_t)(old), (AO_t)(new_val)))
+# define AO_HAVE_int_fetch_compare_and_swap_full
+#endif
+#if defined(AO_HAVE_fetch_compare_and_swap_acquire) \
+    && !defined(AO_HAVE_int_fetch_compare_and_swap_acquire)
+# define AO_int_fetch_compare_and_swap_acquire(addr, old, new_val) \
+       ((int)AO_fetch_compare_and_swap_acquire((volatile AO_t *)(addr), \
+                                               (AO_t)(old), (AO_t)(new_val)))
+# define AO_HAVE_int_fetch_compare_and_swap_acquire
+#endif
+#if defined(AO_HAVE_fetch_compare_and_swap_release) \
+    && !defined(AO_HAVE_int_fetch_compare_and_swap_release)
+# define AO_int_fetch_compare_and_swap_release(addr, old, new_val) \
+       ((int)AO_fetch_compare_and_swap_release((volatile AO_t *)(addr), \
+                                               (AO_t)(old), (AO_t)(new_val)))
+# define AO_HAVE_int_fetch_compare_and_swap_release
+#endif
+#if defined(AO_HAVE_fetch_compare_and_swap_write) \
+    && !defined(AO_HAVE_int_fetch_compare_and_swap_write)
+# define AO_int_fetch_compare_and_swap_write(addr, old, new_val) \
+       ((int)AO_fetch_compare_and_swap_write((volatile AO_t *)(addr), \
+                                             (AO_t)(old), (AO_t)(new_val)))
+# define AO_HAVE_int_fetch_compare_and_swap_write
+#endif
+#if defined(AO_HAVE_fetch_compare_and_swap_read) \
+    && !defined(AO_HAVE_int_fetch_compare_and_swap_read)
+# define AO_int_fetch_compare_and_swap_read(addr, old, new_val) \
+       ((int)AO_fetch_compare_and_swap_read((volatile AO_t *)(addr), \
+                                            (AO_t)(old), (AO_t)(new_val)))
+# define AO_HAVE_int_fetch_compare_and_swap_read
+#endif
+#if defined(AO_HAVE_fetch_compare_and_swap) \
+    && !defined(AO_HAVE_int_fetch_compare_and_swap)
+# define AO_int_fetch_compare_and_swap(addr, old, new_val) \
+       ((int)AO_fetch_compare_and_swap((volatile AO_t *)(addr), \
+                                       (AO_t)(old), (AO_t)(new_val)))
+# define AO_HAVE_int_fetch_compare_and_swap
+#endif
 
 /* AO_load */
 #if defined(AO_HAVE_load_acquire) \
diff --git a/src/atomic_ops/sysdeps/armcc/arm_v6.h b/src/atomic_ops/sysdeps/armcc/arm_v6.h
index 16e7f1a..c2c9b1d 100644
--- a/src/atomic_ops/sysdeps/armcc/arm_v6.h
+++ b/src/atomic_ops/sysdeps/armcc/arm_v6.h
@@ -198,7 +198,26 @@ __asm__ {
 }
 #define AO_HAVE_compare_and_swap
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_INLINE AO_t
+AO_fetch_compare_and_swap(volatile AO_t *addr, AO_t old_val, AO_t new_val)
+{
+         AO_t fetched_val, tmp;
+
+retry:
+__asm__ {
+        mov     tmp, #2
+        ldrex   fetched_val, [addr]
+        teq     fetched_val, old_val
+#     ifdef __thumb__
+        it      eq
+#     endif
+        strexeq tmp, new_val, [addr]
+        teq     tmp, #1
+        beq     retry
+        }
+        return fetched_val;
+}
+#define AO_HAVE_fetch_compare_and_swap
 
 /* helper functions for the Realview compiler: LDREXD is not usable
  * with inline assembler, so use the "embedded" assembler as
diff --git a/src/atomic_ops/sysdeps/emul_cas.h b/src/atomic_ops/sysdeps/emul_cas.h
index fa93141..4ea2097 100644
--- a/src/atomic_ops/sysdeps/emul_cas.h
+++ b/src/atomic_ops/sysdeps/emul_cas.h
@@ -46,6 +46,9 @@
 int AO_compare_and_swap_emulation(volatile AO_t *addr, AO_t old,
                                   AO_t new_val);
 
+AO_t AO_fetch_compare_and_swap_emulation(volatile AO_t *addr, AO_t old_val,
+                                         AO_t new_val);
+
 int AO_compare_double_and_swap_double_emulation(volatile AO_double_t *addr,
                                                 AO_t old_val1, AO_t old_val2,
                                                 AO_t new_val1, AO_t new_val2);
@@ -56,6 +59,12 @@ void AO_store_full_emulation(volatile AO_t *addr, AO_t val);
        AO_compare_and_swap_emulation(addr, old, newval)
 #define AO_HAVE_compare_and_swap_full
 
+#ifndef AO_HAVE_fetch_compare_and_swap_full
+# define AO_fetch_compare_and_swap_full(addr, old, newval) \
+                AO_fetch_compare_and_swap_emulation(addr, old, newval)
+# define AO_HAVE_fetch_compare_and_swap_full
+#endif
+
 #ifndef AO_HAVE_compare_double_and_swap_double
 # define AO_compare_double_and_swap_double_full(addr, old1, old2, \
                                                 newval1, newval2) \
@@ -64,8 +73,6 @@ void AO_store_full_emulation(volatile AO_t *addr, AO_t val);
 # define AO_HAVE_compare_double_and_swap_double_full
 #endif
 
-/* FIXME: implement AO_fetch_compare_and_swap */
-
 #undef AO_store
 #undef AO_HAVE_store
 #undef AO_store_write
diff --git a/src/atomic_ops/sysdeps/gcc/arm.h b/src/atomic_ops/sysdeps/gcc/arm.h
index 5a53d4e..4466c5b 100644
--- a/src/atomic_ops/sysdeps/gcc/arm.h
+++ b/src/atomic_ops/sysdeps/gcc/arm.h
@@ -265,7 +265,29 @@ AO_compare_and_swap(volatile AO_t *addr, AO_t old_val, AO_t new_val)
 }
 #define AO_HAVE_compare_and_swap
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_INLINE AO_t
+AO_fetch_compare_and_swap(volatile AO_t *addr, AO_t old_val, AO_t new_val)
+{
+  AO_t fetched_val, flag;
+
+  __asm__ __volatile__("@AO_fetch_compare_and_swap\n"
+    AO_THUMB_GO_ARM
+    "1:     mov     %0, #2\n"           /* store a flag */
+    "       ldrex   %1, [%3]\n"         /* get original */
+    "       teq     %1, %4\n"           /* see if match */
+#   ifdef __thumb2__
+      "       it      eq\n"
+#   endif
+    "       strexeq %0, %5, [%3]\n"     /* store new one if matched */
+    "       teq     %0, #1\n"
+    "       beq     1b\n"               /* if update failed, repeat */
+    AO_THUMB_RESTORE_MODE
+    : "=&r"(flag), "=&r"(fetched_val), "+m"(*addr)
+    : "r"(addr), "r"(old_val), "r"(new_val)
+    : AO_THUMB_SWITCH_CLOBBERS "cc");
+  return fetched_val;
+}
+#define AO_HAVE_fetch_compare_and_swap
 
 #if !defined(__ARM_ARCH_6__) && !defined(__ARM_ARCH_6J__) \
     && !defined(__ARM_ARCH_6T2__) && !defined(__ARM_ARCH_6Z__) \
diff --git a/src/atomic_ops/sysdeps/gcc/hexagon.h b/src/atomic_ops/sysdeps/gcc/hexagon.h
index 9dff708..fed10e0 100644
--- a/src/atomic_ops/sysdeps/gcc/hexagon.h
+++ b/src/atomic_ops/sysdeps/gcc/hexagon.h
@@ -92,6 +92,27 @@ AO_compare_and_swap(volatile AO_t *addr, AO_t old, AO_t new_val)
 }
 #define AO_HAVE_compare_and_swap
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_INLINE AO_t
+AO_fetch_compare_and_swap(volatile AO_t *addr, AO_t old_val, AO_t new_val)
+{
+  AO_t __oldval;
+
+  __asm__ __volatile__(
+     "1:\n"
+     "  %0 = memw_locked(%2);\n"        /* load and reserve            */
+     "  {\n"
+     "    p2 = cmp.eq(%0,%3);\n"        /* if load is not equal to     */
+     "    if (!p2.new) jump:nt 2f; \n"  /* old_val, fail               */
+     "  }\n"
+     "  memw_locked(%2,p1) = %4;\n"     /* else store conditional      */
+     "  if (!p1) jump 1b;\n"            /* retry if lost reservation   */
+     "2:\n"
+     : "=&r" (__oldval), "+m"(*addr)
+     : "r" (addr), "r" (old_val), "r" (new_val)
+     : "p1", "p2", "memory"
+  );
+  return __oldval;
+}
+#define AO_HAVE_fetch_compare_and_swap
 
 #include "../ao_t_is_int.h"
diff --git a/src/atomic_ops/sysdeps/gcc/ia64.h b/src/atomic_ops/sysdeps/gcc/ia64.h
index 086f314..94ddbb0 100644
--- a/src/atomic_ops/sysdeps/gcc/ia64.h
+++ b/src/atomic_ops/sysdeps/gcc/ia64.h
@@ -189,8 +189,6 @@ AO_compare_and_swap_release(volatile AO_t *addr,
 }
 #define AO_HAVE_compare_and_swap_release
 
-/* FIXME: implement AO_fetch_compare_and_swap */
-
 AO_INLINE int
 AO_char_compare_and_swap_acquire(volatile unsigned char *addr,
                                  unsigned char old, unsigned char new_val)
@@ -247,6 +245,92 @@ AO_short_compare_and_swap_release(volatile unsigned short *addr,
 }
 #define AO_HAVE_short_compare_and_swap_release
 
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_acquire(volatile AO_t *addr, AO_t old, AO_t new_val)
+{
+  AO_t fetched_val;
+  AO_MASK(old);
+  __asm__ __volatile__(AO_SWIZZLE
+                       "mov ar.ccv=%[old] ;; cmpxchg" AO_LEN
+                       ".acq %0=[%1],%[new_val],ar.ccv"
+                       : "=r"(fetched_val) AO_OUT_ADDR
+                       : AO_IN_ADDR, [new_val]"r"(new_val), [old]"r"(old)
+                       : "memory");
+  return fetched_val;
+}
+#define AO_HAVE_fetch_compare_and_swap_acquire
+
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_release(volatile AO_t *addr, AO_t old, AO_t new_val)
+{
+  AO_t fetched_val;
+  AO_MASK(old);
+  __asm__ __volatile__(AO_SWIZZLE
+                       "mov ar.ccv=%[old] ;; cmpxchg" AO_LEN
+                       ".rel %0=[%1],%[new_val],ar.ccv"
+                       : "=r"(fetched_val) AO_OUT_ADDR
+                       : AO_IN_ADDR, [new_val]"r"(new_val), [old]"r"(old)
+                       : "memory");
+  return fetched_val;
+}
+#define AO_HAVE_fetch_compare_and_swap_release
+
+AO_INLINE unsigned char
+AO_char_fetch_compare_and_swap_acquire(volatile unsigned char *addr,
+                                unsigned char old, unsigned char new_val)
+{
+  unsigned char fetched_val;
+  __asm__ __volatile__(AO_SWIZZLE
+               "mov ar.ccv=%[old] ;; cmpxchg1.acq %0=[%1],%[new_val],ar.ccv"
+               : "=r"(fetched_val) AO_OUT_ADDR
+               : AO_IN_ADDR, [new_val]"r"(new_val), [old]"r"((AO_t)old)
+               : "memory");
+  return fetched_val;
+}
+#define AO_HAVE_char_fetch_compare_and_swap_acquire
+
+AO_INLINE unsigned char
+AO_char_fetch_compare_and_swap_release(volatile unsigned char *addr,
+                                unsigned char old, unsigned char new_val)
+{
+  unsigned char fetched_val;
+  __asm__ __volatile__(AO_SWIZZLE
+                "mov ar.ccv=%[old] ;; cmpxchg1.rel %0=[%1],%[new_val],ar.ccv"
+                : "=r"(fetched_val) AO_OUT_ADDR
+                : AO_IN_ADDR, [new_val]"r"(new_val), [old]"r"((AO_t)old)
+                : "memory");
+  return fetched_val;
+}
+#define AO_HAVE_char_fetch_compare_and_swap_release
+
+AO_INLINE unsigned short
+AO_short_fetch_compare_and_swap_acquire(volatile unsigned short *addr,
+                                unsigned short old, unsigned short new_val)
+{
+  unsigned short fetched_val;
+  __asm__ __volatile__(AO_SWIZZLE
+                "mov ar.ccv=%[old] ;; cmpxchg2.acq %0=[%1],%[new_val],ar.ccv"
+                : "=r"(fetched_val) AO_OUT_ADDR
+                : AO_IN_ADDR, [new_val]"r"(new_val), [old]"r"((AO_t)old)
+                : "memory");
+  return fetched_val;
+}
+#define AO_HAVE_short_fetch_compare_and_swap_acquire
+
+AO_INLINE unsigned short
+AO_short_fetch_compare_and_swap_release(volatile unsigned short *addr,
+                                unsigned short old, unsigned short new_val)
+{
+  unsigned short fetched_val;
+  __asm__ __volatile__(AO_SWIZZLE
+                "mov ar.ccv=%[old] ;; cmpxchg2.rel %0=[%1],%[new_val],ar.ccv"
+                : "=r"(fetched_val) AO_OUT_ADDR
+                : AO_IN_ADDR, [new_val]"r"(new_val), [old]"r"((AO_t)old)
+                : "memory");
+  return fetched_val;
+}
+#define AO_HAVE_short_fetch_compare_and_swap_release
+
 #ifndef _ILP32
 
 AO_INLINE int
@@ -273,6 +357,30 @@ AO_int_compare_and_swap_release(volatile unsigned int *addr,
 }
 #define AO_HAVE_int_compare_and_swap_release
 
+AO_INLINE unsigned int
+AO_int_fetch_compare_and_swap_acquire(volatile unsigned int *addr,
+                                unsigned int old, unsigned int new_val)
+{
+  unsigned int fetched_val;
+  __asm__ __volatile__("mov ar.ccv=%3 ;; cmpxchg4.acq %0=[%1],%2,ar.ccv"
+                       : "=r"(fetched_val)
+                       : AO_IN_ADDR, "r"(new_val), "r"((AO_t)old) : "memory");
+  return fetched_val;
+}
+#define AO_HAVE_int_fetch_compare_and_swap_acquire
+
+AO_INLINE unsigned int
+AO_int_fetch_compare_and_swap_release(volatile unsigned int *addr,
+                                unsigned int old, unsigned int new_val)
+{
+  unsigned int fetched_val;
+  __asm__ __volatile__("mov ar.ccv=%3 ;; cmpxchg4.rel %0=[%1],%2,ar.ccv"
+                       : "=r"(fetched_val)
+                       : AO_IN_ADDR, "r"(new_val), "r"((AO_t)old) : "memory");
+  return fetched_val;
+}
+#define AO_HAVE_int_fetch_compare_and_swap_release
+
 #endif /* !_ILP32 */
 
 /* FIXME: Add compare_and_swap_double as soon as there is widely        */
diff --git a/src/atomic_ops/sysdeps/gcc/mips.h b/src/atomic_ops/sysdeps/gcc/mips.h
index a91426c..9adfe21 100644
--- a/src/atomic_ops/sysdeps/gcc/mips.h
+++ b/src/atomic_ops/sysdeps/gcc/mips.h
@@ -96,9 +96,7 @@ AO_compare_and_swap_full(volatile AO_t *addr, AO_t old, AO_t new_val) {
 
 /* FIXME: implement AO_fetch_compare_and_swap */
 
-/*
- * FIXME: We should also implement fetch_and_add and or primitives
- * directly.
- */
+/* FIXME: We should also implement AO_fetch_and_add, AO_and, AO_or,     */
+/* AO_xor primitives directly.                                          */
 
 #include "../ao_t_is_int.h"
diff --git a/src/atomic_ops/sysdeps/gcc/powerpc.h b/src/atomic_ops/sysdeps/gcc/powerpc.h
index 5312a8e..36cb613 100644
--- a/src/atomic_ops/sysdeps/gcc/powerpc.h
+++ b/src/atomic_ops/sysdeps/gcc/powerpc.h
@@ -225,7 +225,68 @@ AO_compare_and_swap_full(volatile AO_t *addr, AO_t old, AO_t new_val) {
 }
 #define AO_HAVE_compare_and_swap_full
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_INLINE AO_t
+AO_fetch_compare_and_swap(volatile AO_t *addr, AO_t old_val, AO_t new_val)
+{
+  AO_t fetched_val;
+#if defined(__powerpc64__) || defined(__ppc64__) || defined(__64BIT__)
+/* FIXME: Completely untested.  */
+  __asm__ __volatile__(
+               "1:ldarx %0,0,%1\n"   /* load and reserve                */
+               "cmpd %0, %3\n"       /* if load is not equal to         */
+               "bne 2f\n"            /*   old_val, fail                 */
+               "stdcx. %2,0,%1\n"    /* else store conditional          */
+               "bne- 1b\n"           /* retry if lost reservation       */
+               "2:\n"
+              : "=&r"(fetched_val),
+              : "r"(addr), "r"(new_val), "r"(old_val)
+              : "memory", "cr0");
+#else
+  __asm__ __volatile__(
+               "1:lwarx %0,0,%1\n"   /* load and reserve                */
+               "cmpw %0, %3\n"       /* if load is not equal to         */
+               "bne 2f\n"            /*   old_val, fail                 */
+               "stwcx. %2,0,%1\n"    /* else store conditional          */
+               "bne- 1b\n"           /* retry if lost reservation       */
+               "2:\n"
+              : "=&r"(fetched_val),
+              : "r"(addr), "r"(new_val), "r"(old_val)
+              : "memory", "cr0");
+#endif
+  return fetched_val;
+}
+#define AO_HAVE_fetch_compare_and_swap
+
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_acquire(volatile AO_t *addr, AO_t old_val,
+                                  AO_t new_val)
+{
+  AO_t result = AO_fetch_compare_and_swap(addr, old_val, new_val);
+  AO_lwsync();
+  return result;
+}
+#define AO_HAVE_fetch_compare_and_swap_acquire
+
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_release(volatile AO_t *addr, AO_t old_val,
+                                  AO_t new_val)
+{
+  AO_lwsync();
+  return AO_fetch_compare_and_swap(addr, old_val, new_val);
+}
+#define AO_HAVE_fetch_compare_and_swap_release
+
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_full(volatile AO_t *addr, AO_t old_val,
+                               AO_t new_val)
+{
+  AO_t result;
+  AO_lwsync();
+  result = AO_fetch_compare_and_swap(addr, old_val, new_val);
+  AO_lwsync();
+  return result;
+}
+#define AO_HAVE_fetch_compare_and_swap_full
 
 AO_INLINE AO_t
 AO_fetch_and_add(volatile AO_t *addr, AO_t incr) {
diff --git a/src/atomic_ops/sysdeps/gcc/sparc.h b/src/atomic_ops/sysdeps/gcc/sparc.h
index 7647893..af81629 100644
--- a/src/atomic_ops/sysdeps/gcc/sparc.h
+++ b/src/atomic_ops/sysdeps/gcc/sparc.h
@@ -61,9 +61,9 @@ AO_compare_and_swap_full(volatile AO_t *addr, AO_t old, AO_t new_val) {
   return (int)ret;
 }
 #define AO_HAVE_compare_and_swap_full
-#endif /* !AO_NO_SPARC_V9 */
 
 /* FIXME: implement AO_fetch_compare_and_swap */
+#endif /* !AO_NO_SPARC_V9 */
 
 /* FIXME: This needs to be extended for SPARC v8 and v9.        */
 /* SPARC V8 also has swap.  V9 has CAS.                         */
diff --git a/src/atomic_ops/sysdeps/gcc/x86.h b/src/atomic_ops/sysdeps/gcc/x86.h
index c408dbc..44e815a 100644
--- a/src/atomic_ops/sysdeps/gcc/x86.h
+++ b/src/atomic_ops/sysdeps/gcc/x86.h
@@ -149,7 +149,23 @@ AO_compare_and_swap_full(volatile AO_t *addr, AO_t old, AO_t new_val)
 }
 #define AO_HAVE_compare_and_swap_full
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_full(volatile AO_t *addr, AO_t old_val,
+                               AO_t new_val)
+{
+# ifdef AO_USE_SYNC_CAS_BUILTIN
+    return __sync_val_compare_and_swap(addr, old_val, new_val
+                                       /* empty protection list */);
+# else
+    AO_t fetched_val;
+    __asm__ __volatile__("lock; cmpxchgl %3, %4"
+                         : "=a" (fetched_val), "=m" (*addr)
+                         : "0" (old_val), "q" (new_val), "m" (*addr)
+                         : "memory");
+    return fetched_val;
+# endif
+}
+#define AO_HAVE_fetch_compare_and_swap_full
 
 /* Returns nonzero if the comparison succeeded. */
 /* Really requires at least a Pentium.          */
diff --git a/src/atomic_ops/sysdeps/gcc/x86_64.h b/src/atomic_ops/sysdeps/gcc/x86_64.h
index de68c0f..7e869c1 100644
--- a/src/atomic_ops/sysdeps/gcc/x86_64.h
+++ b/src/atomic_ops/sysdeps/gcc/x86_64.h
@@ -143,7 +143,23 @@ AO_compare_and_swap_full(volatile AO_t *addr, AO_t old, AO_t new_val)
 }
 #define AO_HAVE_compare_and_swap_full
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_full(volatile AO_t *addr, AO_t old_val,
+                               AO_t new_val)
+{
+# ifdef AO_USE_SYNC_CAS_BUILTIN
+    return __sync_val_compare_and_swap(addr, old_val, new_val
+                                       /* empty protection list */);
+# else
+    AO_t fetched_val;
+    __asm__ __volatile__("lock; cmpxchgq %3, %4"
+                         : "=a" (fetched_val), "=m" (*addr)
+                         : "0" (old_val), "q" (new_val), "m" (*addr)
+                         : "memory");
+    return fetched_val;
+# endif
+}
+#define AO_HAVE_fetch_compare_and_swap_full
 
 #ifdef AO_CMPXCHG16B_AVAILABLE
 
diff --git a/src/atomic_ops/sysdeps/generic_pthread.h b/src/atomic_ops/sysdeps/generic_pthread.h
index f051fc9..ee18f52 100644
--- a/src/atomic_ops/sysdeps/generic_pthread.h
+++ b/src/atomic_ops/sysdeps/generic_pthread.h
@@ -233,7 +233,20 @@ AO_compare_and_swap_full(volatile AO_t *addr, AO_t old, AO_t new_val)
 }
 #define AO_HAVE_compare_and_swap_full
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_full(volatile AO_t *addr, AO_t old_val,
+                               AO_t new_val)
+{
+  AO_t fetched_val;
+
+  pthread_mutex_lock(&AO_pt_lock);
+  fetched_val = *addr;
+  if (fetched_val == old_val)
+    *addr = new_val;
+  pthread_mutex_unlock(&AO_pt_lock);
+  return fetched_val;
+}
+#define AO_HAVE_fetch_compare_and_swap_full
 
 /* Unlike real architectures, we define both double-width CAS variants. */
 
diff --git a/src/atomic_ops/sysdeps/hpc/ia64.h b/src/atomic_ops/sysdeps/hpc/ia64.h
index 68e78cd..a71deff 100644
--- a/src/atomic_ops/sysdeps/hpc/ia64.h
+++ b/src/atomic_ops/sysdeps/hpc/ia64.h
@@ -107,8 +107,6 @@ AO_compare_and_swap_release(volatile AO_t *addr,
 }
 #define AO_HAVE_compare_and_swap_release
 
-/* FIXME: implement AO_fetch_compare_and_swap */
-
 AO_INLINE int
 AO_char_compare_and_swap_acquire(volatile unsigned char *addr,
                                  unsigned char old, unsigned char new_val)
@@ -161,6 +159,73 @@ AO_short_compare_and_swap_release(volatile unsigned short *addr,
 }
 #define AO_HAVE_short_compare_and_swap_release
 
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_acquire(volatile AO_t *addr, AO_t old_val,
+                                  AO_t new_val)
+{
+  _Asm_mov_to_ar(_AREG_CCV, old_val, _DOWN_MEM_FENCE);
+  return _Asm_cmpxchg(AO_T_SIZE, _SEM_ACQ, addr,
+                      new_val, _LDHINT_NONE, _DOWN_MEM_FENCE);
+}
+#define AO_HAVE_fetch_compare_and_swap_acquire
+
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_release(volatile AO_t *addr, AO_t old_val,
+                                  AO_t new_val)
+{
+  _Asm_mov_to_ar(_AREG_CCV, old_val, _UP_MEM_FENCE);
+  return _Asm_cmpxchg(AO_T_SIZE, _SEM_REL, addr,
+                      new_val, _LDHINT_NONE, _UP_MEM_FENCE);
+
+}
+#define AO_HAVE_fetch_compare_and_swap_release
+
+AO_INLINE unsigned char
+AO_char_fetch_compare_and_swap_acquire(volatile unsigned char *addr,
+                                unsigned char old_val, unsigned char new_val)
+{
+  _Asm_mov_to_ar(_AREG_CCV, old_val, _DOWN_MEM_FENCE);
+  return _Asm_cmpxchg(_SZ_B, _SEM_ACQ, addr,
+                      new_val, _LDHINT_NONE, _DOWN_MEM_FENCE);
+
+}
+#define AO_HAVE_char_fetch_compare_and_swap_acquire
+
+AO_INLINE unsigned char
+AO_char_fetch_compare_and_swap_release(volatile unsigned char *addr,
+                                unsigned char old_val, unsigned char new_val)
+{
+  _Asm_mov_to_ar(_AREG_CCV, old_val, _UP_MEM_FENCE);
+  return _Asm_cmpxchg(_SZ_B, _SEM_REL, addr,
+                      new_val, _LDHINT_NONE, _UP_MEM_FENCE);
+
+}
+#define AO_HAVE_char_fetch_compare_and_swap_release
+
+AO_INLINE unsigned short
+AO_short_fetch_compare_and_swap_acquire(volatile unsigned short *addr,
+                                        unsigned short old_val,
+                                        unsigned short new_val)
+{
+  _Asm_mov_to_ar(_AREG_CCV, old_val, _DOWN_MEM_FENCE);
+  return _Asm_cmpxchg(_SZ_B, _SEM_ACQ, addr,
+                      new_val, _LDHINT_NONE, _DOWN_MEM_FENCE);
+
+}
+#define AO_HAVE_short_fetch_compare_and_swap_acquire
+
+AO_INLINE unsigned short
+AO_short_fetch_compare_and_swap_release(volatile unsigned short *addr,
+                                        unsigned short old_val,
+                                        unsigned short new_val)
+{
+  _Asm_mov_to_ar(_AREG_CCV, old_val, _UP_MEM_FENCE);
+  return _Asm_cmpxchg(_SZ_B, _SEM_REL, addr,
+                      new_val, _LDHINT_NONE, _UP_MEM_FENCE);
+
+}
+#define AO_HAVE_short_fetch_compare_and_swap_release
+
 #ifndef __LP64__
 # include "../ao_t_is_int.h"
 #endif
diff --git a/src/atomic_ops/sysdeps/ibmc/powerpc.h b/src/atomic_ops/sysdeps/ibmc/powerpc.h
index a51c3d5..fef181a 100644
--- a/src/atomic_ops/sysdeps/ibmc/powerpc.h
+++ b/src/atomic_ops/sysdeps/ibmc/powerpc.h
@@ -120,5 +120,43 @@ AO_compare_and_swap_full(volatile AO_t *addr, AO_t old, AO_t new_val)
 }
 #define AO_HAVE_compare_and_swap_full
 
-/* FIXME: We should also implement AO_fetch_compare_and_swap,           */
-/* AO_fetch_and_add, AO_and/or/xor primitives directly.                 */
+/*AO_INLINE AO_t
+AO_fetch_compare_and_swap(volatile AO_t *addr, AO_t old_val, AO_t new_val)
+{
+# error FIXME Implement me
+}
+#define AO_HAVE_fetch_compare_and_swap*/
+
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_acquire(volatile AO_t *addr, AO_t old_val,
+                                  AO_t new_val)
+{
+  AO_t result = AO_fetch_compare_and_swap(addr, old_val, new_val);
+  AO_lwsync();
+  return result;
+}
+#define AO_HAVE_fetch_compare_and_swap_acquire
+
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_release(volatile AO_t *addr, AO_t old_val,
+                                  AO_t new_val)
+{
+  AO_lwsync();
+  return AO_fetch_compare_and_swap(addr, old_val, new_val);
+}
+#define AO_HAVE_fetch_compare_and_swap_release
+
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_full(volatile AO_t *addr, AO_t old_val,
+                               AO_t new_val)
+{
+  AO_t result;
+  AO_lwsync();
+  result = AO_fetch_compare_and_swap(addr, old_val, new_val);
+  AO_lwsync();
+  return result;
+}
+#define AO_HAVE_fetch_compare_and_swap_full
+
+/* FIXME: We should also implement AO_fetch_and_add, AO_and, AO_or,     */
+/* AO_xor primitives directly.                                          */
diff --git a/src/atomic_ops/sysdeps/icc/ia64.h b/src/atomic_ops/sysdeps/icc/ia64.h
index 9562265..8e65e9c 100644
--- a/src/atomic_ops/sysdeps/icc/ia64.h
+++ b/src/atomic_ops/sysdeps/icc/ia64.h
@@ -152,8 +152,6 @@ AO_compare_and_swap_release(volatile AO_t *addr,
 }
 #define AO_HAVE_compare_and_swap_release
 
-/* FIXME: implement AO_fetch_compare_and_swap */
-
 AO_INLINE int
 AO_char_compare_and_swap_acquire(volatile unsigned char *addr,
                                  unsigned char old, unsigned char new_val)
@@ -213,3 +211,73 @@ AO_int_compare_and_swap_release(volatile unsigned int *addr,
   return (oldval == old);
 }
 #define AO_HAVE_int_compare_and_swap_release
+
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_acquire(volatile AO_t *addr, AO_t old_val,
+                                  AO_t new_val)
+{
+  return _InterlockedCompareExchange64_acq(addr, new_val, old_val);
+}
+#define AO_HAVE_fetch_compare_and_swap_acquire
+
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_release(volatile AO_t *addr, AO_t old_val,
+                                  AO_t new_val)
+{
+  return _InterlockedCompareExchange64_rel(addr, new_val, old_val);
+}
+#define AO_HAVE_fetch_compare_and_swap_release
+
+AO_INLINE unsigned char
+AO_char_fetch_compare_and_swap_acquire(volatile unsigned char *addr,
+                                       unsigned char old_val,
+                                       unsigned char new_val)
+{
+  return _InterlockedCompareExchange8_acq(addr, new_val, old_val);
+}
+#define AO_HAVE_char_fetch_compare_and_swap_acquire
+
+AO_INLINE unsigned char
+AO_char_fetch_compare_and_swap_release(volatile unsigned char *addr,
+                                       unsigned char old_val,
+                                       unsigned char new_val)
+{
+  return _InterlockedCompareExchange8_rel(addr, new_val, old_val);
+}
+#define AO_HAVE_char_fetch_compare_and_swap_release
+
+AO_INLINE unsigned short
+AO_short_fetch_compare_and_swap_acquire(volatile unsigned short *addr,
+                                        unsigned short old_val,
+                                        unsigned short new_val)
+{
+  return _InterlockedCompareExchange16_acq(addr, new_val, old_val);
+}
+#define AO_HAVE_short_fetch_compare_and_swap_acquire
+
+AO_INLINE unsigned short
+AO_short_fetch_compare_and_swap_release(volatile unsigned short *addr,
+                                        unsigned short old_val,
+                                        unsigned short new_val)
+{
+  return _InterlockedCompareExchange16_rel(addr, new_val, old_val);
+}
+#define AO_HAVE_short_fetch_compare_and_swap_release
+
+AO_INLINE unsigned int
+AO_int_fetch_compare_and_swap_acquire(volatile unsigned int *addr,
+                                      unsigned int old_val,
+                                      unsigned int new_val)
+{
+  return _InterlockedCompareExchange_acq(addr, new_val, old_val);
+}
+#define AO_HAVE_int_fetch_compare_and_swap_acquire
+
+AO_INLINE unsigned int
+AO_int_fetch_compare_and_swap_release(volatile unsigned int *addr,
+                                      unsigned int old_val,
+                                      unsigned int new_val)
+{
+  return _InterlockedCompareExchange_rel(addr, new_val, old_val);
+}
+#define AO_HAVE_int_fetch_compare_and_swap_release
diff --git a/src/atomic_ops/sysdeps/msftc/common32_defs.h b/src/atomic_ops/sysdeps/msftc/common32_defs.h
index 3b5c782..a4ba451 100644
--- a/src/atomic_ops/sysdeps/msftc/common32_defs.h
+++ b/src/atomic_ops/sysdeps/msftc/common32_defs.h
@@ -116,5 +116,19 @@ AO_compare_and_swap_full(volatile AO_t *addr, AO_t old, AO_t new_val)
 }
 # define AO_HAVE_compare_and_swap_full
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+  AO_INLINE AO_t
+  AO_fetch_compare_and_swap_full(volatile AO_t *addr, AO_t old_val,
+                                 AO_t new_val)
+  {
+#   ifdef AO_OLD_STYLE_INTERLOCKED_COMPARE_EXCHANGE
+      return (AO_t)_InterlockedCompareExchange(
+                                        (PVOID AO_INTERLOCKED_VOLATILE *)addr,
+                                        (PVOID)new_val, (PVOID)old_val);
+#   else
+      return (AO_t)_InterlockedCompareExchange(
+                                         (LONG AO_INTERLOCKED_VOLATILE *)addr,
+                                         (LONG)new_val, (LONG)old_val);
+#   endif
+  }
+# define AO_HAVE_fetch_compare_and_swap_full
 #endif /* AO_ASSUME_WINDOWS98 */
diff --git a/src/atomic_ops/sysdeps/msftc/x86_64.h b/src/atomic_ops/sysdeps/msftc/x86_64.h
index 3b10543..a4bbd40 100644
--- a/src/atomic_ops/sysdeps/msftc/x86_64.h
+++ b/src/atomic_ops/sysdeps/msftc/x86_64.h
@@ -85,7 +85,14 @@ AO_compare_and_swap_full(volatile AO_t *addr,
 }
 #define AO_HAVE_compare_and_swap_full
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_full(volatile AO_t *addr, AO_t old_val,
+                               AO_t new_val)
+{
+  return (AO_t)_InterlockedCompareExchange64((LONGLONG volatile *)addr,
+                                        (LONGLONG)new_val, (LONGLONG)old_val);
+}
+#define AO_HAVE_fetch_compare_and_swap_full
 
 /* As far as we can tell, the lfence and sfence instructions are not    */
 /* currently needed or useful for cached memory accesses.               */
diff --git a/src/atomic_ops/sysdeps/sunc/x86.h b/src/atomic_ops/sysdeps/sunc/x86.h
index 8db5851..114e5fa 100644
--- a/src/atomic_ops/sysdeps/sunc/x86.h
+++ b/src/atomic_ops/sysdeps/sunc/x86.h
@@ -142,7 +142,18 @@ AO_compare_and_swap_full (volatile AO_t *addr, AO_t old, AO_t new_val)
 }
 #define AO_HAVE_compare_and_swap_full
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_full(volatile AO_t *addr, AO_t old_val,
+                               AO_t new_val)
+{
+    AO_t fetched_val;
+    __asm__ __volatile__("lock; cmpxchgl %1, %2"
+                         : "=a" (fetched_val)
+                         : "r" (new_val), "m" (*addr), "0" (old_val)
+                         : "memory");
+    return fetched_val;
+}
+#define AO_HAVE_fetch_compare_and_swap_full
 
 #if 0
 /* FIXME: not tested (and probably wrong). Besides,     */
diff --git a/src/atomic_ops/sysdeps/sunc/x86_64.h b/src/atomic_ops/sysdeps/sunc/x86_64.h
index d888a5d..0a718be 100644
--- a/src/atomic_ops/sysdeps/sunc/x86_64.h
+++ b/src/atomic_ops/sysdeps/sunc/x86_64.h
@@ -142,7 +142,18 @@ AO_compare_and_swap_full (volatile AO_t *addr, AO_t old, AO_t new_val)
 }
 #define AO_HAVE_compare_and_swap_full
 
-/* FIXME: implement AO_fetch_compare_and_swap */
+AO_INLINE AO_t
+AO_fetch_compare_and_swap_full(volatile AO_t *addr, AO_t old_val,
+                               AO_t new_val)
+{
+    AO_t fetched_val;
+    __asm__ __volatile__("lock; cmpxchgq %1, %2"
+                         : "=a" (fetched_val)
+                         : "r" (new_val), "m" (*addr), "0" (old_val)
+                         : "memory");
+    return fetched_val;
+}
+#define AO_HAVE_fetch_compare_and_swap_full
 
 #ifdef AO_CMPXCHG16B_AVAILABLE
 /* NEC LE-IT: older AMD Opterons are missing this instruction.