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