https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127641
Bug ID: 127641
Summary: [VRP] Range info lost after store-to-load forwarding
(memcpy falls back to libcall)
Product: gcc
Version: 16.1.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: 3440910457 at qq dot com
Target Milestone: ---
# Range info lost after store-to-load forwarding (memcpy falls back to libcall)
## What's wrong
When I ran a benchmark for `std::function` and `std::move_only_function` with
signature `void(std::string, std::string, std::string, std::string)` in GCC
16.1.0 (MinGW-w64, MSYS2, x86-64, `-O2`), the `std::move_only_function` version
was 50% slower than `std::function`.
In the following description I simply write `void(std::string)` instead of
`void(std::string, std::string, std::string, std::string)`.
Here is a tiny sample <https://godbolt.org/z/5jfce8sb7> (GCC 16.1).
`std::function` calls `memcpy` in .L16
`std::move_only_function` calls `memcpy` in .L67 and .L70
Similar behavior is seen on GCC trunk.
## What probably happened
This is probably because the range information for `memcpy` is lost in the
`std::move_only_function` case after the devirtualization optimization
introduced in GCC 16.
```cpp
void foo() {
std::string s{};
std::move_only_function<void(std::string)> f = /*...*/;
for (/*...*/) { f(s); }
}
```
The invocation list is as follows:
`foo` -call_1-> `operator()` -call_2-> `_M_invoker` -call_3->
`target_free_function`
call_1: The signature of `operator()` is `void(std::string)`, so a COPY of
`std::string` is made here.
call_3: The signature of `target_free_function` is `void(std::string)`, so a
MOVE of `std::string` is made here.
In the copy constructor and move constructor of `std::string`, `memcpy`
(`__builtin_memcpy`) is called. However, only the `memcpy` in the move
constructor has range information:
```cpp
_GLIBCXX20_CONSTEXPR
basic_string(basic_string&& __str) noexcept
: _M_dataplus(_M_local_data(), std::move(__str._M_get_allocator()))
{
if (__str._M_is_local()) // _M_is_local assumes "__str.length() < 16"
{
_M_init_local_buf();
// The `memcpy` in `traits_type::copy` knows the range information,
// so the compiler can avoid the libcall for `memcpy`.
traits_type::copy(_M_local_buf, __str._M_local_buf,
__str.length() + 1);
}
/*...*/
}
```
There is no range information in the copy constructor:
```cpp
_GLIBCXX20_CONSTEXPR
basic_string(const basic_string& __str)
: _M_dataplus(_M_local_data(),
_Alloc_traits::_S_select_on_copy(__str._M_get_allocator()))
{
// No `_M_is_local` here and no `_M_is_local` in
`_M_construct<true>(...)`.
// So there is no range information for `memcpy` in
`_M_construct<true>(...)`,
// and the compiler must use a libcall for `memcpy`.
_M_construct<true>(__str._M_data(), __str.length());
}
```
So, theoretically speaking, only one `memcpy` call is expected, as in the
`std::function` case. However, there are 2, not 1, `memcpy` calls in the
`std::move_only_function` case.
That's because the range information for `memcpy` is lost after 3 steps of
optimization:
1. devirtualization
`call_2` is eliminated, so `call_1` and `call_3` end up in the same scope.
```cpp
n0 = x + 1;
__builtin_memcpy(_, _, n0); // (call_1) COPY-Ctor, no range info
s._M_length = x; // store
/*...*/
n1 = s._M_length + 1; // load
if (n1 > 16)
__builtin_unreachable();// range info provided for SSA n1
__builtin_memcpy(_, _, n1); // (call_3) MOVE-Ctor, has range info
```
2. store-to-load forwarding
The compiler forwards the store to the load, so SSA name `n1` is replaced by
`n0`.
```cpp
n0 = x + 1;
__builtin_memcpy(_, _, n0); // (call_1) COPY-Ctor, no range info
/*...*/
if (n0 > 16)
__builtin_unreachable();// guard moved from n1 to n0, but the range info
did not
__builtin_memcpy(_, _, n0); // (call_3) MOVE-Ctor, no range info
```
3. redundant guard removal
The guard is then removed as a redundant assumption, and the range information
is not available at the second `memcpy`. So it is lost. (bug?)
```cpp
n0 = x + 1;
__builtin_memcpy(_, _, n0); // (call_1) COPY-Ctor, no range info
/*...*/
__builtin_memcpy(_, _, n0); // (call_3) MOVE-Ctor, no range info
```
In short, the range information is attached to the SSA name. When `n1` is
replaced by the equivalent `n0`, the bound is not transferred to the value used
by the second `memcpy`; since `n0` is also used by call_1, it cannot simply
carry a global `<= 16` range. As a result, two `memcpy` calls without range
information are emitted.
## Why the `std::function` case is not affected
The first devirtualization optimization does not happen for `std::function`, so
`call_1` and `call_3` stay in different scopes. No store-to-load forwarding is
possible.
## How to fix it
1. The libstdc++ workaround
Change the copy constructor of `std::string` so that the SSO copy has range
information and the two copies no longer share one size SSA name: SSA `n1` (the
bounded one in MOVE-Ctor) is no longer replaced by `n0`, so its range
information is preserved.
New copy constructor for `basic_string` in bits/basic_string.h:
```cpp
/**
* @brief Construct string with copy of value of @a __str.
* @param __str Source string.
*/
_GLIBCXX20_CONSTEXPR
basic_string(const basic_string& __str)
: _M_dataplus(_M_local_data(),
_Alloc_traits::_S_select_on_copy(__str._M_get_allocator()))
{
if (__str._M_is_local()) // `_M_is_local` provides range info
{
_M_init_local_buf();
traits_type::copy(_M_local_buf, __str._M_local_buf,
__str.length() + 1);
_M_length(__str.length());
}
else
_M_construct<true>(__str._M_data(), __str.length());
}
```
With this workaround, the `std::move_only_function` case is no longer 50%
slower than `std::function`; it is about 2% faster.
2. The compiler fix
I don't really know the implementation details of the GCC store-load
optimization, so I'm not sure whether this is a bug or just an inherent
limitation of that optimization.
---
link: <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85316> ([meta] VRP)
