1 //===- llvm/ADT/PointerUnion.h - Discriminated Union of 2 Ptrs --*- 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 // 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/Support/PointerLikeTypeTraits.h" 21 #include <cassert> 22 #include <cstddef> 23 #include <cstdint> 24 25 namespace llvm { 26 27 template <typename T> struct PointerUnionTypeSelectorReturn { 28 typedef T Return; 29 }; 30 31 /// Get a type based on whether two types are the same or not. 32 /// 33 /// For: 34 /// 35 /// \code 36 /// typedef typename PointerUnionTypeSelector<T1, T2, EQ, NE>::Return Ret; 37 /// \endcode 38 /// 39 /// Ret will be EQ type if T1 is same as T2 or NE type otherwise. 40 template <typename T1, typename T2, typename RET_EQ, typename RET_NE> 41 struct PointerUnionTypeSelector { 42 typedef typename PointerUnionTypeSelectorReturn<RET_NE>::Return Return; 43 }; 44 45 template <typename T, typename RET_EQ, typename RET_NE> 46 struct PointerUnionTypeSelector<T, T, RET_EQ, RET_NE> { 47 typedef typename PointerUnionTypeSelectorReturn<RET_EQ>::Return Return; 48 }; 49 50 template <typename T1, typename T2, typename RET_EQ, typename RET_NE> 51 struct PointerUnionTypeSelectorReturn< 52 PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>> { 53 typedef 54 typename PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>::Return Return; 55 }; 56 57 /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion 58 /// for the two template arguments. 59 template <typename PT1, typename PT2> class PointerUnionUIntTraits { 60 public: 61 static inline void *getAsVoidPointer(void *P) { return P; } 62 static inline void *getFromVoidPointer(void *P) { return P; } 63 64 enum { 65 PT1BitsAv = (int)(PointerLikeTypeTraits<PT1>::NumLowBitsAvailable), 66 PT2BitsAv = (int)(PointerLikeTypeTraits<PT2>::NumLowBitsAvailable), 67 NumLowBitsAvailable = PT1BitsAv < PT2BitsAv ? PT1BitsAv : PT2BitsAv 68 }; 69 }; 70 71 /// A discriminated union of two pointer types, with the discriminator in the 72 /// low bit of the pointer. 73 /// 74 /// This implementation is extremely efficient in space due to leveraging the 75 /// low bits of the pointer, while exposing a natural and type-safe API. 76 /// 77 /// Common use patterns would be something like this: 78 /// PointerUnion<int*, float*> P; 79 /// P = (int*)0; 80 /// printf("%d %d", P.is<int*>(), P.is<float*>()); // prints "1 0" 81 /// X = P.get<int*>(); // ok. 82 /// Y = P.get<float*>(); // runtime assertion failure. 83 /// Z = P.get<double*>(); // compile time failure. 84 /// P = (float*)0; 85 /// Y = P.get<float*>(); // ok. 86 /// X = P.get<int*>(); // runtime assertion failure. 87 template <typename PT1, typename PT2> class PointerUnion { 88 public: 89 typedef PointerIntPair<void *, 1, bool, PointerUnionUIntTraits<PT1, PT2>> 90 ValTy; 91 92 private: 93 ValTy Val; 94 95 struct IsPT1 { 96 static const int Num = 0; 97 }; 98 struct IsPT2 { 99 static const int Num = 1; 100 }; 101 template <typename T> struct UNION_DOESNT_CONTAIN_TYPE {}; 102 103 public: 104 PointerUnion() = default; 105 106 PointerUnion(PT1 V) 107 : Val(const_cast<void *>( 108 PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) {} 109 PointerUnion(PT2 V) 110 : Val(const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)), 111 1) {} 112 113 /// Test if the pointer held in the union is null, regardless of 114 /// which type it is. 115 bool isNull() const { 116 // Convert from the void* to one of the pointer types, to make sure that 117 // we recursively strip off low bits if we have a nested PointerUnion. 118 return !PointerLikeTypeTraits<PT1>::getFromVoidPointer(Val.getPointer()); 119 } 120 explicit operator bool() const { return !isNull(); } 121 122 /// Test if the Union currently holds the type matching T. 123 template <typename T> int is() const { 124 typedef typename ::llvm::PointerUnionTypeSelector< 125 PT1, T, IsPT1, ::llvm::PointerUnionTypeSelector< 126 PT2, T, IsPT2, UNION_DOESNT_CONTAIN_TYPE<T>>>::Return 127 Ty; 128 int TyNo = Ty::Num; 129 return static_cast<int>(Val.getInt()) == TyNo; 130 } 131 132 /// Returns the value of the specified pointer type. 133 /// 134 /// If the specified pointer type is incorrect, assert. 135 template <typename T> T get() const { 136 assert(is<T>() && "Invalid accessor called"); 137 return PointerLikeTypeTraits<T>::getFromVoidPointer(Val.getPointer()); 138 } 139 140 /// Returns the current pointer if it is of the specified pointer type, 141 /// otherwises returns null. 142 template <typename T> T dyn_cast() const { 143 if (is<T>()) 144 return get<T>(); 145 return T(); 146 } 147 148 /// If the union is set to the first pointer type get an address pointing to 149 /// it. 150 PT1 const *getAddrOfPtr1() const { 151 return const_cast<PointerUnion *>(this)->getAddrOfPtr1(); 152 } 153 154 /// If the union is set to the first pointer type get an address pointing to 155 /// it. 156 PT1 *getAddrOfPtr1() { 157 assert(is<PT1>() && "Val is not the first pointer"); 158 assert( 159 get<PT1>() == Val.getPointer() && 160 "Can't get the address because PointerLikeTypeTraits changes the ptr"); 161 return const_cast<PT1 *>(reinterpret_cast<const PT1 *>(Val.getAddrOfPointer())); 162 } 163 164 /// Assignment from nullptr which just clears the union. 165 const PointerUnion &operator=(std::nullptr_t) { 166 Val.initWithPointer(nullptr); 167 return *this; 168 } 169 170 /// Assignment operators - Allow assigning into this union from either 171 /// pointer type, setting the discriminator to remember what it came from. 172 const PointerUnion &operator=(const PT1 &RHS) { 173 Val.initWithPointer( 174 const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(RHS))); 175 return *this; 176 } 177 const PointerUnion &operator=(const PT2 &RHS) { 178 Val.setPointerAndInt( 179 const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(RHS)), 180 1); 181 return *this; 182 } 183 184 void *getOpaqueValue() const { return Val.getOpaqueValue(); } 185 static inline PointerUnion getFromOpaqueValue(void *VP) { 186 PointerUnion V; 187 V.Val = ValTy::getFromOpaqueValue(VP); 188 return V; 189 } 190 }; 191 192 template <typename PT1, typename PT2> 193 bool operator==(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { 194 return lhs.getOpaqueValue() == rhs.getOpaqueValue(); 195 } 196 197 template <typename PT1, typename PT2> 198 bool operator!=(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { 199 return lhs.getOpaqueValue() != rhs.getOpaqueValue(); 200 } 201 202 template <typename PT1, typename PT2> 203 bool operator<(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { 204 return lhs.getOpaqueValue() < rhs.getOpaqueValue(); 205 } 206 207 // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has 208 // # low bits available = min(PT1bits,PT2bits)-1. 209 template <typename PT1, typename PT2> 210 struct PointerLikeTypeTraits<PointerUnion<PT1, PT2>> { 211 static inline void *getAsVoidPointer(const PointerUnion<PT1, PT2> &P) { 212 return P.getOpaqueValue(); 213 } 214 215 static inline PointerUnion<PT1, PT2> getFromVoidPointer(void *P) { 216 return PointerUnion<PT1, PT2>::getFromOpaqueValue(P); 217 } 218 219 // The number of bits available are the min of the two pointer types. 220 enum { 221 NumLowBitsAvailable = PointerLikeTypeTraits< 222 typename PointerUnion<PT1, PT2>::ValTy>::NumLowBitsAvailable 223 }; 224 }; 225 226 /// A pointer union of three pointer types. See documentation for PointerUnion 227 /// for usage. 228 template <typename PT1, typename PT2, typename PT3> class PointerUnion3 { 229 public: 230 typedef PointerUnion<PT1, PT2> InnerUnion; 231 typedef PointerUnion<InnerUnion, PT3> ValTy; 232 233 private: 234 ValTy Val; 235 236 struct IsInnerUnion { 237 ValTy Val; 238 IsInnerUnion(ValTy val) : Val(val) {} 239 template <typename T> int is() const { 240 return Val.template is<InnerUnion>() && 241 Val.template get<InnerUnion>().template is<T>(); 242 } 243 template <typename T> T get() const { 244 return Val.template get<InnerUnion>().template get<T>(); 245 } 246 }; 247 248 struct IsPT3 { 249 ValTy Val; 250 IsPT3(ValTy val) : Val(val) {} 251 template <typename T> int is() const { return Val.template is<T>(); } 252 template <typename T> T get() const { return Val.template get<T>(); } 253 }; 254 255 public: 256 PointerUnion3() = default; 257 258 PointerUnion3(PT1 V) { Val = InnerUnion(V); } 259 PointerUnion3(PT2 V) { Val = InnerUnion(V); } 260 PointerUnion3(PT3 V) { Val = V; } 261 262 /// Test if the pointer held in the union is null, regardless of 263 /// which type it is. 264 bool isNull() const { return Val.isNull(); } 265 explicit operator bool() const { return !isNull(); } 266 267 /// Test if the Union currently holds the type matching T. 268 template <typename T> int is() const { 269 // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3. 270 typedef typename ::llvm::PointerUnionTypeSelector< 271 PT1, T, IsInnerUnion, 272 ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return 273 Ty; 274 return Ty(Val).template is<T>(); 275 } 276 277 /// Returns the value of the specified pointer type. 278 /// 279 /// If the specified pointer type is incorrect, assert. 280 template <typename T> T get() const { 281 assert(is<T>() && "Invalid accessor called"); 282 // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3. 283 typedef typename ::llvm::PointerUnionTypeSelector< 284 PT1, T, IsInnerUnion, 285 ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return 286 Ty; 287 return Ty(Val).template get<T>(); 288 } 289 290 /// Returns the current pointer if it is of the specified pointer type, 291 /// otherwises returns null. 292 template <typename T> T dyn_cast() const { 293 if (is<T>()) 294 return get<T>(); 295 return T(); 296 } 297 298 /// Assignment from nullptr which just clears the union. 299 const PointerUnion3 &operator=(std::nullptr_t) { 300 Val = nullptr; 301 return *this; 302 } 303 304 /// Assignment operators - Allow assigning into this union from either 305 /// pointer type, setting the discriminator to remember what it came from. 306 const PointerUnion3 &operator=(const PT1 &RHS) { 307 Val = InnerUnion(RHS); 308 return *this; 309 } 310 const PointerUnion3 &operator=(const PT2 &RHS) { 311 Val = InnerUnion(RHS); 312 return *this; 313 } 314 const PointerUnion3 &operator=(const PT3 &RHS) { 315 Val = RHS; 316 return *this; 317 } 318 319 void *getOpaqueValue() const { return Val.getOpaqueValue(); } 320 static inline PointerUnion3 getFromOpaqueValue(void *VP) { 321 PointerUnion3 V; 322 V.Val = ValTy::getFromOpaqueValue(VP); 323 return V; 324 } 325 }; 326 327 // Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has 328 // # low bits available = min(PT1bits,PT2bits,PT2bits)-2. 329 template <typename PT1, typename PT2, typename PT3> 330 struct PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3>> { 331 static inline void *getAsVoidPointer(const PointerUnion3<PT1, PT2, PT3> &P) { 332 return P.getOpaqueValue(); 333 } 334 335 static inline PointerUnion3<PT1, PT2, PT3> getFromVoidPointer(void *P) { 336 return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P); 337 } 338 339 // The number of bits available are the min of the two pointer types. 340 enum { 341 NumLowBitsAvailable = PointerLikeTypeTraits< 342 typename PointerUnion3<PT1, PT2, PT3>::ValTy>::NumLowBitsAvailable 343 }; 344 }; 345 346 /// A pointer union of four pointer types. See documentation for PointerUnion 347 /// for usage. 348 template <typename PT1, typename PT2, typename PT3, typename PT4> 349 class PointerUnion4 { 350 public: 351 typedef PointerUnion<PT1, PT2> InnerUnion1; 352 typedef PointerUnion<PT3, PT4> InnerUnion2; 353 typedef PointerUnion<InnerUnion1, InnerUnion2> ValTy; 354 355 private: 356 ValTy Val; 357 358 public: 359 PointerUnion4() = default; 360 361 PointerUnion4(PT1 V) { Val = InnerUnion1(V); } 362 PointerUnion4(PT2 V) { Val = InnerUnion1(V); } 363 PointerUnion4(PT3 V) { Val = InnerUnion2(V); } 364 PointerUnion4(PT4 V) { Val = InnerUnion2(V); } 365 366 /// Test if the pointer held in the union is null, regardless of 367 /// which type it is. 368 bool isNull() const { return Val.isNull(); } 369 explicit operator bool() const { return !isNull(); } 370 371 /// Test if the Union currently holds the type matching T. 372 template <typename T> int is() const { 373 // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2. 374 typedef typename ::llvm::PointerUnionTypeSelector< 375 PT1, T, InnerUnion1, ::llvm::PointerUnionTypeSelector< 376 PT2, T, InnerUnion1, InnerUnion2>>::Return Ty; 377 return Val.template is<Ty>() && Val.template get<Ty>().template is<T>(); 378 } 379 380 /// Returns the value of the specified pointer type. 381 /// 382 /// If the specified pointer type is incorrect, assert. 383 template <typename T> T get() const { 384 assert(is<T>() && "Invalid accessor called"); 385 // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2. 386 typedef typename ::llvm::PointerUnionTypeSelector< 387 PT1, T, InnerUnion1, ::llvm::PointerUnionTypeSelector< 388 PT2, T, InnerUnion1, InnerUnion2>>::Return Ty; 389 return Val.template get<Ty>().template get<T>(); 390 } 391 392 /// Returns the current pointer if it is of the specified pointer type, 393 /// otherwises returns null. 394 template <typename T> T dyn_cast() const { 395 if (is<T>()) 396 return get<T>(); 397 return T(); 398 } 399 400 /// Assignment from nullptr which just clears the union. 401 const PointerUnion4 &operator=(std::nullptr_t) { 402 Val = nullptr; 403 return *this; 404 } 405 406 /// Assignment operators - Allow assigning into this union from either 407 /// pointer type, setting the discriminator to remember what it came from. 408 const PointerUnion4 &operator=(const PT1 &RHS) { 409 Val = InnerUnion1(RHS); 410 return *this; 411 } 412 const PointerUnion4 &operator=(const PT2 &RHS) { 413 Val = InnerUnion1(RHS); 414 return *this; 415 } 416 const PointerUnion4 &operator=(const PT3 &RHS) { 417 Val = InnerUnion2(RHS); 418 return *this; 419 } 420 const PointerUnion4 &operator=(const PT4 &RHS) { 421 Val = InnerUnion2(RHS); 422 return *this; 423 } 424 425 void *getOpaqueValue() const { return Val.getOpaqueValue(); } 426 static inline PointerUnion4 getFromOpaqueValue(void *VP) { 427 PointerUnion4 V; 428 V.Val = ValTy::getFromOpaqueValue(VP); 429 return V; 430 } 431 }; 432 433 // Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has 434 // # low bits available = min(PT1bits,PT2bits,PT2bits)-2. 435 template <typename PT1, typename PT2, typename PT3, typename PT4> 436 struct PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4>> { 437 static inline void * 438 getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) { 439 return P.getOpaqueValue(); 440 } 441 442 static inline PointerUnion4<PT1, PT2, PT3, PT4> getFromVoidPointer(void *P) { 443 return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P); 444 } 445 446 // The number of bits available are the min of the two pointer types. 447 enum { 448 NumLowBitsAvailable = PointerLikeTypeTraits< 449 typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy>::NumLowBitsAvailable 450 }; 451 }; 452 453 // Teach DenseMap how to use PointerUnions as keys. 454 template <typename T, typename U> struct DenseMapInfo<PointerUnion<T, U>> { 455 typedef PointerUnion<T, U> Pair; 456 typedef DenseMapInfo<T> FirstInfo; 457 typedef DenseMapInfo<U> SecondInfo; 458 459 static inline Pair getEmptyKey() { return Pair(FirstInfo::getEmptyKey()); } 460 static inline Pair getTombstoneKey() { 461 return Pair(FirstInfo::getTombstoneKey()); 462 } 463 static unsigned getHashValue(const Pair &PairVal) { 464 intptr_t key = (intptr_t)PairVal.getOpaqueValue(); 465 return DenseMapInfo<intptr_t>::getHashValue(key); 466 } 467 static bool isEqual(const Pair &LHS, const Pair &RHS) { 468 return LHS.template is<T>() == RHS.template is<T>() && 469 (LHS.template is<T>() ? FirstInfo::isEqual(LHS.template get<T>(), 470 RHS.template get<T>()) 471 : SecondInfo::isEqual(LHS.template get<U>(), 472 RHS.template get<U>())); 473 } 474 }; 475 476 } // end namespace llvm 477 478 #endif // LLVM_ADT_POINTERUNION_H 479