On 9/27/19 1:24 PM, Jonathan Wakely wrote:
On 20/09/19 07:08 +0200, François Dumont wrote:
I already realized that previous patch will be too controversial to
be accepted.
In this new version I just implement a real memmove in __memmove so
A real memmove doesn't just work backwards, it needs to detect any
overlaps and work forwards *or* backwards, as needed.
ok, good to know, I understand now why using __builtin_memcopy didn't
show any performance enhancement when I tested it !
I think your change will break this case:
#include <algorithm>
constexpr int f(int i, int j, int k)
{
int arr[5] = { 0, 0, i, j, k };
std::move(arr+2, arr+5, arr);
return arr[0] + arr[1] + arr[2];
}
static_assert( f(1, 2, 3) == 6 );
This is valid because std::move only requires that the result iterator
is not in the input range, but it's OK for the two ranges to overlap.
I haven't tested it, but I think with your change the array will end
up containing {3, 2, 3, 2, 3} instead of {1, 2, 3, 2, 3}.
Indeed, I've added a std::move constexpr test in this new proposal which
demonstrate that.
C++ Standard clearly states that [copy|move]_backward is done backward.
So in this new proposal I propose to add a __memcopy used in copy/move
and keep __memmove for *_backward algos. Both are using
__builtin_memmove as before.
* include/bits/stl_algobase.h (__memmove): Return void, loop as long as
__n != 0.
(__memcopy): New.
(__copy_move<_IsMove, true,
std::random_access_iterator_tag>::__copy_m):
Adapt to use latter.
(__copy_move_backward_a): Remove std::is_constant_evaluated block.
* testsuite/25_algorithms/copy/constexpr.cc (test): Add check on copied
values.
* testsuite/25_algorithms/copy_backward/constexpr.cc (test): Likewise
and rename in test1.
(test2): New.
* testsuite/25_algorithms/copy/constexpr_neg.cc: New.
* testsuite/25_algorithms/copy_backward/constexpr.cc: New.
* testsuite/25_algorithms/equal/constexpr_neg.cc: New.
* testsuite/25_algorithms/move/constexpr.cc: New.
* testsuite/25_algorithms/move/constexpr_neg.cc: New.
Tested under Linux x86_64.
Ok to commit ?
François
Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h (révision 276259)
+++ include/bits/stl_algobase.h (copie de travail)
@@ -78,18 +78,18 @@
_GLIBCXX_BEGIN_NAMESPACE_VERSION
/*
- * A constexpr wrapper for __builtin_memmove.
+ * A constexpr wrapper for memcopy.
* @param __num The number of elements of type _Tp (not bytes).
*/
template<bool _IsMove, typename _Tp>
_GLIBCXX14_CONSTEXPR
- inline void*
- __memmove(_Tp* __dst, const _Tp* __src, size_t __num)
+ inline void
+ __memcopy(_Tp* __dst, const _Tp* __src, ptrdiff_t __num)
{
#ifdef __cpp_lib_is_constant_evaluated
if (std::is_constant_evaluated())
{
- for(; __num > 0; --__num)
+ for (; __num != 0; --__num)
{
if constexpr (_IsMove)
*__dst = std::move(*__src);
@@ -98,15 +98,40 @@
++__src;
++__dst;
}
- return __dst;
}
else
#endif
- return __builtin_memmove(__dst, __src, sizeof(_Tp) * __num);
- return __dst;
+ __builtin_memmove(__dst, __src, sizeof(_Tp) * __num);
}
/*
+ * A constexpr wrapper for memmove.
+ * @param __num The number of elements of type _Tp (not bytes).
+ */
+ template<bool _IsMove, typename _Tp>
+ _GLIBCXX14_CONSTEXPR
+ inline void
+ __memmove(_Tp* __dst, const _Tp* __src, ptrdiff_t __num)
+ {
+#ifdef __cpp_lib_is_constant_evaluated
+ if (std::is_constant_evaluated())
+ {
+ __dst += __num;
+ __src += __num;
+ for (; __num != 0; --__num)
+ {
+ if constexpr (_IsMove)
+ *--__dst = std::move(*--__src);
+ else
+ *--__dst = *--__src;
+ }
+ }
+ else
+#endif
+ __builtin_memmove(__dst, __src, sizeof(_Tp) * __num);
+ }
+
+ /*
* A constexpr wrapper for __builtin_memcmp.
* @param __num The number of elements of type _Tp (not bytes).
*/
@@ -446,7 +471,7 @@
#endif
const ptrdiff_t _Num = __last - __first;
if (_Num)
- std::__memmove<_IsMove>(__result, __first, _Num);
+ std::__memcopy<_IsMove>(__result, __first, _Num);
return __result + _Num;
}
};
@@ -676,12 +701,6 @@
&& __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,
- _Category>::__copy_move_b(__first, __last,
- __result);
-#endif
return std::__copy_move_backward<_IsMove, __simple,
_Category>::__copy_move_b(__first,
__last,
Index: testsuite/25_algorithms/copy/constexpr.cc
===================================================================
--- testsuite/25_algorithms/copy/constexpr.cc (révision 276259)
+++ testsuite/25_algorithms/copy/constexpr.cc (copie de travail)
@@ -24,12 +24,12 @@
constexpr bool
test()
{
- constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+ constexpr std::array<int, 12> ca0{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}};
std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
const auto out6 = std::copy(ca0.begin(), ca0.begin() + 8, ma0.begin() + 2);
- return out6 == ma0.begin() + 10;
+ return out6 == ma0.begin() + 10 && *(ma0.begin() + 2) == 1 && *out6 == 0;
}
static_assert(test());
Index: testsuite/25_algorithms/copy/constexpr_neg.cc
===================================================================
--- testsuite/25_algorithms/copy/constexpr_neg.cc (nonexistent)
+++ testsuite/25_algorithms/copy/constexpr_neg.cc (copie de travail)
@@ -0,0 +1,38 @@
+// Copyright (C) 2019 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
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do compile { target c++2a xfail *-*-* } }
+
+#include <algorithm>
+#include <array>
+
+constexpr bool
+test()
+{
+ constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+ std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
+
+ const auto out6 = std::copy(ca0.begin() + 8, ca0.begin(), ma0.begin() + 2);
+
+ return out6 == ma0.begin() + 10;
+}
+
+static_assert(test()); // { dg-error "outside the bounds" }
+
+// { dg-prune-output "non-constant condition" }
+// { dg-prune-output "in 'constexpr'" }
Index: testsuite/25_algorithms/copy_backward/constexpr.cc
===================================================================
--- testsuite/25_algorithms/copy_backward/constexpr.cc (révision 276259)
+++ testsuite/25_algorithms/copy_backward/constexpr.cc (copie de travail)
@@ -22,15 +22,27 @@
#include <array>
constexpr bool
-test()
+test1()
{
- constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+ constexpr std::array<int, 12> ca0{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}};
std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
const auto out7 = std::copy_backward(ca0.begin(), ca0.begin() + 8,
ma0.begin() + 10);
- return true;
+ return out7 == ma0.begin() + 2 && *out7 == 1 && *(ma0.begin() + 10) == 0;
}
-static_assert(test());
+static_assert(test1());
+
+constexpr bool
+test2()
+{
+ std::array<int, 12> ma0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+ const auto out7 = std::copy_backward(ma0.begin(), ma0.begin() + 8,
+ ma0.begin() + 10);
+
+ return out7 == ma0.begin() + 2 && *out7 == 0 && *(ma0.begin() + 9) == 7;
+}
+
+static_assert(test2());
Index: testsuite/25_algorithms/copy_backward/constexpr_neg.cc
===================================================================
--- testsuite/25_algorithms/copy_backward/constexpr_neg.cc (nonexistent)
+++ testsuite/25_algorithms/copy_backward/constexpr_neg.cc (copie de travail)
@@ -0,0 +1,39 @@
+// Copyright (C) 2019 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
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do compile { target c++2a xfail *-*-* } }
+
+#include <algorithm>
+#include <array>
+
+constexpr bool
+test()
+{
+ constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+ std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
+
+ const auto out7 = std::copy_backward(ca0.begin() + 8, ca0.begin(),
+ ma0.begin() + 10);
+
+ return out7 == ma0.begin() + 2;
+}
+
+static_assert(test()); // { dg-error "outside the bounds" }
+
+// { dg-prune-output "non-constant condition" }
+// { dg-prune-output "in 'constexpr'" }
Index: testsuite/25_algorithms/equal/constexpr_neg.cc
===================================================================
--- testsuite/25_algorithms/equal/constexpr_neg.cc (nonexistent)
+++ testsuite/25_algorithms/equal/constexpr_neg.cc (copie de travail)
@@ -0,0 +1,49 @@
+// Copyright (C) 2019 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
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do compile { target c++2a xfail *-*-* } }
+
+#include <algorithm>
+#include <array>
+
+constexpr bool
+test01()
+{
+ constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+ constexpr std::array<int, 12> ca1{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+
+ const auto outa = std::equal(ca0.end(), ca0.begin(), ca1.begin());
+ return outa;
+}
+
+static_assert(test01()); // { dg-error "outside the bounds" }
+
+constexpr bool
+test02()
+{
+ constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+ constexpr std::array<int, 11> ca1{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}};
+
+ const auto outa = std::equal(ca0.begin(), ca0.end(), ca1.begin());
+ return outa;
+}
+
+static_assert(test02()); // { dg-error "outside the bounds" }
+
+// { dg-prune-output "non-constant condition" }
+// { dg-prune-output "in 'constexpr'" }
Index: testsuite/25_algorithms/move/constexpr.cc
===================================================================
--- testsuite/25_algorithms/move/constexpr.cc (nonexistent)
+++ testsuite/25_algorithms/move/constexpr.cc (copie de travail)
@@ -0,0 +1,47 @@
+// Copyright (C) 2019 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
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do compile { target c++2a } }
+
+#include <algorithm>
+#include <array>
+
+constexpr bool
+test1()
+{
+ constexpr std::array<int, 12> ca0{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}};
+ std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
+
+ const auto out6 = std::move(ca0.begin(), ca0.begin() + 8, ma0.begin() + 2);
+
+ return out6 == ma0.begin() + 10 && *(ma0.begin() + 2) == 1 && *out6 == 0;
+}
+
+static_assert(test1());
+
+constexpr bool
+test2()
+{
+ std::array<int, 12> ca0{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}};
+
+ const auto out6 = std::move(ca0.begin() + 2, ca0.begin() + 8, ca0.begin());
+
+ return out6 == ca0.begin() + 6 && *(ca0.begin()) == 3 && *out6 == 7;
+}
+
+static_assert(test2());
Index: testsuite/25_algorithms/move/constexpr_neg.cc
===================================================================
--- testsuite/25_algorithms/move/constexpr_neg.cc (nonexistent)
+++ testsuite/25_algorithms/move/constexpr_neg.cc (copie de travail)
@@ -0,0 +1,38 @@
+// Copyright (C) 2019 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
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do compile { target c++2a xfail *-*-* } }
+
+#include <algorithm>
+#include <array>
+
+constexpr bool
+test()
+{
+ constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+ std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
+
+ const auto out6 = std::move(ca0.begin() + 8, ca0.begin(), ma0.begin() + 2);
+
+ return out6 == ma0.begin() + 10;
+}
+
+static_assert(test()); // { dg-error "outside the bounds" }
+
+// { dg-prune-output "non-constant condition" }
+// { dg-prune-output "in 'constexpr'" }