https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93059
--- Comment #24 from fdlbxtqi <euloanty at live dot com> --- Comment on attachment 47559 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=47559 An untested patch >From 1dfd714e1f29e229d69a0c7f6f84bf05dd4ee85d Mon Sep 17 00:00:00 2001 >From: expnkx <unlv...@live.com> >Date: Sun, 29 Dec 2019 09:49:19 -0500 >Subject: [PATCH] Untested patch fix volatile bug of std::copyXXX and > std::uninitialized_copyXXX Support custom contiguous_iterator Fix undefined > behavior of &*end constexpr std::fill Greatly improve performance of > std::copyXXX and std::uninitialized_copyXX for different types and apply > pipeline optimization to reduce branch misprediction > >--- > libstdc++-v3/include/bits/stl_algobase.h | 170 ++++++++++++++++++++--- > 1 file changed, 148 insertions(+), 22 deletions(-) > >diff --git a/libstdc++-v3/include/bits/stl_algobase.h >b/libstdc++-v3/include/bits/stl_algobase.h >index 40d056ae8d5..01672a8f232 100644 >--- a/libstdc++-v3/include/bits/stl_algobase.h >+++ b/libstdc++-v3/include/bits/stl_algobase.h >@@ -1,6 +1,6 @@ > // Core algorithmic facilities -*- C++ -*- > >-// Copyright (C) 2001-2019 Free Software Foundation, Inc. >+// Copyright (C) 2001-2020 Free Software Foundation, Inc. > // > // This file is part of the GNU ISO C++ Library. This library is free > // software; you can redistribute it and/or modify it under the >@@ -84,10 +84,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > * A constexpr wrapper for __builtin_memmove. > * @param __num The number of elements of type _Tp (not bytes). > */ >+#ifndef __cpp_lib_concepts > template<bool _IsMove, typename _Tp> >+ _GLIBCXX14_CONSTEXPR >+ inline void volatile* >+ __memmove(_Tp volatile* __dst, _Tp volatile const* __src, size_t __num) >+ { >+ for(; __num > 0; --__num) >+ { >+#if __cplusplus >= 201103L >+ if constexpr (_IsMove) >+ *__dst = std::move(*__src); >+ else >+#endif >+ *__dst = *__src; >+ ++__src; >+ ++__dst; >+ } >+ return __dst; >+ } >+#endif >+ template<bool _IsMove, typename _Tp,typename _Tp_src> >+/* >+#ifdef __cpp_lib_concepts >+ requires (is_trivially_copyable_v<_Tp>&&!is_volatile_v<_Tp> >+ &&is_trivially_copyable_v<_Tp_src>&&!is_volatile_v<_Tp_src> >+ >&&(same_as<_Tp,_Tp_src>||(sizeof(_Tp)==sizeof(_Tp_src)&&integral<_Tp>&&integral<_Tp_src>))) >+#endif >+*/ > _GLIBCXX14_CONSTEXPR > inline void* >- __memmove(_Tp* __dst, const _Tp* __src, size_t __num) >+ __memmove(_Tp* __dst, _Tp_src const* __src, size_t __num) > { > #ifdef __cpp_lib_is_constant_evaluated > if (std::is_constant_evaluated()) >@@ -106,9 +133,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > else > #endif > return __builtin_memmove(__dst, __src, sizeof(_Tp) * __num); >- return __dst; > } >- > /* > * A constexpr wrapper for __builtin_memcmp. > * @param __num The number of elements of type _Tp (not bytes). >@@ -431,7 +456,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > } > }; > #endif >- >+#ifndef __cpp_lib_concepts > template<bool _IsMove> > struct __copy_move<_IsMove, true, random_access_iterator_tag> > { >@@ -448,12 +473,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > static_assert( __assignable::type::value, "type is not assignable" ); > #endif > const ptrdiff_t _Num = __last - __first; >- if (_Num) >- std::__memmove<_IsMove>(__result, __first, _Num); >+ if (!_Num) >+ return __result + _Num; >+//since before C++20, we do not have [[likely]] attribute. We need to do it >manually >+ std::__memmove<_IsMove>(__result, __first, _Num); > return __result + _Num; > } > }; >- >+#endif > // Helpers for streambuf iterators (either istream or ostream). > // NB: avoid including <iosfwd>, relatively large. > template<typename _CharT> >@@ -491,11 +518,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > typedef typename iterator_traits<_II>::value_type _ValueTypeI; > typedef typename iterator_traits<_OI>::value_type _ValueTypeO; > typedef typename iterator_traits<_II>::iterator_category _Category; >+#ifdef __cpp_lib_concepts >+ if constexpr( >+ ((!is_volatile_v<std::remove_reference_t<decltype(*__first)>>)&& >+ is_trivially_copyable_v<_ValueTypeI>)&& >+ ((!is_volatile_v<std::remove_reference_t<decltype(*__result)>>)&& >+ is_trivially_copyable_v<_ValueTypeO>)&& >+ contiguous_iterator<_II>&& >+ contiguous_iterator<_OI>&& >+ (same_as<_ValueTypeI,_ValueTypeO> >+ ||(integral<_ValueTypeI>&&integral<_ValueTypeO>&& >+ sizeof(_ValueTypeI)==sizeof(_ValueTypeO)))) >+ { >+ using __assignable = conditional<_IsMove, >+ is_move_assignable<_OI>, >+ is_copy_assignable<_OI>>; >+ static_assert( __assignable::type::value, "result type is not >assignable" ); >+ ptrdiff_t const _Num = __last - __first; >+ if (_Num) >+#ifdef __has_cpp_attribute(likely) >+//This if statement is by default bad since it affects CPU pipeline. >+//needs likely attribute or the branch misprediction penalty (100% >misprediction rate probably) is HUGE >+ [[likely]] >+#endif >+ std::__memmove<_IsMove>(to_address(__result), to_address(__first), >_Num); >+ return __result + _Num; >+ } >+ else >+ return std::__copy_move<_IsMove, false, >+#else > const bool __simple = (__is_trivially_copyable(_ValueTypeI) > && __is_pointer<_II>::__value > && __is_pointer<_OI>::__value > && __are_same<_ValueTypeI, _ValueTypeO>::__value); > return std::__copy_move<_IsMove, __simple, >+#endif > _Category>::__copy_m(__first, __last, __result); > } > >@@ -581,6 +638,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > * Note that the end of the output range is permitted to be contained > * within [first,last). > */ >+ > template<typename _II, typename _OI> > _GLIBCXX20_CONSTEXPR > inline _OI >@@ -595,7 +653,6 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > return std::__copy_move_a<__is_move_iterator<_II>::__value> > (std::__miter_base(__first), std::__miter_base(__last), __result); > } >- > #if __cplusplus >= 201103L > /** > * @brief Moves the range [first,last) into result. >@@ -698,6 +755,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > }; > #endif > >+#ifndef __cpp_lib_concepts > template<bool _IsMove> > struct __copy_move_backward<_IsMove, true, random_access_iterator_tag> > { >@@ -714,11 +772,13 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > static_assert( __assignable::type::value, "type is not assignable" ); > #endif > const ptrdiff_t _Num = __last - __first; >- if (_Num) >- std::__memmove<_IsMove>(__result - _Num, __first, _Num); >+ if (!_Num) >+ return __result - _Num; >+ std::__memmove<_IsMove>(__result - _Num, __first, _Num); > return __result - _Num; > } > }; >+#endif > > template<bool _IsMove, typename _BI1, typename _BI2> > _GLIBCXX20_CONSTEXPR >@@ -728,21 +788,56 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > typedef typename iterator_traits<_BI1>::value_type _ValueType1; > typedef typename iterator_traits<_BI2>::value_type _ValueType2; > typedef typename iterator_traits<_BI1>::iterator_category _Category; >- const bool __simple = (__is_trivially_copyable(_ValueType1) >- && __is_pointer<_BI1>::__value >- && __is_pointer<_BI2>::__value >- && __are_same<_ValueType1, _ValueType2>::__value); >- > #ifdef __cpp_lib_is_constant_evaluated > if (std::is_constant_evaluated()) >- return std::__copy_move_backward<true, false, >+ return std::__copy_move_backward<true, false, > _Category>::__copy_move_b(__first, __last, > __result); >+ else >+ { > #endif >+#if __cpp_lib_concepts >+ if constexpr( >+ ((!is_volatile_v<std::remove_reference_t<decltype(*__first)>>)&& >+ is_trivially_copyable_v<_ValueType1>)&& >+ ((!is_volatile_v<std::remove_reference_t<decltype(*__result)>>)&& >+ is_trivially_copyable_v<_ValueType2>)&& >+ contiguous_iterator<_BI1>&& >+ contiguous_iterator<_BI2>&& >+ (same_as<_ValueType1,_ValueType2> >+ ||(integral<_ValueType1>&&integral<_ValueType2>&& >+ sizeof(_ValueType1)==sizeof(_ValueType2)))) >+ { >+ using __assignable = conditional<_IsMove, >+ is_move_assignable<_ValueType2>, >+ is_copy_assignable<_ValueType2>>; >+ // trivial types can have deleted assignment >+ static_assert( __assignable::type::value, "type is not assignable" ); >+ ptrdiff_t const _Num = __last - __first; >+ if (_Num) >+ #ifdef __has_cpp_attribute(likely) >+ [[likely]] >+ #endif >+ std::__memmove<_IsMove>(to_address(__result) - _Num, >to_address(__first), _Num); >+ return __result - _Num; >+ } >+#else >+ const bool __simple = ( >+#if __cplusplus >= 201103L >+ (!is_volatile<typename >std::remove_reference<decltype(*__first)>::type>::value)&& >+#endif >+ __is_trivially_copyable(_ValueType1) >+ && __is_pointer<_BI1>::__value >+ && __is_pointer<_BI2>::__value >+ && __are_same<_ValueType1, _ValueType2>::__value); > return std::__copy_move_backward<_IsMove, __simple, > _Category>::__copy_move_b(__first, > __last, > __result); >+#endif >+#ifdef __cpp_lib_is_constant_evaluated >+ } >+#endif > } > > template<bool _IsMove, typename _BI1, typename _BI2> >@@ -908,16 +1003,33 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > } > > // Specialization: for char types we can use memset. >+ > template<typename _Tp> >+ _GLIBCXX20_CONSTEXPR > inline typename > __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type > __fill_a1(_Tp* __first, _Tp* __last, const _Tp& __c) > { >- const _Tp __tmp = __c; >+ _Tp const __tmp = __c; >+#ifdef __cpp_lib_is_constant_evaluated >+ if (std::is_constant_evaluated()) >+ { >+ for (; __first != __last; ++__first) >+ *__first = __tmp; >+ } >+ else >+ { >+#endif > if (const size_t __len = __last - __first) >+#ifdef __has_cpp_attribute(likely) >+ [[likely]] >+#endif > __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len); >+#ifdef __cpp_lib_is_constant_evaluated > } >- >+#endif >+ } >+#ifndef __cpp_lib_concepts > template<typename _Ite, typename _Cont, typename _Tp> > _GLIBCXX20_CONSTEXPR > inline void >@@ -925,7 +1037,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last, > const _Tp& __value) > { std::__fill_a1(__first.base(), __last.base(), __value); } >- >+#endif > template<typename _Tp, typename _VTp> > void > __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&, >@@ -936,7 +1048,14 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > _GLIBCXX20_CONSTEXPR > inline void > __fill_a(_FIte __first, _FIte __last, const _Tp& __value) >- { std::__fill_a1(__first, __last, __value); } >+ { >+#ifdef __cpp_lib_concepts >+ if constexpr(contiguous_iterator<_FIte>) >+ std::__fill_a1(to_address(__first), to_address(__last), __value); >+ else >+#endif >+ std::__fill_a1(__first, __last, __value); >+ } > > template<typename _Ite, typename _Seq, typename _Cat, typename _Tp> > void >@@ -1306,6 +1425,9 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > const size_t __len1 = __last1 - __first1; > const size_t __len2 = __last2 - __first2; > if (const size_t __len = std::min(__len1, __len2)) >+#ifdef __has_cpp_attribute(likely) >+ [[likely]] >+#endif > if (int __result = std::__memcmp(__first1, __first2, __len)) > return __result < 0; > return __len1 < __len2; >@@ -1733,7 +1855,11 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO > if (__len) > { > const auto __c >- = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0; >+ = __builtin_memcmp(to_address(__first1), >to_address(__first2), __len) <=> 0; >+//&*__first1 is not correct and would crash program. Must use to_address() >+//since a lot of debugging iterator would not be allowed to dereference >__first2. >+//It is undefined behavior to derefernce sentinal iterators >+//For example, VC's implementation > if (__c != 0) > return __c; > } >-- >2.24.0.windows.2 >
