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 /// \file
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 "llvm/Support/type_traits.h"
20 #include <cassert>
21 #include <cstdint>
22 #include <cstring>
23 #include <limits>
24 
25 namespace llvm {
26 
27 namespace detail {
28 template <typename Ptr> struct PunnedPointer {
29   static_assert(sizeof(Ptr) == sizeof(intptr_t), "");
30 
31   // Asserts that allow us to let the compiler implement the destructor and
32   // copy/move constructors
33   static_assert(std::is_trivially_destructible<Ptr>::value, "");
34   static_assert(std::is_trivially_copy_constructible<Ptr>::value, "");
35   static_assert(std::is_trivially_move_constructible<Ptr>::value, "");
36 
37   explicit constexpr PunnedPointer(intptr_t i = 0) { *this = i; }
38 
39   constexpr intptr_t asInt() const {
40     intptr_t R = 0;
41     std::memcpy(&R, Data, sizeof(R));
42     return R;
43   }
44 
45   constexpr operator intptr_t() const { return asInt(); }
46 
47   constexpr PunnedPointer &operator=(intptr_t V) {
48     std::memcpy(Data, &V, sizeof(Data));
49     return *this;
50   }
51 
52   Ptr *getPointerAddress() { return reinterpret_cast<Ptr *>(Data); }
53   const Ptr *getPointerAddress() const { return reinterpret_cast<Ptr *>(Data); }
54 
55 private:
56   alignas(Ptr) unsigned char Data[sizeof(Ptr)];
57 };
58 } // namespace detail
59 
60 template <typename T, typename Enable> struct DenseMapInfo;
61 template <typename PointerT, unsigned IntBits, typename PtrTraits>
62 struct PointerIntPairInfo;
63 
64 /// PointerIntPair - This class implements a pair of a pointer and small
65 /// integer.  It is designed to represent this in the space required by one
66 /// pointer by bitmangling the integer into the low part of the pointer.  This
67 /// can only be done for small integers: typically up to 3 bits, but it depends
68 /// on the number of bits available according to PointerLikeTypeTraits for the
69 /// type.
70 ///
71 /// Note that PointerIntPair always puts the IntVal part in the highest bits
72 /// possible.  For example, PointerIntPair<void*, 1, bool> will put the bit for
73 /// the bool into bit #2, not bit #0, which allows the low two bits to be used
74 /// for something else.  For example, this allows:
75 ///   PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool>
76 /// ... and the two bools will land in different bits.
77 template <typename PointerTy, unsigned IntBits, typename IntType = unsigned,
78           typename PtrTraits = PointerLikeTypeTraits<PointerTy>,
79           typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>>
80 class PointerIntPair {
81   // Used by MSVC visualizer and generally helpful for debugging/visualizing.
82   using InfoTy = Info;
83   detail::PunnedPointer<PointerTy> Value;
84 
85 public:
86   constexpr PointerIntPair() = default;
87 
88   PointerIntPair(PointerTy PtrVal, IntType IntVal) {
89     setPointerAndInt(PtrVal, IntVal);
90   }
91 
92   explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); }
93 
94   PointerTy getPointer() const { return Info::getPointer(Value); }
95 
96   IntType getInt() const { return (IntType)Info::getInt(Value); }
97 
98   void setPointer(PointerTy PtrVal) & {
99     Value = Info::updatePointer(Value, PtrVal);
100   }
101 
102   void setInt(IntType IntVal) & {
103     Value = Info::updateInt(Value, static_cast<intptr_t>(IntVal));
104   }
105 
106   void initWithPointer(PointerTy PtrVal) & {
107     Value = Info::updatePointer(0, PtrVal);
108   }
109 
110   void setPointerAndInt(PointerTy PtrVal, IntType IntVal) & {
111     Value = Info::updateInt(Info::updatePointer(0, PtrVal),
112                             static_cast<intptr_t>(IntVal));
113   }
114 
115   PointerTy const *getAddrOfPointer() const {
116     return const_cast<PointerIntPair *>(this)->getAddrOfPointer();
117   }
118 
119   PointerTy *getAddrOfPointer() {
120     assert(Value == reinterpret_cast<intptr_t>(getPointer()) &&
121            "Can only return the address if IntBits is cleared and "
122            "PtrTraits doesn't change the pointer");
123     return Value.getPointerAddress();
124   }
125 
126   void *getOpaqueValue() const {
127     return reinterpret_cast<void *>(Value.asInt());
128   }
129 
130   void setFromOpaqueValue(void *Val) & {
131     Value = reinterpret_cast<intptr_t>(Val);
132   }
133 
134   static PointerIntPair getFromOpaqueValue(void *V) {
135     PointerIntPair P;
136     P.setFromOpaqueValue(V);
137     return P;
138   }
139 
140   // Allow PointerIntPairs to be created from const void * if and only if the
141   // pointer type could be created from a const void *.
142   static PointerIntPair getFromOpaqueValue(const void *V) {
143     (void)PtrTraits::getFromVoidPointer(V);
144     return getFromOpaqueValue(const_cast<void *>(V));
145   }
146 
147   bool operator==(const PointerIntPair &RHS) const {
148     return Value == RHS.Value;
149   }
150 
151   bool operator!=(const PointerIntPair &RHS) const {
152     return Value != RHS.Value;
153   }
154 
155   bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; }
156   bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; }
157 
158   bool operator<=(const PointerIntPair &RHS) const {
159     return Value <= RHS.Value;
160   }
161 
162   bool operator>=(const PointerIntPair &RHS) const {
163     return Value >= RHS.Value;
164   }
165 };
166 
167 template <typename PointerT, unsigned IntBits, typename PtrTraits>
168 struct PointerIntPairInfo {
169   static_assert(PtrTraits::NumLowBitsAvailable <
170                     std::numeric_limits<uintptr_t>::digits,
171                 "cannot use a pointer type that has all bits free");
172   static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
173                 "PointerIntPair with integer size too large for pointer");
174   enum MaskAndShiftConstants : uintptr_t {
175     /// PointerBitMask - The bits that come from the pointer.
176     PointerBitMask =
177         ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1),
178 
179     /// IntShift - The number of low bits that we reserve for other uses, and
180     /// keep zero.
181     IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits,
182 
183     /// IntMask - This is the unshifted mask for valid bits of the int type.
184     IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1),
185 
186     // ShiftedIntMask - This is the bits for the integer shifted in place.
187     ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
188   };
189 
190   static PointerT getPointer(intptr_t Value) {
191     return PtrTraits::getFromVoidPointer(
192         reinterpret_cast<void *>(Value & PointerBitMask));
193   }
194 
195   static intptr_t getInt(intptr_t Value) {
196     return (Value >> IntShift) & IntMask;
197   }
198 
199   static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) {
200     intptr_t PtrWord =
201         reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr));
202     assert((PtrWord & ~PointerBitMask) == 0 &&
203            "Pointer is not sufficiently aligned");
204     // Preserve all low bits, just update the pointer.
205     return PtrWord | (OrigValue & ~PointerBitMask);
206   }
207 
208   static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) {
209     intptr_t IntWord = static_cast<intptr_t>(Int);
210     assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
211 
212     // Preserve all bits other than the ones we are updating.
213     return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift;
214   }
215 };
216 
217 // Provide specialization of DenseMapInfo for PointerIntPair.
218 template <typename PointerTy, unsigned IntBits, typename IntType>
219 struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>, void> {
220   using Ty = PointerIntPair<PointerTy, IntBits, IntType>;
221 
222   static Ty getEmptyKey() {
223     uintptr_t Val = static_cast<uintptr_t>(-1);
224     Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable;
225     return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
226   }
227 
228   static Ty getTombstoneKey() {
229     uintptr_t Val = static_cast<uintptr_t>(-2);
230     Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
231     return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
232   }
233 
234   static unsigned getHashValue(Ty V) {
235     uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue());
236     return unsigned(IV) ^ unsigned(IV >> 9);
237   }
238 
239   static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; }
240 };
241 
242 // Teach SmallPtrSet that PointerIntPair is "basically a pointer".
243 template <typename PointerTy, unsigned IntBits, typename IntType,
244           typename PtrTraits>
245 struct PointerLikeTypeTraits<
246     PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> {
247   static inline void *
248   getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) {
249     return P.getOpaqueValue();
250   }
251 
252   static inline PointerIntPair<PointerTy, IntBits, IntType>
253   getFromVoidPointer(void *P) {
254     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
255   }
256 
257   static inline PointerIntPair<PointerTy, IntBits, IntType>
258   getFromVoidPointer(const void *P) {
259     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
260   }
261 
262   static constexpr int NumLowBitsAvailable =
263       PtrTraits::NumLowBitsAvailable - IntBits;
264 };
265 
266 // Allow structured bindings on PointerIntPair.
267 template <std::size_t I, typename PointerTy, unsigned IntBits, typename IntType,
268           typename PtrTraits, typename Info>
269 decltype(auto)
270 get(const PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info> &Pair) {
271   static_assert(I < 2);
272   if constexpr (I == 0)
273     return Pair.getPointer();
274   else
275     return Pair.getInt();
276 }
277 
278 } // end namespace llvm
279 
280 namespace std {
281 template <typename PointerTy, unsigned IntBits, typename IntType,
282           typename PtrTraits, typename Info>
283 struct tuple_size<
284     llvm::PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>>
285     : std::integral_constant<std::size_t, 2> {};
286 
287 template <std::size_t I, typename PointerTy, unsigned IntBits, typename IntType,
288           typename PtrTraits, typename Info>
289 struct tuple_element<
290     I, llvm::PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>>
291     : std::conditional<I == 0, PointerTy, IntType> {};
292 } // namespace std
293 
294 #endif // LLVM_ADT_POINTERINTPAIR_H
295