<algorithm>: reverse_copy is mistakenly vectorized for pair<int&, int&> on 32-bit targets

[frederick-vs-ja]

Describe the bug

From DevCom-10662768.

MSVC STL's pair<int&, int&> is trivially copyable but not trivially copy assignable. Currently, vectorization of reverse_copy incorrectly detects the element type with is_trivially_copyable, which is problematic with pair<int&, int&> and its friends.

STL/stl/inc/algorithm

Lines 5095 to 5115 in 63354c3

	#if _USE_STD_VECTOR_ALGORITHMS
	using _Elem = remove_reference_t<_Iter_ref_t<remove_const_t<decltype(_UFirst)>>>;
	using _DestElem = remove_reference_t<_Iter_ref_t<decltype(_UDest)>>;
	constexpr bool _Allow_vectorization = conjunction_v<is_same<remove_const_t<_Elem>, _DestElem>,
	bool_constant<_Iterators_are_contiguous<decltype(_ULast), decltype(_UDest)>>, is_trivially_copyable<_Elem>,
	negation<is_volatile<_Elem>>>;
	constexpr size_t _Nx = sizeof(_Elem);
	if constexpr (_Allow_vectorization && _Nx <= 8 && (_Nx & (_Nx - 1)) == 0) {
	#if _HAS_CXX20
	if (!_STD is_constant_evaluated())
	#endif // _HAS_CXX20
	{
	_STD _Reverse_copy_vectorized<_Nx>(
	_STD _To_address(_UFirst), _STD _To_address(_ULast), _STD _To_address(_UDest));
	_UDest += _ULast - _UFirst;
	_STD _Seek_wrapped(_Dest, _UDest);
	return _Dest;
	}
	}
	#endif // _USE_STD_VECTOR_ALGORITHMS

STL/stl/inc/algorithm

Lines 5175 to 5192 in 63354c3

	#if _USE_STD_VECTOR_ALGORITHMS
	if constexpr (contiguous_iterator<_It> && contiguous_iterator<_Out>) {
	using _Elem = remove_reference_t<iter_reference_t<_It>>;
	using _DestElem = remove_reference_t<iter_reference_t<_Out>>;
	constexpr bool _Allow_vectorization = conjunction_v<is_same<remove_const_t<_Elem>, _DestElem>,
	is_trivially_copyable<_Elem>, negation<is_volatile<_Elem>>>;
	constexpr size_t _Nx = sizeof(_Elem);
	if constexpr (_Allow_vectorization && _Nx <= 8 && (_Nx & (_Nx - 1)) == 0) {
	if (!_STD is_constant_evaluated()) {
	_STD _Reverse_copy_vectorized<_Nx>(
	_STD to_address(_First), _STD to_address(_Last), _STD to_address(_Result));
	_Result += _Last - _First;
	return _Result;
	}
	}
	}
	#endif // _USE_STD_VECTOR_ALGORITHMS

Command-line test case

C:\repro>type repro.cpp
#include <algorithm>
#include <cstdio>
#include <utility>

using Pear = std::pair<int &, int &>;
#ifdef _MSC_VER
static_assert(__is_trivially_copyable(Pear));
static_assert(__is_assignable(Pear &, const Pear &));
static_assert(!__is_trivially_assignable(Pear &, const Pear &));
#endif

int main() {
  std::pair<int, int> src[] = {{1, 2}, {3, 4}, {5, 6}};
  std::pair<int, int> dst[] = {{3, 1}, {4, 1}, {5, 9}};
  std::pair<int &, int &> srcref[] = {src[0], src[1], src[2]};
  std::pair<int &, int &> dstref[] = {dst[0], dst[1], dst[2]};
  std::reverse_copy(srcref, srcref + 3, dstref);
  // Now dst should be {5,6}, {3,4}, {1,2}
  for (auto &p : dst) {
    printf("%d %d\n", p.first, p.second);
  }
}

