llvm/ADT/PointerIntPair.h

0001 //===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines the PointerIntPair class.
0011 ///
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_ADT_POINTERINTPAIR_H
0015 #define LLVM_ADT_POINTERINTPAIR_H
0016
0017 #include "llvm/Support/Compiler.h"
0018 #include "llvm/Support/PointerLikeTypeTraits.h"
0019 #include "llvm/Support/type_traits.h"
0020 #include <cassert>
0021 #include <cstdint>
0022 #include <cstring>
0023 #include <limits>
0024
0025 namespace llvm {
0026
0027 namespace detail {
0028 template <typename Ptr> struct PunnedPointer {
0029   static_assert(sizeof(Ptr) == sizeof(intptr_t), "");
0030
0031   // Asserts that allow us to let the compiler implement the destructor and
0032   // copy/move constructors
0033   static_assert(std::is_trivially_destructible<Ptr>::value, "");
0034   static_assert(std::is_trivially_copy_constructible<Ptr>::value, "");
0035   static_assert(std::is_trivially_move_constructible<Ptr>::value, "");
0036
0037   explicit constexpr PunnedPointer(intptr_t i = 0) { *this = i; }
0038
0039   constexpr intptr_t asInt() const {
0040     intptr_t R = 0;
0041     std::memcpy(&R, Data, sizeof(R));
0042     return R;
0043   }
0044
0045   constexpr operator intptr_t() const { return asInt(); }
0046
0047   constexpr PunnedPointer &operator=(intptr_t V) {
0048     std::memcpy(Data, &V, sizeof(Data));
0049     return *this;
0050   }
0051
0052   Ptr *getPointerAddress() { return reinterpret_cast<Ptr *>(Data); }
0053   const Ptr *getPointerAddress() const { return reinterpret_cast<Ptr *>(Data); }
0054
0055 private:
0056   alignas(Ptr) unsigned char Data[sizeof(Ptr)];
0057 };
0058 } // namespace detail
0059
0060 template <typename T, typename Enable> struct DenseMapInfo;
0061 template <typename PointerT, unsigned IntBits, typename PtrTraits>
0062 struct PointerIntPairInfo;
0063
0064 /// PointerIntPair - This class implements a pair of a pointer and small
0065 /// integer.  It is designed to represent this in the space required by one
0066 /// pointer by bitmangling the integer into the low part of the pointer.  This
0067 /// can only be done for small integers: typically up to 3 bits, but it depends
0068 /// on the number of bits available according to PointerLikeTypeTraits for the
0069 /// type.
0070 ///
0071 /// Note that PointerIntPair always puts the IntVal part in the highest bits
0072 /// possible.  For example, PointerIntPair<void*, 1, bool> will put the bit for
0073 /// the bool into bit #2, not bit #0, which allows the low two bits to be used
0074 /// for something else.  For example, this allows:
0075 ///   PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool>
0076 /// ... and the two bools will land in different bits.
0077 template <typename PointerTy, unsigned IntBits, typename IntType = unsigned,
0078           typename PtrTraits = PointerLikeTypeTraits<PointerTy>,
0079           typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>>
0080 class PointerIntPair {
0081   // Used by MSVC visualizer and generally helpful for debugging/visualizing.
0082   using InfoTy = Info;
0083   detail::PunnedPointer<PointerTy> Value;
0084
0085 public:
0086   constexpr PointerIntPair() = default;
0087
0088   PointerIntPair(PointerTy PtrVal, IntType IntVal) {
0089     setPointerAndInt(PtrVal, IntVal);
0090   }
0091
0092   explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); }
0093
0094   PointerTy getPointer() const { return Info::getPointer(Value); }
0095
0096   IntType getInt() const { return (IntType)Info::getInt(Value); }
0097
0098   void setPointer(PointerTy PtrVal) & {
0099     Value = Info::updatePointer(Value, PtrVal);
0100   }
0101
0102   void setInt(IntType IntVal) & {
0103     Value = Info::updateInt(Value, static_cast<intptr_t>(IntVal));
0104   }
0105
0106   void initWithPointer(PointerTy PtrVal) & {
0107     Value = Info::updatePointer(0, PtrVal);
0108   }
0109
0110   void setPointerAndInt(PointerTy PtrVal, IntType IntVal) & {
0111     Value = Info::updateInt(Info::updatePointer(0, PtrVal),
0112                             static_cast<intptr_t>(IntVal));
0113   }
0114
0115   PointerTy const *getAddrOfPointer() const {
0116     return const_cast<PointerIntPair *>(this)->getAddrOfPointer();
0117   }
0118
0119   PointerTy *getAddrOfPointer() {
0120     assert(Value == reinterpret_cast<intptr_t>(getPointer()) &&
0121            "Can only return the address if IntBits is cleared and "
0122            "PtrTraits doesn't change the pointer");
0123     return Value.getPointerAddress();
0124   }
0125
0126   void *getOpaqueValue() const {
0127     return reinterpret_cast<void *>(Value.asInt());
0128   }
0129
0130   void setFromOpaqueValue(void *Val) & {
0131     Value = reinterpret_cast<intptr_t>(Val);
0132   }
0133
0134   static PointerIntPair getFromOpaqueValue(void *V) {
0135     PointerIntPair P;
0136     P.setFromOpaqueValue(V);
0137     return P;
0138   }
0139
0140   // Allow PointerIntPairs to be created from const void * if and only if the
0141   // pointer type could be created from a const void *.
0142   static PointerIntPair getFromOpaqueValue(const void *V) {
0143     (void)PtrTraits::getFromVoidPointer(V);
0144     return getFromOpaqueValue(const_cast<void *>(V));
0145   }
0146
0147   bool operator==(const PointerIntPair &RHS) const {
0148     return Value == RHS.Value;
0149   }
0150
0151   bool operator!=(const PointerIntPair &RHS) const {
0152     return Value != RHS.Value;
0153   }
0154
0155   bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; }
0156   bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; }
0157
0158   bool operator<=(const PointerIntPair &RHS) const {
0159     return Value <= RHS.Value;
0160   }
0161
0162   bool operator>=(const PointerIntPair &RHS) const {
0163     return Value >= RHS.Value;
0164   }
0165 };
0166
0167 template <typename PointerT, unsigned IntBits, typename PtrTraits>
0168 struct PointerIntPairInfo {
0169   static_assert(PtrTraits::NumLowBitsAvailable <
0170                     std::numeric_limits<uintptr_t>::digits,
0171                 "cannot use a pointer type that has all bits free");
0172   static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
0173                 "PointerIntPair with integer size too large for pointer");
0174   enum MaskAndShiftConstants : uintptr_t {
0175     /// PointerBitMask - The bits that come from the pointer.
0176     PointerBitMask =
0177         ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1),
0178
0179     /// IntShift - The number of low bits that we reserve for other uses, and
0180     /// keep zero.
0181     IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits,
0182
0183     /// IntMask - This is the unshifted mask for valid bits of the int type.
0184     IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1),
0185
0186     // ShiftedIntMask - This is the bits for the integer shifted in place.
0187     ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
0188   };
0189
0190   static PointerT getPointer(intptr_t Value) {
0191     return PtrTraits::getFromVoidPointer(
0192         reinterpret_cast<void *>(Value & PointerBitMask));
0193   }
0194
0195   static intptr_t getInt(intptr_t Value) {
0196     return (Value >> IntShift) & IntMask;
0197   }
0198
0199   static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) {
0200     intptr_t PtrWord =
0201         reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr));
0202     assert((PtrWord & ~PointerBitMask) == 0 &&
0203            "Pointer is not sufficiently aligned");
0204     // Preserve all low bits, just update the pointer.
0205     return PtrWord | (OrigValue & ~PointerBitMask);
0206   }
0207
0208   static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) {
0209     intptr_t IntWord = static_cast<intptr_t>(Int);
0210     assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
0211
0212     // Preserve all bits other than the ones we are updating.
0213     return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift;
0214   }
0215 };
0216
0217 // Provide specialization of DenseMapInfo for PointerIntPair.
0218 template <typename PointerTy, unsigned IntBits, typename IntType>
0219 struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>, void> {
0220   using Ty = PointerIntPair<PointerTy, IntBits, IntType>;
0221
0222   static Ty getEmptyKey() {
0223     uintptr_t Val = static_cast<uintptr_t>(-1);
0224     Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable;
0225     return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
0226   }
0227
0228   static Ty getTombstoneKey() {
0229     uintptr_t Val = static_cast<uintptr_t>(-2);
0230     Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
0231     return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
0232   }
0233
0234   static unsigned getHashValue(Ty V) {
0235     uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue());
0236     return unsigned(IV) ^ unsigned(IV >> 9);
0237   }
0238
0239   static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; }
0240 };
0241
0242 // Teach SmallPtrSet that PointerIntPair is "basically a pointer".
0243 template <typename PointerTy, unsigned IntBits, typename IntType,
0244           typename PtrTraits>
0245 struct PointerLikeTypeTraits<
0246     PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> {
0247   static inline void *
0248   getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) {
0249     return P.getOpaqueValue();
0250   }
0251
0252   static inline PointerIntPair<PointerTy, IntBits, IntType>
0253   getFromVoidPointer(void *P) {
0254     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
0255   }
0256
0257   static inline PointerIntPair<PointerTy, IntBits, IntType>
0258   getFromVoidPointer(const void *P) {
0259     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
0260   }
0261
0262   static constexpr int NumLowBitsAvailable =
0263       PtrTraits::NumLowBitsAvailable - IntBits;
0264 };
0265
0266 // Allow structured bindings on PointerIntPair.
0267 template <std::size_t I, typename PointerTy, unsigned IntBits, typename IntType,
0268           typename PtrTraits, typename Info>
0269 decltype(auto)
0270 get(const PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info> &Pair) {
0271   static_assert(I < 2);
0272   if constexpr (I == 0)
0273     return Pair.getPointer();
0274   else
0275     return Pair.getInt();
0276 }
0277
0278 } // end namespace llvm
0279
0280 namespace std {
0281 template <typename PointerTy, unsigned IntBits, typename IntType,
0282           typename PtrTraits, typename Info>
0283 struct tuple_size<
0284     llvm::PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>>
0285     : std::integral_constant<std::size_t, 2> {};
0286
0287 template <std::size_t I, typename PointerTy, unsigned IntBits, typename IntType,
0288           typename PtrTraits, typename Info>
0289 struct tuple_element<
0290     I, llvm::PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>>
0291     : std::conditional<I == 0, PointerTy, IntType> {};
0292 } // namespace std
0293
0294 #endif // LLVM_ADT_POINTERINTPAIR_H