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