C:\repro>cl /EHsc /W4 /WX /std:c++latest .\repro.cpp
用于 x86 的 Microsoft (R) C/C++ 优化编译器 19.41.33901 版
版权所有(C) Microsoft Corporation。保留所有权利。

/std:c++latest 作为最新的 C++
working 草稿中的语言功能预览提供。我们希望你提供有关 bug 和改进建议的反馈。
但是，请注意，这些功能按原样提供，没有支持，并且会随着工作草稿的变化
而更改或移除。有关详细信息，请参阅
https://go.microsoft.com/fwlink/?linkid=2045807。

repro.cpp
Microsoft (R) Incremental Linker Version 14.41.33901.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:repro.exe
repro.obj

C:\repro>.\repro.exe
3 1
4 1
5 9

Expected behavior

The output should be

5 6
3 4
1 2

A 64-bit target program outputs the correct results.

STL version

Microsoft Visual Studio Community 2022 Preview
Version 17.11.0 Preview 1.0

Additional context

See also WG21-P3279R0.

[StephanTLavavej]

Thanks - this is a regression presumably going back to #804 in VS 2019 16.8.

[AlexGuteniev]

I think this should be fixed by implementing the paper.

I have some special algorithms implemented directly in application code, that also have this assumption, and making the traits behaving expected would fix those too.

[AlexGuteniev]

Until the paper can't be implemented, can have workaround with transition comment though.

[frederick-vs-ja]

I think I can implement the workaround.

Workaround for Leopard in WG21-P3279R0 seems implementable to me. It should be sufficient to detect whether a T::operator= has the one of the expected types. Although such detection will be extreme boilerplate.

[Quuxplusone]

