<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/68428>68428</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [AArch64]: Atomic Exchange Allows Reordering past Acquire Fence
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          lukeg101
      </td>
    </tr>
</table>

<pre>
    Consider the following litmus test that exposes buggy behaviour (this is a nasty bug):
```
C test

{ *x = 0; *y = 0; } // fixed initial state where x and y are 0

P0 (atomic_int* y,atomic_int* x) {
  atomic_store_explicit(x,1,memory_order_relaxed);
 atomic_thread_fence(memory_order_release);
 atomic_store_explicit(y,1,memory_order_relaxed);
}
P1 (atomic_int* y,atomic_int* x) {
 atomic_exchange_explicit(y,2,memory_order_release);
 atomic_thread_fence(memory_order_acquire);
  int r0 = atomic_load_explicit(x,memory_order_relaxed);
}

exists (P1:r0=0 /\ y=2)

```
where 'P0:r0 = 0' means thread P0, local variable r0 has value 0.

When simulating this test under the C/C++ model from its initial state, the outcome of execution in the exists clause is forbidden by the source model. The allowed outcomes are:
```
{ P1:r0=0; y=1; }
{ P1:r0=1; y=1; }
{ P1:r0=1; y=2; }
```

If we compile this with clang trunk for armv8.2-a using -O2 (https://godbolt.org/z/Grha1988f), we get the following test:
```
AArch64 test

{ [P1_r0]=0;[x]=0;[y]=0;
  uint64_t %P0_x=x; uint64_t %P0_y=y;
  uint64_t %P1_P1_r0=P1_r0;uint64_t %P1_x=x;uint64_t %P1_y=y }

  P0 |  P1                    ;
   MOV W9,#1        |   MOV W9,#2 ;
   STR W9,[X%P0_x]  |   SWP W9, WZR, [X%P1_y]  ;
   DMB ISH |   DMB ISHLD            ;
   STR W9,[X%P0_y]  |   LDR W8,[X%P1_x] ;
   RET              |   STR W8,[X%P1_P1_r0]  ;
                    | RET                  ;


exists (P1_r0=0 /\ [y]=2)
```
Which under the aarch64 model permits the following outcomes:
```
{ P1:r0=0; [y]=1; }
{ P1:r0=0; [y]=2; } <-- Forbidden by source model, a bug!
{ P1:r0=1; [y]=1; }
{ P1:r0=1; [y]=2; }
```
So what is going on? The SWP instruction as introduced in armv8.2-a with LSE is not regarded as doing a read when the destination register is the zero register. In this case the write to y can be reordered past the `DMB ISHLD` fence so that we observe the load of x on P1 before the store to y. This results in the outcome `{P1_r0 = 0; y=2}` when the load of x on P1 occurs before the write of x on P0, and the write to y on P1 occurs after the store to y on P0.

This is caused by the LLVM dead register definitions [pass](https://llvm.org/docs/doxygen/AArch64DeadRegisterDefinitionsPass_8cpp_source.html), that zeros out the destination register of SWP, since it is not used in the source program. This optimisation is applied at `-O1` and above, and hence we do not observe this bug with `clang -O0`. This does not occur in GCC (see Godbolt above), since the destination register is not zero'd out. 

My advice is to not apply this optimisation to `SWP` so that the destination register is not zero'd out like in clang `-O0`

The official Arm AArch64 memory model has been updated to reflect this - hence my catching it now.

So what does this mean? Well it means there are thread-local optimisations that are influencing the semantics of concurrent programs. This is a standard re-ordering bug as far as concurrency is concerned, but you can only observe this when you don't keep the value of the `compare_exchange` around to observe it. In other words it is a [heisenbug](https://en.wikipedia.org/wiki/Heisenbug)! This raises questions of whether there are more bugs like this.



</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJycWNtu27rSfhr6ZmBDouPThS98qLsKtGiQBCs__huDpkYWdyTSi6Riaz39xpCSYztJ0e6isCCRc-Q33wwjnFN7jThnoyUbrXui9oWx87J-wX2apL2dyZr5yminMrTgC4TclKU5Kr2HUvmqduDRefCF8ICng3HoYFfv9w3ssBCvytQWGJ_6QjlQDgRo4XxDWxifseGCJWuWLNg4af-H11VQ2i7F38kSGF-cgA3XkLBheGsu3iZrYHzD-AZydcIMlFZeiRKcFx7hWKBFOIHQGTQgLEJyqf0-IR-FN5WSW6U94wtoGF9dfzkxPgM2WUYZgHbVeWNxi6dDqaTyjE9PjK9SxlcVVsY2W2MztFuLpThhFoLuNLQKfGFRZNsctUTGp7diKBx-JPbObvObdtlk3Yad_g9ht4t4koXQ-3cO8A8c-CyCXwUu5D-1stdioLQHm4RTb1WURmS3uf_t-OMvnpTzjjJxn7LhwiZsuE4CmEYraNhwzUn4EovXYI3YYnxynwTxFpR8AhUK7SBGCfcJ4ysojRQlvAqrxK5ECqYQDl5FWSMkg0srzwVqcKqqS-Gp2kIFhVqrdVeLK8Y3K8aXjC-hMhmWkFtTgfLuGv9kmfab2ktTIZgc8ISy9spoUDqstWmQpagdUqnmxu5UlqGGXRN2OFNbidHQAJ4KBEFUgFmn11FlfVbTVMEXCaaipeSmbfV-tCn9o038etON9fD7LYcjgjTVQZUYM3pUvqCgKcO21i8UNghbvU4HvC-gdpT7_k9O-Ci8PziKLxDN3mQ7U_qBsXvGN_8yvvlqC5HOptOcAMNXZGuP_oY1A7N9kqPFwspifPcx-42W9-nWJmy0bvPHRsvT1Vtz8dZWTK20H99tPTA-uk-2JzZcnyhPN98pf81nYuk2Gh6u2-fyZrnTevM5KIWbagMgsp2sAO5T-ODfhRPw4-ff8EyZZHx43hxkr5b4ldDj00O7Mlr-Xxf1aN0JPj7fx2V4_v8HenTbyN-w7ULX-scSvj3-1Yq2b9_Xn_n7genmwvT39QM8Ty-W0-jZpYqHL083-YheP70T7cBw7cL7fE5W75VeOf4ZF26vmfANXxd8eA3f50LJ4oKehIhwjtR0QFsRM12XQ0cdf0Abb578ihdutvLzlDBc9fuwuSS3S2IjSIg4nqSf0s3veZB-7MGHYT4aONIIpRzsTciLZsNNIFlCrNLO21oGvhZE7t6arJZhzrlgq0Bm3x-_kBptPFjcC5thRjJZUCsgNKMjNRc6iAydV1oExRb3ynm0JE1r_6I1548D-KYjY0rhMKwfrfII3kADUmjYIVgMTRczOAgXiY-Nk3PdsHECodmDM3FiPCKYnUP7GjVSN6fmdAKjiR92mBsbl8K0E4xR61EOLLq6DI3uqrVRRieRKd-mw9geJsGBc-i3xoyUtXWXNmOA5y2hgdMEeRP8lbjIfYv-N4-j9FV3f2rnYUndNus67Pfvf_-AjA7ofBYZ5qGVG-0ISwfhHMHpthmV5WvVdqLMSBcep2aPmvFN21XWKLKHVu36Teu9cG47lYfDNpbBoPBV2TawcEYEA0f5_RwwJieUkoRTdLzKdwgM0bVH1JbZwZq9FVV7jObgVaVcVEgXhMOhVIRYT0fZ_5nSmVHSxc68YncCRUDRESEzwcwbiFS4fsRKYOMkdvb-T6q01mJmMPoWToyc-7paEeU5RPgam3pnbfYW06-qhbRRmhifhGFoAJdn_aMBkb0qGaYqHx2mMJvo7lUGvCGvKZnj5Fwlf2IaSvWCFFSMPOTwdgwiVjF5riQNiAtbQTd3xMm55WsaTHeIGupDJjxm5JvFvETpo-P99hgqqn8vC-IX5UGb4xXUO2oLeQ-CNBcTuz1jWZJENyfTHC1C7RFJ9eOsfJkeF_NBe5TOyxq1jKMxgsNKaK-kIzBKo2VtLWrfoc21hx-uoM4LnQlLVdYPhEVKCDXCQS4sPc4aZBPK1GiJVtM9YgW72kNj6kB6RpfNNfoCv9ByZjTjEw8viIfgYpzyTd7xIs2hIlzh4lUqIN2aWodUd0qVD9RrKD1wNDZzbXkJ4oMClUNN7eoDUkA9OKoXdcBMiZYc6J3xzV9nMYJ42jKqUHR7_6cmqFGyTU7RBMNvh1MRq-3qvYtIo5gH7weJXjYfZrPhTPRwno5n43Ga3PFJr5jnOM2H-TSdjYaTWTaRIk_T8TAbz9IJppOR7Kk5T_gwTZJxOr5L-GQwlTIZ7-6GciamScKn7C7BSqhy0HFeTzlX43w8vePTXil2WLrw5wzONR4hLDLO2Wjds3OS6ZP37C4padZ50-KVL8PfQdpqCF17AYtw0YQv7SHBgiYXBw94Rk7odYt4X4UNlUSvtuX85ragfFHvBtJULVu3j_7Bmv-g9IxvgqdE3SGS_wYAAP__xbFfiA">