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 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 template<typename PT1, typename PT2> 199 static bool operator<(PointerUnion<PT1, PT2> lhs, 200 PointerUnion<PT1, PT2> rhs) { 201 return lhs.getOpaqueValue() < rhs.getOpaqueValue(); 202 } 203 204 // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has 205 // # low bits available = min(PT1bits,PT2bits)-1. 206 template<typename PT1, typename PT2> 207 class PointerLikeTypeTraits<PointerUnion<PT1, PT2> > { 208 public: 209 static inline void * 210 getAsVoidPointer(const PointerUnion<PT1, PT2> &P) { 211 return P.getOpaqueValue(); 212 } 213 static inline PointerUnion<PT1, PT2> 214 getFromVoidPointer(void *P) { 215 return PointerUnion<PT1, PT2>::getFromOpaqueValue(P); 216 } 217 218 // The number of bits available are the min of the two pointer types. 219 enum { 220 NumLowBitsAvailable = 221 PointerLikeTypeTraits<typename PointerUnion<PT1,PT2>::ValTy> 222 ::NumLowBitsAvailable 223 }; 224 }; 225 226 227 /// PointerUnion3 - This is a pointer union of three pointer types. See 228 /// documentation for PointerUnion for usage. 229 template <typename PT1, typename PT2, typename PT3> 230 class PointerUnion3 { 231 public: 232 typedef PointerUnion<PT1, PT2> InnerUnion; 233 typedef PointerUnion<InnerUnion, PT3> ValTy; 234 private: 235 ValTy Val; 236 237 struct IsInnerUnion { 238 ValTy Val; 239 IsInnerUnion(ValTy val) : Val(val) { } 240 template<typename T> 241 int is() const { 242 return Val.template is<InnerUnion>() && 243 Val.template get<InnerUnion>().template is<T>(); 244 } 245 template<typename T> 246 T get() const { 247 return Val.template get<InnerUnion>().template get<T>(); 248 } 249 }; 250 251 struct IsPT3 { 252 ValTy Val; 253 IsPT3(ValTy val) : Val(val) { } 254 template<typename T> 255 int is() const { 256 return Val.template is<T>(); 257 } 258 template<typename T> 259 T get() const { 260 return Val.template get<T>(); 261 } 262 }; 263 264 public: 265 PointerUnion3() {} 266 267 PointerUnion3(PT1 V) { 268 Val = InnerUnion(V); 269 } 270 PointerUnion3(PT2 V) { 271 Val = InnerUnion(V); 272 } 273 PointerUnion3(PT3 V) { 274 Val = V; 275 } 276 277 /// isNull - Return true if the pointer held in the union is null, 278 /// regardless of which type it is. 279 bool isNull() const { return Val.isNull(); } 280 explicit operator bool() const { return !isNull(); } 281 282 /// is<T>() return true if the Union currently holds the type matching T. 283 template<typename T> 284 int is() const { 285 // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3. 286 typedef typename 287 ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion, 288 ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 > 289 >::Return Ty; 290 return Ty(Val).template is<T>(); 291 } 292 293 /// get<T>() - Return the value of the specified pointer type. If the 294 /// specified pointer type is incorrect, assert. 295 template<typename T> 296 T get() const { 297 assert(is<T>() && "Invalid accessor called"); 298 // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3. 299 typedef typename 300 ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion, 301 ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 > 302 >::Return Ty; 303 return Ty(Val).template get<T>(); 304 } 305 306 /// dyn_cast<T>() - If the current value is of the specified pointer type, 307 /// return it, otherwise return null. 308 template<typename T> 309 T dyn_cast() const { 310 if (is<T>()) return get<T>(); 311 return T(); 312 } 313 314 /// \brief Assignment from nullptr which just clears the union. 315 const PointerUnion3 &operator=(std::nullptr_t) { 316 Val = nullptr; 317 return *this; 318 } 319 320 /// Assignment operators - Allow assigning into this union from either 321 /// pointer type, setting the discriminator to remember what it came from. 322 const PointerUnion3 &operator=(const PT1 &RHS) { 323 Val = InnerUnion(RHS); 324 return *this; 325 } 326 const PointerUnion3 &operator=(const PT2 &RHS) { 327 Val = InnerUnion(RHS); 328 return *this; 329 } 330 const PointerUnion3 &operator=(const PT3 &RHS) { 331 Val = RHS; 332 return *this; 333 } 334 335 void *getOpaqueValue() const { return Val.getOpaqueValue(); } 336 static inline PointerUnion3 getFromOpaqueValue(void *VP) { 337 PointerUnion3 V; 338 V.Val = ValTy::getFromOpaqueValue(VP); 339 return V; 340 } 341 }; 342 343 // Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has 344 // # low bits available = min(PT1bits,PT2bits,PT2bits)-2. 345 template<typename PT1, typename PT2, typename PT3> 346 class PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3> > { 347 public: 348 static inline void * 349 getAsVoidPointer(const PointerUnion3<PT1, PT2, PT3> &P) { 350 return P.getOpaqueValue(); 351 } 352 static inline PointerUnion3<PT1, PT2, PT3> 353 getFromVoidPointer(void *P) { 354 return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P); 355 } 356 357 // The number of bits available are the min of the two pointer types. 358 enum { 359 NumLowBitsAvailable = 360 PointerLikeTypeTraits<typename PointerUnion3<PT1, PT2, PT3>::ValTy> 361 ::NumLowBitsAvailable 362 }; 363 }; 364 365 /// PointerUnion4 - This is a pointer union of four pointer types. See 366 /// documentation for PointerUnion for usage. 367 template <typename PT1, typename PT2, typename PT3, typename PT4> 368 class PointerUnion4 { 369 public: 370 typedef PointerUnion<PT1, PT2> InnerUnion1; 371 typedef PointerUnion<PT3, PT4> InnerUnion2; 372 typedef PointerUnion<InnerUnion1, InnerUnion2> ValTy; 373 private: 374 ValTy Val; 375 public: 376 PointerUnion4() {} 377 378 PointerUnion4(PT1 V) { 379 Val = InnerUnion1(V); 380 } 381 PointerUnion4(PT2 V) { 382 Val = InnerUnion1(V); 383 } 384 PointerUnion4(PT3 V) { 385 Val = InnerUnion2(V); 386 } 387 PointerUnion4(PT4 V) { 388 Val = InnerUnion2(V); 389 } 390 391 /// isNull - Return true if the pointer held in the union is null, 392 /// regardless of which type it is. 393 bool isNull() const { return Val.isNull(); } 394 explicit operator bool() const { return !isNull(); } 395 396 /// is<T>() return true if the Union currently holds the type matching T. 397 template<typename T> 398 int is() const { 399 // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2. 400 typedef typename 401 ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1, 402 ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 > 403 >::Return Ty; 404 return Val.template is<Ty>() && 405 Val.template get<Ty>().template is<T>(); 406 } 407 408 /// get<T>() - Return the value of the specified pointer type. If the 409 /// specified pointer type is incorrect, assert. 410 template<typename T> 411 T get() const { 412 assert(is<T>() && "Invalid accessor called"); 413 // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2. 414 typedef typename 415 ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1, 416 ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 > 417 >::Return Ty; 418 return Val.template get<Ty>().template get<T>(); 419 } 420 421 /// dyn_cast<T>() - If the current value is of the specified pointer type, 422 /// return it, otherwise return null. 423 template<typename T> 424 T dyn_cast() const { 425 if (is<T>()) return get<T>(); 426 return T(); 427 } 428 429 /// \brief Assignment from nullptr which just clears the union. 430 const PointerUnion4 &operator=(std::nullptr_t) { 431 Val = nullptr; 432 return *this; 433 } 434 435 /// Assignment operators - Allow assigning into this union from either 436 /// pointer type, setting the discriminator to remember what it came from. 437 const PointerUnion4 &operator=(const PT1 &RHS) { 438 Val = InnerUnion1(RHS); 439 return *this; 440 } 441 const PointerUnion4 &operator=(const PT2 &RHS) { 442 Val = InnerUnion1(RHS); 443 return *this; 444 } 445 const PointerUnion4 &operator=(const PT3 &RHS) { 446 Val = InnerUnion2(RHS); 447 return *this; 448 } 449 const PointerUnion4 &operator=(const PT4 &RHS) { 450 Val = InnerUnion2(RHS); 451 return *this; 452 } 453 454 void *getOpaqueValue() const { return Val.getOpaqueValue(); } 455 static inline PointerUnion4 getFromOpaqueValue(void *VP) { 456 PointerUnion4 V; 457 V.Val = ValTy::getFromOpaqueValue(VP); 458 return V; 459 } 460 }; 461 462 // Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has 463 // # low bits available = min(PT1bits,PT2bits,PT2bits)-2. 464 template<typename PT1, typename PT2, typename PT3, typename PT4> 465 class PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4> > { 466 public: 467 static inline void * 468 getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) { 469 return P.getOpaqueValue(); 470 } 471 static inline PointerUnion4<PT1, PT2, PT3, PT4> 472 getFromVoidPointer(void *P) { 473 return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P); 474 } 475 476 // The number of bits available are the min of the two pointer types. 477 enum { 478 NumLowBitsAvailable = 479 PointerLikeTypeTraits<typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy> 480 ::NumLowBitsAvailable 481 }; 482 }; 483 484 // Teach DenseMap how to use PointerUnions as keys. 485 template<typename T, typename U> 486 struct DenseMapInfo<PointerUnion<T, U> > { 487 typedef PointerUnion<T, U> Pair; 488 typedef DenseMapInfo<T> FirstInfo; 489 typedef DenseMapInfo<U> SecondInfo; 490 491 static inline Pair getEmptyKey() { 492 return Pair(FirstInfo::getEmptyKey()); 493 } 494 static inline Pair getTombstoneKey() { 495 return Pair(FirstInfo::getTombstoneKey()); 496 } 497 static unsigned getHashValue(const Pair &PairVal) { 498 intptr_t key = (intptr_t)PairVal.getOpaqueValue(); 499 return DenseMapInfo<intptr_t>::getHashValue(key); 500 } 501 static bool isEqual(const Pair &LHS, const Pair &RHS) { 502 return LHS.template is<T>() == RHS.template is<T>() && 503 (LHS.template is<T>() ? 504 FirstInfo::isEqual(LHS.template get<T>(), 505 RHS.template get<T>()) : 506 SecondInfo::isEqual(LHS.template get<U>(), 507 RHS.template get<U>())); 508 } 509 }; 510 } 511 512 #endif 513