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

    <tr>
        <th>Summary</th>
        <td>
            [libcxx] Miscompilation of string code when using new-struct-path-tbaa
        </td>
    </tr>

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

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

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

<pre>
    When using libcxx and clang 14, we observe a miscompilation of the following simple `std::string` code:

```
std::string r;
...
r = std::string("Hello, ") + "world";
```

We expect string r to be equal to "Hello, world" but we end up with "H" followed by 11 garbage characters, depending on the earlier contents of r. This is a [godbolt demo](https://godbolt.org/z/qdo7WPEzz). The only non-trivial factor to trigger the wrong behavior, is the use of the new TBAA struct path format (using clang option `-new-struct-path-tbaa`).

# Analysis

After appending to the left-hand side string, the statement triggers a move constructor and move assignment to get the result in place. Each move consists of a copy of the string representation, followed by a zero operation that clears the representation of the stolen string. It seems these memory access operations do not have proper TBAA information, leading to incorrect memory optimization. 

## TBAA tags

In the [LLVM IR for the move assignment operator and move constructor](https://godbolt.org/z/fdver7dd5), we can find back the TBAA tags for the memory operations. These tags should be compatible as they may refer to overlapping memory access. The internal representation of a basic_string is the following structure:

```
    union __ulx{__long __lx; __short __lxx;};

    enum {__n_words = sizeof(__ulx) / sizeof(size_type)};

    struct __raw
    {
        size_type __words[__n_words];
    };

    struct __rep
    {
        union
        {
            __long  __l;
            __short __s;
            __raw   __r;
        };
    };

    __compressed_pair<__rep, allocator_type> __r_;
```

Type-punning using a union violates strict aliasing, but is supported by e.g. GCC [provided the memory is accessed through the union type](https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Type-punning). Also in clang, access using a union is normally given the tag of "omnipotent char".

The move assignment operator is doing (in `__move_assign`):

```
  __r_.first() = __str.__r_.first();
  __str.__set_short_size(0);
```

The assignment at the level of `__rep` gives a `memcpy` intrinsic with TBAA base and access tag of `__rep`, which has a member (the anonymous union) of omnipotent char. `__set_short_size` uses the access expression `__r_.first().__s.__size_`, the union access has base and access tag of omnipotent char.

The move constructor is doing:

```
    : __r_(_VSTD::move(__str.__r_))
{
    __str.__zero();
```

The move at the level of the `__compressed_pair` gives a `memcpy` intrinsic with TBAA base and access tag of the `__compressed_pair`, but this structure has no members in the TBAA info, **this seems incomplete**:

```
!8 = !{!9, !9, i64 0, i64 24}
!9 = !{!6, i64 24, !"_ZTSNSt3__117__compressed_pairINS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE5__repES5_EE"}
```

The function `__zero` is doing:

```
    void __zero() _NOEXCEPT
        {
            size_type (&__a)[__n_words] = __r_.first().__r.__words;
            for (unsigned __i = 0; __i < __n_words; ++__i)
                __a[__i] = 0;
        }
```

The store of the zero value in the loop body is given TBAA base and access tag of `long`, **this is clearly wrong**. However, function `__zero` violates the constraint "memory is accessed through the union type" from the GCC manual (cited above). The use of the intermediate reference variable `a` is equivalent to the counter-example (using an intermediate pointer variable `int* ip`) given there. If the source code is changed to remove the use of the reference variable, the base and access tag is omnipotent char, as expected.

# Workaround

Changing the code of `__move_assign` do the assignment at the level of `__raw`:

```
  __r_.first().__r = __str.__r_.first().__r;
```

Gives a memcpy with TBAA tag of omnipotent char (since we are accessing a union member) and prevents the incorrect memory optimization. Presumably because this forces to alias with the `__compressed_pair` (but as noted above, that tag seems incomplete).

# Credits

Bhramar Bhushan Vatsa, Wouter Vermaelen and Jeroen Dobbelaere contributed to this bug report.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJytWNtu4zgS_RrnhbDhS-zED3lIHPdMFjPdjU3QWeyLQEm0xR1J1JCUE-fr91RRsuVL3L3ABkks81Isnqo6VaXYpNu710yVona6XItcx8n7u5BlKpJcYmB03RsvxJsSJnbKbpSQotAuMUWlc-m1KYVZCZ8psTJ5bt5IhtNFlSvRmw2dT3uTe_w6bzGDEZGYVNHY8LE3bP_Phs0vfz3aJGxv8hBmBoNBeLCiN3kUx9LHt73x-HcFNUhlPPfGc3w80OObsXlKQ62so0PD_1cl1HulEi_as4U3Isbo37XM6bl7QitTxLUnhBRAqyvxpn3G62gqoKJSEW_FaCTW0sZyrUSSSSsTr6wjQamqsJfOA5yEpZI218oCrNKr0jvC2A7ES6adwK8UvenD2qSxyT02F6Y3fcTtM-8rR4iMv-C3mR8YC2S-fODv79TcvH5ffuB5TsJg0zLfitKUfdx2o3HDFZQyfGmMrNdQgdR5swa6xSqTG20saQwlaKJ2qjV_qd7Ey8P9PSFXA8BKAoWVsYX0AOM2eFdwKVOx3wD7Pnb1w4Y-bej7WEqyCRQ88JDxRNyXMt867brj9ytAKGTVwkd6Q5dcrXw_Ix92OlWidY8FTzovvSqAantFwrMw8GygHXQBArSZB6Vzel2G9UaslWchVrka2OtSVLlM1EAsZZLtpWgXbCbxrdq2ELU-pSpsh0AOH1Kr6yRSfChrgJGyIbx8BgSTHC7hmqO72_eyTY4gDkcMxBM8WKmCd8BGBXzEQnaSKOf2sp1IDczvBQyrRGVpIhhRl8F0jYI4vcVXl4mxlkKkEUrWLPQHrx2II6uR4Vigl-sDyz0FR4cf__HHjz_F0z_JV3joGPWgbdckHTv9muOv0o2yN2k6hV81bJbIUqw0JMYy-YvP3am516S9YAsXBw3g5FUuM3WeEjkQGWJBnJPetHMrCrmFoVaKQwk62xxOSggeWCIEoUaMWzj3GctKqOd0EjWe00Rdh2kZhtr-hFEFfuqSZEZRnb_3bh6iKKeQxsc7GBGfuI31_J0GejePe6LciVBlXQjeXEbgvtQFFtYfyqxghSCbKffLfpQeIr-tFGF_VmxDGFFk5dt-FOfsv_CyVhBW8unwnZ0m5AeTh-7uyyep6sJJDNXh0Mka-mlApM-Dw_fzLaruk3ncOHyezHcv8PmFooh8D07jVBpVUkPOItwOXi7hJQlFToB_sqSDossJ8AUr-1VdluRdgbNl4zqgfiR85ZhjgKLMtXQNr1IChHO6uqpw4UBkagAe-m2xoBgHtWzAxGk3rCiPcRTwsDX1Ogs5hU9jlc8Fd5IM1mXdBDfyly5VahIXpvD_W6Aj1f9WhZjNfJGDhro34_x3nztis5CTGK_Ajoe3hpYlMWGORLnWGxVoCwRA4YkEb4pSV4aSNOd0jBwkrpdLhKaJf-kw3FJzPowiWhyFxSEP_iyyyaaDlbbOc_0z55iMiDEGx1Mdh2oXOOWDk0YUXlg27K477yLZwW2kb1LuRuWMCd2CPBC1HgHG1cpsCKMn1ZYGQXcgM7BaKJSYdsFyivm9sUGL714W03amkWQzyQlbFTHYFRrT6RI1zLYwtWtiFzBg-5FtBkHe0ZWhEaqYQKzN6SgBKaSaGuUYRUKN_oiOGsX2bttIIB0_udOxUme9pVuJtF7yc4rHihDi4OIfzy-PoTgmgczOrUtwEpw3Urq81i6hAuTIYz71hODcRz7AmZ2QO2an_4NPXJDdMpGnMnmXGtkYpWk8xlHI79I9lTmhVwC93Id9XDZRlUNNjFdh6jL4vfHoluMOD4ToeDQPUsOnnl2LYfswviYqb7fND7fNOquCABBK9O-X56_PfhJFo9HNyb2fvj5Ho3G3THhKaGhE3hV5K7V3T8lyibH5LiPQwHLKsbV8nkbLJXVGO7U-s_WqLhO_iwr2ErLdL_vnxuhUdN1LRF-_Lf-1WH5_-YVsu8__vHkWRZI89LAIaNjvJGLJrcOac4mYCj7qUUpiNUU6ahY0DLURfVmI_TET6ihhLpysd5Ekjn5IvSmvaLQans3xlxFHVW93HRb3BRuZ16r14dyYSsTo4MkIITv9hE6pYGkipePz-OUGAzmOW70wNRC_oylB7cotylnb72oC0iaQlkQsU2L89SxPXbI1BQ9TvVDIkpptGCTRVEvImBmsaVk7LScXzoVKNVQI1bYqEwWIrJZxeAEhGw9F_64BXdPFBW1r2t5X7zK8rWh7VDQGB4Irw18PxGIEAAkdMtN8XxlYtIJPTUdmapsoft_BAKMfXRMIBqoyax410KcXaFPLOXNC4knpsaD2I7y_UOlJ__xq7F8SBijT7syC1OLWLmt0bfPuYSVCnaL_lcyPGh6Y_I9FC0XohcJl0K2QzwbLb01WCSmlk0XOZ13BjQlhjVZQ2jbzdwu_kC7IuIQ8GHfDL2KC311sgb_Ty4ECBtyiOUwkmZijDCyTUKiYUDoHJS-lSihJ6YzTVycQFuGVAN3sNFmdvjdZWDiyP2i-HzIrC6DwkNUO9hc_pHeSBL-amlz9B7xfKnqfQHf_B4Idj48mjlUu4aP8Wspq6Bb8mW8X1_xmA3XV4Cq9m6TzyVxeee1zdQceDK8ViQr_PHl52DS37Hxv-zeR514NXdU2vztqCIBiHQ8gE1_yfNN-9NFz_Ac2wlftXK2oQ5hOJ7fXV9ndKh7GqZTD0W0iV9PxbKZmaTIerW5GaqxGQ3mVS1zVkeJgJ3qzxSIoSU4fr_TdeDgeD6ej0Wg8HV5PB2oi49t4Mru-nk9vVjLuXQ9VIXU-ID2oU7myd6wSMHKYzOn10H4yhJRinEi-rD3K07vY1iUgWRGjqitW4I4v8F8Ed-BD">