1 //===- llvm/ADT/PointerUnion.h - Discriminated Union of 2 Ptrs --*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file defines the PointerUnion class, which is a discriminated union of 11 /// pointer types. 12 /// 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ADT_POINTERUNION_H 16 #define LLVM_ADT_POINTERUNION_H 17 18 #include "llvm/ADT/DenseMapInfo.h" 19 #include "llvm/ADT/PointerIntPair.h" 20 #include "llvm/ADT/STLExtras.h" 21 #include "llvm/Support/Casting.h" 22 #include "llvm/Support/PointerLikeTypeTraits.h" 23 #include <algorithm> 24 #include <cassert> 25 #include <cstddef> 26 #include <cstdint> 27 28 namespace llvm { 29 30 namespace pointer_union_detail { 31 /// Determine the number of bits required to store integers with values < n. 32 /// This is ceil(log2(n)). bitsRequired(unsigned n)33 constexpr int bitsRequired(unsigned n) { 34 return n > 1 ? 1 + bitsRequired((n + 1) / 2) : 0; 35 } 36 lowBitsAvailable()37 template <typename... Ts> constexpr int lowBitsAvailable() { 38 return std::min<int>({PointerLikeTypeTraits<Ts>::NumLowBitsAvailable...}); 39 } 40 41 /// Find the first type in a list of types. 42 template <typename T, typename...> struct GetFirstType { 43 using type = T; 44 }; 45 46 /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion 47 /// for the template arguments. 48 template <typename ...PTs> class PointerUnionUIntTraits { 49 public: getAsVoidPointer(void * P)50 static inline void *getAsVoidPointer(void *P) { return P; } getFromVoidPointer(void * P)51 static inline void *getFromVoidPointer(void *P) { return P; } 52 static constexpr int NumLowBitsAvailable = lowBitsAvailable<PTs...>(); 53 }; 54 55 template <typename Derived, typename ValTy, int I, typename ...Types> 56 class PointerUnionMembers; 57 58 template <typename Derived, typename ValTy, int I> 59 class PointerUnionMembers<Derived, ValTy, I> { 60 protected: 61 ValTy Val; 62 PointerUnionMembers() = default; PointerUnionMembers(ValTy Val)63 PointerUnionMembers(ValTy Val) : Val(Val) {} 64 65 friend struct PointerLikeTypeTraits<Derived>; 66 }; 67 68 template <typename Derived, typename ValTy, int I, typename Type, 69 typename ...Types> 70 class PointerUnionMembers<Derived, ValTy, I, Type, Types...> 71 : public PointerUnionMembers<Derived, ValTy, I + 1, Types...> { 72 using Base = PointerUnionMembers<Derived, ValTy, I + 1, Types...>; 73 public: 74 using Base::Base; 75 PointerUnionMembers() = default; 76 PointerUnionMembers(Type V) 77 : Base(ValTy(const_cast<void *>( 78 PointerLikeTypeTraits<Type>::getAsVoidPointer(V)), 79 I)) {} 80 81 using Base::operator=; 82 Derived &operator=(Type V) { 83 this->Val = ValTy( 84 const_cast<void *>(PointerLikeTypeTraits<Type>::getAsVoidPointer(V)), 85 I); 86 return static_cast<Derived &>(*this); 87 }; 88 }; 89 } 90 91 // This is a forward declaration of CastInfoPointerUnionImpl 92 // Refer to its definition below for further details 93 template <typename... PTs> struct CastInfoPointerUnionImpl; 94 /// A discriminated union of two or more pointer types, with the discriminator 95 /// in the low bit of the pointer. 96 /// 97 /// This implementation is extremely efficient in space due to leveraging the 98 /// low bits of the pointer, while exposing a natural and type-safe API. 99 /// 100 /// Common use patterns would be something like this: 101 /// PointerUnion<int*, float*> P; 102 /// P = (int*)0; 103 /// printf("%d %d", P.is<int*>(), P.is<float*>()); // prints "1 0" 104 /// X = P.get<int*>(); // ok. 105 /// Y = P.get<float*>(); // runtime assertion failure. 106 /// Z = P.get<double*>(); // compile time failure. 107 /// P = (float*)0; 108 /// Y = P.get<float*>(); // ok. 109 /// X = P.get<int*>(); // runtime assertion failure. 110 /// PointerUnion<int*, int*> Q; // compile time failure. 111 template <typename... PTs> 112 class PointerUnion 113 : public pointer_union_detail::PointerUnionMembers< 114 PointerUnion<PTs...>, 115 PointerIntPair< 116 void *, pointer_union_detail::bitsRequired(sizeof...(PTs)), int, 117 pointer_union_detail::PointerUnionUIntTraits<PTs...>>, 118 0, PTs...> { 119 static_assert(TypesAreDistinct<PTs...>::value, 120 "PointerUnion alternative types cannot be repeated"); 121 // The first type is special because we want to directly cast a pointer to a 122 // default-initialized union to a pointer to the first type. But we don't 123 // want PointerUnion to be a 'template <typename First, typename ...Rest>' 124 // because it's much more convenient to have a name for the whole pack. So 125 // split off the first type here. 126 using First = TypeAtIndex<0, PTs...>; 127 using Base = typename PointerUnion::PointerUnionMembers; 128 129 /// This is needed to give the CastInfo implementation below access 130 /// to protected members. 131 /// Refer to its definition for further details. 132 friend struct CastInfoPointerUnionImpl<PTs...>; 133 134 public: 135 PointerUnion() = default; 136 137 PointerUnion(std::nullptr_t) : PointerUnion() {} 138 using Base::Base; 139 140 /// Test if the pointer held in the union is null, regardless of 141 /// which type it is. 142 bool isNull() const { return !this->Val.getPointer(); } 143 144 explicit operator bool() const { return !isNull(); } 145 146 // FIXME: Replace the uses of is(), get() and dyn_cast() with 147 // isa<T>, cast<T> and the llvm::dyn_cast<T> 148 149 /// Test if the Union currently holds the type matching T. 150 template <typename T> inline bool is() const { return isa<T>(*this); } 151 152 /// Returns the value of the specified pointer type. 153 /// 154 /// If the specified pointer type is incorrect, assert. 155 template <typename T> inline T get() const { 156 assert(isa<T>(*this) && "Invalid accessor called"); 157 return cast<T>(*this); 158 } 159 160 /// Returns the current pointer if it is of the specified pointer type, 161 /// otherwise returns null. 162 template <typename T> inline T dyn_cast() const { 163 return llvm::dyn_cast_if_present<T>(*this); 164 } 165 166 /// If the union is set to the first pointer type get an address pointing to 167 /// it. 168 First const *getAddrOfPtr1() const { 169 return const_cast<PointerUnion *>(this)->getAddrOfPtr1(); 170 } 171 172 /// If the union is set to the first pointer type get an address pointing to 173 /// it. 174 First *getAddrOfPtr1() { 175 assert(isa<First>(*this) && "Val is not the first pointer"); 176 assert( 177 PointerLikeTypeTraits<First>::getAsVoidPointer(cast<First>(*this)) == 178 this->Val.getPointer() && 179 "Can't get the address because PointerLikeTypeTraits changes the ptr"); 180 return const_cast<First *>( 181 reinterpret_cast<const First *>(this->Val.getAddrOfPointer())); 182 } 183 184 /// Assignment from nullptr which just clears the union. 185 const PointerUnion &operator=(std::nullptr_t) { 186 this->Val.initWithPointer(nullptr); 187 return *this; 188 } 189 190 /// Assignment from elements of the union. 191 using Base::operator=; 192 193 void *getOpaqueValue() const { return this->Val.getOpaqueValue(); } 194 static inline PointerUnion getFromOpaqueValue(void *VP) { 195 PointerUnion V; 196 V.Val = decltype(V.Val)::getFromOpaqueValue(VP); 197 return V; 198 } 199 }; 200 201 template <typename ...PTs> 202 bool operator==(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) { 203 return lhs.getOpaqueValue() == rhs.getOpaqueValue(); 204 } 205 206 template <typename ...PTs> 207 bool operator!=(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) { 208 return lhs.getOpaqueValue() != rhs.getOpaqueValue(); 209 } 210 211 template <typename ...PTs> 212 bool operator<(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) { 213 return lhs.getOpaqueValue() < rhs.getOpaqueValue(); 214 } 215 216 /// We can't (at least, at this moment with C++14) declare CastInfo 217 /// as a friend of PointerUnion like this: 218 /// ``` 219 /// template<typename To> 220 /// friend struct CastInfo<To, PointerUnion<PTs...>>; 221 /// ``` 222 /// The compiler complains 'Partial specialization cannot be declared as a 223 /// friend'. 224 /// So we define this struct to be a bridge between CastInfo and 225 /// PointerUnion. 226 template <typename... PTs> struct CastInfoPointerUnionImpl { 227 using From = PointerUnion<PTs...>; 228 229 template <typename To> static inline bool isPossible(From &F) { 230 return F.Val.getInt() == FirstIndexOfType<To, PTs...>::value; 231 } 232 233 template <typename To> static To doCast(From &F) { 234 assert(isPossible<To>(F) && "cast to an incompatible type!"); 235 return PointerLikeTypeTraits<To>::getFromVoidPointer(F.Val.getPointer()); 236 } 237 }; 238 239 // Specialization of CastInfo for PointerUnion 240 template <typename To, typename... PTs> 241 struct CastInfo<To, PointerUnion<PTs...>> 242 : public DefaultDoCastIfPossible<To, PointerUnion<PTs...>, 243 CastInfo<To, PointerUnion<PTs...>>> { 244 using From = PointerUnion<PTs...>; 245 using Impl = CastInfoPointerUnionImpl<PTs...>; 246 247 static inline bool isPossible(From &f) { 248 return Impl::template isPossible<To>(f); 249 } 250 251 static To doCast(From &f) { return Impl::template doCast<To>(f); } 252 253 static inline To castFailed() { return To(); } 254 }; 255 256 template <typename To, typename... PTs> 257 struct CastInfo<To, const PointerUnion<PTs...>> 258 : public ConstStrippingForwardingCast<To, const PointerUnion<PTs...>, 259 CastInfo<To, PointerUnion<PTs...>>> { 260 }; 261 262 // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has 263 // # low bits available = min(PT1bits,PT2bits)-1. 264 template <typename ...PTs> 265 struct PointerLikeTypeTraits<PointerUnion<PTs...>> { 266 static inline void *getAsVoidPointer(const PointerUnion<PTs...> &P) { 267 return P.getOpaqueValue(); 268 } 269 270 static inline PointerUnion<PTs...> getFromVoidPointer(void *P) { 271 return PointerUnion<PTs...>::getFromOpaqueValue(P); 272 } 273 274 // The number of bits available are the min of the pointer types minus the 275 // bits needed for the discriminator. 276 static constexpr int NumLowBitsAvailable = PointerLikeTypeTraits<decltype( 277 PointerUnion<PTs...>::Val)>::NumLowBitsAvailable; 278 }; 279 280 // Teach DenseMap how to use PointerUnions as keys. 281 template <typename ...PTs> struct DenseMapInfo<PointerUnion<PTs...>> { 282 using Union = PointerUnion<PTs...>; 283 using FirstInfo = 284 DenseMapInfo<typename pointer_union_detail::GetFirstType<PTs...>::type>; 285 286 static inline Union getEmptyKey() { return Union(FirstInfo::getEmptyKey()); } 287 288 static inline Union getTombstoneKey() { 289 return Union(FirstInfo::getTombstoneKey()); 290 } 291 292 static unsigned getHashValue(const Union &UnionVal) { 293 intptr_t key = (intptr_t)UnionVal.getOpaqueValue(); 294 return DenseMapInfo<intptr_t>::getHashValue(key); 295 } 296 297 static bool isEqual(const Union &LHS, const Union &RHS) { 298 return LHS == RHS; 299 } 300 }; 301 302 } // end namespace llvm 303 304 #endif // LLVM_ADT_POINTERUNION_H 305