contrib/llvm/include/llvm/ADT/PointerSumType.h

   1 //===- llvm/ADT/PointerSumType.h --------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLVM_ADT_POINTERSUMTYPE_H
  11 #define LLVM_ADT_POINTERSUMTYPE_H
  12
  13 #include "llvm/ADT/bit.h"
  14 #include "llvm/ADT/DenseMapInfo.h"
  15 #include "llvm/Support/PointerLikeTypeTraits.h"
  16 #include <cassert>
  17 #include <cstdint>
  18 #include <type_traits>
  19
  20 namespace llvm {
  21
  22 /// A compile time pair of an integer tag and the pointer-like type which it
  23 /// indexes within a sum type. Also allows the user to specify a particular
  24 /// traits class for pointer types with custom behavior such as over-aligned
  25 /// allocation.
  26 template <uintptr_t N, typename PointerArgT,
  27           typename TraitsArgT = PointerLikeTypeTraits<PointerArgT>>
  28 struct PointerSumTypeMember {
  29   enum { Tag = N };
  30   using PointerT = PointerArgT;
  31   using TraitsT = TraitsArgT;
  32 };
  33
  34 namespace detail {
  35
  36 template <typename TagT, typename... MemberTs> struct PointerSumTypeHelper;
  37
  38 } // end namespace detail
  39
  40 /// A sum type over pointer-like types.
  41 ///
  42 /// This is a normal tagged union across pointer-like types that uses the low
  43 /// bits of the pointers to store the tag.
  44 ///
  45 /// Each member of the sum type is specified by passing a \c
  46 /// PointerSumTypeMember specialization in the variadic member argument list.
  47 /// This allows the user to control the particular tag value associated with
  48 /// a particular type, use the same type for multiple different tags, and
  49 /// customize the pointer-like traits used for a particular member. Note that
  50 /// these *must* be specializations of \c PointerSumTypeMember, no other type
  51 /// will suffice, even if it provides a compatible interface.
  52 ///
  53 /// This type implements all of the comparison operators and even hash table
  54 /// support by comparing the underlying storage of the pointer values. It
  55 /// doesn't support delegating to particular members for comparisons.
  56 ///
  57 /// It also default constructs to a zero tag with a null pointer, whatever that
  58 /// would be. This means that the zero value for the tag type is significant
  59 /// and may be desirable to set to a state that is particularly desirable to
  60 /// default construct.
  61 ///
  62 /// Having a supported zero-valued tag also enables getting the address of a
  63 /// pointer stored with that tag provided it is stored in its natural bit
  64 /// representation. This works because in the case of a zero-valued tag, the
  65 /// pointer's value is directly stored into this object and we can expose the
  66 /// address of that internal storage. This is especially useful when building an
  67 /// `ArrayRef` of a single pointer stored in a sum type.
  68 ///
  69 /// There is no support for constructing or accessing with a dynamic tag as
  70 /// that would fundamentally violate the type safety provided by the sum type.
  71 template <typename TagT, typename... MemberTs> class PointerSumType {
  72   using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
  73
  74   // We keep both the raw value and the min tag value's pointer in a union. When
  75   // the minimum tag value is zero, this allows code below to cleanly expose the
  76   // address of the zero-tag pointer instead of just the zero-tag pointer
  77   // itself. This is especially useful when building `ArrayRef`s out of a single
  78   // pointer. However, we have to carefully access the union due to the active
  79   // member potentially changing. When we *store* a new value, we directly
  80   // access the union to allow us to store using the obvious types. However,
  81   // when we *read* a value, we copy the underlying storage out to avoid relying
  82   // on one member or the other being active.
  83   union StorageT {
  84     // Ensure we get a null default constructed value. We don't use a member
  85     // initializer because some compilers seem to not implement those correctly
  86     // for a union.
  87     StorageT() : Value(0) {}
  88
  89     uintptr_t Value;
  90
  91     typename HelperT::template Lookup<HelperT::MinTag>::PointerT MinTagPointer;
  92   };
  93
  94   StorageT Storage;
  95
  96 public:
  97   constexpr PointerSumType() = default;
  98
  99   /// A typed setter to a given tagged member of the sum type.
 100   template <TagT N>
 101   void set(typename HelperT::template Lookup<N>::PointerT Pointer) {
 102     void *V = HelperT::template Lookup<N>::TraitsT::getAsVoidPointer(Pointer);
 103     assert((reinterpret_cast<uintptr_t>(V) & HelperT::TagMask) == 0 &&
 104            "Pointer is insufficiently aligned to store the discriminant!");
 105     Storage.Value = reinterpret_cast<uintptr_t>(V) | N;
 106   }
 107
 108   /// A typed constructor for a specific tagged member of the sum type.
 109   template <TagT N>
 110   static PointerSumType
 111   create(typename HelperT::template Lookup<N>::PointerT Pointer) {
 112     PointerSumType Result;
 113     Result.set<N>(Pointer);
 114     return Result;
 115   }
 116
 117   /// Clear the value to null with the min tag type.
 118   void clear() { set<HelperT::MinTag>(nullptr); }
 119
 120   TagT getTag() const {
 121     return static_cast<TagT>(getOpaqueValue() & HelperT::TagMask);
 122   }
 123
 124   template <TagT N> bool is() const { return N == getTag(); }
 125
 126   template <TagT N> typename HelperT::template Lookup<N>::PointerT get() const {
 127     void *P = is<N>() ? getVoidPtr() : nullptr;
 128     return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(P);
 129   }
 130
 131   template <TagT N>
 132   typename HelperT::template Lookup<N>::PointerT cast() const {
 133     assert(is<N>() && "This instance has a different active member.");
 134     return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(
 135         getVoidPtr());
 136   }
 137
 138   /// If the tag is zero and the pointer's value isn't changed when being
 139   /// stored, get the address of the stored value type-punned to the zero-tag's
 140   /// pointer type.
 141   typename HelperT::template Lookup<HelperT::MinTag>::PointerT const *
 142   getAddrOfZeroTagPointer() const {
 143     return const_cast<PointerSumType *>(this)->getAddrOfZeroTagPointer();
 144   }
 145
 146   /// If the tag is zero and the pointer's value isn't changed when being
 147   /// stored, get the address of the stored value type-punned to the zero-tag's
 148   /// pointer type.
 149   typename HelperT::template Lookup<HelperT::MinTag>::PointerT *
 150   getAddrOfZeroTagPointer() {
 151     static_assert(HelperT::MinTag == 0, "Non-zero minimum tag value!");
 152     assert(is<HelperT::MinTag>() && "The active tag is not zero!");
 153     // Store the initial value of the pointer when read out of our storage.
 154     auto InitialPtr = get<HelperT::MinTag>();
 155     // Now update the active member of the union to be the actual pointer-typed
 156     // member so that accessing it indirectly through the returned address is
 157     // valid.
 158     Storage.MinTagPointer = InitialPtr;
 159     // Finally, validate that this was a no-op as expected by reading it back
 160     // out using the same underlying-storage read as above.
 161     assert(InitialPtr == get<HelperT::MinTag>() &&
 162            "Switching to typed storage changed the pointer returned!");
 163     // Now we can correctly return an address to typed storage.
 164     return &Storage.MinTagPointer;
 165   }
 166
 167   explicit operator bool() const {
 168     return getOpaqueValue() & HelperT::PointerMask;
 169   }
 170   bool operator==(const PointerSumType &R) const {
 171     return getOpaqueValue() == R.getOpaqueValue();
 172   }
 173   bool operator!=(const PointerSumType &R) const {
 174     return getOpaqueValue() != R.getOpaqueValue();
 175   }
 176   bool operator<(const PointerSumType &R) const {
 177     return getOpaqueValue() < R.getOpaqueValue();
 178   }
 179   bool operator>(const PointerSumType &R) const {
 180     return getOpaqueValue() > R.getOpaqueValue();
 181   }
 182   bool operator<=(const PointerSumType &R) const {
 183     return getOpaqueValue() <= R.getOpaqueValue();
 184   }
 185   bool operator>=(const PointerSumType &R) const {
 186     return getOpaqueValue() >= R.getOpaqueValue();
 187   }
 188
 189   uintptr_t getOpaqueValue() const {
 190     // Read the underlying storage of the union, regardless of the active
 191     // member.
 192     return bit_cast<uintptr_t>(Storage);
 193   }
 194
 195 protected:
 196   void *getVoidPtr() const {
 197     return reinterpret_cast<void *>(getOpaqueValue() & HelperT::PointerMask);
 198   }
 199 };
 200
 201 namespace detail {
 202
 203 /// A helper template for implementing \c PointerSumType. It provides fast
 204 /// compile-time lookup of the member from a particular tag value, along with
 205 /// useful constants and compile time checking infrastructure..
 206 template <typename TagT, typename... MemberTs>
 207 struct PointerSumTypeHelper : MemberTs... {
 208   // First we use a trick to allow quickly looking up information about
 209   // a particular member of the sum type. This works because we arranged to
 210   // have this type derive from all of the member type templates. We can select
 211   // the matching member for a tag using type deduction during overload
 212   // resolution.
 213   template <TagT N, typename PointerT, typename TraitsT>
 214   static PointerSumTypeMember<N, PointerT, TraitsT>
 215   LookupOverload(PointerSumTypeMember<N, PointerT, TraitsT> *);
 216   template <TagT N> static void LookupOverload(...);
 217   template <TagT N> struct Lookup {
 218     // Compute a particular member type by resolving the lookup helper ovorload.
 219     using MemberT = decltype(
 220         LookupOverload<N>(static_cast<PointerSumTypeHelper *>(nullptr)));
 221
 222     /// The Nth member's pointer type.
 223     using PointerT = typename MemberT::PointerT;
 224
 225     /// The Nth member's traits type.
 226     using TraitsT = typename MemberT::TraitsT;
 227   };
 228
 229   // Next we need to compute the number of bits available for the discriminant
 230   // by taking the min of the bits available for each member. Much of this
 231   // would be amazingly easier with good constexpr support.
 232   template <uintptr_t V, uintptr_t... Vs>
 233   struct Min : std::integral_constant<
 234                    uintptr_t, (V < Min<Vs...>::value ? V : Min<Vs...>::value)> {
 235   };
 236   template <uintptr_t V>
 237   struct Min<V> : std::integral_constant<uintptr_t, V> {};
 238   enum { NumTagBits = Min<MemberTs::TraitsT::NumLowBitsAvailable...>::value };
 239
 240   // Also compute the smallest discriminant and various masks for convenience.
 241   constexpr static TagT MinTag =
 242       static_cast<TagT>(Min<MemberTs::Tag...>::value);
 243   enum : uint64_t {
 244     PointerMask = static_cast<uint64_t>(-1) << NumTagBits,
 245     TagMask = ~PointerMask
 246   };
 247
 248   // Finally we need a recursive template to do static checks of each
 249   // member.
 250   template <typename MemberT, typename... InnerMemberTs>
 251   struct Checker : Checker<InnerMemberTs...> {
 252     static_assert(MemberT::Tag < (1 << NumTagBits),
 253                   "This discriminant value requires too many bits!");
 254   };
 255   template <typename MemberT> struct Checker<MemberT> : std::true_type {
 256     static_assert(MemberT::Tag < (1 << NumTagBits),
 257                   "This discriminant value requires too many bits!");
 258   };
 259   static_assert(Checker<MemberTs...>::value,
 260                 "Each member must pass the checker.");
 261 };
 262
 263 } // end namespace detail
 264
 265 // Teach DenseMap how to use PointerSumTypes as keys.
 266 template <typename TagT, typename... MemberTs>
 267 struct DenseMapInfo<PointerSumType<TagT, MemberTs...>> {
 268   using SumType = PointerSumType<TagT, MemberTs...>;
 269   using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
 270   enum { SomeTag = HelperT::MinTag };
 271   using SomePointerT =
 272       typename HelperT::template Lookup<HelperT::MinTag>::PointerT;
 273   using SomePointerInfo = DenseMapInfo<SomePointerT>;
 274
 275   static inline SumType getEmptyKey() {
 276     return SumType::create<SomeTag>(SomePointerInfo::getEmptyKey());
 277   }
 278
 279   static inline SumType getTombstoneKey() {
 280     return SumType::create<SomeTag>(SomePointerInfo::getTombstoneKey());
 281   }
 282
 283   static unsigned getHashValue(const SumType &Arg) {
 284     uintptr_t OpaqueValue = Arg.getOpaqueValue();
 285     return DenseMapInfo<uintptr_t>::getHashValue(OpaqueValue);
 286   }
 287
 288   static bool isEqual(const SumType &LHS, const SumType &RHS) {
 289     return LHS == RHS;
 290   }
 291 };
 292
 293 } // end namespace llvm
 294
 295 #endif // LLVM_ADT_POINTERSUMTYPE_H