From patchwork Wed May 31 20:20:19 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 70410 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id EF54B3853D33 for ; Wed, 31 May 2023 20:21:07 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org EF54B3853D33 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1685564468; bh=cjxO7MoTx7vRPnxlzlEvuu32FIyQ0596GexLdXfr9zU=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=om01Lxu1b2AQCJ9RBL26OEp2DdK+aCX1UA1HKSfWtjY65/vUHcA+AtWuyhX9bWIXJ HgLfiJFpFiKkFDh6jmvFdaHnmVCkE1WkLGf4QZ7KTg/LknrNEei+fanMH/MO5ZeVLI V7WSUmGfv1gMbGA0C4+MOxDZdAw3CLgsLzdKHUN8= 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 EF9B938582BE for ; Wed, 31 May 2023 20:20:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org EF9B938582BE Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-259-lyfPCzFjNF-UojYjMmBBWg-1; Wed, 31 May 2023 16:20:21 -0400 X-MC-Unique: lyfPCzFjNF-UojYjMmBBWg-1 Received: from smtp.corp.redhat.com (int-mx10.intmail.prod.int.rdu2.redhat.com [10.11.54.10]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id ECCF2185A78B; Wed, 31 May 2023 20:20:20 +0000 (UTC) Received: from localhost (unknown [10.42.28.9]) by smtp.corp.redhat.com (Postfix) with ESMTP id B8AD1492B0A; Wed, 31 May 2023 20:20:20 +0000 (UTC) To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed] libstdc++: Express std::vector's size() <= capacity() invariant in code Date: Wed, 31 May 2023 21:20:19 +0100 Message-Id: <20230531202019.20749-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.10 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=unavailable 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+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Tested x86_64-linux. Pushed to trunk. -- >8 -- This adds optimizer hints so that GCC knows that size() <= capacity() is always true. This allows the compiler to optimize away re-allocating paths when assigning new values to the vector without resizing it, e.g., vec.assign(vec.size(), new_val). libstdc++-v3/ChangeLog: * include/bits/stl_vector.h (_Vector_base::_M_invariant()): New function. (vector::size(), vector::capacity()): Call _M_invariant(). * testsuite/23_containers/vector/capacity/invariant.cc: New test. * testsuite/23_containers/vector/types/1.cc: Add suppression for false positive warning (PR110060). --- libstdc++-v3/include/bits/stl_vector.h | 30 +++++++++++++++++-- .../vector/capacity/invariant.cc | 16 ++++++++++ .../testsuite/23_containers/vector/types/1.cc | 2 +- 3 files changed, 44 insertions(+), 4 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/vector/capacity/invariant.cc diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index acb29396d26..e593be443bc 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -388,6 +388,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } protected: + + __attribute__((__always_inline__)) + _GLIBCXX20_CONSTEXPR void + _M_invariant() const + { +#if __OPTIMIZE__ + if (this->_M_impl._M_finish < this->_M_impl._M_start) + __builtin_unreachable(); + if (this->_M_impl._M_finish > this->_M_impl._M_end_of_storage) + __builtin_unreachable(); + + size_t __sz = this->_M_impl._M_finish - this->_M_impl._M_start; + size_t __cap = this->_M_impl._M_end_of_storage - this->_M_impl._M_start; + if (__sz > __cap) + __builtin_unreachable(); +#endif + } + _GLIBCXX20_CONSTEXPR void _M_create_storage(size_t __n) @@ -987,7 +1005,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR size_type size() const _GLIBCXX_NOEXCEPT - { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } + { + _Base::_M_invariant(); + return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); + } /** Returns the size() of the largest possible %vector. */ _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR @@ -1073,8 +1094,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR size_type capacity() const _GLIBCXX_NOEXCEPT - { return size_type(this->_M_impl._M_end_of_storage - - this->_M_impl._M_start); } + { + _Base::_M_invariant(); + return size_type(this->_M_impl._M_end_of_storage + - this->_M_impl._M_start); + } /** * Returns true if the %vector is empty. (Thus begin() would diff --git a/libstdc++-v3/testsuite/23_containers/vector/capacity/invariant.cc b/libstdc++-v3/testsuite/23_containers/vector/capacity/invariant.cc new file mode 100644 index 00000000000..d68db694add --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/capacity/invariant.cc @@ -0,0 +1,16 @@ +// { dg-do compile } +// { dg-options "-O3 -g0" } +// { dg-final { scan-assembler-not "_Znw" } } +// GCC should be able to optimize away the paths involving reallocation. + +#include + +void fill(std::vector& vec) +{ + vec.assign(vec.size(), 0); +} + +void fill_val(std::vector& vec, int i) +{ + vec.assign(vec.size(), i); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/types/1.cc b/libstdc++-v3/testsuite/23_containers/vector/types/1.cc index 079e5af9556..9be07d9fd5c 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/types/1.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/types/1.cc @@ -18,7 +18,7 @@ // . // { dg-do compile } -// { dg-options "-Wno-unused-result" } +// { dg-options "-Wno-unused-result -Wno-stringop-overread" } #include #include