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