Branch data Line data Source code
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 : 0 : explicit constexpr PunnedPointer(intptr_t i = 0) { *this = i; }
38 : :
39 : 0 : constexpr intptr_t asInt() const {
40 : 0 : intptr_t R = 0;
41 : 0 : std::memcpy(&R, Data, sizeof(R));
42 : 0 : return R;
43 : : }
44 : :
45 : 0 : constexpr operator intptr_t() const { return asInt(); }
46 : :
47 : 0 : constexpr PunnedPointer &operator=(intptr_t V) {
48 : 0 : std::memcpy(Data, &V, sizeof(Data));
49 : 0 : 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 : 0 : constexpr PointerIntPair() = default;
87 : :
88 : 0 : PointerIntPair(PointerTy PtrVal, IntType IntVal) {
89 : 0 : setPointerAndInt(PtrVal, IntVal);
90 : 0 : }
91 : :
92 : : explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); }
93 : :
94 : 0 : PointerTy getPointer() const { return Info::getPointer(Value); }
95 : :
96 : 0 : IntType getInt() const { return (IntType)Info::getInt(Value); }
97 : :
98 : 0 : void setPointer(PointerTy PtrVal) & {
99 : 0 : Value = Info::updatePointer(Value, PtrVal);
100 : 0 : }
101 : :
102 : 0 : void setInt(IntType IntVal) & {
103 : 0 : Value = Info::updateInt(Value, static_cast<intptr_t>(IntVal));
104 : 0 : }
105 : :
106 : : void initWithPointer(PointerTy PtrVal) & {
107 : : Value = Info::updatePointer(0, PtrVal);
108 : : }
109 : :
110 : 0 : void setPointerAndInt(PointerTy PtrVal, IntType IntVal) & {
111 : 0 : Value = Info::updateInt(Info::updatePointer(0, PtrVal),
112 : : static_cast<intptr_t>(IntVal));
113 : 0 : }
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 : 0 : void *getOpaqueValue() const {
127 : 0 : return reinterpret_cast<void *>(Value.asInt());
128 : : }
129 : :
130 : 0 : void setFromOpaqueValue(void *Val) & {
131 : 0 : Value = reinterpret_cast<intptr_t>(Val);
132 : 0 : }
133 : :
134 : 0 : static PointerIntPair getFromOpaqueValue(void *V) {
135 [ # # ]: 0 : PointerIntPair P;
136 : 0 : P.setFromOpaqueValue(V);
137 : 0 : 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 : 0 : static PointerT getPointer(intptr_t Value) {
191 : 0 : return PtrTraits::getFromVoidPointer(
192 : 0 : reinterpret_cast<void *>(Value & PointerBitMask));
193 : : }
194 : :
195 : 0 : static intptr_t getInt(intptr_t Value) {
196 : 0 : return (Value >> IntShift) & IntMask;
197 : : }
198 : :
199 : 0 : static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) {
200 : 0 : intptr_t PtrWord =
201 : 0 : reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr));
202 [ # # ]: 0 : assert((PtrWord & ~PointerBitMask) == 0 &&
203 : : "Pointer is not sufficiently aligned");
204 : : // Preserve all low bits, just update the pointer.
205 : 0 : return PtrWord | (OrigValue & ~PointerBitMask);
206 : : }
207 : :
208 : 0 : static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) {
209 : 0 : intptr_t IntWord = static_cast<intptr_t>(Int);
210 [ # # ]: 0 : assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
211 : :
212 : : // Preserve all bits other than the ones we are updating.
213 : 0 : 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
|
