title: What are the C++11 memory ordering guarantees in this corner case?
body: <p>I'm writing some lock-free code, and I came up with an interesting pattern, but I'm not sure if it will behave as expected under relaxed memory ordering.</p>
  
  <p>The simplest way to explain it is using an example:</p>
  
  <pre><code>std::atomic&lt;int&gt; a, b, c;
  
  auto a_local = a.load(std::memory_order_relaxed);
  auto b_local = b.load(std::memory_order_relaxed);
  if (a_local &lt; b_local) {
      auto c_local = c.fetch_add(1, std::memory_order_relaxed);
  }
  </code></pre>
  
  <p>Note that all operations use <code>std::memory_order_relaxed</code>.</p>
  
  <p>Obviously, on the thread that this is executed on, the loads for <code>a</code> and <code>b</code> must be done before the <code>if</code> condition is evaluated.</p>
  
  <p>Similarly, the read-modify-write (RMW) operation on <code>c</code> must be done after the condition is evaluated (because it's conditional on that... condition).</p>
  
  <p>What I want to know is, does this code guarantee that the value of <code>c_local</code> is at least as up-to-date as the values of <code>a_local</code> and <code>b_local</code>? If so, how is this possible given the relaxed memory ordering? Is the control dependency together with the RWM operation acting as some sort of acquire fence? (Note that there's not even a corresponding release anywhere.)</p>
  
  <p>If the above holds true, I believe this example should also work (assuming no overflow) -- am I right?</p>
  
  <pre><code>std::atomic&lt;int&gt; a(0), b(0);
  
  // Thread 1
  while (true) {
      auto a_local = a.fetch_add(1, std::memory_order_relaxed);
      if (a_local &gt;= 0) {    // Always true at runtime
          b.fetch_add(1, std::memory_order_relaxed);
      }
  }
  
  // Thread 2
  auto b_local = b.load(std::memory_order_relaxed);
  if (b_local &lt; 777) {
      // Note that fetch_add returns the pre-incrementation value
      auto a_local = a.fetch_add(1, std::memory_order_relaxed);
      assert(b_local &lt;= a_local);    // Is this guaranteed?
  }
  </code></pre>
  
  <p>On thread 1, there is a control dependency which I suspect guarantees that <code>a</code> is always incremented before <code>b</code> is incremented (but they each keep being incremented neck-and-neck). On thread 2, there is another control dependency which I suspect guarantees that <code>b</code> is loaded into <code>b_local</code> before <code>a</code> is incremented. I also think that the value returned from <code>fetch_add</code> will be at least as recent as any observed value in <code>b_local</code>, and the <code>assert</code> should therefore hold. But I'm not sure, since this departs significantly from the usual memory-ordering examples, and my understanding of the C++11 memory model is not perfect (I have trouble reasoning about these memory ordering effects with any degree of certainty). Any insights would be appreciated!</p>
  
  <hr>
  
  <p><strong>Update</strong>: As bames53 has helpfully pointed out in the comments, given a sufficiently smart compiler, it's possible that an <code>if</code> could be optimised out entirely under the right circumstances, in which case the relaxed loads could be reordered to occur after the RMW, causing their values to be more up-to-date than the <code>fetch_add</code> return value (the <code>assert</code> could fire in my second example). However, what if instead of an <code>if</code>, an <code>atomic_signal_fence</code> (not <code>atomic_thread_fence</code>) is inserted? That certainly can't be ignored by the compiler no matter what optimizations are done, but does it ensure that the code behaves as expected? Is the CPU allowed to do any re-ordering in such a case?</p>
  
  <p>The second example then becomes:</p>
  
  <pre><code>std::atomic&lt;int&gt; a(0), b(0);
  
  // Thread 1
  while (true) {
      auto a_local = a.fetch_add(1, std::memory_order_relaxed);
      std::atomic_signal_fence(std::memory_order_acq_rel);
      b.fetch_add(1, std::memory_order_relaxed);
  }
  
  // Thread 2
  auto b_local = b.load(std::memory_order_relaxed);
  std::atomic_signal_fence(std::memory_order_acq_rel);
  // Note that fetch_add returns the pre-incrementation value
  auto a_local = a.fetch_add(1, std::memory_order_relaxed);
  assert(b_local &lt;= a_local);    // Is this guaranteed?
  </code></pre>
  
  <hr>
  
  <p><strong>Another update</strong>: After reading all the responses so far and combing through the standard myself, I don't think it can be shown that the code is correct using only the standard. So, can anyone come up with a counter-example of a theoretical system that complies with the standard and also fires the assert?</p>