LLVM  14.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 namespace pointer_union_detail {
27  /// Determine the number of bits required to store integers with values < n.
28  /// This is ceil(log2(n)).
29  constexpr int bitsRequired(unsigned n) {
30  return n > 1 ? 1 + bitsRequired((n + 1) / 2) : 0;
31  }
32 
33  template <typename... Ts> constexpr int lowBitsAvailable() {
34  return std::min<int>({PointerLikeTypeTraits<Ts>::NumLowBitsAvailable...});
35  }
36 
37  /// Find the index of a type in a list of types. TypeIndex<T, Us...>::Index
38  /// is the index of T in Us, or sizeof...(Us) if T does not appear in the
39  /// list.
40  template <typename T, typename ...Us> struct TypeIndex;
41  template <typename T, typename ...Us> struct TypeIndex<T, T, Us...> {
42  static constexpr int Index = 0;
43  };
44  template <typename T, typename U, typename... Us>
45  struct TypeIndex<T, U, Us...> {
46  static constexpr int Index = 1 + TypeIndex<T, Us...>::Index;
47  };
48  template <typename T> struct TypeIndex<T> {
49  static constexpr int Index = 0;
50  };
51 
52  /// Find the first type in a list of types.
53  template <typename T, typename...> struct GetFirstType {
54  using type = T;
55  };
56 
57  /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
58  /// for the template arguments.
59  template <typename ...PTs> class PointerUnionUIntTraits {
60  public:
61  static inline void *getAsVoidPointer(void *P) { return P; }
62  static inline void *getFromVoidPointer(void *P) { return P; }
63  static constexpr int NumLowBitsAvailable = lowBitsAvailable<PTs...>();
64  };
65 
66  template <typename Derived, typename ValTy, int I, typename ...Types>
68 
69  template <typename Derived, typename ValTy, int I>
70  class PointerUnionMembers<Derived, ValTy, I> {
71  protected:
72  ValTy Val;
73  PointerUnionMembers() = default;
74  PointerUnionMembers(ValTy Val) : Val(Val) {}
75 
76  friend struct PointerLikeTypeTraits<Derived>;
77  };
78 
79  template <typename Derived, typename ValTy, int I, typename Type,
80  typename ...Types>
81  class PointerUnionMembers<Derived, ValTy, I, Type, Types...>
82  : public PointerUnionMembers<Derived, ValTy, I + 1, Types...> {
83  using Base = PointerUnionMembers<Derived, ValTy, I + 1, Types...>;
84  public:
85  using Base::Base;
86  PointerUnionMembers() = default;
88  : Base(ValTy(const_cast<void *>(
89  PointerLikeTypeTraits<Type>::getAsVoidPointer(V)),
90  I)) {}
91 
92  using Base::operator=;
93  Derived &operator=(Type V) {
94  this->Val = ValTy(
95  const_cast<void *>(PointerLikeTypeTraits<Type>::getAsVoidPointer(V)),
96  I);
97  return static_cast<Derived &>(*this);
98  };
99  };
100 }
101 
102 /// A discriminated union of two or more pointer types, with the discriminator
103 /// in the low bit of the pointer.
104 ///
105 /// This implementation is extremely efficient in space due to leveraging the
106 /// low bits of the pointer, while exposing a natural and type-safe API.
107 ///
108 /// Common use patterns would be something like this:
109 /// PointerUnion<int*, float*> P;
110 /// P = (int*)0;
111 /// printf("%d %d", P.is<int*>(), P.is<float*>()); // prints "1 0"
112 /// X = P.get<int*>(); // ok.
113 /// Y = P.get<float*>(); // runtime assertion failure.
114 /// Z = P.get<double*>(); // compile time failure.
115 /// P = (float*)0;
116 /// Y = P.get<float*>(); // ok.
117 /// X = P.get<int*>(); // runtime assertion failure.
118 template <typename... PTs>
121  PointerUnion<PTs...>,
122  PointerIntPair<
123  void *, pointer_union_detail::bitsRequired(sizeof...(PTs)), int,
124  pointer_union_detail::PointerUnionUIntTraits<PTs...>>,
125  0, PTs...> {
126  // The first type is special because we want to directly cast a pointer to a
127  // default-initialized union to a pointer to the first type. But we don't
128  // want PointerUnion to be a 'template <typename First, typename ...Rest>'
129  // because it's much more convenient to have a name for the whole pack. So
130  // split off the first type here.
131  using First = typename pointer_union_detail::GetFirstType<PTs...>::type;
132  using Base = typename PointerUnion::PointerUnionMembers;
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  /// Test if the Union currently holds the type matching T.
147  template <typename T> bool is() const {
148  constexpr int Index = pointer_union_detail::TypeIndex<T, PTs...>::Index;
149  static_assert(Index < sizeof...(PTs),
150  "PointerUnion::is<T> given type not in the union");
151  return this->Val.getInt() == Index;
152  }
153 
154  /// Returns the value of the specified pointer type.
155  ///
156  /// If the specified pointer type is incorrect, assert.
157  template <typename T> T get() const {
158  assert(is<T>() && "Invalid accessor called");
159  return PointerLikeTypeTraits<T>::getFromVoidPointer(this->Val.getPointer());
160  }
161 
162  /// Returns the current pointer if it is of the specified pointer type,
163  /// otherwise returns null.
164  template <typename T> T dyn_cast() const {
165  if (is<T>())
166  return get<T>();
167  return T();
168  }
169 
170  /// If the union is set to the first pointer type get an address pointing to
171  /// it.
172  First const *getAddrOfPtr1() const {
173  return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
174  }
175 
176  /// If the union is set to the first pointer type get an address pointing to
177  /// it.
178  First *getAddrOfPtr1() {
179  assert(is<First>() && "Val is not the first pointer");
180  assert(
182  this->Val.getPointer() &&
183  "Can't get the address because PointerLikeTypeTraits changes the ptr");
184  return const_cast<First *>(
185  reinterpret_cast<const First *>(this->Val.getAddrOfPointer()));
186  }
187 
188  /// Assignment from nullptr which just clears the union.
189  const PointerUnion &operator=(std::nullptr_t) {
190  this->Val.initWithPointer(nullptr);
191  return *this;
192  }
193 
194  /// Assignment from elements of the union.
195  using Base::operator=;
196 
197  void *getOpaqueValue() const { return this->Val.getOpaqueValue(); }
198  static inline PointerUnion getFromOpaqueValue(void *VP) {
199  PointerUnion V;
200  V.Val = decltype(V.Val)::getFromOpaqueValue(VP);
201  return V;
202  }
203 };
204 
205 template <typename ...PTs>
207  return lhs.getOpaqueValue() == rhs.getOpaqueValue();
208 }
209 
210 template <typename ...PTs>
212  return lhs.getOpaqueValue() != rhs.getOpaqueValue();
213 }
214 
215 template <typename ...PTs>
217  return lhs.getOpaqueValue() < rhs.getOpaqueValue();
218 }
219 
220 // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
221 // # low bits available = min(PT1bits,PT2bits)-1.
222 template <typename ...PTs>
224  static inline void *getAsVoidPointer(const PointerUnion<PTs...> &P) {
225  return P.getOpaqueValue();
226  }
227 
228  static inline PointerUnion<PTs...> getFromVoidPointer(void *P) {
230  }
231 
232  // The number of bits available are the min of the pointer types minus the
233  // bits needed for the discriminator.
234  static constexpr int NumLowBitsAvailable = PointerLikeTypeTraits<decltype(
235  PointerUnion<PTs...>::Val)>::NumLowBitsAvailable;
236 };
237 
238 // Teach DenseMap how to use PointerUnions as keys.
239 template <typename ...PTs> struct DenseMapInfo<PointerUnion<PTs...>> {
240  using Union = PointerUnion<PTs...>;
241  using FirstInfo =
243 
244  static inline Union getEmptyKey() { return Union(FirstInfo::getEmptyKey()); }
245 
246  static inline Union getTombstoneKey() {
247  return Union(FirstInfo::getTombstoneKey());
248  }
249 
250  static unsigned getHashValue(const Union &UnionVal) {
251  intptr_t key = (intptr_t)UnionVal.getOpaqueValue();
253  }
254 
255  static bool isEqual(const Union &LHS, const Union &RHS) {
256  return LHS == RHS;
257  }
258 };
259 
260 } // end namespace llvm
261 
262 #endif // LLVM_ADT_POINTERUNION_H
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I, Type, Types... >::operator=
Derived & operator=(Type V)
Definition: PointerUnion.h:93
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
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::pointer_union_detail::PointerUnionMembers
Definition: PointerUnion.h:67
intptr_t
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:246
llvm::pointer_union_detail::TypeIndex
Find the index of a type in a list of types.
Definition: PointerUnion.h:40
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1976
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::PointerLikeTypeTraits< PointerUnion< PTs... > >::getAsVoidPointer
static void * getAsVoidPointer(const PointerUnion< PTs... > &P)
Definition: PointerUnion.h:224
llvm::PointerUnion::getOpaqueValue
void * getOpaqueValue() const
Definition: PointerUnion.h:197
llvm::PointerUnion::get
T get() const
Returns the value of the specified pointer type.
Definition: PointerUnion.h:157
llvm::PointerUnion::PointerUnion
PointerUnion()=default
llvm::PointerUnion::is
bool is() const
Test if the Union currently holds the type matching T.
Definition: PointerUnion.h:147
PointerIntPair.h
llvm::DenseMapInfo
Definition: APInt.h:34
PointerLikeTypeTraits.h
llvm::pointer_union_detail::PointerUnionUIntTraits::NumLowBitsAvailable
static constexpr int NumLowBitsAvailable
Definition: PointerUnion.h:63
llvm::DenseMapInfo< PointerUnion< PTs... > >::getHashValue
static unsigned getHashValue(const Union &UnionVal)
Definition: PointerUnion.h:250
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I, Type, Types... >::PointerUnionMembers
PointerUnionMembers(Type V)
Definition: PointerUnion.h:87
llvm::pointer_union_detail::lowBitsAvailable
constexpr int lowBitsAvailable()
Definition: PointerUnion.h:33
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:59
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:164
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:338
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:29
TemplateParamKind::Type
@ Type
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1974
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I >::Val
ValTy Val
Definition: PointerUnion.h:72
llvm::PointerUnion::getFromOpaqueValue
static PointerUnion getFromOpaqueValue(void *VP)
Definition: PointerUnion.h:198
llvm::DenseMapInfo< PointerUnion< PTs... > >::isEqual
static bool isEqual(const Union &LHS, const Union &RHS)
Definition: PointerUnion.h:255
llvm::pointer_union_detail::PointerUnionUIntTraits::getFromVoidPointer
static void * getFromVoidPointer(void *P)
Definition: PointerUnion.h:62
llvm::PointerUnion::getAddrOfPtr1
First * getAddrOfPtr1()
If the union is set to the first pointer type get an address pointing to it.
Definition: PointerUnion.h:178
llvm::PointerLikeTypeTraits< PointerUnion< PTs... > >::getFromVoidPointer
static PointerUnion< PTs... > getFromVoidPointer(void *P)
Definition: PointerUnion.h:228
llvm::PointerUnion
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:119
llvm::PointerUnion::PointerUnion
PointerUnion(std::nullptr_t)
Definition: PointerUnion.h:137
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:172
llvm::pointer_union_detail::GetFirstType::type
T type
Definition: PointerUnion.h:54
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:244
llvm::PointerUnion::operator=
const PointerUnion & operator=(std::nullptr_t)
Assignment from nullptr which just clears the union.
Definition: PointerUnion.h:189
llvm::pointer_union_detail::PointerUnionMembers< Derived, ValTy, I >::PointerUnionMembers
PointerUnionMembers(ValTy Val)
Definition: PointerUnion.h:74
DenseMapInfo.h
llvm::pointer_union_detail::PointerUnionUIntTraits::getAsVoidPointer
static void * getAsVoidPointer(void *P)
Definition: PointerUnion.h:61
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::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::pointer_union_detail::GetFirstType
Find the first type in a list of types.
Definition: PointerUnion.h:53