[LLVMdev] compare and swap

[Torvald Riegel]

On Thursday 21 February 2008 19:26, Cory Nelson wrote:
> Food for thought, on x86 it is typical to have a lock-free algorithm like
> so:
>
> int cmp, newcmp = *ptr;
> do { cmp = newcmp; }
> while((newcmp = cas(ptr, exch, cmp)) != cmp);

Yes, that's lists etc. If you want to use CAS for locking though (there is no 
TAS intrinsic), you would do while(!cas(&lock, 0, myID)); or have an 
load-loop if you'd do test-and-test-and-set things.

> Which translates (optimized) into:
>
> mov eax, [ptr]
> loop:
> lock cmpxchg [ptr], exch
> jnz loop
>
> cmpxchg fills eax with the old [ptr] value and sets ZF on success, so
> it can be used without extra load and compare instructions.  I am not
> sure if LLVM has any concept of volatile, but [ptr] will probably be
> treated as such in any algo and a CAS that returns a bool will force
> you to use an extra mov (that can't be optimized out, due to volatile)
> to get a new compare value.  So having an intrinsic that returns the
> old value is important.

Agreed. I guess it really depends how much we want to have. If minimal is 
sufficient, then load+store and some form of CAS are all we need.

Torvald