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