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