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

    <tr>
        <th>Summary</th>
        <td>
            [Armv7-a]: Control-dependency between atomic accesses removed by -O1.
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </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 captures bad behaviour:
```
C test

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

// Concurrent threads
P0 (atomic_int* y,int* x) {
  int r0 = *x;
  if (r0 == 1) {
 atomic_store_explicit(y,1,memory_order_relaxed);
  }
}

P1 (atomic_int* y,int* x) {
  int r0 = atomic_load_explicit(y,memory_order_acquire);
  *x = 1;
}

// predicate over final state - does this outcome occur?
exists (P0:r0=1 /\ P1:r0=1)
```
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:
```
{P0:r0=0; P1:r0=0;}
{P0:r0=1; P1:r0=0;}   
```

When compiling to target armv7-a using either GCC or LLVM trunk (https://godbolt.org/z/nxWTbEfK1), the compiled program has the following outcomes when simulated under the armv7 model:
```
{P0:r0=0; P1:r0=0;} 
{P0:r0=1; P1:r0=0;}
{P0:r0=1; P1:r0=1;} <--- forbidden by source model, bug!
```
Since the `CMP;MOVEQ   r1, #1;STREQ` sequence is predicated on the result of CMP, but the STREQ can be reordered before the LDR of x on thread P0, allowing the outcome {P0:r0=1; P1:r0=1;}. 

The issue is that the control dependency between the load and store on P0 has been removed by the compiler. Both GCC and LLVM produce the following (replace symbolic registers e.g. %P0_x with concrete registers containing x).

```
ARM test

{ [P0_r0]=0;[P1_r0]=0;[x]=0;[y]=0;
 %P0_P0_r0=P0_r0;%P0_x=x;%P0_y=y;
  %P1_P1_r0=P1_r0;%P1_x=x;%P1_y=y }
(*****************************************************************)
(* the Telechat toolsuite                        *)
(* *)
(* Luke Geeson, University College London, UK.                   *)
(* gcc -O1 -march=armv7-a -pthread --std=c11 -marm -fno-section-anchors*)
(* *)
(*****************************************************************)
 P0                   |  P1                   ;
   LDR R2,[%P0_x]      | LDR R2,[%P1_y]      ;
   CMP R2,#1           |   DMB ISH             ;
 MOVEQ R1,#1         |   MOV R1,#1           ;
   STREQ R1,[%P0_y]    | STR R1,[%P1_x]      ;
   STR R2,[%P0_P0_r0]  |   STR R2,[%P1_P1_r0]  ;
 BX LR               |   BX LR               ;


exists (P0_r0=1 /\ P1_r0=1) <--- yes, allowed by arm.cat, bug!
```
The forbidden {P0:r0=1; P1:r0=1;} behaviour disappears in GCC when optimising using -O2 or above, since R2 is reused in the STREQ when the EQ condition holds - a data dependency masks the loss of the control dependency. This buggy behaviour remains in clang -O2 and above however (https://godbolt.org/z/hGv7P3vGW).

To fix this - mark relaxed atomic load/stores as not predicated, and ideally use an explicit branch to enforce the control dependency so that it is not lost:
```
ARM test-fixed

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

  P0                   |  P1                   ;
   LDR R0,[%P0_x]      |   MOV R2,#1           ;
   CMP R0,#1           |   LDR R0,[%P1_y]      ;
   BNE L0x2c           |   DMB ISH             ;
 MOV R2,#1           |   STR R2,[%P1_x]      ;
   STR R2,[%P0_y]      | STR R0,[%P1_P1_r0]  ;
  L0x2c:               |                       ;
 STR R0,[%P0_P0_r0]  |                       ;


exists (P0_r0=1 /\ P1_r0=1)
```
This prevents the buggy behaviour.

We will follow up by reporting the bug for GCC.

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzcWE9z6jgS_zTKpcuULYdADhz483i7NcmGycvO21tKlhusjSwxkkxgP_2WJAOGceZlZ06zKSrE7v-t7l-3wqwVG4U4IcMZGS5uWOMqbSayecNNlmY3hS4Pk7lWVpRowFUIay2lfhdqA1K4urHg0DpwFXPA2dY1Bi0UrIQCK7YTujEkn5J0QdIpuUvbT3icB8mWFH-PZkDodA8kX0BK8vB06DyNFkDoktAlrMUeSxBKOMEkWMccwnuFBmEPTJVwAGYQ0gvtUXKuFW-MQeWdNshKG8mrFAgdM6drwV-FcoRO4UDovP1zT-g9kNEsMgMI5cCkwTfvMsnPlLVXFGmenF1Kthas0wZfcb-VggtH6Njbygid11hrc3jVpkTzalCyPZaE3ncMkNHimK9FN8BV9kcjaGWkZuW1SxfuMP5rIwxeuXM8sez08sqxNvNbg6Xg_qT0Dg2shTodXQKlRguuEhZ047iuETTnvniWUQfuhXXWB7hKST41KckXWaiG4RxW2emV962v2mJxEDpqxduqoiOokSnb1gKsUkLnIDVnEnbMCFZI9FmqmIUdkw1COuiG9r1CBVbUjWTO90SIIHREo44dMyd0OSd0RugMal2ihLXRNQhnLwvYW_b8pwSsAffIGye0AqECrU0Dl6yxCMLCWptClCUqKA6Bw-rGcIyGBvBSITDfsFge9VrfGh81JRnNzvkNTXfOrX_s1F6HMetlBIB-G-fMcV1vhQyJ0-CY2aADZurdKGHQWP8ehavQwNf5HLSBh4dfHsGZRr35Sqic21ofSaivjS4LLd1Amw2hy_8QulT77y_Fl_VPoSja5EaLWMLW6I1hdTjZS1w75em9c7hYdk40uBhT_CcSCZ_O5I8Zs6PKfJ4kyWVVdCvCp6FoNoRmvV5_E4pjCJHcpfPHFclnj0-_fPkZAIwHJyA096a-vTx_-ZncpWDx1wa9jLDn_i5Bx2o1aBvpfCF7XcG0C4QgD5wpKDxXQBf0M2OtTbT_sHj2cvuoqtOb7HhM3Vb5RGoG0K0-3xfC2iY4HoZXLA7ljJZQ4hZViYofoED3jhjD8fgYpksAb-_ZKiJD4TkM1nrngzh0C80MYKZdFQrYi4YK3hpdNm2iz3XnpwZuJeMI9lAXWgoOBjfCOjQWcLAZAKHDVfq6h3fhKu8tN-iww-QDYEJ5bR7uL6Dq6qinz4_9A3g4W6WvJiXDxbEAh7NVdv1mf_F06DzFsRA9jZryRfs9a_0n-WJ_ejqQfHG4mCfDVfYaLeaL9nsW33YlsyjZGYd0TOj0r_-574YTauQFJfJQpFpL2wiH8MFPj4KeVw_NG8JXRKuVb6l_KrFDY4U7wFxLiRuEB63KlvjT4HN2NpxD8pRBUjPDK5IvjkCebNsGThLrSpIveBa5akjWSicWuR9xCVO80sZ-KoS__qcNx0NIT3pHc4BV1kc5N0rAyGdK6Nwv721nDRdnDdd03zEnekfP_HHV8tE8u_YCFo8z-Pu3v33gRRwPz9m1dJR9fPqlh3ZpPc6CyDU8YUL002v59vJ8Qc26UV7qucrGEceO3lxzHFEmcJw0zf4FD89959FPOe28nd_dZfX1elV9PS2qx2l9QHuabHGAMFMPOHM_mNYvYXwcJ_1n1oPTpQxKYdl2i8z4JTRMp7Dt6K0TtQibV9y_kifqFy9W6F1YUG3YEJ6pn5sGGxtuYZ2ZHrT4Rz_ftSpF2F4rLUsLCTAomWPd-Voz-2bb6WqtH_n9g9ivssL6bGwOnTAM1kyoEAOXrPXXz9ngMFT6Hf1d4xPLYvV1N1rlu6_fr-fmi_a3zbjZJ1Az8wbttay9N4W9gNBl2AosMAtKu842FM5WlSBKZFIewG_uTMHxogWF8cjnN2BUa23avaBnF7E6rirC-ex7I1Jb99EGehzwSbgr_x-N-VbBnwXO9GPgbIGrDxKvYTP9CDavbXwEvrN_fIGHdE_5_w68vwPav4W6z4Lm4SITgZ7-CDJjACSf9sJm389Z9trCb2H7d-X_AOx-gKXxBrND5SIeXUHN5bUf4V1I2S7v0Gw9aBvcauOOV5Oi2Xhw9tDait6Uk7y8z-_ZDU6yu_s8H4_yLLupJveYjzM-5GU5ZjguRultdpfeF_x2fVsM6Ti9EROa0jwd52l6T7NhNsBbvCvGw2y4Hhf5LSvJbeqBUA6k3NUe1G7C5WZyN8zSuxvJCpT2-C8-M_FMSdFsLLlNpU_ZWcwJJ8M_A6dxeQsNP4V5BKOk52LUYiDjHK1F270GJU_Z4KYxcnKFvcJVTTHguiZ06S23X8nW6H8jd4Qug_eW0GUI4L8BAAD__9DsljM">