[libc++] Forward more often to memmove in copy

[philnik]

Summary

In D122982 I accidentally disabled the memmove optimization. This re-enables it and adds more cases where copy forwards to memmove.
Fixes https://github.com/llvm/llvm-project/issues/33687

[xbolva00]

Fixes https://github.com/llvm/llvm-project/issues/33687

What exactly? For the testcases, I see two memmoves with libc++:

https://gcc.godbolt.org/z/GeWf6b179

[philnik]

In D124328#3469921, @xbolva00 wrote:

Fixes https://github.com/llvm/llvm-project/issues/33687

What exactly? For the testcases, I see two memmoves with libc++:

https://gcc.godbolt.org/z/GeWf6b179

This now unwraps even weird stuff like reverse_iterator<reverse_iterator<int*>>. It also unwraps reverse_iterator<std::vector<int>::iterator> properly (and combinations). In D122982 I disabled the std::vector<int>::iterator unwrapping accidentally.

[var-const]

Is it possible to add some tests for this? For checking the optimization, perhaps use structs containing pointers to dynamically-allocated memory that have deep-copying constructors, then check that only the pointers themselves were copied?

libcxx/include/__algorithm/copy.h

74

Nit: I think checking _InIter should happen before _OutIter for consistency with the argument order.

106

Question: why wouldn't the other reverse_iter overload that calls __unwrap_iter handle the case?

[philnik]

• address comments

[philnik]

In D124328#3479081, @var-const wrote:

Is it possible to add some tests for this? For checking the optimization, perhaps use structs containing pointers to dynamically-allocated memory that have deep-copying constructors, then check that only the pointers themselves were copied?

I don't think there is a way to check other than grepping for memmove in the binary. IIUC you suggestion would be to add non-trivial assignment operators, but that would disable the optimization. The optimization should only apply if it's invisible to the user.

libcxx/include/__algorithm/copy.h

106

With a reverse_iterator<reverse_iterator<int*>> the other overload would have _InIter = reverse_iterator<int*>. This is only a random access iterator and not a contiguous iterator, so it wouldn't get unwrapped.

[var-const]

In D124328#3480095, @philnik wrote:

IIUC you suggestion would be to add non-trivial assignment operators, but that would disable the optimization. The optimization should only apply if it's invisible to the user.

Ah, I think you're right.

libcxx/include/__algorithm/copy.h

106

Can you please add a comment to that effect in this function? The fact that __unwrap_iter only deals with contiguous iterators is really not obvious without looking at its implementation.

[philnik]

• Try to fix C++03

[dcheng]

Not sure if this helps, but Chrome noticed this breakage during an attempt to roll libc++: https://crbug.com/1322961

The "test" that we have for this is quite horrible and I'm not sure that we'd want to adopt it here, but just for the sake of completeness: https://source.chromium.org/chromium/chromium/src/+/main:base/containers/checked_iterators_unittest.cc;l=101;drc=633d2d745d1fd09256ab846e7f923fbc5c084770

[philnik]

• Add test

[philnik]

• Try to fix CI

[ldionne]

libcxx/include/__algorithm/copy.h

51

This is one of the reasons why I like sharing implementations between ranges versions of algorithms and non-ranges versions. Even a simple algorithm like std::copy can become not-so-simple due to subtle reasons, and we'd risk not fixing/improving one of the two algorithms if we had two copies. Nothing to do about this comment, just a rationale for why I can appear annoying with my requests to share ranges and non-ranges code.

59–69

Is it possible that what you're looking for here is instead is_contiguous_iterator<_Iter> && is_trivially_copy_assignable<value_type<_Iter>>? I don't think we have a trait for is_contiguous_iterator that works with older standards and understands __wrap_iter properly, but we probably should if that's indeed what you mean.

90–92

Can you negate the condition used below instead? It makes it easier to understand what's going on:

__enable_if_t<!(is_copy_constructible<_InIter>::value
                && is_copy_constructible<_Sent>::value
                && is_copy_constructible<_OutIter>::value)>

101–105

Can you use class = __enable_if_t<...> instead to allow placing the return type in the usual place? Note that if you run into duplicate declaration issues, you can use non-type template parameters instead:

template <class _InIter, class _Sent, class _OutIter, __enable_if_t<CONDITION>* = nullptr>
...

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp

13

This needs a comment explaining what the test does (it tests that we optimize copy operations into memmoves IIUC).

[philnik]

• Address comments

[philnik]

• Try to fix CI

[pkasting]

@philnik It looks like you're working on this in your spare time. Do you know when you'll be able to get back to it? Chromium downstream is waiting on this to land before updating to the latest libc++ sources, to avoid regressing perf.

[philnik]

In D124328#3547884, @pkasting wrote:

@philnik It looks like you're working on this in your spare time. Do you know when you'll be able to get back to it? Chromium downstream is waiting on this to land before updating to the latest libc++ sources, to avoid regressing perf.

The patch works. Right now I'm just waiting for @ldionne to review it. It should be done by Friday.

