Add support for unwrapping all contiguous iterators

[EricWF]

Summary

Merge branch 'finish-optimization-for-move' of github.com:efcs/llvm-project into finish-optimization-for-move

libcxx/include/algorithm

 _ForwardIterator
 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
 {
     typedef typename iterator_traits<_ForwardIterator>::value_type __v;
     return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
                            __value_, __equal_to<__v, _Tp>());
 }
 
-// copy
-template <class _Iter>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_Iter
-__unwrap_iter(_Iter __i)
-{
-    return __i;
-}
-
-template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-typename enable_if
-<
-    is_trivially_copy_assignable<_Tp>::value,
-    _Tp*
->::type
-__unwrap_iter(move_iterator<_Tp*> __i)
-{
-    return __i.base();
-}
-
-#if _LIBCPP_DEBUG_LEVEL < 2
-
-template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
-typename enable_if
-<
-    is_trivially_copy_assignable<_Tp>::value,
-    _Tp*
->::type
-__unwrap_iter(__wrap_iter<_Tp*> __i)
-{
-    return __i.base();
-}
-
-template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
-typename enable_if
-<
-    is_trivially_copy_assignable<_Tp>::value,
-    const _Tp*
->::type
-__unwrap_iter(__wrap_iter<const _Tp*> __i)
-{
-    return __i.base();
-}
-
-#else
-
-template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
-typename enable_if
-<
-    is_trivially_copy_assignable<_Tp>::value,
-    __wrap_iter<_Tp*>
->::type
-__unwrap_iter(__wrap_iter<_Tp*> __i)
-{
-    return __i;
-}
-
-#endif  // _LIBCPP_DEBUG_LEVEL < 2
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 __copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
     for (; __first != __last; ++__first, (void) ++__result)
         *__result = *__first;
     return __result;
 }
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
-__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, false_type)
 {
-    return __copy_constexpr(__first, __last, __result);
+    return std::__copy_constexpr(__first, __last, __result);
 }
 
 template <class _Tp, class _Up>
-inline _LIBCPP_INLINE_VISIBILITY
-typename enable_if
-<
-    is_same<typename remove_const<_Tp>::type, _Up>::value &&
-    is_trivially_copy_assignable<_Up>::value,
-    _Up*
->::type
-__copy(_Tp* __first, _Tp* __last, _Up* __result)
+_Up
+__copy(_Tp __first, _Tp __last, _Up __result, true_type)
 {
+
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)
-        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+        _VSTD::memmove(std::__to_address(__result), std::__to_address(__first), __n * sizeof(typename iterator_traits<_Tp>::value_type));
     return __result + __n;
 }
 
 template <class _InputIterator, class _OutputIterator>
+using __can_optimize_copy_on_pointers = _And<
+    __is_unwrappable_contiguous_iterator<_InputIterator>,
+    __is_unwrappable_contiguous_iterator<_OutputIterator>,
+    is_lvalue_reference<typename iterator_traits<_InputIterator>::reference>,
+    _IsSame<
+        typename remove_const<typename iterator_traits<_InputIterator>::value_type>::type,
+        typename iterator_traits<_OutputIterator>::value_type
+    >,
+    is_trivially_copy_assignable<typename iterator_traits<_OutputIterator>::value_type>
+  >;
+
+
+template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
 _OutputIterator
 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
+
     if (__libcpp_is_constant_evaluated()) {
-        return _VSTD::__copy_constexpr(
-            __unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
+        return _VSTD::__copy_constexpr(__first, __last, __result);
     } else {
-        return _VSTD::__copy(
-            __unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
+        return _VSTD::__copy(__first, __last, __result, __can_optimize_copy_on_pointers<_InputIterator, _OutputIterator>() );
     }
 }
 
 // copy_backward
 
 template <class _BidirectionalIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 __copy_backward_constexpr(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
 {
     while (__first != __last)
         *--__result = *--__last;
     return __result;
 }
 
 template <class _BidirectionalIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
-__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
+__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result, false_type)
 {
-    return __copy_backward_constexpr(__first, __last, __result);
+    return std::__copy_backward_constexpr(__first, __last, __result);
 }
 
 template <class _Tp, class _Up>
 inline _LIBCPP_INLINE_VISIBILITY
-typename enable_if
-<
-    is_same<typename remove_const<_Tp>::type, _Up>::value &&
-    is_trivially_copy_assignable<_Up>::value,
-    _Up*
->::type
-__copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
+_Up
+__copy_backward(_Tp __first, _Tp __last, _Up __result, true_type)
 {
+
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)
     {
         __result -= __n;
-        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+        _VSTD::memmove(std::__unwrap_contiguous(__result),
+                      std::__unwrap_contiguous(__first),
+                      __n * sizeof(typename iterator_traits<_Tp>::value_type));
     }
     return __result;
 }
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
 _BidirectionalIterator2
 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
               _BidirectionalIterator2 __result)
 {
+
     if (__libcpp_is_constant_evaluated()) {
-        return _VSTD::__copy_backward_constexpr(__unwrap_iter(__first),
-                                                __unwrap_iter(__last),
-                                                __unwrap_iter(__result));
+        return _VSTD::__copy_backward_constexpr(__first, __last, __result);
     } else {
-        return _VSTD::__copy_backward(__unwrap_iter(__first),
-                                      __unwrap_iter(__last),
-                                      __unwrap_iter(__result));
+        return _VSTD::__copy_backward(__first, __last, __result,
+                                      __can_optimize_copy_on_pointers<_BidirectionalIterator1, _BidirectionalIterator2>());
     }
 }
 
 // copy_if
 
 template<class _InputIterator, class _OutputIterator, class _Predicate>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
     return _VSTD::copy(__first, __first + __n, __result);
 }
 
 // move
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
-__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result, false_type)
 {
     for (; __first != __last; ++__first, (void) ++__result)
         *__result = _VSTD::move(*__first);
     return __result;
 }
 
 template <class _Tp, class _Up>
 inline _LIBCPP_INLINE_VISIBILITY
