1 //===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- 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 PointerIntPair class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_POINTERINTPAIR_H 15 #define LLVM_ADT_POINTERINTPAIR_H 16 17 #include "llvm/Support/Compiler.h" 18 #include "llvm/Support/PointerLikeTypeTraits.h" 19 #include <cassert> 20 21 namespace llvm { 22 23 template<typename T> 24 struct DenseMapInfo; 25 26 /// PointerIntPair - This class implements a pair of a pointer and small 27 /// integer. It is designed to represent this in the space required by one 28 /// pointer by bitmangling the integer into the low part of the pointer. This 29 /// can only be done for small integers: typically up to 3 bits, but it depends 30 /// on the number of bits available according to PointerLikeTypeTraits for the 31 /// type. 32 /// 33 /// Note that PointerIntPair always puts the IntVal part in the highest bits 34 /// possible. For example, PointerIntPair<void*, 1, bool> will put the bit for 35 /// the bool into bit #2, not bit #0, which allows the low two bits to be used 36 /// for something else. For example, this allows: 37 /// PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool> 38 /// ... and the two bools will land in different bits. 39 /// 40 template <typename PointerTy, unsigned IntBits, typename IntType=unsigned, 41 typename PtrTraits = PointerLikeTypeTraits<PointerTy> > 42 class PointerIntPair { 43 intptr_t Value; 44 enum LLVM_ENUM_INT_TYPE(uintptr_t) { 45 /// PointerBitMask - The bits that come from the pointer. 46 PointerBitMask = 47 ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable)-1), 48 49 /// IntShift - The number of low bits that we reserve for other uses, and 50 /// keep zero. 51 IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable-IntBits, 52 53 /// IntMask - This is the unshifted mask for valid bits of the int type. 54 IntMask = (uintptr_t)(((intptr_t)1 << IntBits)-1), 55 56 // ShiftedIntMask - This is the bits for the integer shifted in place. 57 ShiftedIntMask = (uintptr_t)(IntMask << IntShift) 58 }; 59 public: 60 PointerIntPair() : Value(0) {} 61 PointerIntPair(PointerTy PtrVal, IntType IntVal) { 62 assert(IntBits <= PtrTraits::NumLowBitsAvailable && 63 "PointerIntPair formed with integer size too large for pointer"); 64 setPointerAndInt(PtrVal, IntVal); 65 } 66 explicit PointerIntPair(PointerTy PtrVal) { 67 initWithPointer(PtrVal); 68 } 69 70 PointerTy getPointer() const { 71 return PtrTraits::getFromVoidPointer( 72 reinterpret_cast<void*>(Value & PointerBitMask)); 73 } 74 75 IntType getInt() const { 76 return (IntType)((Value >> IntShift) & IntMask); 77 } 78 79 void setPointer(PointerTy PtrVal) { 80 intptr_t PtrWord 81 = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal)); 82 assert((PtrWord & ((1 << PtrTraits::NumLowBitsAvailable)-1)) == 0 && 83 "Pointer is not sufficiently aligned"); 84 // Preserve all low bits, just update the pointer. 85 Value = PtrWord | (Value & ~PointerBitMask); 86 } 87 88 void setInt(IntType IntVal) { 89 intptr_t IntWord = static_cast<intptr_t>(IntVal); 90 assert(IntWord < (1 << IntBits) && "Integer too large for field"); 91 92 // Preserve all bits other than the ones we are updating. 93 Value &= ~ShiftedIntMask; // Remove integer field. 94 Value |= IntWord << IntShift; // Set new integer. 95 } 96 97 void initWithPointer(PointerTy PtrVal) { 98 intptr_t PtrWord 99 = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal)); 100 assert((PtrWord & ((1 << PtrTraits::NumLowBitsAvailable)-1)) == 0 && 101 "Pointer is not sufficiently aligned"); 102 Value = PtrWord; 103 } 104 105 void setPointerAndInt(PointerTy PtrVal, IntType IntVal) { 106 intptr_t PtrWord 107 = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal)); 108 assert((PtrWord & ((1 << PtrTraits::NumLowBitsAvailable)-1)) == 0 && 109 "Pointer is not sufficiently aligned"); 110 intptr_t IntWord = static_cast<intptr_t>(IntVal); 111 assert(IntWord < (1 << IntBits) && "Integer too large for field"); 112 113 Value = PtrWord | (IntWord << IntShift); 114 } 115 116 PointerTy const *getAddrOfPointer() const { 117 return const_cast<PointerIntPair *>(this)->getAddrOfPointer(); 118 } 119 120 PointerTy *getAddrOfPointer() { 121 assert(Value == reinterpret_cast<intptr_t>(getPointer()) && 122 "Can only return the address if IntBits is cleared and " 123 "PtrTraits doesn't change the pointer"); 124 return reinterpret_cast<PointerTy *>(&Value); 125 } 126 127 void *getOpaqueValue() const { return reinterpret_cast<void*>(Value); } 128 void setFromOpaqueValue(void *Val) { Value = reinterpret_cast<intptr_t>(Val);} 129 130 static PointerIntPair getFromOpaqueValue(void *V) { 131 PointerIntPair P; P.setFromOpaqueValue(V); return P; 132 } 133 134 // Allow PointerIntPairs to be created from const void * if and only if the 135 // pointer type could be created from a const void *. 136 static PointerIntPair getFromOpaqueValue(const void *V) { 137 (void)PtrTraits::getFromVoidPointer(V); 138 return getFromOpaqueValue(const_cast<void *>(V)); 139 } 140 141 bool operator==(const PointerIntPair &RHS) const {return Value == RHS.Value;} 142 bool operator!=(const PointerIntPair &RHS) const {return Value != RHS.Value;} 143 bool operator<(const PointerIntPair &RHS) const {return Value < RHS.Value;} 144 bool operator>(const PointerIntPair &RHS) const {return Value > RHS.Value;} 145 bool operator<=(const PointerIntPair &RHS) const {return Value <= RHS.Value;} 146 bool operator>=(const PointerIntPair &RHS) const {return Value >= RHS.Value;} 147 }; 148 149 template <typename T> struct isPodLike; 150 template<typename PointerTy, unsigned IntBits, typename IntType> 151 struct isPodLike<PointerIntPair<PointerTy, IntBits, IntType> > { 152 static const bool value = true; 153 }; 154 155 // Provide specialization of DenseMapInfo for PointerIntPair. 156 template<typename PointerTy, unsigned IntBits, typename IntType> 157 struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType> > { 158 typedef PointerIntPair<PointerTy, IntBits, IntType> Ty; 159 static Ty getEmptyKey() { 160 uintptr_t Val = static_cast<uintptr_t>(-1); 161 Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable; 162 return Ty(reinterpret_cast<PointerTy>(Val), IntType((1 << IntBits)-1)); 163 } 164 static Ty getTombstoneKey() { 165 uintptr_t Val = static_cast<uintptr_t>(-2); 166 Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable; 167 return Ty(reinterpret_cast<PointerTy>(Val), IntType(0)); 168 } 169 static unsigned getHashValue(Ty V) { 170 uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue()); 171 return unsigned(IV) ^ unsigned(IV >> 9); 172 } 173 static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; } 174 }; 175 176 // Teach SmallPtrSet that PointerIntPair is "basically a pointer". 177 template<typename PointerTy, unsigned IntBits, typename IntType, 178 typename PtrTraits> 179 class PointerLikeTypeTraits<PointerIntPair<PointerTy, IntBits, IntType, 180 PtrTraits> > { 181 public: 182 static inline void * 183 getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) { 184 return P.getOpaqueValue(); 185 } 186 static inline PointerIntPair<PointerTy, IntBits, IntType> 187 getFromVoidPointer(void *P) { 188 return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); 189 } 190 static inline PointerIntPair<PointerTy, IntBits, IntType> 191 getFromVoidPointer(const void *P) { 192 return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); 193 } 194 enum { 195 NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits 196 }; 197 }; 198 199 } // end namespace llvm 200 #endif 201