[ldionne]

LGTM, but let's fix the failing CI tests. Thanks!

libcxx/include/__algorithm/copy.h

113

I would like to investigate (in a different patch if the experiment turns out positive) the possibility of overloading __unwrap_iter (and __rewrap_iter) for reverse_iterator<reverse_iterator<It>> more generally. If that works out, we would get some added benefits in other algorithms as well for free, and this overload could go away entirely.

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp

14

[philnik]

• Fix tests and address comments

libcxx/include/__algorithm/copy.h

113

Added a TODO

libcxx/include/__algorithm/copy.h

template <class _InValueT,
                              && is_trivially_copy_assignable<_OutValueT>::value> >
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_InValueT*, _OutValueT*> __copy_impl(_InValueT* __first, _InValueT* __last, _OutValueT* __result) {
   if (__libcpp_is_constant_evaluated()
 // TODO: Remove this once GCC supports __builtin_memmove during constant evaluation
 #ifndef _LIBCPP_COMPILER_GCC
       && !is_trivially_copyable<_InValueT>::value
 #endif
      )
     return std::__copy_impl<_InValueT*, _InValueT*, _OutValueT*>(__first, __last, __result);
   const size_t __n = static_cast<size_t>(__last - __first);
   if (__n > 0)
     ::__builtin_memmove(__result, __first, __n * sizeof(_OutValueT));
   return std::make_pair(__first + __n, __result + __n);
 }
 
-template <class _InValueT,
-          class _OutValueT,
-          class = __enable_if_t<is_same<typename remove_const<_InValueT>::type, _OutValueT>::value
-                             && is_trivially_copy_assignable<_OutValueT>::value> >
+template <class _Iter>
+using __is_trivially_copy_assignable_unwrapped =
+    _And<__is_cpp17_contiguous_iterator<_Iter>, is_trivially_copy_assignable<__iter_value_type<_Iter> > >;
+
+template <class _InIter,
+          class _OutIter,
+          class = __enable_if_t<is_same<typename remove_const<typename iterator_traits<_InIter>::value_type>::type,
+                                        typename iterator_traits<_OutIter>::value_type>::value
+                             && __is_trivially_copy_assignable_unwrapped<_InIter>::value
+                             && __is_trivially_copy_assignable_unwrapped<_OutIter>::value> >
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-pair<reverse_iterator<_InValueT*>, reverse_iterator<_OutValueT*> >
-__copy_impl(reverse_iterator<_InValueT*> __first,
-            reverse_iterator<_InValueT*> __last,
-            reverse_iterator<_OutValueT*> __result) {
-  auto __first_base = __first.base();
-  auto __last_base = __last.base();
-  auto __result_base = __result.base();
+pair<reverse_iterator<_InIter>, reverse_iterator<_OutIter> >
+__copy_impl(reverse_iterator<_InIter> __first,
+            reverse_iterator<_InIter> __last,
+            reverse_iterator<_OutIter> __result) {
+  auto __first_base = std::__unwrap_iter(__first.base());
+  auto __last_base = std::__unwrap_iter(__last.base());
+  auto __result_base = std::__unwrap_iter(__result.base());
   auto __result_first = __result_base - (__first_base - __last_base);
   std::__copy_impl(__last_base, __first_base, __result_first);
-  return std::make_pair(__last, reverse_iterator<_OutValueT*>(__result_first));
+  return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first)));
 }
 
 template <class _InIter, class _Sent, class _OutIter>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+pair<reverse_iterator<reverse_iterator<_InIter> >, reverse_iterator<reverse_iterator<_OutIter> > >
+__copy_impl(reverse_iterator<reverse_iterator<_InIter> > __first,
+            reverse_iterator<reverse_iterator<_Sent> > __last,
+            reverse_iterator<reverse_iterator<_OutIter> > __result);
+
+template <class _InIter, class _Sent, class _OutIter,
+          __enable_if_t<!(is_copy_constructible<_InIter>::value
+                       && is_copy_constructible<_Sent>::value
+                       && is_copy_constructible<_OutIter>::value), int> = 0 >
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) {
   return std::__copy_impl(std::move(__first), std::move(__last), std::move(__result));
 }
 
 template <class _InIter, class _Sent, class _OutIter,
           __enable_if_t<is_copy_constructible<_InIter>::value
                      && is_copy_constructible<_Sent>::value
-                     && is_copy_constructible<_OutIter>::value> >
+                     && is_copy_constructible<_OutIter>::value, int> = 0>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) {
+pair<_InIter, _OutIter>
+__copy(_InIter __first, _Sent __last, _OutIter __result) {
   auto __ret = std::__copy_impl(std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result));
   return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
 }
 
