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
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. Andrew
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