[LLVMdev] compare and swap

[Cory Nelson]

On Thu, Feb 21, 2008 at 9:34 AM, Andrew Lenharth <andrewl at lenharth.org> wrote:
> On 2/21/08, Torvald Riegel <torvald at se.inf.tu-dresden.de> wrote:
>  >  why is the intrinsic name not CAS? And having another version that returns
>  >  just a bool might be better in some cases ( 1. does  CAS return the value on
>  >  all architectures? 2. you can just jump based on a flag and don't need to
>  >  compare it again). Just my 2 cents though ...
>
>  I was going from chandler's docs, but it could be renamed trivially
>  (and I almost did at several points).
>
>  1) yes, but on some it may be easier to have a bool version than others.
>  2.a) to get the bool, the x86 (and some others) backend would have to
>  generate the compare instruction anyway, so you don't save anything by
>  having a bool version.
>  2.b) in the case of a load locked store conditional based backend, the
>  bool version would save a compare if the store conditional has the
>  typical returns success or failure semantics.
>
>  So, yes, a CAS that returned bool could be useful.  However, it is
>  pretty easy to pattern match
>  CAS -> Compare
>  in those backends that can save the compare by testing the result of
>  the store conditional.

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);

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.

Of course, I am quite ignorant of LLVM's capabilities, so I could be
completely off base here.

-- 
Cory Nelson