+// __unwrap_iter can't unwrap random_access_iterators, so we need to unwrap two reverse_iterators manually
+template <class _InIter, class _Sent, class _OutIter>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+pair<reverse_iterator<reverse_iterator<_InIter> >, reverse_iterator<reverse_iterator<_OutIter> > >
+__copy_impl(reverse_iterator<reverse_iterator<_InIter> > __first,
+            reverse_iterator<reverse_iterator<_Sent> > __last,
+            reverse_iterator<reverse_iterator<_OutIter> > __result) {
+  auto __ret = std::__copy(__first.base().base(), __last.base().base(), __result.base().base());
+  return std::make_pair(reverse_iterator<reverse_iterator<_InIter> >(reverse_iterator<_InIter>(__ret.first)),
+                        reverse_iterator<reverse_iterator<_OutIter> >(reverse_iterator<_OutIter>(__ret.second)));
+}
+
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
   return std::__copy(__first, __last, __result).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_COPY_H

libcxx/include/__iterator/iterator_traits.h

 struct __is_cpp17_contiguous_iterator : false_type {};
 #endif
 
 // Any native pointer which is an iterator is also a contiguous iterator.
 template <class _Up>
 struct __is_cpp17_contiguous_iterator<_Up*> : true_type {};
 
 
+template <class _Iter>
+class __wrap_iter;
+
 template <class _Tp>
 struct __is_exactly_cpp17_input_iterator
     : public integral_constant<bool,
          __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
         !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {};
 
-#if _LIBCPP_STD_VER >= 17
 template<class _InputIterator>
 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
 
 template<class _InputIterator>
-using __iter_key_type = remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;
+using __iter_key_type = typename remove_const<typename iterator_traits<_InputIterator>::value_type::first_type>::type;
 
 template<class _InputIterator>
 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;
 
 template<class _InputIterator>
 using __iter_to_alloc_type = pair<
-    add_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>,
+    typename add_const<typename iterator_traits<_InputIterator>::value_type::first_type>::type,
     typename iterator_traits<_InputIterator>::value_type::second_type>;
-#endif // _LIBCPP_STD_VER >= 17
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: debug_level=1
+
+// <algorithm>
+
+// this test checks that std::copy forwards to memmove when appropriate.
+
+#include <algorithm>
+#include <cassert>
+#include <type_traits>
+
+struct S {
+  int i;
+  constexpr S(int i_) : i(i_) {}
+  S(const S&) = default;
+  S(S&&) = delete;
+  constexpr S& operator=(const S&) = default;
+  S& operator=(S&&) = delete;
+  constexpr bool operator==(const S&) const = default;
+};
+
+static_assert(std::is_trivially_copyable_v<S>);
+
+template <class T>
+struct NotIncrementableIt {
+  T* i;
+  using iterator_category = std::contiguous_iterator_tag;
+  using iterator_concept = std::contiguous_iterator_tag;
+  using value_type = T;
+  using difference_type = ptrdiff_t;
+  using pointer = T*;
+  using reference = T&;
+
+  constexpr NotIncrementableIt(T* i_) : i(i_) {}
+
+  friend constexpr bool operator==(const NotIncrementableIt& lhs, const NotIncrementableIt& rhs) {
+    return lhs.i == rhs.i;
+  }
+
+  constexpr T& operator*() { return *i; }
+  constexpr T* operator->() { return i; }
+  constexpr T* operator->() const { return i; }
+
+  constexpr NotIncrementableIt& operator++() {
+    assert(false);
+    return *this;
+  }
+
+  constexpr NotIncrementableIt& operator--() {
+    assert(false);
+    return *this;
+  }
+
+  friend constexpr NotIncrementableIt operator+(const NotIncrementableIt& it, ptrdiff_t size) { return it.i + size; }
+};
+
+static_assert(std::__is_cpp17_contiguous_iterator<NotIncrementableIt<S>>::value);
+
+template <class Iter>
+constexpr void test_normal() {
+  S a[] = {1, 2, 3, 4};
+  S b[] = {0, 0, 0, 0};
+  std::copy(Iter(a), Iter(a + 4), Iter(b));
+  assert(std::equal(a, a + 4, b));
+}
+
+template <class Iter>
+constexpr void test_reverse() {
+  S a[] = {1, 2, 3, 4};
+  S b[] = {0, 0, 0, 0};
+  std::copy(std::make_reverse_iterator(Iter(a + 4)),
+            std::make_reverse_iterator(Iter(a)),
+            std::make_reverse_iterator(Iter(b + 4)));
+}
+
+template <class Iter>
+constexpr void test_reverse_reverse() {
+  S a[] = {1, 2, 3, 4};
+  S b[] = {0, 0, 0, 0};
+  std::copy(std::make_reverse_iterator(std::make_reverse_iterator(Iter(a))),
+            std::make_reverse_iterator(std::make_reverse_iterator(Iter(a + 4))),
+            std::make_reverse_iterator(std::make_reverse_iterator(Iter(b))));
+}
+
+constexpr bool test() {
+  test_normal<S*>();
+  test_normal<NotIncrementableIt<S>>();
+  test_reverse<S*>();
+  test_reverse<NotIncrementableIt<S>>();
+  test_reverse_reverse<S*>();
+  test_reverse_reverse<NotIncrementableIt<S>>();
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+}