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