From patchwork Fri Aug 30 10:52:27 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuseppe D'Angelo X-Patchwork-Id: 1978904 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=kdab.com header.i=@kdab.com header.a=rsa-sha256 header.s=dkim header.b=Ia5zWzD7; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4WwFNt1gNCz1ydy for ; Fri, 30 Aug 2024 20:53:02 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 29221385DDFA for ; Fri, 30 Aug 2024 10:53:00 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail.kdab.com (mail.kdab.com [176.9.126.58]) by sourceware.org (Postfix) with ESMTPS id 8B3DA3858C50; Fri, 30 Aug 2024 10:52:29 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8B3DA3858C50 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=kdab.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=kdab.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 8B3DA3858C50 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=176.9.126.58 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1725015153; cv=none; b=pAgP8Oa94iFjOu4LCgDyljzE9wuoD+Rvf5LLMTcnI+5CNTQCBe4FqUkfNMCj82buVAmikfjwDJQPzm6UuEZt5XOh8GkALyr1dnGWdYFp2n3VSIZJw4GJykBPtb8lPlkOcpi8teI0GKSeJZv7nDuqZjJZzoUuDhYath/VKYIKKIA= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1725015153; c=relaxed/simple; bh=EFH0crvwFFLSQvAz/HIT3qTVLSemYXKk8GMC5XSWHwE=; h=DKIM-Signature:Message-ID:Date:MIME-Version:To:From:Subject; b=W0iG225LXDrxGRzHeEiv+7QVWBiNjFxfm8WniFcUYkJR9eyXQw3F+LHvNZqAmdkWBQdBXA7cPMmCfxiJLH6o22KlLTR4cX+XlcdkamCokX4Cy6mmDwZmDcUxaQ1lqHLRUHOgOuwNffRX8N3q9s+2EjSMACwPuCqWzJek9lnq4sI= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kdab.com; h= content-type:content-type:organization:subject:subject:from:from :content-language:mime-version:date:date:message-id; s=dkim; t= 1725015148; x=1725879149; bh=EFH0crvwFFLSQvAz/HIT3qTVLSemYXKk8GM C5XSWHwE=; b=Ia5zWzD7KNwMvIc3nJ7BKJM301kNiv8TaM57MXZmTIoeyiQE7Vx fpoaFJj1kT3lb+dhYCqEDuzB3GRuZS8UuHtZqbmEvay4l3AR0dwI8td3wvd4tCY/ xus9sfjn+EpLaj1ojo9vDy8j0cKBZUGfSPmNA+/p1HtO4ohCO7u2oyU0= X-Virus-Scanned: amavisd-new at kdab.com Message-ID: <6a76ea27-65b5-4fdd-b55e-b7981a7fad1e@kdab.com> Date: Fri, 30 Aug 2024 12:52:27 +0200 MIME-Version: 1.0 To: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org Content-Language: en-GB From: Giuseppe D'Angelo Subject: [PATCH] libstdc++: Do not use use memmove for 1-element ranges [PR108846, PR116471] Organization: KDAB (France) S.A.S., a KDAB Group company X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE, URI_HEX autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org Hello, This patch completes the fix for PR108846, extending it to range-based copy/move algorithms, and also fixes a faulty static_assert in them (PR116471). It's a minor improvement over the patch I've attached to PR116471 (I've fixed the constraints of __assign_one). Thank you, From 1b75da8e2514e01a7b54117c63facbf0f3b49a88 Mon Sep 17 00:00:00 2001 From: Giuseppe D'Angelo Date: Fri, 23 Aug 2024 15:05:54 +0200 Subject: [PATCH] libstdc++: Do not use use memmove for 1-element ranges [PR108846,PR116471] This commit ports the fixes already applied by 822a11a1e642e0abe92a996e7033a5066905a447 to the range-based versions of copy/move algorithms. When doing so, a further bug (PR116471) was discovered in the implementation of the range-based algorithms: although the algorithms are already constrained by the indirectly_copyable/movable concepts, there was a failing static_assert in the memmove path. This static_assert checked that iterator's value type was assignable by using the is_copy_assignable (move) type traits. However, this is a problem, because the traits are too strict when checking for constness; a type like struct S { S& operator=(S &) = default; }; is trivially copyable (and thus could benefit of the memmove path), but it does not satisfy is_copy_assignable because the operator takes by non-const reference. Now, the reason for the check to be there is because a type with a deleted assignment operator like struct E { E& operator=(const E&) = delete; }; is still trivially copyable, but not assignable. We don't want algorithms like std::ranges::copy to compile because they end up selecting the memmove path, "ignoring" the fact that E isn't even copy assignable. But the static_assert isn't needed here any longer: as noted before, the ranges algorithms already have the appropriate constraints; and even if they didn't, there's now a non-discaded codepath to deal with ranges of length 1 where there is an explicit assignment operation. Therefore, this commit removes it. (In fact, 822a11a1e642e0abe92a996e7033a5066905a447 removed the same static_assert from the non-ranges algorithms.) libstdc++-v3/ChangeLog: PR libstdc++/108846 PR libstdc++/116471 * include/bits/ranges_algobase.h: Add __assign_one helper function. (__copy_or_move): Remove a spurious static_assert; use __assign_one for memcpyable ranges of length 1. (__copy_or_move_backward): Likewise. * testsuite/25_algorithms/copy/108846.cc: Extend to range-based algorithms, and cover both memcpyable and non-memcpyable cases. * testsuite/25_algorithms/copy_backward/108846.cc: Likewise. * testsuite/25_algorithms/copy_n/108846.cc: Likewise. * testsuite/25_algorithms/move/108846.cc: Likewise. * testsuite/25_algorithms/move_backward/108846.cc: Likewise. Signed-off-by: Giuseppe D'Angelo --- libstdc++-v3/include/bits/ranges_algobase.h | 46 +++++++++---------- .../testsuite/25_algorithms/copy/108846.cc | 36 +++++++++++++++ .../25_algorithms/copy_backward/108846.cc | 36 +++++++++++++++ .../testsuite/25_algorithms/copy_n/108846.cc | 38 ++++++++++++++- .../testsuite/25_algorithms/move/108846.cc | 40 +++++++++++++++- .../25_algorithms/move_backward/108846.cc | 38 ++++++++++++++- 6 files changed, 206 insertions(+), 28 deletions(-) diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h index 39cf06bdd3e..2ab1d10b0af 100644 --- a/libstdc++-v3/include/bits/ranges_algobase.h +++ b/libstdc++-v3/include/bits/ranges_algobase.h @@ -225,6 +225,18 @@ namespace ranges copy_backward_result<_Iter, _Out>> __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result); + template + requires (_IsMove + ? indirectly_movable<_Iter, _Out> + : indirectly_copyable<_Iter, _Out>) + constexpr void __assign_one(_Iter& __iter, _Out& __result) + { + if constexpr (_IsMove) + *__result = std::move(*__iter); + else + *__result = *__iter; + } + template _Sent, weakly_incrementable _Out> @@ -279,23 +291,19 @@ namespace ranges if constexpr (__memcpyable<_Iter, _Out>::__value) { using _ValueTypeI = iter_value_t<_Iter>; - static_assert(_IsMove - ? is_move_assignable_v<_ValueTypeI> - : is_copy_assignable_v<_ValueTypeI>); auto __num = __last - __first; - if (__num) + if (__builtin_expect(__num > 1, true)) __builtin_memmove(__result, __first, sizeof(_ValueTypeI) * __num); + else if (__num == 1) + __assign_one<_IsMove>(__first, __result); return {__first + __num, __result + __num}; } } for (auto __n = __last - __first; __n > 0; --__n) { - if constexpr (_IsMove) - *__result = std::move(*__first); - else - *__result = *__first; + __assign_one<_IsMove>(__first, __result); ++__first; ++__result; } @@ -305,10 +313,7 @@ namespace ranges { while (__first != __last) { - if constexpr (_IsMove) - *__result = std::move(*__first); - else - *__result = *__first; + __assign_one<_IsMove>(__first, __result); ++__first; ++__result; } @@ -414,13 +419,12 @@ namespace ranges if constexpr (__memcpyable<_Out, _Iter>::__value) { using _ValueTypeI = iter_value_t<_Iter>; - static_assert(_IsMove - ? is_move_assignable_v<_ValueTypeI> - : is_copy_assignable_v<_ValueTypeI>); auto __num = __last - __first; - if (__num) + if (__builtin_expect(__num > 1, true)) __builtin_memmove(__result - __num, __first, sizeof(_ValueTypeI) * __num); + else if (__num == 1) + __assign_one<_IsMove>(__first, __result); return {__first + __num, __result - __num}; } } @@ -432,10 +436,7 @@ namespace ranges { --__tail; --__result; - if constexpr (_IsMove) - *__result = std::move(*__tail); - else - *__result = *__tail; + __assign_one<_IsMove>(__tail, __result); } return {std::move(__lasti), std::move(__result)}; } @@ -448,10 +449,7 @@ namespace ranges { --__tail; --__result; - if constexpr (_IsMove) - *__result = std::move(*__tail); - else - *__result = *__tail; + __assign_one<_IsMove>(__tail, __result); } return {std::move(__lasti), std::move(__result)}; } diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc b/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc index 964028901b8..e8dd16d47ba 100644 --- a/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc +++ b/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc @@ -26,6 +26,10 @@ test_pr108846() // If this is optimized to memmove it will overwrite tail padding. std::copy(src, src+1, dst); VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::copy(src, src+1, dst); + VERIFY(ddst.x == 3); +#endif } struct B2 { @@ -49,10 +53,42 @@ test_non_const_copy_assign() // Ensure the not-taken trivial copy path works for this type. std::copy(src, src+1, dst); VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::copy(src, src+1, dst); + VERIFY(ddst.x == 3); +#endif +} + +struct B3 { + B3(int i, short j) : i(i), j(j) {} + B3& operator=(B3& b) = default; + int i; + short j; +}; +struct D3 : B3 { + D3(int i, short j, short x) : B3(i, j), x(x) {} + short x; // Stored in tail padding of B3 +}; + +void +test_non_const_copy_assign_trivial() +{ + D3 ddst(1, 2, 3); + D3 dsrc(4, 5, 6); + B3 *dst = &ddst; + B3 *src = &dsrc; + // If this is optimized to memmove it will overwrite tail padding. + std::copy(src, src+1, dst); + VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::copy(src, src+1, dst); + VERIFY(ddst.x == 3); +#endif } int main() { test_pr108846(); test_non_const_copy_assign(); + test_non_const_copy_assign_trivial(); } diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc index 84b3d5a285b..4942f913f11 100644 --- a/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc +++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc @@ -26,6 +26,10 @@ test_pr108846() // If this is optimized to memmove it will overwrite tail padding. std::copy_backward(src, src+1, dst+1); VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::copy_backward(src, src+1, dst+1); + VERIFY(ddst.x == 3); +#endif } struct B2 { @@ -49,10 +53,42 @@ test_non_const_copy_assign() // Ensure the not-taken trivial copy path works for this type. std::copy_backward(src, src+1, dst+1); VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::copy_backward(src, src+1, dst+1); + VERIFY(ddst.x == 3); +#endif +} + +struct B3 { + B3(int i, short j) : i(i), j(j) {} + B3& operator=(B3& b) = default; + int i; + short j; +}; +struct D3 : B3 { + D3(int i, short j, short x) : B3(i, j), x(x) {} + short x; // Stored in tail padding of B3 +}; + +void +test_non_const_copy_assign_trivial() +{ + D3 ddst(1, 2, 3); + D3 dsrc(4, 5, 6); + B3 *dst = &ddst; + B3 *src = &dsrc; + // If this is optimized to memmove it will overwrite tail padding. + std::copy_backward(src, src+1, dst+1); + VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::copy_backward(src, src+1, dst+1); + VERIFY(ddst.x == 3); +#endif } int main() { test_pr108846(); test_non_const_copy_assign(); + test_non_const_copy_assign_trivial(); } diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc b/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc index 9ed43e154b7..50deb5dd051 100644 --- a/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc +++ b/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc @@ -26,11 +26,15 @@ test_pr108846() // If this is optimized to memmove it will overwrite tail padding. std::copy_n(src, 1, dst); VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::copy_n(src, 1, dst); + VERIFY(ddst.x == 3); +#endif } struct B2 { B2(int i, short j) : i(i), j(j) {} - B2& operator=(B2&) = default; + B2& operator=(B2& b) { i = b.i; j = b.j; return *this; } int i; short j; }; @@ -49,10 +53,42 @@ test_non_const_copy_assign() // Ensure the not-taken trivial copy path works for this type. std::copy_n(src, 1, dst); VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::copy_n(src, 1, dst); + VERIFY(ddst.x == 3); +#endif +} + +struct B3 { + B3(int i, short j) : i(i), j(j) {} + B3& operator=(B3& b) = default; + int i; + short j; +}; +struct D3 : B3 { + D3(int i, short j, short x) : B3(i, j), x(x) {} + short x; // Stored in tail padding of B3 +}; + +void +test_non_const_copy_assign_trivial() +{ + D3 ddst(1, 2, 3); + D3 dsrc(4, 5, 6); + B3 *dst = &ddst; + B3 *src = &dsrc; + // If this is optimized to memmove it will overwrite tail padding. + std::copy_n(src, 1, dst); + VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::copy_n(src, 1, dst); + VERIFY(ddst.x == 3); +#endif } int main() { test_pr108846(); test_non_const_copy_assign(); + test_non_const_copy_assign_trivial(); } diff --git a/libstdc++-v3/testsuite/25_algorithms/move/108846.cc b/libstdc++-v3/testsuite/25_algorithms/move/108846.cc index 8248b87d5e2..2dd52a44290 100644 --- a/libstdc++-v3/testsuite/25_algorithms/move/108846.cc +++ b/libstdc++-v3/testsuite/25_algorithms/move/108846.cc @@ -26,6 +26,37 @@ test_pr108846() // If this is optimized to memmove it will overwrite tail padding. std::move(src, src+1, dst); VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::move(src, src+1, dst); + VERIFY(ddst.x == 3); +#endif +} + +struct B2 { + B2(int i, short j) : i(i), j(j) {} + B2& operator=(B2&& b) { i = b.i; j = b.j; return *this; } + int i; + short j; +}; +struct D2 : B2 { + D2(int i, short j, short x) : B2(i, j), x(x) {} + short x; // Stored in tail padding of B2 +}; + +void +test_move_only() +{ + D2 ddst(1, 2, 3); + D2 dsrc(4, 5, 6); + B2 *dst = &ddst; + B2 *src = &dsrc; + // Ensure the not-taken trivial copy path works for this type. + std::move(src, src+1, dst); + VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::move(src, src+1, dst); + VERIFY(ddst.x == 3); +#endif } struct B3 { @@ -40,19 +71,24 @@ struct D3 : B3 { }; void -test_move_only() +test_move_only_trivial() { D3 ddst(1, 2, 3); D3 dsrc(4, 5, 6); B3 *dst = &ddst; B3 *src = &dsrc; - // Ensure the not-taken trivial copy path works for this type. + // If this is optimized to memmove it will overwrite tail padding. std::move(src, src+1, dst); VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::move(src, src+1, dst); + VERIFY(ddst.x == 3); +#endif } int main() { test_pr108846(); test_move_only(); + test_move_only_trivial(); } diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc index 035743560e0..92ac0f5bae5 100644 --- a/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc +++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc @@ -26,6 +26,37 @@ test_pr108846() // If this is optimized to memmove it will overwrite tail padding. std::move_backward(src, src+1, dst+1); VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::move_backward(src, src+1, dst+1); + VERIFY(ddst.x == 3); +#endif +} + +struct B2 { + B2(int i, short j) : i(i), j(j) {} + B2& operator=(B2&& b) { i = b.i; j = b.j; return *this; } + int i; + short j; +}; +struct D2 : B2 { + D2(int i, short j, short x) : B2(i, j), x(x) {} + short x; // Stored in tail padding of B2 +}; + +void +test_move_only() +{ + D2 ddst(1, 2, 3); + D2 dsrc(4, 5, 6); + B2 *dst = &ddst; + B2 *src = &dsrc; + // Ensure the not-taken trivial copy path works for this type. + std::move_backward(src, src+1, dst+1); + VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::move_backward(src, src+1, dst+1); + VERIFY(ddst.x == 3); +#endif } struct B3 { @@ -40,7 +71,7 @@ struct D3 : B3 { }; void -test_move_only() +test_move_only_trivial() { D3 ddst(1, 2, 3); D3 dsrc(4, 5, 6); @@ -49,10 +80,15 @@ test_move_only() // Ensure the not-taken trivial copy path works for this type. std::move_backward(src, src+1, dst+1); VERIFY(ddst.x == 3); +#if __cpp_lib_ranges >= 201911L + std::ranges::move_backward(src, src+1, dst+1); + VERIFY(ddst.x == 3); +#endif } int main() { test_pr108846(); test_move_only(); + test_move_only_trivial(); } -- 2.34.1