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