Author of P3279R0 here. (I admit R0 is a mess; I'm planning an R1 that will be a different kind of mess. Sorry.)

@AlexGuteniev says "I think this should be fixed by implementing [P3279]." P3279 proposes that C++ should redefine the meaning of is_trivially_copyable such that is_trivially_copyable<pair<int&, int&>> becomes 100% guaranteed false (because pair<int&, int&> does assign-through and therefore after P3279 its assignment would be non-trivial by definition).

Therefore, the appropriate way to "implement P3279" today, if you want to take @AlexGuteniev's advice (and mine), is to anticipate the paper's changes and make Microsoft's is_trivially_copyable<pair<int&, int&>> yield false today. The easiest way to do that is to give it an assignment operator that is non-trivial according to today's C++. Basically, "don't lie to the compiler" — don't write pair in such a way that the compiler thinks it's trivially copyable when in fact you want it not to be trivially copied.

On my blog I have a whole series of "#sd-8-adjacent" guidelines; and though I haven't written it up yet, certainly one of those guidelines should be "Don't go out of your way to make a type falsely advertise trivial copyability when you don't want people to trivially copy it." I think you can (and should) assume that users will follow that guideline instinctively. Your single solitary problem here is that your own std::pair fails to follow the guideline: it falsely advertises trivial copyability when in fact you don't want it to be trivially copied. So just stop advertising it as such, and you're golden!

The bug report here concerns the false-advertising of std::pair, not really anything wrong with reverse_copy. I really strongly encourage you not to "fix" your reverse_copy. Because even if you "fix" your own reverse_copy, you can't fix all the library algorithms that are already out there in the wild that will fail when presented with your falsely-advertising std::pair — but you can fix your std::pair so that it will work correctly with all those existing algorithms (and also with your own reverse_copy).

See further pre-filing discussion on the cpplang Slack.

[frederick-vs-ja]

Therefore, the appropriate way to "implement P3279" today, if you want to take @AlexGuteniev's advice (and mine), is to anticipate the paper's changes and make Microsoft's is_trivially_copyable<pair<int&, int&>> yield false today.

Hmm, the crux of MSVC STL's pair (and tuple) is that it's copy- and move-assigned by assignment operator templates that are not copy or move assignment operators. Perhaps it would be better to switch to use real copy and move assignment operators, but I'm not sure whether we can do this before vNext due to ABI issues, see #3013.

I really strongly encourage you not to "fix" your reverse_copy. Because even if you "fix" your own reverse_copy, you can't fix all the library algorithms that are already out there in the wild that will fail when presented with your falsely-advertising std::pair

I think this is possible. I'm preparing a patch making vectorization correctly applied for regular trivially copyable classes (which are trivially copy & move constructible & assignable with expected semantics), while ruling out your Leopard in WG21-P3279R0. The trick is extremely verbose and forbidden for user code because it detects conversion from &T::operator= to certain types. But I think it's fine for the library implementation itself and it can work.

BTW, now I guess it would be better to add new traits of names is_bitwise_constructible, is_bitwise_convertible, and is_bitwise_assignable, and deprecate corresponding is_trivially_meowable.

[frederick-vs-ja]

There're still some unresovlable problems though.

Given struct VolatileMem { volatile int x; };, it seems that vectorization (including memcpy/memmove) shouldn't be applied for a range of it. But it's generally impossible to detect the volatile member and I'm not seeing any paper addressing this (except for those for reflection).

Edit: there's already one such paper, see below.

[Quuxplusone]

There're still some unresovle problems though.

Given struct VolatileMem { volatile int x; };, it seems that vectorization (including memcpy/memmove) shouldn't be applied for a range of it. But it's generally impossible to detect the volatile member and I'm not seeing any paper addressing this (except for those for reflection).

I covered that case in "When is a trivially copyable type not trivially copyable?" (2018-07-13), and in the paper P1153R0 Copying volatile subobjects is not trivial (2018); but ended up dropping P1153. IIRC, I dropped it simply because I thought it wasn't worth spending time on: The library never goes out of its way to care about volatile, so there didn't seem to be a good reason for is_trivially_fooable specifically to go out of its way to care, either. But I could see an argument for picking it back up.

I really strongly encourage you not to "fix" your reverse_copy. Because even if you "fix" your own reverse_copy, you can't fix all the library algorithms that are already out there in the wild that will fail when presented with your falsely-advertising std::pair

I think this is possible. I'm preparing a patch [...] ruling out your Leopard. The trick is extremely verbose and forbidden for user code [...] But I think it's fine for the library implementation itself and it can work.

Please don't use any "trick" in Microsoft's reverse_copy that can't also be applied to

• Folly's fbvector
• Abseil's any_invocable
• Qt's qIsRelocatable

etc. etc. Microsoft's pair is currently giving bad behavior on all third-party libraries, which is why fixing pair should be higher-priority than "fixing" reverse_copy alone. It would be more intellectually honest, IMO, to leave the 32-bit reverse_copy "broken" (and leave this bug report open) until such time as you can fix pair itself.

[StephanTLavavej]

I disagree. With the Core Language as it stands today, our pair type is doing nothing wrong (it is something that the Core Language allows to exist, and user types could behave like it too), and our type traits are doing nothing wrong. It's the algorithm's use of is_trivially_copyable when we're about to (bypass) an assignment, where is_trivially_copy_assignable would be the proper question to ask.

We should patch this optimization, and audit the STL for all other uses of is_trivially_copyable that would be vulnerable to similar problems.

If other third-party libraries made the same mistake that we did, they should also patch themselves.

[StephanTLavavej]

We'll revisit this in July 2024.

[frederick-vs-ja]

I disappointedly found that while it's possible to rule out Leopard, it doesn't seem possible to rule out a class wrapping it, e.g. struct LeopardHouse { Leopard _; };. MSVC and Clang behave differently - MSVC doesn't think LeopardHouse is trivially copy assignable while Clang does, and currently Clang seems right. However, P3279 seemingly makes MSVC's behavior correct.

I guess at least we need the __is_bitwise_assignable intrinsic if we can't change __is_trivially_assignable directly.