-typename enable_if
-<
-    is_same<typename remove_const<_Tp>::type, _Up>::value &&
-    is_trivially_copy_assignable<_Up>::value,
-    _Up*
->::type
-__move(_Tp* __first, _Tp* __last, _Up* __result)
+_Up
+__move(_Tp __first, _Tp __last, _Up __result, true_type)
 {
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)
-        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+        _VSTD::memmove(std::__unwrap_contiguous(__result), std::__unwrap_contiguous(__first), __n * sizeof(typename iterator_traits<_Tp>::value_type));
     return __result + __n;
 }
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
-    return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
+    return _VSTD::__move(__first, __last, __result, __can_optimize_copy_on_pointers<_InputIterator, _OutputIterator>() );
 }
 
 // move_backward
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
-__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result, false_type)
 {
     while (__first != __last)
         *--__result = _VSTD::move(*--__last);
     return __result;
 }
 
 template <class _Tp, class _Up>
 inline _LIBCPP_INLINE_VISIBILITY
-typename enable_if
-<
-    is_same<typename remove_const<_Tp>::type, _Up>::value &&
-    is_trivially_copy_assignable<_Up>::value,
-    _Up*
->::type
-__move_backward(_Tp* __first, _Tp* __last, _Up* __result)
+_Up
+__move_backward(_Tp __first, _Tp __last, _Up __result, true_type)
 {
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)
     {
         __result -= __n;
-        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+        _VSTD::memmove(std::__unwrap_contiguous(__result), std::__unwrap_contiguous(__first), __n * sizeof(typename iterator_traits<_Up>::value_type));
     }
     return __result;
 }
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_INLINE_VISIBILITY
 _BidirectionalIterator2
 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
               _BidirectionalIterator2 __result)
 {
-    return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
+    return _VSTD::__move_backward(__first, __last, __result, __can_optimize_copy_on_pointers<_BidirectionalIterator1, _BidirectionalIterator2>());
 }
 
 // iter_swap
 
 // moved to <type_traits> for better swap / noexcept support
 
 // transform
 

libcxx/include/iterator

 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
 struct __has_iterator_category_convertible_to
     : public integral_constant<bool, is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
 {};
 
 template <class _Tp, class _Up>
 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : public false_type {};
 
+
+template <class _Tp, class _Up, bool = _IsValidExpansion<_ITER_CONCEPT, _Tp >::value >
+struct __has_iterator_concept_convertible_to
+    : public integral_constant<bool, is_convertible< _ITER_CONCEPT<_Tp>, _Up>::value>
+{};
+
+template <class _Tp, class _Up>
+struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : public false_type {};
+
+
 template <class _Tp>
 struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
 
 #if _LIBCPP_STD_VER > 17
 template <class _Tp>
 struct __is_cpp17_contiguous_iterator : public __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag> {};
+template <class _Tp>
+struct __has_contiguous_iterator_concept : public __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> {};
 #else
 template <class _Tp>
 struct __is_cpp17_contiguous_iterator : public false_type {};
+template <class _Tp>
+struct __has_contiguous_iterator_concept : public false_type {};
 #endif
 
 
 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> {};

 __wrap_iter<_Iter>
 operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT;
 
 template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy(_Ip, _Ip, _Op);
 template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy_backward(_B1, _B1, _B2);
 template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY move(_Ip, _Ip, _Op);
 template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY move_backward(_B1, _B1, _B2);
 
