[llvm-dev] Atomic LL/SC loops in llvm

[Tim Northover via llvm-dev]

Hi James,

Thanks for the very detailed summary, there's some really interesting
details in there that I wasn't aware of.

On 10 May 2016 at 12:22, James Knight <jyknight at google.com> wrote:
> Anyone got any other ideas for how to do this, without needing to introduce
> a bunch of per-target code?

My only vaguely plausible idea to actually fix it so far was some kind
of do-not-touch region for the register allocator to avoid spills
(and, in light of your explanations, other things). Maybe some kind of
MBB level no-spill/volatile flag would even be enough.

IME most of the optimization benefits come at ISel time (choosing
better branch sequences, INC vs ADD etc), so I'm not *too* worried
about hobbling later machine passes.

For completeness, I've also been tempted to simply check for spills
and report_fatal_error given how often it's actually come up in the
last few years. That's really unfriendly though, so probably not a
good idea.

> That last restriction seems most odd as a hard constraint, as opposed to
> just a performance win. It is apparently because a common implementation is
> for the LL instruction to pull the cache-line local, and invalidate it from
> all remote caches (as if the LL were actually a write). The subsequent SC
> will then succeed only if the cacheline has not been invalidated since the
> LL. With a naive implementation, LL operations on two CPUs executing the
> same loop might just ping-pong the cacheline back and forth between them
> forever, without either CPU being able to successfully execute the SC -- by
> the time each got to it, the cacheline will have already been invalidated by
> the other CPU. Delaying the remote invalidation request for a little while
> in this situation is sufficient to prevent that problem. (But how long is a
> little while?)

I have a suspicion this kind of unpredictable starvation (or something
like it) is why ARM added such CISCy instructions to handle things in
v8.1.

Cheers.

Tim.