LLVM  15.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 /// \file
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"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/Support/Casting.h"
23 #include <algorithm>
24 #include <cassert>
25 #include <cstddef>
26 #include <cstdint>
27 
28 namespace llvm {
29 
30 namespace pointer_union_detail {
31  /// Determine the number of bits required to store integers with values < n.
32  /// This is ceil(log2(n)).
33  constexpr int bitsRequired(unsigned n) {
34  return n > 1 ? 1 + bitsRequired((n + 1) / 2) : 0;
35  }
36 
37  template <typename... Ts> constexpr int lowBitsAvailable() {
38  return std::min<int>({PointerLikeTypeTraits<Ts>::NumLowBitsAvailable...});
39  }
40 
41  /// Find the first type in a list of types.
42  template <typename T, typename...> struct GetFirstType {
43  using type = T;
44  };
45 
46  /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
47  /// for the template arguments.
48  template <typename ...PTs> class PointerUnionUIntTraits {
49  public:
50  static inline void *getAsVoidPointer(void *P) { return P; }
51  static inline void *getFromVoidPointer(void *P) { return P; }
52  static constexpr int NumLowBitsAvailable = lowBitsAvailable<PTs...>();
53  };
54 
55  template <typename Derived, typename ValTy, int I, typename ...Types>
57 
58  template <typename Derived, typename ValTy, int I>
59  class PointerUnionMembers<Derived, ValTy, I> {
60  protected:
61  ValTy Val;
62  PointerUnionMembers() = default;
63  PointerUnionMembers(ValTy Val) : Val(Val) {}
64 
65  friend struct PointerLikeTypeTraits<Derived>;
66  };
67 
68  template <typename Derived, typename ValTy, int I, typename Type,
69  typename ...Types>
70  class PointerUnionMembers<Derived, ValTy, I, Type, Types...>
71  : public PointerUnionMembers<Derived, ValTy, I + 1, Types...> {
72  using Base = PointerUnionMembers<Derived, ValTy, I + 1, Types...>;
73  public:
74  using Base::Base;
75  PointerUnionMembers() = default;
77  : Base(ValTy(const_cast<void *>(
78  PointerLikeTypeTraits<Type>::getAsVoidPointer(V)),
79  I)) {}
80 
81  using Base::operator=;
82  Derived &operator=(Type V) {
83  this->Val = ValTy(
84  const_cast<void *>(PointerLikeTypeTraits<Type>::getAsVoidPointer(V)),
85  I);
86  return static_cast<Derived &>(*this);
87  };
88  };
89 }
90 
91 // This is a forward declaration of CastInfoPointerUnionImpl
92 // Refer to its definition below for further details
93 template <typename... PTs> struct CastInfoPointerUnionImpl;
94 /// A discriminated union of two or more pointer types, with the discriminator
95 /// in the low bit of the pointer.
96 ///
97 /// This implementation is extremely efficient in space due to leveraging the
98 /// low bits of the pointer, while exposing a natural and type-safe API.
99 ///
100 /// Common use patterns would be something like this:
101 /// PointerUnion<int*, float*> P;
102 /// P = (int*)0;
103 /// printf("%d %d", P.is<int*>(), P.is<float*>()); // prints "1 0"
104 /// X = P.get<int*>(); // ok.
105 /// Y = P.get<float*>(); // runtime assertion failure.
106 /// Z = P.get<double*>(); // compile time failure.
107 /// P = (float*)0;
108 /// Y = P.get<float*>(); // ok.
109 /// X = P.get<int*>(); // runtime assertion failure.
110 /// PointerUnion<int*, int*> Q; // compile time failure.
111 template <typename... PTs>
114  PointerUnion<PTs...>,
115  PointerIntPair<
116  void *, pointer_union_detail::bitsRequired(sizeof...(PTs)), int,
117  pointer_union_detail::PointerUnionUIntTraits<PTs...>>,
118  0, PTs...> {
119  static_assert(TypesAreDistinct<PTs...>::value,
120  "PointerUnion alternative types cannot be repeated");
121  // The first type is special because we want to directly cast a pointer to a
122  // default-initialized union to a pointer to the first type. But we don't
123  // want PointerUnion to be a 'template <typename First, typename ...Rest>'
124  // because it's much more convenient to have a name for the whole pack. So
125  // split off the first type here.
126  using First = TypeAtIndex<0, PTs...>;
127  using Base = typename PointerUnion::PointerUnionMembers;
128 
129  /// This is needed to give the CastInfo implementation below access
130  /// to protected members.
131  /// Refer to its definition for further details.
132  friend struct CastInfoPointerUnionImpl<PTs...>;
133 
134 public:
135  PointerUnion() = default;
136 
137  PointerUnion(std::nullptr_t) : PointerUnion() {}
138  using Base::Base;
139 
140  /// Test if the pointer held in the union is null, regardless of
141  /// which type it is.
142  bool isNull() const { return !this->Val.getPointer(); }
143 
144  explicit operator bool() const { return !isNull(); }
145 
146  // FIXME: Replace the uses of is(), get() and dyn_cast() with
147  // isa<T>, cast<T> and the llvm::dyn_cast<T>
148 
149  /// Test if the Union currently holds the type matching T.
150  template <typename T> inline bool is() const { return isa<T>(*this); }
151 
152  /// Returns the value of the specified pointer type.
153  ///
154  /// If the specified pointer type is incorrect, assert.
155  template <typename T> inline T get() const {
156  assert(isa<T>(*this) && "Invalid accessor called");
157  return cast<T>(*this);
158  }
159 
160  /// Returns the current pointer if it is of the specified pointer type,
161  /// otherwise returns null.
162  template <typename T> inline T dyn_cast() const {
163  return llvm::dyn_cast<T>(*this);
164  }
165 
166  /// If the union is set to the first pointer type get an address pointing to
167  /// it.
168  First const *getAddrOfPtr1() const {
169  return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
170  }
171 
172  /// If the union is set to the first pointer type get an address pointing to
173  /// it.
174  First *getAddrOfPtr1() {
175  assert(is<First>() && "Val is not the first pointer");
176  assert(
178  this->Val.getPointer() &&
179  "Can't get the address because PointerLikeTypeTraits changes the ptr");
180  return const_cast<First *>(
181  reinterpret_cast<const First *>(this->Val.getAddrOfPointer()));
182  }
183 
184  /// Assignment from nullptr which just clears the union.
185  const PointerUnion &operator=(std::nullptr_t) {
186  this->Val.initWithPointer(nullptr);
187  return *this;
188  }
189 
190  /// Assignment from elements of the union.
191  using Base::operator=;
192 
193  void *getOpaqueValue() const { return this->Val.getOpaqueValue(); }
194  static inline PointerUnion getFromOpaqueValue(void *VP) {
195  PointerUnion V;
196  V.Val = decltype(V.Val)::getFromOpaqueValue(VP);
197  return V;
198  }
199 };
200 
201 template <typename ...PTs>
203  return lhs.getOpaqueValue() == rhs.getOpaqueValue();
204 }
205 
206 template <typename ...PTs>
208  return lhs.getOpaqueValue() != rhs.getOpaqueValue();
209 }
210 
211 template <typename ...PTs>
213  return lhs.getOpaqueValue() < rhs.getOpaqueValue();
214 }
215 
216 /// We can't (at least, at this moment with C++14) declare CastInfo
217 /// as a friend of PointerUnion like this:
218 /// ```
219 /// template<typename To>
220 /// friend struct CastInfo<To, PointerUnion<PTs...>>;
221 /// ```
222 /// The compiler complains 'Partial specialization cannot be declared as a
223 /// friend'.
224 /// So we define this struct to be a bridge between CastInfo and
225 /// PointerUnion.
226 template <typename... PTs> struct CastInfoPointerUnionImpl {
227  using From = PointerUnion<PTs...>;
228 
229  template <typename To> static inline bool isPossible(From &F) {
230  return F.Val.getInt() == FirstIndexOfType<To, PTs...>::value;
231  }
232 
233  template <typename To> static To doCast(From &F) {
234  assert(isPossible<To>(F) && "cast to an incompatible type !");
235  return PointerLikeTypeTraits<To>::getFromVoidPointer(F.Val.getPointer());
236  }
237 };
238 
239 // Specialization of CastInfo for PointerUnion
240 template <typename To, typename... PTs>
241 struct CastInfo<To, PointerUnion<PTs...>>
242  : public DefaultDoCastIfPossible<To, PointerUnion<PTs...>,
243  CastInfo<To, PointerUnion<PTs...>>> {
244  using From = PointerUnion<PTs...>;
246 
247  static inline bool isPossible(From &f) {
248  return Impl::template isPossible<To>(f);
249  }
250 
251  static To doCast(From &f) { return Impl::template doCast<To>(f); }
252 
253  static inline To castFailed() { return To(); }
254 };
255 
256 template <typename To, typename... PTs>
257 struct CastInfo<To, const PointerUnion<PTs...>>
258  : public ConstStrippingForwardingCast<To, const PointerUnion<PTs...>,
259  CastInfo<To, PointerUnion<PTs...>>> {
260 };
261 
262 // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
263 // # low bits available = min(PT1bits,PT2bits)-1.
264 template <typename ...PTs>
266  static inline void *getAsVoidPointer(const PointerUnion<PTs...> &P) {
267  return P.getOpaqueValue();
268  }
269 
270  static inline PointerUnion<PTs...> getFromVoidPointer(void *P) {
272  }
273 
274  // The number of bits available are the min of the pointer types minus the
275  // bits needed for the discriminator.
276  static constexpr int NumLowBitsAvailable = PointerLikeTypeTraits<decltype(
277  PointerUnion<PTs...>::Val)>::NumLowBitsAvailable;
278 };
279 
280 // Teach DenseMap how to use PointerUnions as keys.
281 template <typename ...PTs> struct DenseMapInfo<PointerUnion<PTs...>> {
282  using Union = PointerUnion<PTs...>;
283  using FirstInfo =
285 
286  static inline Union getEmptyKey() { return Union(FirstInfo::getEmptyKey()); }
287 
288  static inline Union getTombstoneKey() {
289  return Union(FirstInfo::getTombstoneKey());
290  }
291 
292  static unsigned getHashValue(const Union &UnionVal) {
293  intptr_t key = (intptr_t)UnionVal.getOpaqueValue();
295  }
296 
297  static bool isEqual(const Union &LHS, const Union &RHS) {
298  return LHS == RHS;
299  }
300 };
301 
302 } // end namespace llvm
303 
304 #endif // LLVM_ADT_POINTERUNION_H
llvm::CastInfoPointerUnionImpl::isPossible
static bool isPossible(From &F)
Definition: PointerUnion.h:229
llvm::CastInfo< To, PointerUnion< PTs... > >::isPossible
static bool isPossible(From &f)
Definition: PointerUnion.h:247
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I, Type, Types... >::operator=
Derived & operator=(Type V)
Definition: PointerUnion.h:82
llvm::DefaultDoCastIfPossible
This cast trait just provides the default implementation of doCastIfPossible to make CastInfo special...
Definition: Casting.h:317
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:142
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::pointer_union_detail::PointerUnionMembers
Definition: PointerUnion.h:56
intptr_t
llvm::CastInfo
This struct provides a method for customizing the way a cast is performed.
Definition: Casting.h:484
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::CastInfo< To, PointerUnion< PTs... > >::castFailed
static To castFailed()
Definition: PointerUnion.h:253
llvm::DenseMapInfo< PointerUnion< PTs... > >::getTombstoneKey
static Union getTombstoneKey()
Definition: PointerUnion.h:288
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::CastInfoPointerUnionImpl
We can't (at least, at this moment with C++14) declare CastInfo as a friend of PointerUnion like this...
Definition: PointerUnion.h:93
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2004
T
#define T
Definition: Mips16ISelLowering.cpp:341
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::PointerLikeTypeTraits< PointerUnion< PTs... > >::getAsVoidPointer
static void * getAsVoidPointer(const PointerUnion< PTs... > &P)
Definition: PointerUnion.h:266
llvm::PointerUnion::getOpaqueValue
void * getOpaqueValue() const
Definition: PointerUnion.h:193
llvm::PointerUnion::get
T get() const
Returns the value of the specified pointer type.
Definition: PointerUnion.h:155
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::PointerUnion::PointerUnion
PointerUnion()=default
llvm::PointerUnion::is
bool is() const
Test if the Union currently holds the type matching T.
Definition: PointerUnion.h:150
PointerIntPair.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
f
Itanium Name Demangler i e convert the string _Z1fv into f()". You can also use the CRTP base ManglingParser to perform some simple analysis on the mangled name
PointerLikeTypeTraits.h
llvm::pointer_union_detail::PointerUnionUIntTraits::NumLowBitsAvailable
static constexpr int NumLowBitsAvailable
Definition: PointerUnion.h:52
llvm::DenseMapInfo< PointerUnion< PTs... > >::getHashValue
static unsigned getHashValue(const Union &UnionVal)
Definition: PointerUnion.h:292
llvm::FirstIndexOfType
Find the first index where a type appears in a list of types.
Definition: STLExtras.h:196
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I, Type, Types... >::PointerUnionMembers
PointerUnionMembers(Type V)
Definition: PointerUnion.h:76
llvm::pointer_union_detail::lowBitsAvailable
constexpr int lowBitsAvailable()
Definition: PointerUnion.h:37
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:48
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
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:162
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:339
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:33
TemplateParamKind::Type
@ Type
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2002
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I >::Val
ValTy Val
Definition: PointerUnion.h:61
llvm::PointerUnion::getFromOpaqueValue
static PointerUnion getFromOpaqueValue(void *VP)
Definition: PointerUnion.h:194
llvm::DenseMapInfo< PointerUnion< PTs... > >::isEqual
static bool isEqual(const Union &LHS, const Union &RHS)
Definition: PointerUnion.h:297
llvm::pointer_union_detail::PointerUnionUIntTraits::getFromVoidPointer
static void * getFromVoidPointer(void *P)
Definition: PointerUnion.h:51
llvm::PointerUnion::getAddrOfPtr1
First * getAddrOfPtr1()
If the union is set to the first pointer type get an address pointing to it.
Definition: PointerUnion.h:174
llvm::TypeAtIndex
std::tuple_element_t< I, std::tuple< Ts... > > TypeAtIndex
Find the type at a given index in a list of types.
Definition: STLExtras.h:207
llvm::PointerLikeTypeTraits< PointerUnion< PTs... > >::getFromVoidPointer
static PointerUnion< PTs... > getFromVoidPointer(void *P)
Definition: PointerUnion.h:270
llvm::PointerUnion
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:112
llvm::PointerUnion::PointerUnion
PointerUnion(std::nullptr_t)
Definition: PointerUnion.h:137
Casting.h
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:168
llvm::ConstStrippingForwardingCast
Provides a cast trait that strips const from types to make it easier to implement a const-version of ...
Definition: Casting.h:396
llvm::pointer_union_detail::GetFirstType::type
T type
Definition: PointerUnion.h:43
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::CastInfo< To, PointerUnion< PTs... > >::doCast
static To doCast(From &f)
Definition: PointerUnion.h:251
llvm::DenseMapInfo< PointerUnion< PTs... > >::getEmptyKey
static Union getEmptyKey()
Definition: PointerUnion.h:286
llvm::PointerUnion::operator=
const PointerUnion & operator=(std::nullptr_t)
Assignment from nullptr which just clears the union.
Definition: PointerUnion.h:185
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I >::PointerUnionMembers
PointerUnionMembers(ValTy Val)
Definition: PointerUnion.h:63
DenseMapInfo.h
llvm::pointer_union_detail::PointerUnionUIntTraits::getAsVoidPointer
static void * getAsVoidPointer(void *P)
Definition: PointerUnion.h:50
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::TypesAreDistinct
Determine if all types in Ts are distinct.
Definition: STLExtras.h:180
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::pointer_union_detail::GetFirstType
Find the first type in a list of types.
Definition: PointerUnion.h:42
llvm::CastInfoPointerUnionImpl::doCast
static To doCast(From &F)
Definition: PointerUnion.h:233