1 //===- llvm/ADT/PointerEmbeddedInt.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_POINTEREMBEDDEDINT_H 11 #define LLVM_ADT_POINTEREMBEDDEDINT_H 12 13 #include "llvm/ADT/DenseMapInfo.h" 14 #include "llvm/Support/MathExtras.h" 15 #include "llvm/Support/PointerLikeTypeTraits.h" 16 #include <climits> 17 18 namespace llvm { 19 20 /// Utility to embed an integer into a pointer-like type. This is specifically 21 /// intended to allow embedding integers where fewer bits are required than 22 /// exist in a pointer, and the integer can participate in abstractions along 23 /// side other pointer-like types. For example it can be placed into a \c 24 /// PointerSumType or \c PointerUnion. 25 /// 26 /// Note that much like pointers, an integer value of zero has special utility 27 /// due to boolean conversions. For example, a non-null value can be tested for 28 /// in the above abstractions without testing the particular active member. 29 /// Also, the default constructed value zero initializes the integer. 30 template <typename IntT, int Bits = sizeof(IntT) * CHAR_BIT> 31 class PointerEmbeddedInt { 32 uintptr_t Value; 33 34 // Note: This '<' is correct; using '<=' would result in some shifts 35 // overflowing their storage types. 36 static_assert(Bits < sizeof(uintptr_t) * CHAR_BIT, 37 "Cannot embed more bits than we have in a pointer!"); 38 39 enum : uintptr_t { 40 // We shift as many zeros into the value as we can while preserving the 41 // number of bits desired for the integer. 42 Shift = sizeof(uintptr_t) * CHAR_BIT - Bits, 43 44 // We also want to be able to mask out the preserved bits for asserts. 45 Mask = static_cast<uintptr_t>(-1) << Bits 46 }; 47 48 struct RawValueTag { 49 explicit RawValueTag() = default; 50 }; 51 52 friend class PointerLikeTypeTraits<PointerEmbeddedInt>; 53 PointerEmbeddedInt(uintptr_t Value,RawValueTag)54 explicit PointerEmbeddedInt(uintptr_t Value, RawValueTag) : Value(Value) {} 55 56 public: PointerEmbeddedInt()57 PointerEmbeddedInt() : Value(0) {} 58 PointerEmbeddedInt(IntT I)59 PointerEmbeddedInt(IntT I) { 60 *this = I; 61 } 62 63 PointerEmbeddedInt &operator=(IntT I) { 64 assert((std::is_signed<IntT>::value ? llvm::isInt<Bits>(I) 65 : llvm::isUInt<Bits>(I)) && 66 "Integer has bits outside those preserved!"); 67 Value = static_cast<uintptr_t>(I) << Shift; 68 return *this; 69 } 70 71 // Note that this implicit conversion additionally allows all of the basic 72 // comparison operators to work transparently, etc. IntT()73 operator IntT() const { 74 if (std::is_signed<IntT>::value) 75 return static_cast<IntT>(static_cast<intptr_t>(Value) >> Shift); 76 return static_cast<IntT>(Value >> Shift); 77 } 78 }; 79 80 // Provide pointer like traits to support use with pointer unions and sum 81 // types. 82 template <typename IntT, int Bits> 83 class PointerLikeTypeTraits<PointerEmbeddedInt<IntT, Bits>> { 84 typedef PointerEmbeddedInt<IntT, Bits> T; 85 86 public: getAsVoidPointer(const T & P)87 static inline void *getAsVoidPointer(const T &P) { 88 return reinterpret_cast<void *>(P.Value); 89 } getFromVoidPointer(void * P)90 static inline T getFromVoidPointer(void *P) { 91 return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag()); 92 } getFromVoidPointer(const void * P)93 static inline T getFromVoidPointer(const void *P) { 94 return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag()); 95 } 96 97 enum { NumLowBitsAvailable = T::Shift }; 98 }; 99 100 // Teach DenseMap how to use PointerEmbeddedInt objects as keys if the Int type 101 // itself can be a key. 102 template <typename IntT, int Bits> 103 struct DenseMapInfo<PointerEmbeddedInt<IntT, Bits>> { 104 typedef PointerEmbeddedInt<IntT, Bits> T; 105 106 typedef DenseMapInfo<IntT> IntInfo; 107 108 static inline T getEmptyKey() { return IntInfo::getEmptyKey(); } 109 static inline T getTombstoneKey() { return IntInfo::getTombstoneKey(); } 110 static unsigned getHashValue(const T &Arg) { 111 return IntInfo::getHashValue(Arg); 112 } 113 static bool isEqual(const T &LHS, const T &RHS) { return LHS == RHS; } 114 }; 115 } 116 117 #endif 118