-#if _LIBCPP_DEBUG_LEVEL < 2
-
-template <class _Tp>
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
-typename enable_if
-<
-    is_trivially_copy_assignable<_Tp>::value,
-    _Tp*
->::type
-__unwrap_iter(__wrap_iter<_Tp*>);
-
-#else
-
-template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
-typename enable_if
-<
-    is_trivially_copy_assignable<_Tp>::value,
-    __wrap_iter<_Tp*>
->::type
-__unwrap_iter(__wrap_iter<_Tp*> __i);
-
+#if _LIBCPP_STD_VER > 17
+struct __empty_base {};
+struct __contiguous_iterator_concept_base {
+  using iterator_concept = contiguous_iterator_tag;
+};
 #endif
 
 template <class _Iter>
 class __wrap_iter
+#if _LIBCPP_STD_VER > 17
+: public _If<
+    __has_iterator_concept_convertible_to<_Iter, contiguous_iterator_tag>::value,
+    __contiguous_iterator_concept_base,
+    __empty_base
+  >
+#endif
 {
 public:
     typedef _Iter                                                      iterator_type;
     typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
     typedef typename iterator_traits<iterator_type>::value_type        value_type;
     typedef typename iterator_traits<iterator_type>::difference_type   difference_type;
     typedef typename iterator_traits<iterator_type>::pointer           pointer;
     typedef typename iterator_traits<iterator_type>::reference         reference;
+
 private:
     iterator_type __i;
 public:
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
                 : __i{}
 #endif
     {
#endif
     __wrap_iter<_Iter1>
     operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
 
     template <class _Ip, class _Op> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _Op copy(_Ip, _Ip, _Op);
     template <class _B1, class _B2> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _B2 copy_backward(_B1, _B1, _B2);
     template <class _Ip, class _Op> friend _Op move(_Ip, _Ip, _Op);
     template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2);
 
-#if _LIBCPP_DEBUG_LEVEL < 2
-    template <class _Tp>
-    _LIBCPP_CONSTEXPR_IF_NODEBUG friend
-    typename enable_if
-    <
-        is_trivially_copy_assignable<_Tp>::value,
-        _Tp*
-    >::type
-    __unwrap_iter(__wrap_iter<_Tp*>);
-#else
-  template <class _Tp>
-  inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
-  typename enable_if
-  <
-      is_trivially_copy_assignable<_Tp>::value,
-      __wrap_iter<_Tp*>
-  >::type
-  __unwrap_iter(__wrap_iter<_Tp*> __i);
-#endif
 };
 
 template <class _Iter1, class _Iter2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
 bool
 operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
 {
     return __x.base() == __y.base();

libcxx/include/memory

template <> struct __to_address_helper<true> {
 
     template <class _Pointer>
     _LIBCPP_CONSTEXPR
     static __return_type<_Pointer>
     __do_it(const _Pointer &__p) _NOEXCEPT { return pointer_traits<_Pointer>::to_address(__p); }
 };
 
 template <class _Pointer, bool _Dummy = true>
-using __choose_to_address = __to_address_helper<_IsValidExpansion<__to_address_helper<_Dummy>::template __return_type, _Pointer>::value>;
+using __choose_to_address = __to_address_helper<
+        _IsValidExpansion<__to_address_helper<_Dummy>::template __return_type, _Pointer>::value>;
 
 
 template <class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 _Tp*
 __to_address(_Tp* __p) _NOEXCEPT
 {
     static_assert(!is_function<_Tp>::value, "_Tp is a function type");

 inline _LIBCPP_INLINE_VISIBILITY
 auto
 to_address(const _Pointer& __p) _NOEXCEPT
 {
     return _VSTD::__to_address(__p);
 }
 #endif
 
+
+template <class _Tp, class _Desired>
+struct __to_address_test : _IsSame<
+    decltype(std::__to_address(std::declval<_Tp&>())),
+    _Desired
+> {};
+
+template <class _Iter>
+using __is_unwrappable_contiguous_iterator = _And<
+      __is_cpp17_random_access_iterator<_Iter>,
+      __has_contiguous_iterator_concept<_Iter>,
+      __to_address_test<_Iter,
+     typename remove_reference<typename iterator_traits<_Iter>::pointer>::type
+    >
+>;
+
+template <class _Iter, class = _EnableIf<__is_unwrappable_contiguous_iterator<_Iter>::value> >
+typename iterator_traits<_Iter>::pointer
+__unwrap_contiguous(_Iter __it) {
+  static_assert(std::is_pointer<typename iterator_traits<_Iter>::pointer>::value, "");
+  return std::__to_address(__it);
+}
+
 template <class _Tp, class = void>
 struct __has_size_type : false_type {};
 
 template <class _Tp>
 struct __has_size_type<_Tp,
                typename __void_t<typename _Tp::size_type>::type> : true_type {};
 
 template <class _Alloc, class _DiffType, bool = __has_size_type<_Alloc>::value>