//===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file defines the PointerIntPair class. // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_POINTERINTPAIR_H #define LLVM_ADT_POINTERINTPAIR_H #include "llvm/Support/Compiler.h" #include "llvm/Support/PointerLikeTypeTraits.h" #include "llvm/Support/type_traits.h" #include #include #include namespace llvm { template struct DenseMapInfo; template struct PointerIntPairInfo; /// PointerIntPair - This class implements a pair of a pointer and small /// integer. It is designed to represent this in the space required by one /// pointer by bitmangling the integer into the low part of the pointer. This /// can only be done for small integers: typically up to 3 bits, but it depends /// on the number of bits available according to PointerLikeTypeTraits for the /// type. /// /// Note that PointerIntPair always puts the IntVal part in the highest bits /// possible. For example, PointerIntPair will put the bit for /// the bool into bit #2, not bit #0, which allows the low two bits to be used /// for something else. For example, this allows: /// PointerIntPair, 1, bool> /// ... and the two bools will land in different bits. template , typename Info = PointerIntPairInfo> class PointerIntPair { // Used by MSVC visualizer and generally helpful for debugging/visualizing. using InfoTy = Info; intptr_t Value = 0; public: constexpr PointerIntPair() = default; PointerIntPair(PointerTy PtrVal, IntType IntVal) { setPointerAndInt(PtrVal, IntVal); } explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); } PointerTy getPointer() const { return Info::getPointer(Value); } IntType getInt() const { return (IntType)Info::getInt(Value); } void setPointer(PointerTy PtrVal) LLVM_LVALUE_FUNCTION { Value = Info::updatePointer(Value, PtrVal); } void setInt(IntType IntVal) LLVM_LVALUE_FUNCTION { Value = Info::updateInt(Value, static_cast(IntVal)); } void initWithPointer(PointerTy PtrVal) LLVM_LVALUE_FUNCTION { Value = Info::updatePointer(0, PtrVal); } void setPointerAndInt(PointerTy PtrVal, IntType IntVal) LLVM_LVALUE_FUNCTION { Value = Info::updateInt(Info::updatePointer(0, PtrVal), static_cast(IntVal)); } PointerTy const *getAddrOfPointer() const { return const_cast(this)->getAddrOfPointer(); } PointerTy *getAddrOfPointer() { assert(Value == reinterpret_cast(getPointer()) && "Can only return the address if IntBits is cleared and " "PtrTraits doesn't change the pointer"); return reinterpret_cast(&Value); } void *getOpaqueValue() const { return reinterpret_cast(Value); } void setFromOpaqueValue(void *Val) LLVM_LVALUE_FUNCTION { Value = reinterpret_cast(Val); } static PointerIntPair getFromOpaqueValue(void *V) { PointerIntPair P; P.setFromOpaqueValue(V); return P; } // Allow PointerIntPairs to be created from const void * if and only if the // pointer type could be created from a const void *. static PointerIntPair getFromOpaqueValue(const void *V) { (void)PtrTraits::getFromVoidPointer(V); return getFromOpaqueValue(const_cast(V)); } bool operator==(const PointerIntPair &RHS) const { return Value == RHS.Value; } bool operator!=(const PointerIntPair &RHS) const { return Value != RHS.Value; } bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; } bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; } bool operator<=(const PointerIntPair &RHS) const { return Value <= RHS.Value; } bool operator>=(const PointerIntPair &RHS) const { return Value >= RHS.Value; } }; // Specialize is_trivially_copyable to avoid limitation of llvm::is_trivially_copyable // when compiled with gcc 4.9. template struct is_trivially_copyable> : std::true_type { #ifdef HAVE_STD_IS_TRIVIALLY_COPYABLE static_assert(std::is_trivially_copyable>::value, "inconsistent behavior between llvm:: and std:: implementation of is_trivially_copyable"); #endif }; template struct PointerIntPairInfo { static_assert(PtrTraits::NumLowBitsAvailable < std::numeric_limits::digits, "cannot use a pointer type that has all bits free"); static_assert(IntBits <= PtrTraits::NumLowBitsAvailable, "PointerIntPair with integer size too large for pointer"); enum : uintptr_t { /// PointerBitMask - The bits that come from the pointer. PointerBitMask = ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1), /// IntShift - The number of low bits that we reserve for other uses, and /// keep zero. IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits, /// IntMask - This is the unshifted mask for valid bits of the int type. IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1), // ShiftedIntMask - This is the bits for the integer shifted in place. ShiftedIntMask = (uintptr_t)(IntMask << IntShift) }; static PointerT getPointer(intptr_t Value) { return PtrTraits::getFromVoidPointer( reinterpret_cast(Value & PointerBitMask)); } static intptr_t getInt(intptr_t Value) { return (Value >> IntShift) & IntMask; } static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) { intptr_t PtrWord = reinterpret_cast(PtrTraits::getAsVoidPointer(Ptr)); assert((PtrWord & ~PointerBitMask) == 0 && "Pointer is not sufficiently aligned"); // Preserve all low bits, just update the pointer. return PtrWord | (OrigValue & ~PointerBitMask); } static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) { intptr_t IntWord = static_cast(Int); assert((IntWord & ~IntMask) == 0 && "Integer too large for field"); // Preserve all bits other than the ones we are updating. return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift; } }; // Provide specialization of DenseMapInfo for PointerIntPair. template struct DenseMapInfo> { using Ty = PointerIntPair; static Ty getEmptyKey() { uintptr_t Val = static_cast(-1); Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; return Ty::getFromOpaqueValue(reinterpret_cast(Val)); } static Ty getTombstoneKey() { uintptr_t Val = static_cast(-2); Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; return Ty::getFromOpaqueValue(reinterpret_cast(Val)); } static unsigned getHashValue(Ty V) { uintptr_t IV = reinterpret_cast(V.getOpaqueValue()); return unsigned(IV) ^ unsigned(IV >> 9); } static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; } }; // Teach SmallPtrSet that PointerIntPair is "basically a pointer". template struct PointerLikeTypeTraits< PointerIntPair> { static inline void * getAsVoidPointer(const PointerIntPair &P) { return P.getOpaqueValue(); } static inline PointerIntPair getFromVoidPointer(void *P) { return PointerIntPair::getFromOpaqueValue(P); } static inline PointerIntPair getFromVoidPointer(const void *P) { return PointerIntPair::getFromOpaqueValue(P); } enum { NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits }; }; } // end namespace llvm #endif // LLVM_ADT_POINTERINTPAIR_H