[LLVMdev] Proposal for atomic and synchronization instructions

[Torvald Riegel]

On Monday 09 July 2007 19:33, Scott Michel wrote:
> Torvald Riegel wrote:
> > Hi,
> >
> > I'd like to see support for something like this. I have some comments,
> > and I think there is existing work that you can reuse.
>
> "reuse within the compiler."

within the LLVM compiler framework, to be precise.

>
> > "While the processor may spin and attempt the atomic operation more than
> > once before it is successful, research indicates this is extremely
> > uncommon." I don't understand this sentence, what do you mean?
>
> I'm not sure I can pinpoint the paper from which the statement is based,
> but I seem to recall something similar in the original LL-SC papers
> (Maurice Herlihy, DEC Western Research Labs?) It's a foundation for
> lock-free algorithms.

Well, the statement says that often you have low contention. But that's 
something you want, not necessarily something you will get, and depends on 
the workload/algorithm. I'm missing the context. Is the actual statement as 
obvious as that you should try to use the atomic instructions offered by your 
processor, instead of doing blocking algorithms?

> > You probably don't need to require CAS (compare-and-set) to return the
> > previous value (I think some architectures don't), but just return a
> > boolean value (success/failure).
>
> compare and swap?

Well, do you need the swap, or is a compare-and-set sufficient most of the 
time? What do other architectures offer?

>
> > What are the reasons because of which you picked the Load/Store model for
> > barriers and not some other kind (e.g., acquire/release/...)?
>
> Chandler looked at what the various current LLVM architectures and
> summarized what he found. What he found are the memory barriers that the
> various processors support.

What you would want is to have a model that is (1) easy-to-use for the 
developers and (2) close to what the hardware offers. L/S membars are easy to 
use, but I think some architectures such as Itanium offer different membars 
with different costs. So if you pick the wrong model and have to use stronger 
membars (mfence Itanium) to implement your model, than you pay for that by 
decreased performance.

>
> > Did you have a look at the atomic_ops project?
> > http://www.hpl.hp.com/research/linux/atomic_ops/
> > It already has implementations for several architectures and several
> > compilers. It uses a different consistency model (different set of
> > constraints for operations) and groups necessary memory barriers with
> > instructions (helpful on some architectures). It supports a few more
> > operations. The author (Hans Boehm) seems to also be active in the area
> > of C/C++ memory models (or some support for this).
>
> LLVM doesn't emit external library calls -- there is no "-lllvm" to
> which programs have to link, so adding an atomic operation library is
> likely to be a non-starter. LLVM is interested in emitting instructions
> to make atomic operations (and higher level concurrency primitives)
> possible, which is why Chandler's work is usefully important.

Please have a real look at atomic_ops first. It does have a library part to 
it -- but that's just for a nonblocking stack.

All the atomic operations are macros and asm for the specific 
compiler/architecture pairs. 
So if you reuse that in the LLVM code generators, you save one large part of 
the work. Of course you can redo all this work, surely giving you a very fast 
start...

Second, I guess there has been some serious effort put into selecting the 
specific model. So, for example, if you look at some of Hans' published 
slides etc., there are some arguments in favor of associating membars with 
specific instructions. Do you know reasons why LLVM shouldn't do this?

Has anyone looked at the memory models that are being in discussion for C/C++? 
Although there is no consensus yet AFAIK, it should be good for LLVM to stay 
close.

And please observe that I didn't state that the work is not important or not 
useful. We should just strive to select the best model we have, and reuse 
work if we can. And if we can reuse a tested implementation and model, that 
is a good thing.

Torvald