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/DenseMapInfo.h" 14 #include "llvm/Support/Compiler.h" 15 #include "llvm/Support/PointerLikeTypeTraits.h" 16 17 namespace llvm { 18 19 /// A compile time pair of an integer tag and the pointer-like type which it 20 /// indexes within a sum type. Also allows the user to specify a particular 21 /// traits class for pointer types with custom behavior such as over-aligned 22 /// allocation. 23 template <uintptr_t N, typename PointerArgT, 24 typename TraitsArgT = PointerLikeTypeTraits<PointerArgT>> 25 struct PointerSumTypeMember { 26 enum { Tag = N }; 27 typedef PointerArgT PointerT; 28 typedef TraitsArgT TraitsT; 29 }; 30 31 namespace detail { 32 33 template <typename TagT, typename... MemberTs> 34 struct PointerSumTypeHelper; 35 36 } 37 38 /// A sum type over pointer-like types. 39 /// 40 /// This is a normal tagged union across pointer-like types that uses the low 41 /// bits of the pointers to store the tag. 42 /// 43 /// Each member of the sum type is specified by passing a \c 44 /// PointerSumTypeMember specialization in the variadic member argument list. 45 /// This allows the user to control the particular tag value associated with 46 /// a particular type, use the same type for multiple different tags, and 47 /// customize the pointer-like traits used for a particular member. Note that 48 /// these *must* be specializations of \c PointerSumTypeMember, no other type 49 /// will suffice, even if it provides a compatible interface. 50 /// 51 /// This type implements all of the comparison operators and even hash table 52 /// support by comparing the underlying storage of the pointer values. It 53 /// doesn't support delegating to particular members for comparisons. 54 /// 55 /// It also default constructs to a zero tag with a null pointer, whatever that 56 /// would be. This means that the zero value for the tag type is significant 57 /// and may be desirable to set to a state that is particularly desirable to 58 /// default construct. 59 /// 60 /// There is no support for constructing or accessing with a dynamic tag as 61 /// that would fundamentally violate the type safety provided by the sum type. 62 template <typename TagT, typename... MemberTs> class PointerSumType { 63 uintptr_t Value; 64 65 typedef detail::PointerSumTypeHelper<TagT, MemberTs...> HelperT; 66 67 public: 68 PointerSumType() : Value(0) {} 69 70 /// A typed constructor for a specific tagged member of the sum type. 71 template <TagT N> 72 static PointerSumType 73 create(typename HelperT::template Lookup<N>::PointerT Pointer) { 74 PointerSumType Result; 75 void *V = HelperT::template Lookup<N>::TraitsT::getAsVoidPointer(Pointer); 76 assert((reinterpret_cast<uintptr_t>(V) & HelperT::TagMask) == 0 && 77 "Pointer is insufficiently aligned to store the discriminant!"); 78 Result.Value = reinterpret_cast<uintptr_t>(V) | N; 79 return Result; 80 } 81 82 TagT getTag() const { return static_cast<TagT>(Value & HelperT::TagMask); } 83 84 template <TagT N> bool is() const { return N == getTag(); } 85 86 template <TagT N> typename HelperT::template Lookup<N>::PointerT get() const { 87 void *P = is<N>() ? getImpl() : nullptr; 88 return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(P); 89 } 90 91 template <TagT N> 92 typename HelperT::template Lookup<N>::PointerT cast() const { 93 assert(is<N>() && "This instance has a different active member."); 94 return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(getImpl()); 95 } 96 97 explicit operator bool() const { return Value & HelperT::PointerMask; } 98 bool operator==(const PointerSumType &R) const { return Value == R.Value; } 99 bool operator!=(const PointerSumType &R) const { return Value != R.Value; } 100 bool operator<(const PointerSumType &R) const { return Value < R.Value; } 101 bool operator>(const PointerSumType &R) const { return Value > R.Value; } 102 bool operator<=(const PointerSumType &R) const { return Value <= R.Value; } 103 bool operator>=(const PointerSumType &R) const { return Value >= R.Value; } 104 105 uintptr_t getOpaqueValue() const { return Value; } 106 107 protected: 108 void *getImpl() const { 109 return reinterpret_cast<void *>(Value & HelperT::PointerMask); 110 } 111 }; 112 113 namespace detail { 114 115 /// A helper template for implementing \c PointerSumType. It provides fast 116 /// compile-time lookup of the member from a particular tag value, along with 117 /// useful constants and compile time checking infrastructure.. 118 template <typename TagT, typename... MemberTs> 119 struct PointerSumTypeHelper : MemberTs... { 120 // First we use a trick to allow quickly looking up information about 121 // a particular member of the sum type. This works because we arranged to 122 // have this type derive from all of the member type templates. We can select 123 // the matching member for a tag using type deduction during overload 124 // resolution. 125 template <TagT N, typename PointerT, typename TraitsT> 126 static PointerSumTypeMember<N, PointerT, TraitsT> 127 LookupOverload(PointerSumTypeMember<N, PointerT, TraitsT> *); 128 template <TagT N> static void LookupOverload(...); 129 template <TagT N> struct Lookup { 130 // Compute a particular member type by resolving the lookup helper ovorload. 131 typedef decltype(LookupOverload<N>( 132 static_cast<PointerSumTypeHelper *>(nullptr))) MemberT; 133 134 /// The Nth member's pointer type. 135 typedef typename MemberT::PointerT PointerT; 136 137 /// The Nth member's traits type. 138 typedef typename MemberT::TraitsT TraitsT; 139 }; 140 141 // Next we need to compute the number of bits available for the discriminant 142 // by taking the min of the bits available for each member. Much of this 143 // would be amazingly easier with good constexpr support. 144 template <uintptr_t V, uintptr_t... Vs> 145 struct Min : std::integral_constant< 146 uintptr_t, (V < Min<Vs...>::value ? V : Min<Vs...>::value)> { 147 }; 148 template <uintptr_t V> 149 struct Min<V> : std::integral_constant<uintptr_t, V> {}; 150 enum { NumTagBits = Min<MemberTs::TraitsT::NumLowBitsAvailable...>::value }; 151 152 // Also compute the smallest discriminant and various masks for convenience. 153 enum : uint64_t { 154 MinTag = Min<MemberTs::Tag...>::value, 155 PointerMask = static_cast<uint64_t>(-1) << NumTagBits, 156 TagMask = ~PointerMask 157 }; 158 159 // Finally we need a recursive template to do static checks of each 160 // member. 161 template <typename MemberT, typename... InnerMemberTs> 162 struct Checker : Checker<InnerMemberTs...> { 163 static_assert(MemberT::Tag < (1 << NumTagBits), 164 "This discriminant value requires too many bits!"); 165 }; 166 template <typename MemberT> struct Checker<MemberT> : std::true_type { 167 static_assert(MemberT::Tag < (1 << NumTagBits), 168 "This discriminant value requires too many bits!"); 169 }; 170 static_assert(Checker<MemberTs...>::value, 171 "Each member must pass the checker."); 172 }; 173 174 } 175 176 // Teach DenseMap how to use PointerSumTypes as keys. 177 template <typename TagT, typename... MemberTs> 178 struct DenseMapInfo<PointerSumType<TagT, MemberTs...>> { 179 typedef PointerSumType<TagT, MemberTs...> SumType; 180 181 typedef detail::PointerSumTypeHelper<TagT, MemberTs...> HelperT; 182 enum { SomeTag = HelperT::MinTag }; 183 typedef typename HelperT::template Lookup<HelperT::MinTag>::PointerT 184 SomePointerT; 185 typedef DenseMapInfo<SomePointerT> SomePointerInfo; 186 187 static inline SumType getEmptyKey() { 188 return SumType::create<SomeTag>(SomePointerInfo::getEmptyKey()); 189 } 190 static inline SumType getTombstoneKey() { 191 return SumType::create<SomeTag>( 192 SomePointerInfo::getTombstoneKey()); 193 } 194 static unsigned getHashValue(const SumType &Arg) { 195 uintptr_t OpaqueValue = Arg.getOpaqueValue(); 196 return DenseMapInfo<uintptr_t>::getHashValue(OpaqueValue); 197 } 198 static bool isEqual(const SumType &LHS, const SumType &RHS) { 199 return LHS == RHS; 200 } 201 }; 202 203 } 204 205 #endif 206
