From patchwork Tue Jan 10 11:46:56 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 41417 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp2697826wrt; Tue, 10 Jan 2023 03:48:29 -0800 (PST) X-Google-Smtp-Source: AMrXdXu3/cEryBzbPdtSEy9uMrvalcWewKMrTdCuNhhbpohvdWl2BTCTYES9Ho9xIDfp8U/ysDit X-Received: by 2002:a05:6402:25c3:b0:48e:a55a:9c4b with SMTP id x3-20020a05640225c300b0048ea55a9c4bmr25120062edb.19.1673351309714; Tue, 10 Jan 2023 03:48:29 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673351309; cv=none; d=google.com; s=arc-20160816; b=l7+trpoVgvz1KahZNiMjxPaDGCW6+Ki2fI5kObA9WqQ4HqD967r6n7Bl2EW9d5avaD RNfDgkZbeHX8h/cwkfKJSmYoaiEOG61jJ7qiAS3e91uTOy1R915DCVoUgQAgnUVHpuzj XyZzTJZMm/qxr12t6c0l72efts6acLmy+HoeNN12DCVcIWzdrlf9Rd6n44p7+gdXX5uD IDO9FW2S6ILXeEoRmX5h7o1AU8u4bK3ffLQUoQM7UcS/Rgnj9TC2urGN+bqHpYDtsqui 29acTxrv9rR6TYm0SHJNhnfe/N8hCiWUEqvobks6hlC5oU5KNzEMFTk70GCjTjrr3qnl ikVw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:message-id:date:subject:to :dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=RJeY2hhvViNgEkweno/de3KiWKd76d5ziFYHWYAG97I=; b=n5JCBYRhMKkJIaYHATgpJlnRIqloMPEH+GH3RNmuqWpYSzYqKhrvJhTjSEg2IJy/hW CyDB0Bi7ma3kXs4jZrlFojpxLtmZLsH7KGybpRZSetEThnm2o3Rq4clS+7IqYbPHIuR4 pYtzLs703i00r6WGbkwIL5l4+2DFcEKNEnoWTCMfCa/Rd1ZnRGQiNIgYAFnhYcOOTC/L PDE/dqwVvVTM7ePzG070kOlP7eGnEIpTdZ7vjDy4WxKnYFQ7dWpSpMR6IQvyz2ALOZKe YwcVgabatjVLvBVuguSgfapjSh9O0wD6swRHDgERKdo/24pJZwNIw068Z4GDnfuZfxsC juPw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=QsH1emx+; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id l16-20020a056402029000b00499c59c0ac1si1574596edv.148.2023.01.10.03.48.29 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Jan 2023 03:48:29 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=QsH1emx+; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2693338493EB for ; Tue, 10 Jan 2023 11:47:49 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2693338493EB DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1673351269; bh=RJeY2hhvViNgEkweno/de3KiWKd76d5ziFYHWYAG97I=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=QsH1emx+AKKjWyN5LJTCyEYJ4PpR6SsgzwV7nqlzmmU8bNcpV7Fa6MLaSR4574YS+ OHL4cqgmybDJRyw3JrI7hvdmos+gwEFzVQGxvUPgLIV82CDfLQztrVC+9TEq6MCjpx 3o1eUBfSzmALSDlBgr4J3iGOV5F3s9bSt7j4/IN8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 44A8A385842E for ; Tue, 10 Jan 2023 11:47:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 44A8A385842E Received: from mimecast-mx02.redhat.com (mx3-rdu2.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-231-36WM0rfTNg-sEHMugzmXdQ-1; Tue, 10 Jan 2023 06:46:59 -0500 X-MC-Unique: 36WM0rfTNg-sEHMugzmXdQ-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.rdu2.redhat.com [10.11.54.4]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id EFE261C07588; Tue, 10 Jan 2023 11:46:58 +0000 (UTC) Received: from localhost (unknown [10.33.36.192]) by smtp.corp.redhat.com (Postfix) with ESMTP id B87AD2026D68; Tue, 10 Jan 2023 11:46:58 +0000 (UTC) To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed 2/3] libstdc++: Fix some algos for 16-bit size_t [PR108221] Date: Tue, 10 Jan 2023 11:46:56 +0000 Message-Id: <20230110114657.636853-2-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.4 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP 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.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Jonathan Wakely via Gcc-patches From: Jonathan Wakely Reply-To: Jonathan Wakely Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1754636022609056789?= X-GMAIL-MSGID: =?utf-8?q?1754636022609056789?= Tested x86_64-linux. Pushed to trunk. -- >8 -- Some standard algorithms fail to compile when size_t or ptrdiff_t is narrower than int. The __lg helper function is ambiguous if ptrdiff_t is short or __int20, so replace it with a function template that works for those types as well as signed/unsigned int/long/long long. The helpers for stable_sort perform arithmetic on size values and assume the types won't change, which isn't true if the type promotes to int. libstdc++-v3/ChangeLog: PR libstdc++/108221 * include/bits/stl_algobase.h (__lg): Replace six overloads with a single function template for all integer types. * include/bits/stl_algo.h (__merge_adaptive_resize): Cast arithmetic results back to _Distance. --- libstdc++-v3/include/bits/stl_algo.h | 5 ++- libstdc++-v3/include/bits/stl_algobase.h | 47 ++++++++++++------------ 2 files changed, 26 insertions(+), 26 deletions(-) diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 6386918fc8b..eed04b3c1b8 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -2458,13 +2458,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2) _BidirectionalIterator __new_middle = std::__rotate_adaptive(__first_cut, __middle, __second_cut, - __len1 - __len11, __len22, + _Distance(__len1 - __len11), __len22, __buffer, __buffer_size); std::__merge_adaptive_resize(__first, __first_cut, __new_middle, __len11, __len22, __buffer, __buffer_size, __comp); std::__merge_adaptive_resize(__new_middle, __second_cut, __last, - __len1 - __len11, __len2 - __len22, + _Distance(__len1 - __len11), + _Distance(__len2 - __len22), __buffer, __buffer_size, __comp); } } diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index ae898ed3706..566b6d9c4bc 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -72,7 +72,10 @@ #if __cplusplus >= 201103L # include #endif -#if __cplusplus > 201703L +#if __cplusplus >= 201402L +# include // std::__bit_width +#endif +#if __cplusplus >= 202002L # include #endif @@ -1505,29 +1508,25 @@ _GLIBCXX_END_NAMESPACE_CONTAINER /// This is a helper function for the sort routines and for random.tcc. // Precondition: __n > 0. - inline _GLIBCXX_CONSTEXPR int - __lg(int __n) - { return (int)sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } - - inline _GLIBCXX_CONSTEXPR unsigned - __lg(unsigned __n) - { return (int)sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } - - inline _GLIBCXX_CONSTEXPR long - __lg(long __n) - { return (int)sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } - - inline _GLIBCXX_CONSTEXPR unsigned long - __lg(unsigned long __n) - { return (int)sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } - - inline _GLIBCXX_CONSTEXPR long long - __lg(long long __n) - { return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } - - inline _GLIBCXX_CONSTEXPR unsigned long long - __lg(unsigned long long __n) - { return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } + template + inline _GLIBCXX_CONSTEXPR _Tp + __lg(_Tp __n) + { +#if __cplusplus >= 201402L + return std::__bit_width(make_unsigned_t<_Tp>(__n)) - 1; +#else + // Use +__n so it promotes to at least int. + const int __sz = sizeof(+__n); + int __w = __sz * __CHAR_BIT__ - 1; + if (__sz == sizeof(long long)) + __w -= __builtin_clzll(+__n); + else if (__sz == sizeof(long)) + __w -= __builtin_clzl(+__n); + else if (__sz == sizeof(int)) + __w -= __builtin_clz(+__n); + return __w; +#endif + } _GLIBCXX_BEGIN_NAMESPACE_ALGO