From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id 971A93857C46 for ; Thu, 17 Dec 2020 00:18:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 971A93857C46 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 322A431B; Wed, 16 Dec 2020 16:18:02 -0800 (PST) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.126]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id A1B773F718; Wed, 16 Dec 2020 16:18:01 -0800 (PST) From: Richard Sandiford To: Martin Sebor Mail-Followup-To: Martin Sebor , gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Cc: gcc-patches@gcc.gnu.org Subject: Re: [07/23] Add a class that multiplexes two pointer types References: Date: Thu, 17 Dec 2020 00:17:59 +0000 In-Reply-To: (Martin Sebor's message of "Fri, 27 Nov 2020 17:17:12 -0700") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, KAM_SHORT, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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-List-Received-Date: Thu, 17 Dec 2020 00:18:04 -0000 Martin Sebor writes: > On 11/26/20 10:06 AM, Richard Sandiford wrote: >> Martin Sebor writes: >>> I do have one concern: the tendency to prioritize efficiency >>> over safety (this can be said about most GCC code). Specifically >>> in this class, the address bit twiddling makes me uneasy. I don't >>> think the object model in either language (certainly not C but >>> I don't have the impression C++ either) makes it unequivocally >>> valid. On the contrary, I'd say many of us interpret the current >>> rules as leaving it undefined. There are efforts to sanction >>> this sort of thing under some conditions (e.g, the C object >>> model proposal) but they have not been adopted yet. I think >>> we should try to avoid exploiting these dark corners in new >>> code. >>=20 >> I'd tried to stick to operations that I thought were well-defined. >> The primitives being used are really: >>=20 >> (1) convert a T1* or T2* to char* >> (2) increment an unincremented char* >> (3) decrement an incremented char* >> (4) convert a char* back to T1* or T2* >> (5) convert a char* to an intptr_t in order to test its low bit > > All those are valid as long as the pointer points into the same > object, both before and after. > >> I thought (1) and (4) were allowed. At least, [basic.compound] says >> that void* must be able to hold any object pointer and that it must have >> the same representation as char*, so I thought the conversion in (1) was >> guaranteed to be representable. And (4) only ever undoes (1): it only >> converts the result of (1) back to the original pointer type. >>=20 >> For (2) and (3), the incremented pointer will still be within the >> containing object, so I thought it would be well-defined. Here too, >> (3) only ever undoes (2): it only decrements a pointer that had >> previously been incremented. >>=20 >> One thing I'd deliberately tried to avoid was converting integers >> =E2=80=9Cback=E2=80=9D to pointers, because that seemed like a more dang= erous thing. >> That's why: >>=20 >>>> +template >>>> +inline T2 * >>>> +pointer_mux::second_or_null () const >>>> +{ >>>> + // Micro optimization that's effective as of GCC 11: compute the va= lue >>>> + // of the second pointer as an integer and test that, so that the i= nteger >>>> + // result can be reused as the pointer and so that all computation = can >>>> + // happen before a branch on null. This reduces the number of bran= ches >>>> + // needed for loops. >>>> + return uintptr_t (m_ptr - 1) & 1 ? nullptr : known_second (); > > This is only valid if m_ptr points to the second byte of an object. > If it points to the first byte of A then it's invalid. This would > make the test valid but the result strictly unspecified (though in > practice I'd expect it to do what you expect): > > return (uintptr_t (m_ptr) - 1) & 1 ? nullptr : known_second (); Yeah, I think that's what I meant to write (and was what I thought the code said when I quoted it, without looking properly). It does seem to preserve the optimisation. Here's what I installed after retesting. Thanks, Richard gcc/ * mux-utils.h: New file. --- gcc/mux-utils.h | 251 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 251 insertions(+) create mode 100644 gcc/mux-utils.h diff --git a/gcc/mux-utils.h b/gcc/mux-utils.h new file mode 100644 index 00000000000..b026a9fa4c1 --- /dev/null +++ b/gcc/mux-utils.h @@ -0,0 +1,251 @@ +// Multiplexer utilities +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of GCC. +// +// GCC 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. +// +// GCC 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 GCC; see the file COPYING3. If not see +// . + +#ifndef GCC_MUX_UTILS_H +#define GCC_MUX_UTILS_H 1 + +// A class that stores a choice "A or B", where A has type T1 * and B has +// type T2 *. Both T1 and T2 must have an alignment greater than 1, since +// the low bit is used to identify B over A. T1 and T2 can be the same. +// +// A can be a null pointer but B cannot. +// +// Barring the requirement that B must be nonnull, using the class is +// equivalent to using: +// +// union { T1 *A; T2 *B; }; +// +// and having a separate tag bit to indicate which alternative is active. +// However, using this class can have two advantages over a union: +// +// - It avoides the need to find somewhere to store the tag bit. +// +// - The compiler is aware that B cannot be null, which can make checks +// of the form: +// +// if (auto *B =3D mux.dyn_cast ()) +// +// more efficient. With a union-based representation, the dyn_cast +// check could fail either because MUX is an A or because MUX is a +// null B, both of which require a run-time test. With a pointer_mux, +// only a check for MUX being A is needed. +template +class pointer_mux +{ +public: + // Return an A pointer with the given value. + static pointer_mux first (T1 *); + + // Return a B pointer with the given (nonnull) value. + static pointer_mux second (T2 *); + + pointer_mux () =3D default; + + // Create a null A pointer. + pointer_mux (std::nullptr_t) : m_ptr (nullptr) {} + + // Create an A or B pointer with the given value. This is only valid + // if T1 and T2 are distinct and if T can be resolved to exactly one + // of them. + template::value + !=3D std::is_convertible::value>::type> + pointer_mux (T *ptr); + + // Return true unless the pointer is a null A pointer. + explicit operator bool () const { return m_ptr; } + + // Assign A and B pointers respectively. + void set_first (T1 *ptr) { *this =3D first (ptr); } + void set_second (T2 *ptr) { *this =3D second (ptr); } + + // Return true if the pointer is an A pointer. + bool is_first () const { return !(uintptr_t (m_ptr) & 1); } + + // Return true if the pointer is a B pointer. + bool is_second () const { return uintptr_t (m_ptr) & 1; } + + // Return the contents of the pointer, given that it is known to be + // an A pointer. + T1 *known_first () const { return reinterpret_cast (m_ptr); } + + // Return the contents of the pointer, given that it is known to be + // a B pointer. + T2 *known_second () const { return reinterpret_cast (m_ptr - 1); } + + // If the pointer is an A pointer, return its contents, otherwise + // return null. Thus a null return can mean that the pointer is + // either a null A pointer or a B pointer. + // + // If all A pointers are nonnull, it is more efficient to use: + // + // if (ptr.is_first ()) + // ...use ptr.known_first ()... + // + // over: + // + // if (T1 *a =3D ptr.first_or_null ()) + // ...use a... + T1 *first_or_null () const; + + // If the pointer is a B pointer, return its contents, otherwise + // return null. Using: + // + // if (T1 *b =3D ptr.second_or_null ()) + // ...use b... + // + // should be at least as efficient as: + // + // if (ptr.is_second ()) + // ...use ptr.known_second ()... + T2 *second_or_null () const; + + // Return true if the pointer is a T. + // + // This is only valid if T1 and T2 are distinct and if T can be + // resolved to exactly one of them. The condition is checked using + // a static assertion rather than SFINAE because it gives a clearer + // error message. + template + bool is_a () const; + + // Assert that the pointer is a T and return it as such. See is_a + // for the restrictions on T. + template + T as_a () const; + + // If the pointer is a T, return it as such, otherwise return null. + // See is_a for the restrictions on T. + template + T dyn_cast () const; + +private: + pointer_mux (char *ptr) : m_ptr (ptr) {} + + // The pointer value for A pointers, or the pointer value + 1 for B poin= ters. + // Using a pointer rather than a uintptr_t tells the compiler that secon= d () + // can never return null, and that second_or_null () is only null if + // is_first (). + char *m_ptr; +}; + +template +inline pointer_mux +pointer_mux::first (T1 *ptr) +{ + gcc_checking_assert (!(uintptr_t (ptr) & 1)); + return reinterpret_cast (ptr); +} + +template +inline pointer_mux +pointer_mux::second (T2 *ptr) +{ + gcc_checking_assert (ptr && !(uintptr_t (ptr) & 1)); + return reinterpret_cast (ptr) + 1; +} + +template +template +inline pointer_mux::pointer_mux (T *ptr) + : m_ptr (reinterpret_cast (ptr)) +{ + if (std::is_convertible::value) + { + gcc_checking_assert (m_ptr); + m_ptr +=3D 1; + } +} + +template +inline T1 * +pointer_mux::first_or_null () const +{ + return is_first () ? known_first () : nullptr; +} + +template +inline T2 * +pointer_mux::second_or_null () const +{ + // Micro optimization that's effective as of GCC 11: compute the value + // of the second pointer as an integer and test that, so that the integer + // result can be reused as the pointer and so that all computation can + // happen before a branch on null. This reduces the number of branches + // needed for loops. + return (uintptr_t (m_ptr) - 1) & 1 ? nullptr : known_second (); +} + +template +template +inline bool +pointer_mux::is_a () const +{ + static_assert (std::is_convertible::value + !=3D std::is_convertible::value, + "Ambiguous pointer type"); + if (std::is_convertible::value) + return is_second (); + else + return is_first (); +} + +template +template +inline T +pointer_mux::as_a () const +{ + static_assert (std::is_convertible::value + !=3D std::is_convertible::value, + "Ambiguous pointer type"); + if (std::is_convertible::value) + { + gcc_checking_assert (is_second ()); + return reinterpret_cast (m_ptr - 1); + } + else + { + gcc_checking_assert (is_first ()); + return reinterpret_cast (m_ptr); + } +} + +template +template +inline T +pointer_mux::dyn_cast () const +{ + static_assert (std::is_convertible::value + !=3D std::is_convertible::value, + "Ambiguous pointer type"); + if (std::is_convertible::value) + { + if (is_second ()) + return reinterpret_cast (m_ptr - 1); + } + else + { + if (is_first ()) + return reinterpret_cast (m_ptr); + } + return nullptr; +} + +#endif