Line data Source code
1 : //===- llvm/ADT/PointerUnion.h - Discriminated Union of 2 Ptrs --*- 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 PointerUnion class, which is a discriminated union of
11 : // pointer types.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_ADT_POINTERUNION_H
16 : #define LLVM_ADT_POINTERUNION_H
17 :
18 : #include "llvm/ADT/DenseMapInfo.h"
19 : #include "llvm/ADT/PointerIntPair.h"
20 : #include "llvm/Support/PointerLikeTypeTraits.h"
21 : #include <cassert>
22 : #include <cstddef>
23 : #include <cstdint>
24 :
25 : namespace llvm {
26 :
27 : template <typename T> struct PointerUnionTypeSelectorReturn {
28 : using Return = T;
29 : };
30 :
31 : /// Get a type based on whether two types are the same or not.
32 : ///
33 : /// For:
34 : ///
35 : /// \code
36 : /// using Ret = typename PointerUnionTypeSelector<T1, T2, EQ, NE>::Return;
37 : /// \endcode
38 : ///
39 : /// Ret will be EQ type if T1 is same as T2 or NE type otherwise.
40 : template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
41 : struct PointerUnionTypeSelector {
42 : using Return = typename PointerUnionTypeSelectorReturn<RET_NE>::Return;
43 : };
44 :
45 : template <typename T, typename RET_EQ, typename RET_NE>
46 : struct PointerUnionTypeSelector<T, T, RET_EQ, RET_NE> {
47 : using Return = typename PointerUnionTypeSelectorReturn<RET_EQ>::Return;
48 : };
49 :
50 : template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
51 : struct PointerUnionTypeSelectorReturn<
52 : PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>> {
53 : using Return =
54 : typename PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>::Return;
55 : };
56 :
57 : /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
58 : /// for the two template arguments.
59 : template <typename PT1, typename PT2> class PointerUnionUIntTraits {
60 : public:
61 : static inline void *getAsVoidPointer(void *P) { return P; }
62 : static inline void *getFromVoidPointer(void *P) { return P; }
63 :
64 : enum {
65 : PT1BitsAv = (int)(PointerLikeTypeTraits<PT1>::NumLowBitsAvailable),
66 : PT2BitsAv = (int)(PointerLikeTypeTraits<PT2>::NumLowBitsAvailable),
67 : NumLowBitsAvailable = PT1BitsAv < PT2BitsAv ? PT1BitsAv : PT2BitsAv
68 : };
69 : };
70 :
71 : /// A discriminated union of two pointer types, with the discriminator in the
72 : /// low bit of the pointer.
73 : ///
74 : /// This implementation is extremely efficient in space due to leveraging the
75 : /// low bits of the pointer, while exposing a natural and type-safe API.
76 : ///
77 : /// Common use patterns would be something like this:
78 : /// PointerUnion<int*, float*> P;
79 : /// P = (int*)0;
80 : /// printf("%d %d", P.is<int*>(), P.is<float*>()); // prints "1 0"
81 : /// X = P.get<int*>(); // ok.
82 : /// Y = P.get<float*>(); // runtime assertion failure.
83 : /// Z = P.get<double*>(); // compile time failure.
84 : /// P = (float*)0;
85 : /// Y = P.get<float*>(); // ok.
86 : /// X = P.get<int*>(); // runtime assertion failure.
87 : template <typename PT1, typename PT2> class PointerUnion {
88 : public:
89 : using ValTy =
90 : PointerIntPair<void *, 1, bool, PointerUnionUIntTraits<PT1, PT2>>;
91 :
92 : private:
93 : ValTy Val;
94 :
95 : struct IsPT1 {
96 : static const int Num = 0;
97 : };
98 : struct IsPT2 {
99 : static const int Num = 1;
100 : };
101 : template <typename T> struct UNION_DOESNT_CONTAIN_TYPE {};
102 :
103 : public:
104 : PointerUnion() = default;
105 : PointerUnion(PT1 V)
106 : : Val(const_cast<void *>(
107 : PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) {}
108 : PointerUnion(PT2 V)
109 : : Val(const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)),
110 : 1) {}
111 :
112 : /// Test if the pointer held in the union is null, regardless of
113 : /// which type it is.
114 : bool isNull() const {
115 : // Convert from the void* to one of the pointer types, to make sure that
116 : // we recursively strip off low bits if we have a nested PointerUnion.
117 1753293993 : return !PointerLikeTypeTraits<PT1>::getFromVoidPointer(Val.getPointer());
118 : }
119 :
120 66744681 : explicit operator bool() const { return !isNull(); }
121 :
122 : /// Test if the Union currently holds the type matching T.
123 : template <typename T> int is() const {
124 : using Ty = typename ::llvm::PointerUnionTypeSelector<
125 : PT1, T, IsPT1,
126 : ::llvm::PointerUnionTypeSelector<PT2, T, IsPT2,
127 : UNION_DOESNT_CONTAIN_TYPE<T>>>::Return;
128 : int TyNo = Ty::Num;
129 36269323456 : return static_cast<int>(Val.getInt()) == TyNo;
130 : }
131 :
132 : /// Returns the value of the specified pointer type.
133 : ///
134 : /// If the specified pointer type is incorrect, assert.
135 : template <typename T> T get() const {
136 : assert(is<T>() && "Invalid accessor called");
137 2734678215 : return PointerLikeTypeTraits<T>::getFromVoidPointer(Val.getPointer());
138 : }
139 :
140 : /// Returns the current pointer if it is of the specified pointer type,
141 : /// otherwises returns null.
142 : template <typename T> T dyn_cast() const {
143 7469398924 : if (is<T>())
144 : return get<T>();
145 : return T();
146 : }
147 :
148 : /// If the union is set to the first pointer type get an address pointing to
149 : /// it.
150 : PT1 const *getAddrOfPtr1() const {
151 : return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
152 : }
153 :
154 : /// If the union is set to the first pointer type get an address pointing to
155 : /// it.
156 : PT1 *getAddrOfPtr1() {
157 : assert(is<PT1>() && "Val is not the first pointer");
158 : assert(
159 : get<PT1>() == Val.getPointer() &&
160 : "Can't get the address because PointerLikeTypeTraits changes the ptr");
161 : return const_cast<PT1 *>(
162 : reinterpret_cast<const PT1 *>(Val.getAddrOfPointer()));
163 : }
164 :
165 : /// Assignment from nullptr which just clears the union.
166 0 : const PointerUnion &operator=(std::nullptr_t) {
167 : Val.initWithPointer(nullptr);
168 0 : return *this;
169 : }
170 :
171 : /// Assignment operators - Allow assigning into this union from either
172 : /// pointer type, setting the discriminator to remember what it came from.
173 0 : const PointerUnion &operator=(const PT1 &RHS) {
174 0 : Val.initWithPointer(
175 0 : const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(RHS)));
176 0 : return *this;
177 : }
178 0 : const PointerUnion &operator=(const PT2 &RHS) {
179 0 : Val.setPointerAndInt(
180 0 : const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(RHS)),
181 0 : 1);
182 0 : return *this;
183 0 : }
184 0 :
185 119203094 : void *getOpaqueValue() const { return Val.getOpaqueValue(); }
186 0 : static inline PointerUnion getFromOpaqueValue(void *VP) {
187 : PointerUnion V;
188 0 : V.Val = ValTy::getFromOpaqueValue(VP);
189 0 : return V;
190 0 : }
191 0 : };
192 0 :
193 0 : template <typename PT1, typename PT2>
194 0 : bool operator==(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
195 3 : return lhs.getOpaqueValue() == rhs.getOpaqueValue();
196 0 : }
197 12 :
198 0 : template <typename PT1, typename PT2>
199 0 : bool operator!=(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
200 2 : return lhs.getOpaqueValue() != rhs.getOpaqueValue();
201 0 : }
202 :
203 0 : template <typename PT1, typename PT2>
204 0 : bool operator<(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
205 0 : return lhs.getOpaqueValue() < rhs.getOpaqueValue();
206 0 : }
207 74112 :
208 0 : // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
209 0 : // # low bits available = min(PT1bits,PT2bits)-1.
210 0 : template <typename PT1, typename PT2>
211 0 : struct PointerLikeTypeTraits<PointerUnion<PT1, PT2>> {
212 0 : static inline void *getAsVoidPointer(const PointerUnion<PT1, PT2> &P) {
213 0 : return P.getOpaqueValue();
214 0 : }
215 0 :
216 0 : static inline PointerUnion<PT1, PT2> getFromVoidPointer(void *P) {
217 : return PointerUnion<PT1, PT2>::getFromOpaqueValue(P);
218 0 : }
219 0 :
220 : // The number of bits available are the min of the two pointer types.
221 0 : enum {
222 0 : NumLowBitsAvailable = PointerLikeTypeTraits<
223 0 : typename PointerUnion<PT1, PT2>::ValTy>::NumLowBitsAvailable
224 0 : };
225 0 : };
226 0 :
227 0 : /// A pointer union of three pointer types. See documentation for PointerUnion
228 0 : /// for usage.
229 0 : template <typename PT1, typename PT2, typename PT3> class PointerUnion3 {
230 : public:
231 0 : using InnerUnion = PointerUnion<PT1, PT2>;
232 : using ValTy = PointerUnion<InnerUnion, PT3>;
233 0 :
234 0 : private:
235 : ValTy Val;
236 :
237 0 : struct IsInnerUnion {
238 : ValTy Val;
239 0 :
240 0 : IsInnerUnion(ValTy val) : Val(val) {}
241 :
242 : template <typename T> int is() const {
243 29040824 : return Val.template is<InnerUnion>() &&
244 : Val.template get<InnerUnion>().template is<T>();
245 0 : }
246 0 :
247 : template <typename T> T get() const {
248 : return Val.template get<InnerUnion>().template get<T>();
249 0 : }
250 : };
251 0 :
252 0 : struct IsPT3 {
253 9972339 : ValTy Val;
254 :
255 421 : IsPT3(ValTy val) : Val(val) {}
256 :
257 0 : template <typename T> int is() const { return Val.template is<T>(); }
258 0 : template <typename T> T get() const { return Val.template get<T>(); }
259 : };
260 :
261 0 : public:
262 : PointerUnion3() = default;
263 25765123 : PointerUnion3(PT1 V) { Val = InnerUnion(V); }
264 1592 : PointerUnion3(PT2 V) { Val = InnerUnion(V); }
265 2503282 : PointerUnion3(PT3 V) { Val = V; }
266 :
267 0 : /// Test if the pointer held in the union is null, regardless of
268 : /// which type it is.
269 0 : bool isNull() const { return Val.isNull(); }
270 51 : explicit operator bool() const { return !isNull(); }
271 :
272 : /// Test if the Union currently holds the type matching T.
273 0 : template <typename T> int is() const {
274 : // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
275 0 : using Ty = typename ::llvm::PointerUnionTypeSelector<
276 2160322 : PT1, T, IsInnerUnion,
277 6149391 : ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return;
278 : return Ty(Val).template is<T>();
279 0 : }
280 :
281 0 : /// Returns the value of the specified pointer type.
282 0 : ///
283 : /// If the specified pointer type is incorrect, assert.
284 : template <typename T> T get() const {
285 501796 : assert(is<T>() && "Invalid accessor called");
286 2016433 : // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
287 3745 : using Ty = typename ::llvm::PointerUnionTypeSelector<
288 0 : PT1, T, IsInnerUnion,
289 10903446 : ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return;
290 : return Ty(Val).template get<T>();
291 0 : }
292 0 :
293 0 : /// Returns the current pointer if it is of the specified pointer type,
294 0 : /// otherwises returns null.
295 : template <typename T> T dyn_cast() const {
296 4436058 : if (is<T>())
297 2 : return get<T>();
298 : return T();
299 0 : }
300 0 :
301 : /// Assignment from nullptr which just clears the union.
302 : const PointerUnion3 &operator=(std::nullptr_t) {
303 0 : Val = nullptr;
304 : return *this;
305 0 : }
306 428639 :
307 : /// Assignment operators - Allow assigning into this union from either
308 122 : /// pointer type, setting the discriminator to remember what it came from.
309 2415287 : const PointerUnion3 &operator=(const PT1 &RHS) {
310 3733957 : Val = InnerUnion(RHS);
311 134 : return *this;
312 : }
313 0 : const PointerUnion3 &operator=(const PT2 &RHS) {
314 0 : Val = InnerUnion(RHS);
315 0 : return *this;
316 : }
317 0 : const PointerUnion3 &operator=(const PT3 &RHS) {
318 33 : Val = RHS;
319 0 : return *this;
320 : }
321 :
322 : void *getOpaqueValue() const { return Val.getOpaqueValue(); }
323 0 : static inline PointerUnion3 getFromOpaqueValue(void *VP) {
324 : PointerUnion3 V;
325 : V.Val = ValTy::getFromOpaqueValue(VP);
326 : return V;
327 : }
328 : };
329 757377 :
330 0 : // Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has
331 : // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
332 : template <typename PT1, typename PT2, typename PT3>
333 : struct PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3>> {
334 : static inline void *getAsVoidPointer(const PointerUnion3<PT1, PT2, PT3> &P) {
335 : return P.getOpaqueValue();
336 : }
337 :
338 : static inline PointerUnion3<PT1, PT2, PT3> getFromVoidPointer(void *P) {
339 0 : return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P);
340 : }
341 :
342 10809618 : // The number of bits available are the min of the two pointer types.
343 0 : enum {
344 0 : NumLowBitsAvailable = PointerLikeTypeTraits<
345 0 : typename PointerUnion3<PT1, PT2, PT3>::ValTy>::NumLowBitsAvailable
346 0 : };
347 0 : };
348 0 :
349 : template <typename PT1, typename PT2, typename PT3>
350 0 : bool operator<(PointerUnion3<PT1, PT2, PT3> lhs,
351 0 : PointerUnion3<PT1, PT2, PT3> rhs) {
352 0 : return lhs.getOpaqueValue() < rhs.getOpaqueValue();
353 : }
354 :
355 0 : /// A pointer union of four pointer types. See documentation for PointerUnion
356 0 : /// for usage.
357 0 : template <typename PT1, typename PT2, typename PT3, typename PT4>
358 : class PointerUnion4 {
359 0 : public:
360 0 : using InnerUnion1 = PointerUnion<PT1, PT2>;
361 0 : using InnerUnion2 = PointerUnion<PT3, PT4>;
362 : using ValTy = PointerUnion<InnerUnion1, InnerUnion2>;
363 0 :
364 823 : private:
365 0 : ValTy Val;
366 :
367 0 : public:
368 0 : PointerUnion4() = default;
369 95934953 : PointerUnion4(PT1 V) { Val = InnerUnion1(V); }
370 2127354 : PointerUnion4(PT2 V) { Val = InnerUnion1(V); }
371 1200733 : PointerUnion4(PT3 V) { Val = InnerUnion2(V); }
372 660848 : PointerUnion4(PT4 V) { Val = InnerUnion2(V); }
373 0 :
374 : /// Test if the pointer held in the union is null, regardless of
375 0 : /// which type it is.
376 0 : bool isNull() const { return Val.isNull(); }
377 0 : explicit operator bool() const { return !isNull(); }
378 :
379 0 : /// Test if the Union currently holds the type matching T.
380 0 : template <typename T> int is() const {
381 0 : // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
382 : using Ty = typename ::llvm::PointerUnionTypeSelector<
383 0 : PT1, T, InnerUnion1,
384 0 : ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1,
385 0 : InnerUnion2>>::Return;
386 984868146 : return Val.template is<Ty>() && Val.template get<Ty>().template is<T>();
387 0 : }
388 0 :
389 0 : /// Returns the value of the specified pointer type.
390 : ///
391 : /// If the specified pointer type is incorrect, assert.
392 : template <typename T> T get() const {
393 : assert(is<T>() && "Invalid accessor called");
394 : // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
395 : using Ty = typename ::llvm::PointerUnionTypeSelector<
396 : PT1, T, InnerUnion1,
397 : ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1,
398 : InnerUnion2>>::Return;
399 : return Val.template get<Ty>().template get<T>();
400 : }
401 :
402 : /// Returns the current pointer if it is of the specified pointer type,
403 : /// otherwises returns null.
404 : template <typename T> T dyn_cast() const {
405 : if (is<T>())
406 : return get<T>();
407 : return T();
408 214890 : }
409 :
410 : /// Assignment from nullptr which just clears the union.
411 0 : const PointerUnion4 &operator=(std::nullptr_t) {
412 : Val = nullptr;
413 0 : return *this;
414 : }
415 :
416 : /// Assignment operators - Allow assigning into this union from either
417 : /// pointer type, setting the discriminator to remember what it came from.
418 0 : const PointerUnion4 &operator=(const PT1 &RHS) {
419 0 : Val = InnerUnion1(RHS);
420 0 : return *this;
421 : }
422 0 : const PointerUnion4 &operator=(const PT2 &RHS) {
423 0 : Val = InnerUnion1(RHS);
424 0 : return *this;
425 : }
426 0 : const PointerUnion4 &operator=(const PT3 &RHS) {
427 0 : Val = InnerUnion2(RHS);
428 0 : return *this;
429 846510113 : }
430 0 : const PointerUnion4 &operator=(const PT4 &RHS) {
431 0 : Val = InnerUnion2(RHS);
432 0 : return *this;
433 : }
434 :
435 : void *getOpaqueValue() const { return Val.getOpaqueValue(); }
436 0 : static inline PointerUnion4 getFromOpaqueValue(void *VP) {
437 0 : PointerUnion4 V;
438 0 : V.Val = ValTy::getFromOpaqueValue(VP);
439 : return V;
440 0 : }
441 0 : };
442 0 :
443 : // Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has
444 0 : // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
445 0 : template <typename PT1, typename PT2, typename PT3, typename PT4>
446 0 : struct PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4>> {
447 : static inline void *
448 0 : getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) {
449 0 : return P.getOpaqueValue();
450 0 : }
451 :
452 0 : static inline PointerUnion4<PT1, PT2, PT3, PT4> getFromVoidPointer(void *P) {
453 0 : return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P);
454 0 : }
455 :
456 0 : // The number of bits available are the min of the two pointer types.
457 0 : enum {
458 0 : NumLowBitsAvailable = PointerLikeTypeTraits<
459 : typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy>::NumLowBitsAvailable
460 0 : };
461 0 : };
462 0 :
463 0 : // Teach DenseMap how to use PointerUnions as keys.
464 0 : template <typename T, typename U> struct DenseMapInfo<PointerUnion<T, U>> {
465 0 : using Pair = PointerUnion<T, U>;
466 0 : using FirstInfo = DenseMapInfo<T>;
467 0 : using SecondInfo = DenseMapInfo<U>;
468 0 :
469 0 : static inline Pair getEmptyKey() { return Pair(FirstInfo::getEmptyKey()); }
470 0 :
471 0 : static inline Pair getTombstoneKey() {
472 0 : return Pair(FirstInfo::getTombstoneKey());
473 0 : }
474 0 :
475 0 : static unsigned getHashValue(const Pair &PairVal) {
476 0 : intptr_t key = (intptr_t)PairVal.getOpaqueValue();
477 0 : return DenseMapInfo<intptr_t>::getHashValue(key);
478 0 : }
479 :
480 15674633 : static bool isEqual(const Pair &LHS, const Pair &RHS) {
481 15674633 : return LHS.template is<T>() == RHS.template is<T>() &&
482 163475 : (LHS.template is<T>() ? FirstInfo::isEqual(LHS.template get<T>(),
483 : RHS.template get<T>())
484 : : SecondInfo::isEqual(LHS.template get<U>(),
485 15674633 : RHS.template get<U>()));
486 : }
487 : };
488 :
489 : } // end namespace llvm
490 :
491 : #endif // LLVM_ADT_POINTERUNION_H
|
