Line data Source code
1 : //===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
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/PointerLikeTypeTraits.h"
18 : #include <cassert>
19 : #include <cstdint>
20 : #include <limits>
21 :
22 : namespace llvm {
23 :
24 : template <typename T> struct DenseMapInfo;
25 : template <typename PointerT, unsigned IntBits, typename PtrTraits>
26 : struct PointerIntPairInfo;
27 :
28 : /// PointerIntPair - This class implements a pair of a pointer and small
29 : /// integer. It is designed to represent this in the space required by one
30 : /// pointer by bitmangling the integer into the low part of the pointer. This
31 : /// can only be done for small integers: typically up to 3 bits, but it depends
32 : /// on the number of bits available according to PointerLikeTypeTraits for the
33 : /// type.
34 : ///
35 : /// Note that PointerIntPair always puts the IntVal part in the highest bits
36 : /// possible. For example, PointerIntPair<void*, 1, bool> will put the bit for
37 : /// the bool into bit #2, not bit #0, which allows the low two bits to be used
38 : /// for something else. For example, this allows:
39 : /// PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool>
40 : /// ... and the two bools will land in different bits.
41 : template <typename PointerTy, unsigned IntBits, typename IntType = unsigned,
42 : typename PtrTraits = PointerLikeTypeTraits<PointerTy>,
43 : typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>>
44 : class PointerIntPair {
45 : intptr_t Value = 0;
46 :
47 : public:
48 1411293652 : constexpr PointerIntPair() = default;
49 :
50 1696653978 : PointerIntPair(PointerTy PtrVal, IntType IntVal) {
51 : setPointerAndInt(PtrVal, IntVal);
52 : }
53 :
54 443767504 : explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); }
55 :
56 0 : PointerTy getPointer() const { return Info::getPointer(Value); }
57 :
58 12364328196 : IntType getInt() const { return (IntType)Info::getInt(Value); }
59 :
60 0 : void setPointer(PointerTy PtrVal) {
61 2299941655 : Value = Info::updatePointer(Value, PtrVal);
62 0 : }
63 0 :
64 0 : void setInt(IntType IntVal) {
65 50449438 : Value = Info::updateInt(Value, static_cast<intptr_t>(IntVal));
66 0 : }
67 0 :
68 0 : void initWithPointer(PointerTy PtrVal) {
69 1018202128 : Value = Info::updatePointer(0, PtrVal);
70 0 : }
71 37559357 :
72 0 : void setPointerAndInt(PointerTy PtrVal, IntType IntVal) {
73 900176076 : Value = Info::updateInt(Info::updatePointer(0, PtrVal),
74 502834 : static_cast<intptr_t>(IntVal));
75 490926 : }
76 0 :
77 462513 : PointerTy const *getAddrOfPointer() const {
78 63107 : return const_cast<PointerIntPair *>(this)->getAddrOfPointer();
79 270253864 : }
80 72 :
81 282905 : PointerTy *getAddrOfPointer() {
82 60489007 : assert(Value == reinterpret_cast<intptr_t>(getPointer()) &&
83 51956 : "Can only return the address if IntBits is cleared and "
84 10146060 : "PtrTraits doesn't change the pointer");
85 1233599648 : return reinterpret_cast<PointerTy *>(&Value);
86 0 : }
87 29139708 :
88 728425378 : void *getOpaqueValue() const { return reinterpret_cast<void *>(Value); }
89 0 :
90 8674 : void setFromOpaqueValue(void *Val) {
91 474655629 : Value = reinterpret_cast<intptr_t>(Val);
92 0 : }
93 1885471 :
94 1682312152 : static PointerIntPair getFromOpaqueValue(void *V) {
95 112376 : PointerIntPair P;
96 0 : P.setFromOpaqueValue(V);
97 984213494 : return P;
98 0 : }
99 0 :
100 84983100 : // Allow PointerIntPairs to be created from const void * if and only if the
101 0 : // pointer type could be created from a const void *.
102 112093069 : static PointerIntPair getFromOpaqueValue(const void *V) {
103 204749222 : (void)PtrTraits::getFromVoidPointer(V);
104 7585 : return getFromOpaqueValue(const_cast<void *>(V));
105 17072083 : }
106 7086933 :
107 0 : bool operator==(const PointerIntPair &RHS) const {
108 8407174 : return Value == RHS.Value;
109 10779458 : }
110 1627 :
111 22197053 : bool operator!=(const PointerIntPair &RHS) const {
112 6198 : return Value != RHS.Value;
113 5320 : }
114 2191007 :
115 56953 : bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; }
116 1509 : bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; }
117 83655062 :
118 41050038 : bool operator<=(const PointerIntPair &RHS) const {
119 5266 : return Value <= RHS.Value;
120 89 : }
121 902 :
122 268396 : bool operator>=(const PointerIntPair &RHS) const {
123 0 : return Value >= RHS.Value;
124 21090875 : }
125 0 : };
126 37325625 :
127 3161327 : template <typename PointerT, unsigned IntBits, typename PtrTraits>
128 0 : struct PointerIntPairInfo {
129 260723184 : static_assert(PtrTraits::NumLowBitsAvailable <
130 0 : std::numeric_limits<uintptr_t>::digits,
131 19821657 : "cannot use a pointer type that has all bits free");
132 277967226 : static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
133 0 : "PointerIntPair with integer size too large for pointer");
134 718611350 : enum : uintptr_t {
135 256438 : /// PointerBitMask - The bits that come from the pointer.
136 458553942 : PointerBitMask =
137 72412275 : ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1),
138 3976 :
139 0 : /// IntShift - The number of low bits that we reserve for other uses, and
140 13700721 : /// keep zero.
141 8132055 : IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits,
142 0 :
143 101755180 : /// IntMask - This is the unshifted mask for valid bits of the int type.
144 21807788 : IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1),
145 3987204 :
146 4047767 : // ShiftedIntMask - This is the bits for the integer shifted in place.
147 201854 : ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
148 186503567 : };
149 902 :
150 46420061 : static PointerT getPointer(intptr_t Value) {
151 2393468891 : return PtrTraits::getFromVoidPointer(
152 5247865218 : reinterpret_cast<void *>(Value & PointerBitMask));
153 33763658 : }
154 0 :
155 0 : static intptr_t getInt(intptr_t Value) {
156 6751430078 : return (Value >> IntShift) & IntMask;
157 500415524 : }
158 1725729318 :
159 264547698 : static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) {
160 55454014 : intptr_t PtrWord =
161 43412348 : reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr));
162 2800172823 : assert((PtrWord & ~PointerBitMask) == 0 &&
163 108461074 : "Pointer is not sufficiently aligned");
164 233108902 : // Preserve all low bits, just update the pointer.
165 772147058 : return PtrWord | (OrigValue & ~PointerBitMask);
166 303620273 : }
167 327900713 :
168 157309105 : static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) {
169 434412620 : intptr_t IntWord = static_cast<intptr_t>(Int);
170 1059870750 : assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
171 899730662 :
172 387397501 : // Preserve all bits other than the ones we are updating.
173 14754363191 : return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift;
174 1528865840 : }
175 144519193 : };
176 48781496 :
177 14703859846 : template <typename T> struct isPodLike;
178 1756626032 : template <typename PointerTy, unsigned IntBits, typename IntType>
179 1276579372 : struct isPodLike<PointerIntPair<PointerTy, IntBits, IntType>> {
180 1624218178 : static const bool value = true;
181 13510665 : };
182 2093899520 :
183 1533720395 : // Provide specialization of DenseMapInfo for PointerIntPair.
184 2831017341 : template <typename PointerTy, unsigned IntBits, typename IntType>
185 967436126 : struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>> {
186 810585480 : using Ty = PointerIntPair<PointerTy, IntBits, IntType>;
187 13607476 :
188 2895836067 : static Ty getEmptyKey() {
189 1440842090 : uintptr_t Val = static_cast<uintptr_t>(-1);
190 94455421 : Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable;
191 806819619 : return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
192 52571994 : }
193 1264149 :
194 494870247 : static Ty getTombstoneKey() {
195 192108128 : uintptr_t Val = static_cast<uintptr_t>(-2);
196 143804616 : Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
197 1899310964 : return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
198 1357742404 : }
199 114980535 :
200 436681463 : static unsigned getHashValue(Ty V) {
201 361675112 : uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue());
202 100035778 : return unsigned(IV) ^ unsigned(IV >> 9);
203 413483538 : }
204 2854233 :
205 187078204 : static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; }
206 68493690 : };
207 1040654 :
208 1435683 : // Teach SmallPtrSet that PointerIntPair is "basically a pointer".
209 12897599 : template <typename PointerTy, unsigned IntBits, typename IntType,
210 2424869 : typename PtrTraits>
211 16018678 : struct PointerLikeTypeTraits<
212 12589812 : PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> {
213 1969514 : static inline void *
214 2103180 : getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) {
215 65965168 : return P.getOpaqueValue();
216 16267 : }
217 219512443 :
218 219570329 : static inline PointerIntPair<PointerTy, IntBits, IntType>
219 430284150 : getFromVoidPointer(void *P) {
220 590679395 : return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
221 110853581 : }
222 77498924 :
223 387673532 : static inline PointerIntPair<PointerTy, IntBits, IntType>
224 3582771377 : getFromVoidPointer(const void *P) {
225 928644309 : return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
226 186 : }
227 507326921 :
228 4291184587 : enum { NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits };
229 1162786075 : };
230 1328896 :
231 798648273 : } // end namespace llvm
232 0 :
233 53904463 : #endif // LLVM_ADT_POINTERINTPAIR_H
|
