dcas with llvm

Trying to implement a lock free linked list/stack and other lock free structures sometimes requires the use of a "double compare and swap", essentially comparing two pointers with two other pointers and replacing the first with a new pair, only if both match, atomically. Reading the LangRef it's not obvious how to do this, the cmpxchg instruction is what you'd use if you had just a pair of integers. The trick is to use an int sized (2*pointersize) for example int(64) on a 32bits cpu or int(128) on a 64bits cpu and casting the pointer/values to it. For example:

%struct.dcas = type { i8*, i8* }

%struct.dcas void @dcas(%struct.dcas* %ptr, %struct.dcas %_cmp, 
    %struct.dcas %_newval) {
  %cmp = alloca %struct.dcas
  %newval = alloca %struct.dcas
  store %struct.dcas %_cmp, %cmp
  store %struct.dcas %_newval, %newval

  %res = alloca i64
  %ptri64 = bitcast %struct.test* %ptr to i64*

  %ptrcmpi64 = bitcast %struct.dcas* %cmp to i64*
  %cmpi64 = load i64* %ptrcmpi64

  %ptrnewvali64 = bitcast %struct.dcas* %newval to i64*
  %newvali64 = load i64* %ptrnewvali64

  %resi64 = cmpxchg i64* %ptri64, i64 %cmpi64, i64 %newvali64 seq_cst

  store i64 %resi64, i64* %res
  %resdcasptr = bitcast i64* %res to %struct.dcas*
  %resdcas = load %struct.dcas* %resdcasptr

  ret %resdcas
}

Replace i64 with i128 on 64bits platforms. Tested on x86 (creates cmpxchg8b) and x86_64 (cmpxchg16b), seems to work for arm too but I'm not entirely familiar with arm asm yet to say 100%.

comments powered by Disqus