enable GHC LLVM backend to use LLVM provided CAS / Atomicity primitives?

[carter]

LLVM provides a number of atomicity / memory ordering primitives.

currently the CAS primops exposed at the CMM level are ffi'd inline assembly fun calls. this means that for certain concurrency primops, we've got fun calls within funcalls that could be easily inlined if we did it in a more llvm direct way. A notable example of this is the implementation of stg_atomicModifyMutVarzh

relevant basic llmv docs are the following ​Atomic llvm ops

​semantics of the various ordering levels

relevant locations in the ghc source ​CAS inline assembly

​defn of atomicModifyMutVar cmm code

Based upon my reading of the relevant GHC cmm code, and reading the semantics of the LLVM operations, the right level of atomic ordering in the generated bit code would be "SequentiallyConsistent".

a first step would be to modify the CMM -> LLVM pass to substitute the cas funcall with the right llvm operation. This SEEMS like it'd be very very easy to do and low hanging fruit.

Theres a few upsides that might come out of this.

1. would be easy to augment to also provide a doubleCAS primitive, which would be useful in writing various lock free data structures.
2. would increase the portability / ease of retargeting new platforms / hardware via LLVM. (not needing to worry about the target's memory consistency model / write new cases of inline assembly)
3. (this would need benchmarks) could potentially improve the performance of certain heavy concurrency operations by eliminating a funcall in an otherwise tight loop.
4. Theres probably other interesting possible upside, such as perhaps having more of the rts be nicely writeable in CMM? (esp since theres now native funcall support)
5. Also would make the CMM memory model a bit more explicit perhaps?

This seems like a *relatively* managable patch to write. I'm up for spending time on this if, should it work, it'd be likely to be merged in.

it'd also be a good warm up for a number of other things I want to do, including ​http://hackage.haskell.org/trac/ghc/ticket/5567#comment:10

[carter]

the language at the end of the ticket is vague:

would this be a change folks would like / or at least value experimenting with?

[carter]

go ahead by Simon M here ​http://www.haskell.org/pipermail/ghc-devs/2013-May/001224.html

David Terei points out related work i can refer to as a model for the work, when Tibbe was adding popcount

​https://github.com/ghc/ghc/commit/2906db6c3a3f1000bd7347c7d8e45e65eb2806cb

and

​https://github.com/ghc/ghc/commit/2d0438f329ac153f9e59155f405d27fac0c43d65

I"ll start hacking on this in a week or so.

[carter]

In light of how some other work folks are doing would benefit from this, i'll get this finished up by the close of august

[rrnewton]

A couple additional suggestions copied over from the mailing list:

(1) we should use more unique symbols than "cas", especially for this rewriting trick. How about "ghc_cas" or something?

(2) it would be great to get at least fetch-and-add in addition to CAS and barriers

(3) if we reliably provide this set of special symbols, libraries like atomic-primops may use them in the .cmm and benefit from the CMM->LLVM substitutions

[carter]

Ryan, could you explain what you mean by "rewriting trick"?

I have no idea what you mean.

Ryan, could you please explain what primops you want using the terminology / vocabulary in ​http://llvm.org/docs/LangRef.html#ordering and ​http://llvm.org/docs/Atomics.html ?

[carter]

hrm, I guess you mean the making the CAS ops inline native primops as "rewriting"?

[rrnewton]

Sorry, I was just referring to the proposal to "substitute the cas funcall with the right llvm operation" as rewriting.

That is, the approach would pattern match for the CMM code "ccall cas" or "foreign "C" cas" (I'm afraid I don't know the difference between those) and replace it with the equivalent LLVM op, right?

[carter]

nope, the idea is to provide CMM / Haskell level prim ops. Normal primops. (see my reply on list :) ).

[carter]

Theres a few other bits that need to be added to the ticket based upon the discussion on list, but one that hasn't been addressed is how to support both compiling to a "sequential" version as well as the "-threaded" ATOMIC analogues based upon which RTS is linked into the application

[rrnewton]

Here are some notes on which operations the "atomic-primops" library is currently exposing, and the other concurrent data structure libs (e.g. chaselev-deque) are using:

• CAS on MutVars, MutableArray#, and MutableByteArray#
• fetch and add on MutableByteArray#
• barriers / memory fences

Drafts of .cmm for these can be found inside the atomic-primops library. Note that *only* casMutVar# is currently shipped with GHC.

Ultimately there's no reason that we shouldn't aim for a fairly "complete set". For example, why not have fetch-and-sub and the other "atomicrmw" variants? Relating these to the LLVM atomics and memory orderings, they become:

• CAS variants = LLVM cmpxchg with SequentiallyConsistent ordering
• fetch-and-X variants = LLVM atomicrmw with SequentiallyConsistent
• store_load_barrier = LLVM fenceInst with SequentiallyConsistent
• write_barrier and load_load_barrier = I *think* these are both covered by a FenceInst with AcquireRelease ordering...

I'm not an LLVM expert, so please double check these yourself before trusting them.

[carter]

note: the primary first user for this planned work, ryan newton, is ok with the atomic operations being the threaded versions even with the single threaded RTS. (this will simplify initial engineering, though it does mean there will be a small perf penalty on sequential RTS relative to theoretical peformance).

[carter]

changing this from a feature request to a task since Ryan Newton is getting the ball rolling with preliminary C implementations for the proposed primops

[rrnewton]

Update: the task in ticket #8157 is a prerequisite to this task. A preliminary solution is checked into the atomics branch.

[carter]

i'll work on adding this stuff after the 7.8 rush.

[rrnewton]

FYI, Johan (@tibbe) is interested in this. Carter, have you started the implementation somewhere?

[thoughtpolice]

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

[thoughtpolice]

Milestone renamed

[bgamari]

I have ​Phab:D1282 up on Phabricator covering this.

[Ben Gamari <ben@…>]

In bd41eb2a/ghc:

LLVM: Implement atomic operations in terms of LLVM primitives

This fixes Trac #7883.

This adds proper support for,
  * `MO_AtomicRMW`
  * `MO_AtomicWrite`
  * `MO_CmpXChg`

Test Plan: Validate

Reviewers: rrnewton, austin

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1282

GHC Trac Issues: #7883

[bgamari]

Merged.