Left on Read: Well-Behaved Semantics for No-Return Atomics
To avoid “out-of-thin-air” behaviors, in which values seem to justify themselves, the RC11 memory model takes a conservative approach: it forbids reordering atomic loads with subsequent stores to different locations. This justifies behaviors within a single “in-order” execution, avoiding the complexity of reasoning about multiple candidate executions, at negligible cost in practice. No-return atomic read-modify-write operations, dubbed modify-writes (MWs), change this picture: they are prominent on GPUs and emerging in CPUs and programming languages, and forbidding their reordering is costly. We present Cmw, a declarative memory model extending (a variant of) RC11 with MWs. Cmw permits program-order/reads-from cycles among MWs, letting them compile directly to native instructions without fences, while preserving RC11’s programmability guarantees: since MWs expose no value to their caller, they cannot form the “causality cycles” that break these guarantees. We establish this through several formal data-race-freedom guarantees, and further show that commutative MWs admit fully “in-order” reasoning, covering common idioms such as histogram generation. To establish implementability, we give compilation schemes to PTX, ARM, and x86 and prove them correct. Finally, we evaluate our approach, confirming a substantial performance benefit on GPUs. All of our formal results are mechanized in Rocq.