LLVM 20.0.0git
PointerIntPair.h
Go to the documentation of this file.
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
20#include <cassert>
21#include <cstdint>
22#include <cstring>
23#include <limits>
24
25namespace llvm {
26
27namespace detail {
28template <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
55private:
56 alignas(Ptr) unsigned char Data[sizeof(Ptr)];
57};
58} // namespace detail
59
60template <typename T, typename Enable> struct DenseMapInfo;
61template <typename PointerT, unsigned IntBits, typename PtrTraits>
62struct 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.
77template <typename PointerTy, unsigned IntBits, typename IntType = unsigned,
78 typename PtrTraits = PointerLikeTypeTraits<PointerTy>,
79 typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>>
81 // Used by MSVC visualizer and generally helpful for debugging/visualizing.
82 using InfoTy = Info;
84
85public:
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
116 return const_cast<PointerIntPair *>(this)->getAddrOfPointer();
117 }
118
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
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
167template <typename PointerT, unsigned IntBits, typename PtrTraits>
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.
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.
218template <typename PointerTy, unsigned IntBits, typename IntType>
219struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>, void> {
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
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".
243template <typename PointerTy, unsigned IntBits, typename IntType,
244 typename PtrTraits>
246 PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> {
247 static inline void *
249 return P.getOpaqueValue();
250 }
251
255 }
256
258 getFromVoidPointer(const void *P) {
260 }
261
262 static constexpr int NumLowBitsAvailable =
263 PtrTraits::NumLowBitsAvailable - IntBits;
264};
265
266// Allow structured bindings on PointerIntPair.
267template <std::size_t I, typename PointerTy, unsigned IntBits, typename IntType,
268 typename PtrTraits, typename Info>
269decltype(auto)
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
280namespace std {
281template <typename PointerTy, unsigned IntBits, typename IntType,
282 typename PtrTraits, typename Info>
283struct tuple_size<
284 llvm::PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>>
285 : std::integral_constant<std::size_t, 2> {};
286
287template <std::size_t I, typename PointerTy, unsigned IntBits, typename IntType,
288 typename PtrTraits, typename Info>
289struct 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
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition: blake3_impl.h:78
PointerIntPair - This class implements a pair of a pointer and small integer.
bool operator<(const PointerIntPair &RHS) const
void setPointer(PointerTy PtrVal) &
PointerIntPair(PointerTy PtrVal)
bool operator!=(const PointerIntPair &RHS) const
static PointerIntPair getFromOpaqueValue(const void *V)
bool operator==(const PointerIntPair &RHS) const
PointerIntPair(PointerTy PtrVal, IntType IntVal)
void initWithPointer(PointerTy PtrVal) &
IntType getInt() const
bool operator<=(const PointerIntPair &RHS) const
void setInt(IntType IntVal) &
void setPointerAndInt(PointerTy PtrVal, IntType IntVal) &
void * getOpaqueValue() const
constexpr PointerIntPair()=default
bool operator>=(const PointerIntPair &RHS) const
static PointerIntPair getFromOpaqueValue(void *V)
PointerTy * getAddrOfPointer()
bool operator>(const PointerIntPair &RHS) const
PointerTy const * getAddrOfPointer() const
PointerTy getPointer() const
void setFromOpaqueValue(void *Val) &
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void * PointerTy
Definition: GenericValue.h:21
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:52
static PointerT getPointer(intptr_t Value)
static intptr_t updateInt(intptr_t OrigValue, intptr_t Int)
static intptr_t getInt(intptr_t Value)
@ IntShift
IntShift - The number of low bits that we reserve for other uses, and keep zero.
@ PointerBitMask
PointerBitMask - The bits that come from the pointer.
@ IntMask
IntMask - This is the unshifted mask for valid bits of the int type.
static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr)
static void * getAsVoidPointer(const PointerIntPair< PointerTy, IntBits, IntType > &P)
static PointerIntPair< PointerTy, IntBits, IntType > getFromVoidPointer(void *P)
static PointerIntPair< PointerTy, IntBits, IntType > getFromVoidPointer(const void *P)
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
constexpr intptr_t asInt() const
constexpr PunnedPointer(intptr_t i=0)
const Ptr * getPointerAddress() const
constexpr PunnedPointer & operator=(intptr_t V)