From patchwork Thu Nov 9 01:17:05 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 163208 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b129:0:b0:403:3b70:6f57 with SMTP id q9csp182862vqs; Wed, 8 Nov 2023 18:52:59 -0800 (PST) X-Google-Smtp-Source: AGHT+IHxbPoyL5rRopwdiKprIHx9JUrncpCZFeAUlORh7kvC/SkgbTDeBDMVLISsUsuX+Y3EB3J6 X-Received: by 2002:a05:620a:4245:b0:778:929b:ffcc with SMTP id w5-20020a05620a424500b00778929bffccmr4249488qko.4.1699498379112; Wed, 08 Nov 2023 18:52:59 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1699498379; cv=pass; d=google.com; s=arc-20160816; b=vwXqY72oev3jEASoUAOmTtNS7sbxZ+tzEbzU8uPXrwV0yx9bJ+8eM6HwslXVafC3pf +TkeUhWfdZoFpAHIGj/0baNAqoS8skH/WiD0lLY7JJawF4H1qiuM+q+INZfj4/8FqSWa HFPMKcwFfuD0sMwkvoMe+BXTSnKAoqzUOrJk/pvGDKN/wxcaaFfBgR5pNWU1EEm3par0 WFqVOvrJrMvjzxG8k7pNJCYnDjwvMY+jPAA9LFCUZon1sa4cvNshldeQppdjKk7XROpN xEFzRU5jGy+SM4HtxiV+mL55EP9xWZ5/Cm7hThJJ0hARjkm5cP6IWVjBt1Htr0LYARVg vhFQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:mime-version:user-agent :message-id:in-reply-to:date:references:organization:subject:cc:to :from:dkim-signature:arc-filter:dmarc-filter:delivered-to; bh=PcS1/6CyHEua7G7WgyeRNp0NZ+alAJQ4KEKUhDldjwE=; fh=oMusxtJMgvkRct//zLEZNQY8BTwMO7AEo6P/m9ICreE=; b=fKiL7xXjwpxe43Iv9KVZwXr5nVOnaU9lb3KlXLU0+Ev+9XwVNW31oNQ3fSD+6gKozQ 9uyU9yD0sQgAxB70B2akrOmhJjLI9Lo2Sy9CUu3ercs99zbD59XOqDeL6ca7CqCRULNk SJRYhNUw5wpSgR/BozIIx+yWGVK+zeW/2zylkxh1Tdiv+sECuL3fywG5qV0e4Uuv/sD2 b9kIF0lXvH0tC46Rm7NiAfsXldEGxtgjmaKFtDOvfHD/YrwMxtCtEsyswr/5f8C4uSW+ NqeaD0Ntpp7BJh5rnDquIu/M8VN8LlrpDtUAFujKmTrUZfxJ/vG22rbO21xrPvPZy+Wm wKHg== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@adacore.com header.s=google header.b=C67Ry+yh; arc=pass (i=1); 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=adacore.com Received: from server2.sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id w7-20020a05620a424700b00767f3ee54a3si2283083qko.80.2023.11.08.18.52.59 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 08 Nov 2023 18:52:59 -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=@adacore.com header.s=google header.b=C67Ry+yh; arc=pass (i=1); 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=adacore.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2FC9A385DC18 for ; Thu, 9 Nov 2023 01:17:55 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-qt1-x82c.google.com (mail-qt1-x82c.google.com [IPv6:2607:f8b0:4864:20::82c]) by sourceware.org (Postfix) with ESMTPS id D02023858D38 for ; Thu, 9 Nov 2023 01:17:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D02023858D38 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=adacore.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org D02023858D38 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::82c ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699492650; cv=none; b=act55nJtSvwmb/q8i//UtUptTXXPvufhMUe+nIfnT0uI8Zk47QV0B7xpC2wpFgsSshfH1LM9lQlKjNl61Yd6qw85f9cSs+8FQ8G1CeECW6J8cUHWEF4+QVod7U9UK8mGcL3BnBo7fjth+wR8Hyqk5zVhJvo8Jn95pXBQy3MnR2w= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699492650; c=relaxed/simple; bh=MSPw5nyhyogsX4icqsv7Wen3wgoyWGM18P/wIA6GXBk=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=qopQaJF2nYgJw35EBwwAkdAmjtYm67CRSc+kthE4UOFHjkdjyZsMXU2QAEGW2fQDh0sYe/OS9W/4Yu8J47Wnxjechh0QIbhF1GUf7FbdtPqveYRarvmsjxrAzBIvFmJgSO+XRm4PEQZZimrb0i7e2Hq60MoQzmYhwB3OLWCgxeU= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-qt1-x82c.google.com with SMTP id d75a77b69052e-41cbd2cf3bbso12389491cf.0 for ; Wed, 08 Nov 2023 17:17:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore.com; s=google; t=1699492647; x=1700097447; darn=gcc.gnu.org; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:from:to:cc:subject:date:message-id :reply-to; bh=PcS1/6CyHEua7G7WgyeRNp0NZ+alAJQ4KEKUhDldjwE=; b=C67Ry+yh3wxqX/tB50x74rJiOfGhkeM/ADhSbfL/F0NyhnKXjJXMJnTuYkTDhBcc++ EjhWLF0ze62toQbPV7bwIq1RwMWtl/7OZwanjFSlSagatCd/6H5EqCEaDKbRVhcrovPC D/i1wSieBIKhy2QM/xG22xYPR+2hr6t93Cff7rClH4jNvmRakoTmxzxvWbAqUsb/iEEl APe3I3jj1Bp5Y7u513tqfGAi5ITCg/kgOGkBjUGLhehct4dPvOo2tZUKuhGLY76X82j+ HTvyDHmcWP3FaLLQgjcR74rPL4MEGw1A7lyxF0WXp56zaZ/HieCU+Q+A7fgqIfL1lZxs UiUw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699492647; x=1700097447; h=mime-version:user-agent:message-id:in-reply-to:date:references :organization:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=PcS1/6CyHEua7G7WgyeRNp0NZ+alAJQ4KEKUhDldjwE=; b=qjy10ZcqyVR25SqzdJeL7BxIKIqOF8+/Tslh58UJor97ANEPl2rIPe37AVEQeLi4Yz E4qzjMUs9KFIS+s6SlrFHqcDh7aTHxxOQssqZsRvOTpa852gpieQ15vZ2yir/IXONjpM MisBELR5w6EeZlFpbugWxRoeCSNk5V1jf/RFUvpWzkw/68XMdk+nZL9j57bRnPstHcIE DuFUPbeTYXIl3GplZfM1vhWSGf9GElwzVVXRrL4qbN1FY8Q1Kn1Pasi1O9j74QBtTTtz +T1X5cFYyVqlArGf9kvqe+Bj421/uQihJvNEPnJFujmtJGGNILhaSKVP8dsEtaobbmjo bYUg== X-Gm-Message-State: AOJu0YyXyPzMrcgbtFXyQo0CiAwPXU4Jlo8yruh7Eh8gOivqvmryYc8e t0QVa6aip4dqU6mPIDtN+WxLiQ== X-Received: by 2002:a0c:d84c:0:b0:66c:fa89:a894 with SMTP id i12-20020a0cd84c000000b0066cfa89a894mr10609310qvj.10.1699492647067; Wed, 08 Nov 2023 17:17:27 -0800 (PST) Received: from free.home ([2804:7f1:2080:e9c8:ff5e:88e8:a900:d7b4]) by smtp.gmail.com with ESMTPSA id o22-20020a05620a2a1600b0076f21383b6csm1592760qkp.112.2023.11.08.17.17.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 08 Nov 2023 17:17:26 -0800 (PST) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 3A91H5EF2230303 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 8 Nov 2023 22:17:06 -0300 From: Alexandre Oliva To: Jonathan Wakely Cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org Subject: [PATCH v2] libstdc++: optimize bit iterators assuming normalization [PR110807] Organization: Free thinker, does not speak for AdaCore References: Date: Wed, 08 Nov 2023 22:17:05 -0300 In-Reply-To: (Jonathan Wakely's message of "Wed, 8 Nov 2023 19:32:41 +0000") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-13.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE, URI_HEX, WEIRD_QUOTING 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+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1782017847773618534 X-GMAIL-MSGID: 1782053212188057507 On Nov 8, 2023, Jonathan Wakely wrote: > A single underscore prefix on __GLIBCXX_BUILTIN_ASSUME and > __GLIBCXX_DISABLE_ASSUMPTIONS please. That's entirely gone now. >> + do \ >> + if (std::is_constant_evaluated ()) \ >> + static_assert(expr); \ > This can never be valid. *nod* > This already works fine in constant evaluation anyway. Yeah, that's what I figured. > But what's the null dereference for? The idea was to clearly trigger undefined behavior. Maybe it wasn't needed, it didn't occur to me that __builtin_unreachable() would be enough. I realize I was really trying to emulate attribute assume, even without knowing it existed ;-) >> +#define __GLIBCXX_BUILTIN_ASSUME(expr) \ >> + (void)(false && (expr)) > What's the point of this, just to verify that (expr) is contextually > convertible to bool? I'd have phrased it as "avoid the case in which something compiles with -O0 but not with -O", but yeah ;-) > We don't use the _p suffix for predicates in the library. > Please use just _M_normalized or _M_is_normalized. ACK. It's also gone now. > But do we even need this function? It's not used anywhere else, can we > just inline the condition into _M_assume_normalized() ? I had other uses for it in earlier versions of the patch, but it makes no sense any more indeed. >> + _GLIBCXX20_CONSTEXPR >> + void >> + _M_assume_normalized() const > I think this should use _GLIBCXX_ALWAYS_INLINE *nod*, thanks >> + { >> + __GLIBCXX_BUILTIN_ASSUME (_M_normalized_p ()); > Is there even any benefit to this macro? I just thought it could have other uses, without being aware that the entire concept was available as a statement attribute. Funny, I'd even searched for it among the existing attributes and builtins, but somehow I managed to miss it. Thanks for getting me back down that path. > __attribute__((__assume__(_M_offset < unsigned(_S_word_bit)))); That unfortunately doesn't work, because the assume lowering doesn't go as far as dereferencing the implicit this and making an SSA_NAME out of the loaded _M_offset, which we'd need to be able to optimize based on it. But that only took me a while to figure out and massage into something that had the desired effect. Now, maybe the above *should* have that effect already, but unfortunately it doesn't. > Maybe even get rid of _M_assume_normalized() as a function and just > put that attribute everywhere you currently use _M_assume_normalized. Because of the slight kludge required to make the attribute have the desired effect (namely ensuring the _M_offset reference is evaluated), I've retained it as an inline function. Here's what I'm retesting now. WDYT? libstdc++: optimize bit iterators assuming normalization [PR110807] The representation of bit iterators, using a pointer into an array of words, and an unsigned bit offset into that word, makes for some optimization challenges: because the compiler doesn't know that the offset is always in a certain narrow range, beginning at zero and ending before the word bitwidth, when a function loads an offset that it hasn't normalized itself, it may fail to derive certain reasonable conclusions, even to the point of retaining useless calls that elicit incorrect warnings. Case at hand: The 110807.cc testcase for bit vectors assigns a 1-bit list to a global bit vector variable. Based on the compile-time constant length of the list, we decide in _M_insert_range whether to use the existing storage or to allocate new storage for the vector. After allocation, we decide in _M_copy_aligned how to copy any preexisting portions of the vector to the newly-allocated storage. When copying two or more words, we use __builtin_memmove. However, because we compute the available room using bit offsets without range information, even comparing them with constants, we fail to infer ranges for the preexisting vector depending on word size, and may thus retain the memmove call despite knowing we've only allocated one word. Other parts of the compiler then detect the mismatch between the constant allocation size and the much larger range that could theoretically be copied into the newly-allocated storage if we could reach the call. Ensuring the compiler is aware of the constraints on the offset range enables it to do a much better job at optimizing. Using attribute assume (_M_offset <= ...) didn't work, because gimple lowered that to something that vrp could only use to ensure 'this' was non-NULL. Exposing _M_offset as an automatic variable/gimple register outside the unevaluated assume operand enabled the optimizer to do its job. Rather than placing such load-then-assume constructs all over, I introduced an always-inline member function in bit iterators that does the job of conveying to the compiler the information that the assumption is supposed to hold, and various calls throughout functions pertaining to bit iterators that might not otherwise know that the offsets have to be in range, so that the compiler no longer needs to make conservative assumptions that prevent optimizations. With the explicit assumptions, the compiler can correlate the test for available storage in the vector with the test for how much storage might need to be copied, and determine that, if we're not asking for enough room for two or more words, we can omit entirely the code to copy two or more words, without any runtime overhead whatsoever: no traces remain of the undefined behavior or of the tests that inform the compiler about the assumptions that must hold. for libstdc++-v3/ChangeLog PR libstdc++/110807 * include/bits/stl_bvector.h (_Bit_iterator_base): Add _M_assume_normalized member function. Call it in _M_bump_up, _M_bump_down, _M_incr, operator==, operator<=>, operator<, and operator-. (_Bit_iterator): Also call it in operator*. (_Bit_const_iterator): Likewise. --- libstdc++-v3/include/bits/stl_bvector.h | 37 ++++++++++++++++++++++++++++--- 1 file changed, 34 insertions(+), 3 deletions(-) diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 8d18bcaffd434..bb9f38cdf2d59 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -56,6 +56,10 @@ #ifndef _STL_BVECTOR_H #define _STL_BVECTOR_H 1 +#ifndef _GLIBCXX_ALWAYS_INLINE +#define _GLIBCXX_ALWAYS_INLINE inline __attribute__((__always_inline__)) +#endif + #if __cplusplus >= 201103L #include #include @@ -177,6 +181,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_type * _M_p; unsigned int _M_offset; + _GLIBCXX20_CONSTEXPR _GLIBCXX_ALWAYS_INLINE + void + _M_assume_normalized() const + { + unsigned int ofst = _M_offset; + __attribute__ ((__assume__ (ofst < unsigned(_S_word_bit)))); + } + _GLIBCXX20_CONSTEXPR _Bit_iterator_base(_Bit_type * __x, unsigned int __y) : _M_p(__x), _M_offset(__y) { } @@ -185,6 +197,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void _M_bump_up() { + _M_assume_normalized(); if (_M_offset++ == int(_S_word_bit) - 1) { _M_offset = 0; @@ -196,6 +209,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void _M_bump_down() { + _M_assume_normalized(); if (_M_offset-- == 0) { _M_offset = int(_S_word_bit) - 1; @@ -207,6 +221,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void _M_incr(ptrdiff_t __i) { + _M_assume_normalized(); difference_type __n = __i + _M_offset; _M_p += __n / int(_S_word_bit); __n = __n % int(_S_word_bit); @@ -221,7 +236,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _GLIBCXX_NODISCARD friend _GLIBCXX20_CONSTEXPR bool operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) - { return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset; } + { + __x._M_assume_normalized(); + __y._M_assume_normalized(); + return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset; + } #if __cpp_lib_three_way_comparison [[nodiscard]] @@ -229,6 +248,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER operator<=>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) noexcept { + __x._M_assume_normalized(); + __y._M_assume_normalized(); if (const auto __cmp = __x._M_p <=> __y._M_p; __cmp != 0) return __cmp; return __x._M_offset <=> __y._M_offset; @@ -238,6 +259,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER friend bool operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { + __x._M_assume_normalized(); + __y._M_assume_normalized(); return __x._M_p < __y._M_p || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset); } @@ -266,6 +289,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER friend _GLIBCXX20_CONSTEXPR ptrdiff_t operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { + __x._M_assume_normalized(); + __y._M_assume_normalized(); return (int(_S_word_bit) * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset); } @@ -297,7 +322,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR reference operator*() const - { return reference(_M_p, 1UL << _M_offset); } + { + _M_assume_normalized(); + return reference(_M_p, 1UL << _M_offset); + } _GLIBCXX20_CONSTEXPR iterator& @@ -408,7 +436,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR const_reference operator*() const - { return _Bit_reference(_M_p, 1UL << _M_offset); } + { + _M_assume_normalized(); + return _Bit_reference(_M_p, 1UL << _M_offset); + } _GLIBCXX20_CONSTEXPR const_iterator&