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

    <tr>
        <th>Summary</th>
        <td>
            A miscompilation bug in LICMPass (concurrency)
        </td>
    </tr>

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

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

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

<pre>
    ```C++
A1:  int* bug(int N, atomic<int>& a) {
A2:    int* p = (int*)malloc(sizeof(int));
A3:    
A4:    for (int i = 1; i <= N; i++) {
A5:      *p = i;
A6:      foo(i, a);
A7: }
A8:  
A9:    return p;
A10: }
```

LICMPass of Clang++ (13.0.0+) optimizes the above function into the following (C++ syntax is used for brevity, see [godbolt](https://godbolt.org/z/j3jYnPrK6) for the IR code):

```C++
B1:  int* bug(int N, atomic<int>& a) {
B2:    int* p = (int*)malloc(sizeof(int));
B3:    
B4:    for (int i = 1; i <= N; i++) {
B5:      foo(i, a);
B6:    }
B7:  
B8:    *p = N;
B9: 
B10:   return p;
B11: }
```

This is a miscompilation bug. By compiling and running a concurrent program that involves the `bug` function on Armv8 processors Apple M1 and Cavium ThunderX2, we actually observed certain program behaviors forbidden by the original program before the optimization. The actual program we tested can be found [here](https://github.com/sunghwanl/llvm-miscompilation). (The forbidden behavior can be observed couple of times throughout millions~billions of program runs. The test code includes some intricate crafts, e.g., that helps repeat the test many times.)

In the following, we explain a simplified version of the concurrent program we used and show why the above LICM is a miscompilation bug.

To see a buggy execution, let's consider two threads where the first thread calls the `bug` function.

Thread 1:
```C++
T1.1: void thread1(int N, atomic<int>& a, atomic<int*>& X) {
T1.2:   int* p = bug(N, a);
T1.3:   X.store(p, memory_order_relaxed);
T1.4: }
```

Thread 2:
```C++
T2.1: void thread2(int N, atomic<int>& a, atomic<int*>& X) {
T2.2:   while (a.load(memory_order_acquire) < N);
T2.3:   int *p = X.load(memory_order_relaxed);
T2.4:   if (p != NULL) {
T2.5:     if (*p != N) {
T2.6:       cout << "bug!!!" << endl;
T2.7:     }
T2.8: }
T2.9: }
```

Also suppose that the `foo` function is given as follows:
```C++
F1: void foo(int i, atomic<int>& a) {
F2: a.store(i, memory_order_release);
F3: }
```

Now, if we create two threads as follows, the program should never print `bug!!!` before the problematic LICM in the `bug` function.
```C++
atomic<int> a;
atomic<int*> X;
int N = 1;
a.store(0, memory_order_relaxed);
X.store(NULL, memory_order_relaxed);
thread* th1 = new thread(thread1, N, ref(a), ref(X));
thread* th2 = new thread(thread2, N, ref(a), ref(X));
```

Indeed, once `thread2` reads `N` from `a` in an acquire access mode (line T2.2), the last call to the `foo` function (line A6, writing `N` to `a` with a release mode) synchronizes with the acquire read. Therefore, the last write to `p` (line A5, `*p = N`) by `thread1` *happens-before*
the read from `*p` (line T2.5, `*p != N`) by `thread2`, and `thread2` can only read `N` from `*p`. Note that there is no data race in this program (before the LICM).

However, after the above LICM, the program becomes racy on `*p`, and `thread2` can read a value other than `N` from `*p`. **We actually observed this program printing "bug!!!" by compiling and running it on Armv8 processors Apple M1 and ThunderX2!**

Roughly, the above LICM is wrong because it moves a non-atomic write `*p = i` (line A5) after a release write (line A6). This is wrong even though `p` is never leaked before it is returned. Specifically, LLVM applies the above LICM and inlines the `bug` function in `thread1`, resulting in the following code:
```C++
    ...
O1: for (int i = 1; i <= N; i++) {
O2:   foo(i, a);
O3: }
O4:
O5: *p = N;
O6: X.store(p, memory_order_relaxed);
    ...
```

Now, the write to `p` (line O5) is not properly synchronized anymore, and `thread2` can read an uninitialized value from `p` (line T2.5). In particular, such behavior is allowed by the Arm architecture because it can reorder the two independent stores O5 and O6. Therefore, this program can print "bug!!!", which is originally forbidden.

We conclude that the pointer `p` in the function `bug` should not be treated as completely local even before it is leaked (line A9).

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJysWEtz47gR_jXwpWtZFPQ--CDJcWUqs_bWxsk6py2QbInYgAADgNJoDvntqQZBipTl8Wx2q1QzhvDo19dfd0s4Jw8a8Z7Nt2z-cCcaXxp77xp9KE9Cq7vMFOd7tkjbz47xLX3SB5ZuNhM23QBI7RnfQNYcGF9J7eGJ8R0IbyqZs-mOtqd_YXwBgvE1sGV3m4fb_f0a2PQB2icY3zC-roRSJmd85eRXNPtua02faffKNL4Sl7O43Bsb3wIZHp6w6Tb8uaPVU1hFY0ZazeMDAIxvWp3kRdqi390bQ-8HU0cKLekIWz7E5SrciIt1vG7RN1ZDfbk1SUfXeofHZfj386fdjz8J58DsYaeEPrT6k52TaZImaTTG1F5W8is68CWCyMwRYd_o3EujydsmfL83SpmT1Ae6H-MK7qy9-ALSQeOwCF7MLB6lP5OhDhHYfHswRWaUZ_MHxlel97Vj0w3jj4w_xq3E2APjj18Zf_xt-tu_9E_2bwvSjN4j2Z9-htwUGPy2GZp4G2jbPwS07Z8CtO0YaNs_CrTt_EMobTu09bDYLgdo2q667Q6oT5erAWmd99L24BvUbSeTj1H3UkpHgBBQSZebqpZKBCRlzSGB7Rna7whIQhdgG63D35AbnTfWovZQW3OwogJfCg9SH406RnSyRUrxXKQXhBoNG1sdV3QrR-eMdbCpa4Xw4ySI2ImjbCp4KRtdoH3l5LgTgsh9I5Q6g8kc2iMWkKP1QupefIalOEp6b29sJosCNWTnoIex8iC1UIOze2Ox3WvzKVidwEvZierPnhA8Ok8ShYaMcqvRBaVKiRZv5on0ZZMluakYf-zJlvFHpY7VD2NHM75OCGIvIWl7vaMtnciL0aYhX5k9eFkFL1vTHErTeKikUtJo998s_kGnOiNso11rHdkS8hOkzlVToANnKlp5K3PhEXIr9t6R3zE5JPR_iGyJqnZgsUbhg-fCS5XQ51aXhNA9gNYnPWaiGEj8UisKmwAnq1rJvcQCjmhdQMc-3LkBrhO2pEUQcaU5wak8DxiQ2PNdHI8AbwLRCdo4nAG_YN60cdiBQs_40pF4Jwu04E_EphZF4eBE0W4tktb5-D3kQqn3wD4W3J6fXDjxJhu-TJKQtkcjiyhj8jEhXn3PN3HrdcRKL5MksuWILFvKfXrDUC-TJNLia-K8scj4qqZTFVbGnn81tkD7q0UlvmBxdXH2PdQTHMI_cgh_4xD-pzmEdw45lVIh5aFIlBEF46uRkSL_TyPJAWuifhI8sJZ3biKderp-vfnQLW_xJJYbuScNamB8Egj_H58_X6vb15X2bCstHr8-e2lniDZ8W7R2wDgPEZ90H97toC7UUK1l90AfyBeerEaRfeHJ-uNQb5Qz4Jq6Ng5bMokJQ8VxWB2kg4M8ogbhInG4D-DxeAFHrLRUq7-rdXgMsRc9tuUtbKNwOIzW4_Rjc5_MiZ6Se2Kt3CKR6pBKBsYFcsWe5VxpGlWAxiNaqG0AVEsrfbgW6bB61dZkCivhZR45UH9ARje9eOUrEL29b9MIXvvNkIR9XxQv9P5Mv4crLtTSwv3jG60Xib58OQnCNZ6g-3bVc-au5QeL1PIFYutXr1ft3_BJ_t6T_Hc9eRMYn3SBZMwOjM5DkLqnFym02GCL9CmEzZqKFoIWVC41RBICkVPjBBXVcMZXSmqEwGStPhR-JajIC6UgzgM3cq27ulmEymylD-NClO9NL_0kfQkCYjIEuZRH7qzz0hodZpFwJpTjqCRZExoOG8A6UoxkYZRQk4RelTmdI6ddml5arKmR6701aa9sSlHXqN0PWZSw6YLZSu9dSI8NpQQaHcrp-POtKB6-24WuYxwtasyMVudW1HXUosgEnoy_MJ5FIjhtoBBegBU5tukqXU8AjK8G2U0ZTQ3iEEN_NSdih6DV3qO9aoKuGSXD3FCjaEV-pub7otz7dgWTBByFahAMKU4m6PetDIPW5pdbXfrIusBo7VD6pgZl780a0n88NAymhUmrzNBlP1OLrM6da8Yd48kafSA3icYhCasMjS8CtNE_tOwXATvEpbyG7TpG45In8dIgy9aUEO281UpFKnW-JPX6XCCEBPpXKP6NRUf20tNOO-RhkcDfa8zlXlKOB8M-f_7njyDqWsnRLwPBSvKQ1KTGu2OZ1OP8aonNNSqES1618u18_-3CTH1DkkToPocq_f9O08-xSXtvlH4e1-TnWa_ac-iXbozQz6E5-p197cikb1V-cta7JPcc0BKIIIw3NVp1HrIpDTnnKpLmtzJUQ6Olll4KFa61Cdtl5w3OWyfwSUMtrJd5o0QgEdfk5WXepBGKgkzAa-erja1A2LyUHnPfWBymSqtK8Fc7EZ4MSF1gjbqg4S1418HzPJjxvHhTEAbcQG_FjucNOYQCVcq8JP26YV6dLwPziCF_aQdImm0vzWZtpKb87NMsQrqvhn1OdD2Y8TR5-9C-FdSzET0p9KjOoEwuVJu-o_yMOdsn_frC3nfF_bRYT9fiDu8ni3U65-vVdHlX3s_Xs9l-NkOcTZZFvlhOxEzgbLYoVns-36_TO3nPUz5Nl3yVLqfLyTJZp-tsnqbL1SzLVvtZzmYpVkKqRKljlRh7uJPONXi_mE1WqzslMlQu_ATMOfU1YZO8On-4s_fhN4msOTg2S5V03l1e8dIrvN_cGKnJff0Ployv-oE9PzO-vmusuv_GTyIkoPs1pLbmN8w9449BLcf4Y1D7fwEAAP__QqS3Cw">