llvm/ADT/PointerSumType.h

0001 //===- llvm/ADT/PointerSumType.h --------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_ADT_POINTERSUMTYPE_H
0010 #define LLVM_ADT_POINTERSUMTYPE_H
0011
0012 #include "llvm/ADT/bit.h"
0013 #include "llvm/ADT/DenseMapInfo.h"
0014 #include "llvm/Support/PointerLikeTypeTraits.h"
0015 #include <cassert>
0016 #include <cstdint>
0017 #include <type_traits>
0018
0019 namespace llvm {
0020
0021 /// A compile time pair of an integer tag and the pointer-like type which it
0022 /// indexes within a sum type. Also allows the user to specify a particular
0023 /// traits class for pointer types with custom behavior such as over-aligned
0024 /// allocation.
0025 template <uintptr_t N, typename PointerArgT,
0026           typename TraitsArgT = PointerLikeTypeTraits<PointerArgT>>
0027 struct PointerSumTypeMember {
0028   enum { Tag = N };
0029   using PointerT = PointerArgT;
0030   using TraitsT = TraitsArgT;
0031 };
0032
0033 namespace detail {
0034
0035 template <typename TagT, typename... MemberTs> struct PointerSumTypeHelper;
0036
0037 } // end namespace detail
0038
0039 /// A sum type over pointer-like types.
0040 ///
0041 /// This is a normal tagged union across pointer-like types that uses the low
0042 /// bits of the pointers to store the tag.
0043 ///
0044 /// Each member of the sum type is specified by passing a \c
0045 /// PointerSumTypeMember specialization in the variadic member argument list.
0046 /// This allows the user to control the particular tag value associated with
0047 /// a particular type, use the same type for multiple different tags, and
0048 /// customize the pointer-like traits used for a particular member. Note that
0049 /// these *must* be specializations of \c PointerSumTypeMember, no other type
0050 /// will suffice, even if it provides a compatible interface.
0051 ///
0052 /// This type implements all of the comparison operators and even hash table
0053 /// support by comparing the underlying storage of the pointer values. It
0054 /// doesn't support delegating to particular members for comparisons.
0055 ///
0056 /// It also default constructs to a zero tag with a null pointer, whatever that
0057 /// would be. This means that the zero value for the tag type is significant
0058 /// and may be desirable to set to a state that is particularly desirable to
0059 /// default construct.
0060 ///
0061 /// Having a supported zero-valued tag also enables getting the address of a
0062 /// pointer stored with that tag provided it is stored in its natural bit
0063 /// representation. This works because in the case of a zero-valued tag, the
0064 /// pointer's value is directly stored into this object and we can expose the
0065 /// address of that internal storage. This is especially useful when building an
0066 /// `ArrayRef` of a single pointer stored in a sum type.
0067 ///
0068 /// There is no support for constructing or accessing with a dynamic tag as
0069 /// that would fundamentally violate the type safety provided by the sum type.
0070 template <typename TagT, typename... MemberTs> class PointerSumType {
0071   using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
0072
0073   // We keep both the raw value and the min tag value's pointer in a union. When
0074   // the minimum tag value is zero, this allows code below to cleanly expose the
0075   // address of the zero-tag pointer instead of just the zero-tag pointer
0076   // itself. This is especially useful when building `ArrayRef`s out of a single
0077   // pointer. However, we have to carefully access the union due to the active
0078   // member potentially changing. When we *store* a new value, we directly
0079   // access the union to allow us to store using the obvious types. However,
0080   // when we *read* a value, we copy the underlying storage out to avoid relying
0081   // on one member or the other being active.
0082   union StorageT {
0083     // Ensure we get a null default constructed value. We don't use a member
0084     // initializer because some compilers seem to not implement those correctly
0085     // for a union.
0086     StorageT() : Value(0) {}
0087
0088     uintptr_t Value;
0089
0090     typename HelperT::template Lookup<HelperT::MinTag>::PointerT MinTagPointer;
0091   };
0092
0093   StorageT Storage;
0094
0095 public:
0096   constexpr PointerSumType() = default;
0097
0098   /// A typed setter to a given tagged member of the sum type.
0099   template <TagT N>
0100   void set(typename HelperT::template Lookup<N>::PointerT Pointer) {
0101     void *V = HelperT::template Lookup<N>::TraitsT::getAsVoidPointer(Pointer);
0102     assert((reinterpret_cast<uintptr_t>(V) & HelperT::TagMask) == 0 &&
0103            "Pointer is insufficiently aligned to store the discriminant!");
0104     Storage.Value = reinterpret_cast<uintptr_t>(V) | N;
0105   }
0106
0107   /// A typed constructor for a specific tagged member of the sum type.
0108   template <TagT N>
0109   static PointerSumType
0110   create(typename HelperT::template Lookup<N>::PointerT Pointer) {
0111     PointerSumType Result;
0112     Result.set<N>(Pointer);
0113     return Result;
0114   }
0115
0116   /// Clear the value to null with the min tag type.
0117   void clear() { set<HelperT::MinTag>(nullptr); }
0118
0119   TagT getTag() const {
0120     return static_cast<TagT>(getOpaqueValue() & HelperT::TagMask);
0121   }
0122
0123   template <TagT N> bool is() const { return N == getTag(); }
0124
0125   template <TagT N> typename HelperT::template Lookup<N>::PointerT get() const {
0126     void *P = is<N>() ? getVoidPtr() : nullptr;
0127     return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(P);
0128   }
0129
0130   template <TagT N>
0131   typename HelperT::template Lookup<N>::PointerT cast() const {
0132     assert(is<N>() && "This instance has a different active member.");
0133     return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(
0134         getVoidPtr());
0135   }
0136
0137   /// If the tag is zero and the pointer's value isn't changed when being
0138   /// stored, get the address of the stored value type-punned to the zero-tag's
0139   /// pointer type.
0140   typename HelperT::template Lookup<HelperT::MinTag>::PointerT const *
0141   getAddrOfZeroTagPointer() const {
0142     return const_cast<PointerSumType *>(this)->getAddrOfZeroTagPointer();
0143   }
0144
0145   /// If the tag is zero and the pointer's value isn't changed when being
0146   /// stored, get the address of the stored value type-punned to the zero-tag's
0147   /// pointer type.
0148   typename HelperT::template Lookup<HelperT::MinTag>::PointerT *
0149   getAddrOfZeroTagPointer() {
0150     static_assert(HelperT::MinTag == 0, "Non-zero minimum tag value!");
0151     assert(is<HelperT::MinTag>() && "The active tag is not zero!");
0152     // Store the initial value of the pointer when read out of our storage.
0153     auto InitialPtr = get<HelperT::MinTag>();
0154     // Now update the active member of the union to be the actual pointer-typed
0155     // member so that accessing it indirectly through the returned address is
0156     // valid.
0157     Storage.MinTagPointer = InitialPtr;
0158     // Finally, validate that this was a no-op as expected by reading it back
0159     // out using the same underlying-storage read as above.
0160     assert(InitialPtr == get<HelperT::MinTag>() &&
0161            "Switching to typed storage changed the pointer returned!");
0162     // Now we can correctly return an address to typed storage.
0163     return &Storage.MinTagPointer;
0164   }
0165
0166   explicit operator bool() const {
0167     return getOpaqueValue() & HelperT::PointerMask;
0168   }
0169   bool operator==(const PointerSumType &R) const {
0170     return getOpaqueValue() == R.getOpaqueValue();
0171   }
0172   bool operator!=(const PointerSumType &R) const {
0173     return getOpaqueValue() != R.getOpaqueValue();
0174   }
0175   bool operator<(const PointerSumType &R) const {
0176     return getOpaqueValue() < R.getOpaqueValue();
0177   }
0178   bool operator>(const PointerSumType &R) const {
0179     return getOpaqueValue() > R.getOpaqueValue();
0180   }
0181   bool operator<=(const PointerSumType &R) const {
0182     return getOpaqueValue() <= R.getOpaqueValue();
0183   }
0184   bool operator>=(const PointerSumType &R) const {
0185     return getOpaqueValue() >= R.getOpaqueValue();
0186   }
0187
0188   uintptr_t getOpaqueValue() const {
0189     // Read the underlying storage of the union, regardless of the active
0190     // member.
0191     return bit_cast<uintptr_t>(Storage);
0192   }
0193
0194 protected:
0195   void *getVoidPtr() const {
0196     return reinterpret_cast<void *>(getOpaqueValue() & HelperT::PointerMask);
0197   }
0198 };
0199
0200 namespace detail {
0201
0202 /// A helper template for implementing \c PointerSumType. It provides fast
0203 /// compile-time lookup of the member from a particular tag value, along with
0204 /// useful constants and compile time checking infrastructure..
0205 template <typename TagT, typename... MemberTs>
0206 struct PointerSumTypeHelper : MemberTs... {
0207   // First we use a trick to allow quickly looking up information about
0208   // a particular member of the sum type. This works because we arranged to
0209   // have this type derive from all of the member type templates. We can select
0210   // the matching member for a tag using type deduction during overload
0211   // resolution.
0212   template <TagT N, typename PointerT, typename TraitsT>
0213   static PointerSumTypeMember<N, PointerT, TraitsT>
0214   LookupOverload(PointerSumTypeMember<N, PointerT, TraitsT> *);
0215   template <TagT N> static void LookupOverload(...);
0216   template <TagT N> struct Lookup {
0217     // Compute a particular member type by resolving the lookup helper overload.
0218     using MemberT = decltype(
0219         LookupOverload<N>(static_cast<PointerSumTypeHelper *>(nullptr)));
0220
0221     /// The Nth member's pointer type.
0222     using PointerT = typename MemberT::PointerT;
0223
0224     /// The Nth member's traits type.
0225     using TraitsT = typename MemberT::TraitsT;
0226   };
0227
0228   // Next we need to compute the number of bits available for the discriminant
0229   // by taking the min of the bits available for each member. Much of this
0230   // would be amazingly easier with good constexpr support.
0231   template <uintptr_t V, uintptr_t... Vs>
0232   struct Min : std::integral_constant<
0233                    uintptr_t, (V < Min<Vs...>::value ? V : Min<Vs...>::value)> {
0234   };
0235   template <uintptr_t V>
0236   struct Min<V> : std::integral_constant<uintptr_t, V> {};
0237   enum { NumTagBits = Min<MemberTs::TraitsT::NumLowBitsAvailable...>::value };
0238
0239   // Also compute the smallest discriminant and various masks for convenience.
0240   constexpr static TagT MinTag =
0241       static_cast<TagT>(Min<MemberTs::Tag...>::value);
0242   enum : uint64_t {
0243     PointerMask = static_cast<uint64_t>(-1) << NumTagBits,
0244     TagMask = ~PointerMask
0245   };
0246
0247   // Finally we need a recursive template to do static checks of each
0248   // member.
0249   template <typename MemberT, typename... InnerMemberTs>
0250   struct Checker : Checker<InnerMemberTs...> {
0251     static_assert(MemberT::Tag < (1 << NumTagBits),
0252                   "This discriminant value requires too many bits!");
0253   };
0254   template <typename MemberT> struct Checker<MemberT> : std::true_type {
0255     static_assert(MemberT::Tag < (1 << NumTagBits),
0256                   "This discriminant value requires too many bits!");
0257   };
0258   static_assert(Checker<MemberTs...>::value,
0259                 "Each member must pass the checker.");
0260 };
0261
0262 } // end namespace detail
0263
0264 // Teach DenseMap how to use PointerSumTypes as keys.
0265 template <typename TagT, typename... MemberTs>
0266 struct DenseMapInfo<PointerSumType<TagT, MemberTs...>> {
0267   using SumType = PointerSumType<TagT, MemberTs...>;
0268   using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
0269   enum { SomeTag = HelperT::MinTag };
0270   using SomePointerT =
0271       typename HelperT::template Lookup<HelperT::MinTag>::PointerT;
0272   using SomePointerInfo = DenseMapInfo<SomePointerT>;
0273
0274   static inline SumType getEmptyKey() {
0275     return SumType::template create<SomeTag>(SomePointerInfo::getEmptyKey());
0276   }
0277
0278   static inline SumType getTombstoneKey() {
0279     return SumType::template create<SomeTag>(
0280         SomePointerInfo::getTombstoneKey());
0281   }
0282
0283   static unsigned getHashValue(const SumType &Arg) {
0284     uintptr_t OpaqueValue = Arg.getOpaqueValue();
0285     return DenseMapInfo<uintptr_t>::getHashValue(OpaqueValue);
0286   }
0287
0288   static bool isEqual(const SumType &LHS, const SumType &RHS) {
0289     return LHS == RHS;
0290   }
0291 };
0292
0293 } // end namespace llvm
0294
0295 #endif // LLVM_ADT_POINTERSUMTYPE_H