LLVM  13.0.0git
PointerUnion.h
Go to the documentation of this file.
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"
20 #include <cassert>
21 #include <cstddef>
22 #include <cstdint>
23 
24 namespace llvm {
25 
26 template <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.
39 template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
42 };
43 
44 template <typename T, typename RET_EQ, typename RET_NE>
45 struct PointerUnionTypeSelector<T, T, RET_EQ, RET_NE> {
47 };
48 
49 template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
51  PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>> {
52  using Return =
54 };
55 
56 namespace pointer_union_detail {
57  /// Determine the number of bits required to store integers with values < n.
58  /// This is ceil(log2(n)).
59  constexpr int bitsRequired(unsigned n) {
60  return n > 1 ? 1 + bitsRequired((n + 1) / 2) : 0;
61  }
62 
63  template <typename... Ts> constexpr int lowBitsAvailable() {
64  return std::min<int>({PointerLikeTypeTraits<Ts>::NumLowBitsAvailable...});
65  }
66 
67  /// Find the index of a type in a list of types. TypeIndex<T, Us...>::Index
68  /// is the index of T in Us, or sizeof...(Us) if T does not appear in the
69  /// list.
70  template <typename T, typename ...Us> struct TypeIndex;
71  template <typename T, typename ...Us> struct TypeIndex<T, T, Us...> {
72  static constexpr int Index = 0;
73  };
74  template <typename T, typename U, typename... Us>
75  struct TypeIndex<T, U, Us...> {
76  static constexpr int Index = 1 + TypeIndex<T, Us...>::Index;
77  };
78  template <typename T> struct TypeIndex<T> {
79  static constexpr int Index = 0;
80  };
81 
82  /// Find the first type in a list of types.
83  template <typename T, typename...> struct GetFirstType {
84  using type = T;
85  };
86 
87  /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
88  /// for the template arguments.
89  template <typename ...PTs> class PointerUnionUIntTraits {
90  public:
91  static inline void *getAsVoidPointer(void *P) { return P; }
92  static inline void *getFromVoidPointer(void *P) { return P; }
93  static constexpr int NumLowBitsAvailable = lowBitsAvailable<PTs...>();
94  };
95 
96  template <typename Derived, typename ValTy, int I, typename ...Types>
98 
99  template <typename Derived, typename ValTy, int I>
100  class PointerUnionMembers<Derived, ValTy, I> {
101  protected:
102  ValTy Val;
103  PointerUnionMembers() = default;
104  PointerUnionMembers(ValTy Val) : Val(Val) {}
105 
106  friend struct PointerLikeTypeTraits<Derived>;
107  };
108 
109  template <typename Derived, typename ValTy, int I, typename Type,
110  typename ...Types>
111  class PointerUnionMembers<Derived, ValTy, I, Type, Types...>
112  : public PointerUnionMembers<Derived, ValTy, I + 1, Types...> {
113  using Base = PointerUnionMembers<Derived, ValTy, I + 1, Types...>;
114  public:
115  using Base::Base;
116  PointerUnionMembers() = default;
118  : Base(ValTy(const_cast<void *>(
119  PointerLikeTypeTraits<Type>::getAsVoidPointer(V)),
120  I)) {}
121 
122  using Base::operator=;
123  Derived &operator=(Type V) {
124  this->Val = ValTy(
125  const_cast<void *>(PointerLikeTypeTraits<Type>::getAsVoidPointer(V)),
126  I);
127  return static_cast<Derived &>(*this);
128  };
129  };
130 }
131 
132 /// A discriminated union of two or more pointer types, with the discriminator
133 /// in the low bit of the pointer.
134 ///
135 /// This implementation is extremely efficient in space due to leveraging the
136 /// low bits of the pointer, while exposing a natural and type-safe API.
137 ///
138 /// Common use patterns would be something like this:
139 /// PointerUnion<int*, float*> P;
140 /// P = (int*)0;
141 /// printf("%d %d", P.is<int*>(), P.is<float*>()); // prints "1 0"
142 /// X = P.get<int*>(); // ok.
143 /// Y = P.get<float*>(); // runtime assertion failure.
144 /// Z = P.get<double*>(); // compile time failure.
145 /// P = (float*)0;
146 /// Y = P.get<float*>(); // ok.
147 /// X = P.get<int*>(); // runtime assertion failure.
148 template <typename... PTs>
151  PointerUnion<PTs...>,
152  PointerIntPair<
153  void *, pointer_union_detail::bitsRequired(sizeof...(PTs)), int,
154  pointer_union_detail::PointerUnionUIntTraits<PTs...>>,
155  0, PTs...> {
156  // The first type is special because we want to directly cast a pointer to a
157  // default-initialized union to a pointer to the first type. But we don't
158  // want PointerUnion to be a 'template <typename First, typename ...Rest>'
159  // because it's much more convenient to have a name for the whole pack. So
160  // split off the first type here.
161  using First = typename pointer_union_detail::GetFirstType<PTs...>::type;
162  using Base = typename PointerUnion::PointerUnionMembers;
163 
164 public:
165  PointerUnion() = default;
166 
167  PointerUnion(std::nullptr_t) : PointerUnion() {}
168  using Base::Base;
169 
170  /// Test if the pointer held in the union is null, regardless of
171  /// which type it is.
172  bool isNull() const { return !this->Val.getPointer(); }
173 
174  explicit operator bool() const { return !isNull(); }
175 
176  /// Test if the Union currently holds the type matching T.
177  template <typename T> bool is() const {
178  constexpr int Index = pointer_union_detail::TypeIndex<T, PTs...>::Index;
179  static_assert(Index < sizeof...(PTs),
180  "PointerUnion::is<T> given type not in the union");
181  return this->Val.getInt() == Index;
182  }
183 
184  /// Returns the value of the specified pointer type.
185  ///
186  /// If the specified pointer type is incorrect, assert.
187  template <typename T> T get() const {
188  assert(is<T>() && "Invalid accessor called");
189  return PointerLikeTypeTraits<T>::getFromVoidPointer(this->Val.getPointer());
190  }
191 
192  /// Returns the current pointer if it is of the specified pointer type,
193  /// otherwise returns null.
194  template <typename T> T dyn_cast() const {
195  if (is<T>())
196  return get<T>();
197  return T();
198  }
199 
200  /// If the union is set to the first pointer type get an address pointing to
201  /// it.
202  First const *getAddrOfPtr1() const {
203  return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
204  }
205 
206  /// If the union is set to the first pointer type get an address pointing to
207  /// it.
208  First *getAddrOfPtr1() {
209  assert(is<First>() && "Val is not the first pointer");
210  assert(
212  this->Val.getPointer() &&
213  "Can't get the address because PointerLikeTypeTraits changes the ptr");
214  return const_cast<First *>(
215  reinterpret_cast<const First *>(this->Val.getAddrOfPointer()));
216  }
217 
218  /// Assignment from nullptr which just clears the union.
219  const PointerUnion &operator=(std::nullptr_t) {
220  this->Val.initWithPointer(nullptr);
221  return *this;
222  }
223 
224  /// Assignment from elements of the union.
225  using Base::operator=;
226 
227  void *getOpaqueValue() const { return this->Val.getOpaqueValue(); }
228  static inline PointerUnion getFromOpaqueValue(void *VP) {
229  PointerUnion V;
230  V.Val = decltype(V.Val)::getFromOpaqueValue(VP);
231  return V;
232  }
233 };
234 
235 template <typename ...PTs>
237  return lhs.getOpaqueValue() == rhs.getOpaqueValue();
238 }
239 
240 template <typename ...PTs>
242  return lhs.getOpaqueValue() != rhs.getOpaqueValue();
243 }
244 
245 template <typename ...PTs>
247  return lhs.getOpaqueValue() < rhs.getOpaqueValue();
248 }
249 
250 // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
251 // # low bits available = min(PT1bits,PT2bits)-1.
252 template <typename ...PTs>
254  static inline void *getAsVoidPointer(const PointerUnion<PTs...> &P) {
255  return P.getOpaqueValue();
256  }
257 
258  static inline PointerUnion<PTs...> getFromVoidPointer(void *P) {
260  }
261 
262  // The number of bits available are the min of the pointer types minus the
263  // bits needed for the discriminator.
264  static constexpr int NumLowBitsAvailable = PointerLikeTypeTraits<decltype(
265  PointerUnion<PTs...>::Val)>::NumLowBitsAvailable;
266 };
267 
268 // Teach DenseMap how to use PointerUnions as keys.
269 template <typename ...PTs> struct DenseMapInfo<PointerUnion<PTs...>> {
270  using Union = PointerUnion<PTs...>;
271  using FirstInfo =
273 
274  static inline Union getEmptyKey() { return Union(FirstInfo::getEmptyKey()); }
275 
276  static inline Union getTombstoneKey() {
277  return Union(FirstInfo::getTombstoneKey());
278  }
279 
280  static unsigned getHashValue(const Union &UnionVal) {
281  intptr_t key = (intptr_t)UnionVal.getOpaqueValue();
283  }
284 
285  static bool isEqual(const Union &LHS, const Union &RHS) {
286  return LHS == RHS;
287  }
288 };
289 
290 } // end namespace llvm
291 
292 #endif // LLVM_ADT_POINTERUNION_H
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I, Type, Types... >::operator=
Derived & operator=(Type V)
Definition: PointerUnion.h:123
llvm::PointerUnion::isNull
bool isNull() const
Test if the pointer held in the union is null, regardless of which type it is.
Definition: PointerUnion.h:172
llvm
Definition: AllocatorList.h:23
llvm::pointer_union_detail::PointerUnionMembers
Definition: PointerUnion.h:97
intptr_t
llvm::PointerUnionTypeSelector
Get a type based on whether two types are the same or not.
Definition: PointerUnion.h:40
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::DenseMapInfo< PointerUnion< PTs... > >::getTombstoneKey
static Union getTombstoneKey()
Definition: PointerUnion.h:276
llvm::pointer_union_detail::TypeIndex
Find the index of a type in a list of types.
Definition: PointerUnion.h:70
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
T1
#define T1
Definition: Mips16ISelLowering.cpp:340
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2039
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::PointerUnionTypeSelector< T, T, RET_EQ, RET_NE >::Return
typename PointerUnionTypeSelectorReturn< RET_EQ >::Return Return
Definition: PointerUnion.h:46
llvm::PointerLikeTypeTraits< PointerUnion< PTs... > >::getAsVoidPointer
static void * getAsVoidPointer(const PointerUnion< PTs... > &P)
Definition: PointerUnion.h:254
llvm::PointerUnion::getOpaqueValue
void * getOpaqueValue() const
Definition: PointerUnion.h:227
llvm::PointerUnion::get
T get() const
Returns the value of the specified pointer type.
Definition: PointerUnion.h:187
llvm::PointerUnion::PointerUnion
PointerUnion()=default
llvm::PointerUnion::is
bool is() const
Test if the Union currently holds the type matching T.
Definition: PointerUnion.h:177
PointerIntPair.h
llvm::PointerUnionTypeSelector::Return
typename PointerUnionTypeSelectorReturn< RET_NE >::Return Return
Definition: PointerUnion.h:41
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::PointerUnionTypeSelectorReturn
Definition: PointerUnion.h:26
PointerLikeTypeTraits.h
llvm::pointer_union_detail::PointerUnionUIntTraits::NumLowBitsAvailable
static constexpr int NumLowBitsAvailable
Definition: PointerUnion.h:93
llvm::DenseMapInfo< PointerUnion< PTs... > >::getHashValue
static unsigned getHashValue(const Union &UnionVal)
Definition: PointerUnion.h:280
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I, Type, Types... >::PointerUnionMembers
PointerUnionMembers(Type V)
Definition: PointerUnion.h:117
llvm::pointer_union_detail::lowBitsAvailable
constexpr int lowBitsAvailable()
Definition: PointerUnion.h:63
type
AMD64 Optimization Manual has some nice information about optimizing integer multiplication by a constant How much of it applies to Intel s X86 implementation There are definite trade offs to xmm0 cvttss2siq rdx jb L3 subss xmm0 rax cvttss2siq rdx xorq rdx rax ret instead of xmm1 cvttss2siq rcx movaps xmm2 subss xmm2 cvttss2siq rax rdx xorq rax ucomiss xmm0 cmovb rax ret Seems like the jb branch has high likelihood of being taken It would have saved a few instructions It s not possible to reference and DH registers in an instruction requiring REX prefix divb and mulb both produce results in AH If isel emits a CopyFromReg which gets turned into a movb and that can be allocated a r8b r15b To get around isel emits a CopyFromReg from AX and then right shift it down by and truncate it It s not pretty but it works We need some register allocation magic to make the hack go which would often require a callee saved register Callees usually need to keep this value live for most of their body so it doesn t add a significant burden on them We currently implement this in however this is suboptimal because it means that it would be quite awkward to implement the optimization for callers A better implementation would be to relax the LLVM IR rules for sret arguments to allow a function with an sret argument to have a non void return type
Definition: README-X86-64.txt:70
llvm::pointer_union_detail::PointerUnionUIntTraits
Provide PointerLikeTypeTraits for void* that is used by PointerUnion for the template arguments.
Definition: PointerUnion.h:89
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::PointerUnion::dyn_cast
T dyn_cast() const
Returns the current pointer if it is of the specified pointer type, otherwise returns null.
Definition: PointerUnion.h:194
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:343
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::pointer_union_detail::bitsRequired
constexpr int bitsRequired(unsigned n)
Determine the number of bits required to store integers with values < n.
Definition: PointerUnion.h:59
TemplateParamKind::Type
@ Type
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2037
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I >::Val
ValTy Val
Definition: PointerUnion.h:102
llvm::PointerUnion::getFromOpaqueValue
static PointerUnion getFromOpaqueValue(void *VP)
Definition: PointerUnion.h:228
llvm::PointerUnionTypeSelectorReturn< PointerUnionTypeSelector< T1, T2, RET_EQ, RET_NE > >::Return
typename PointerUnionTypeSelector< T1, T2, RET_EQ, RET_NE >::Return Return
Definition: PointerUnion.h:53
llvm::DenseMapInfo< PointerUnion< PTs... > >::isEqual
static bool isEqual(const Union &LHS, const Union &RHS)
Definition: PointerUnion.h:285
llvm::pointer_union_detail::PointerUnionUIntTraits::getFromVoidPointer
static void * getFromVoidPointer(void *P)
Definition: PointerUnion.h:92
llvm::PointerUnion::getAddrOfPtr1
First * getAddrOfPtr1()
If the union is set to the first pointer type get an address pointing to it.
Definition: PointerUnion.h:208
llvm::PointerLikeTypeTraits< PointerUnion< PTs... > >::getFromVoidPointer
static PointerUnion< PTs... > getFromVoidPointer(void *P)
Definition: PointerUnion.h:258
llvm::PointerUnionTypeSelectorReturn::Return
T Return
Definition: PointerUnion.h:27
llvm::PointerUnion
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:149
llvm::PointerUnion::PointerUnion
PointerUnion(std::nullptr_t)
Definition: PointerUnion.h:167
llvm::PointerUnion::getAddrOfPtr1
const First * getAddrOfPtr1() const
If the union is set to the first pointer type get an address pointing to it.
Definition: PointerUnion.h:202
llvm::pointer_union_detail::GetFirstType::type
T type
Definition: PointerUnion.h:84
llvm::PointerLikeTypeTraits
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
Definition: PointerLikeTypeTraits.h:25
llvm::DenseMapInfo< PointerUnion< PTs... > >::getEmptyKey
static Union getEmptyKey()
Definition: PointerUnion.h:274
llvm::PointerUnion::operator=
const PointerUnion & operator=(std::nullptr_t)
Assignment from nullptr which just clears the union.
Definition: PointerUnion.h:219
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I >::PointerUnionMembers
PointerUnionMembers(ValTy Val)
Definition: PointerUnion.h:104
DenseMapInfo.h
llvm::pointer_union_detail::PointerUnionUIntTraits::getAsVoidPointer
static void * getAsVoidPointer(void *P)
Definition: PointerUnion.h:91
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::pointer_union_detail::GetFirstType
Find the first type in a list of types.
Definition: PointerUnion.h:83