LLVM  14.0.0git
PointerSumType.h
Go to the documentation of this file.
1 //===- llvm/ADT/PointerSumType.h --------------------------------*- 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 #ifndef LLVM_ADT_POINTERSUMTYPE_H
10 #define LLVM_ADT_POINTERSUMTYPE_H
11 
12 #include "llvm/ADT/bit.h"
13 #include "llvm/ADT/DenseMapInfo.h"
15 #include <cassert>
16 #include <cstdint>
17 #include <type_traits>
18 
19 namespace llvm {
20 
21 /// A compile time pair of an integer tag and the pointer-like type which it
22 /// indexes within a sum type. Also allows the user to specify a particular
23 /// traits class for pointer types with custom behavior such as over-aligned
24 /// allocation.
25 template <uintptr_t N, typename PointerArgT,
26  typename TraitsArgT = PointerLikeTypeTraits<PointerArgT>>
28  enum { Tag = N };
29  using PointerT = PointerArgT;
30  using TraitsT = TraitsArgT;
31 };
32 
33 namespace detail {
34 
35 template <typename TagT, typename... MemberTs> struct PointerSumTypeHelper;
36 
37 } // end namespace detail
38 
39 /// A sum type over pointer-like types.
40 ///
41 /// This is a normal tagged union across pointer-like types that uses the low
42 /// bits of the pointers to store the tag.
43 ///
44 /// Each member of the sum type is specified by passing a \c
45 /// PointerSumTypeMember specialization in the variadic member argument list.
46 /// This allows the user to control the particular tag value associated with
47 /// a particular type, use the same type for multiple different tags, and
48 /// customize the pointer-like traits used for a particular member. Note that
49 /// these *must* be specializations of \c PointerSumTypeMember, no other type
50 /// will suffice, even if it provides a compatible interface.
51 ///
52 /// This type implements all of the comparison operators and even hash table
53 /// support by comparing the underlying storage of the pointer values. It
54 /// doesn't support delegating to particular members for comparisons.
55 ///
56 /// It also default constructs to a zero tag with a null pointer, whatever that
57 /// would be. This means that the zero value for the tag type is significant
58 /// and may be desirable to set to a state that is particularly desirable to
59 /// default construct.
60 ///
61 /// Having a supported zero-valued tag also enables getting the address of a
62 /// pointer stored with that tag provided it is stored in its natural bit
63 /// representation. This works because in the case of a zero-valued tag, the
64 /// pointer's value is directly stored into this object and we can expose the
65 /// address of that internal storage. This is especially useful when building an
66 /// `ArrayRef` of a single pointer stored in a sum type.
67 ///
68 /// There is no support for constructing or accessing with a dynamic tag as
69 /// that would fundamentally violate the type safety provided by the sum type.
70 template <typename TagT, typename... MemberTs> class PointerSumType {
71  using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
72 
73  // We keep both the raw value and the min tag value's pointer in a union. When
74  // the minimum tag value is zero, this allows code below to cleanly expose the
75  // address of the zero-tag pointer instead of just the zero-tag pointer
76  // itself. This is especially useful when building `ArrayRef`s out of a single
77  // pointer. However, we have to carefully access the union due to the active
78  // member potentially changing. When we *store* a new value, we directly
79  // access the union to allow us to store using the obvious types. However,
80  // when we *read* a value, we copy the underlying storage out to avoid relying
81  // on one member or the other being active.
82  union StorageT {
83  // Ensure we get a null default constructed value. We don't use a member
84  // initializer because some compilers seem to not implement those correctly
85  // for a union.
86  StorageT() : Value(0) {}
87 
88  uintptr_t Value;
89 
90  typename HelperT::template Lookup<HelperT::MinTag>::PointerT MinTagPointer;
91  };
92 
93  StorageT Storage;
94 
95 public:
96  constexpr PointerSumType() = default;
97 
98  /// A typed setter to a given tagged member of the sum type.
99  template <TagT N>
100  void set(typename HelperT::template Lookup<N>::PointerT Pointer) {
101  void *V = HelperT::template Lookup<N>::TraitsT::getAsVoidPointer(Pointer);
102  assert((reinterpret_cast<uintptr_t>(V) & HelperT::TagMask) == 0 &&
103  "Pointer is insufficiently aligned to store the discriminant!");
104  Storage.Value = reinterpret_cast<uintptr_t>(V) | N;
105  }
106 
107  /// A typed constructor for a specific tagged member of the sum type.
108  template <TagT N>
109  static PointerSumType
110  create(typename HelperT::template Lookup<N>::PointerT Pointer) {
111  PointerSumType Result;
112  Result.set<N>(Pointer);
113  return Result;
114  }
115 
116  /// Clear the value to null with the min tag type.
117  void clear() { set<HelperT::MinTag>(nullptr); }
118 
119  TagT getTag() const {
120  return static_cast<TagT>(getOpaqueValue() & HelperT::TagMask);
121  }
122 
123  template <TagT N> bool is() const { return N == getTag(); }
124 
125  template <TagT N> typename HelperT::template Lookup<N>::PointerT get() const {
126  void *P = is<N>() ? getVoidPtr() : nullptr;
127  return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(P);
128  }
129 
130  template <TagT N>
131  typename HelperT::template Lookup<N>::PointerT cast() const {
132  assert(is<N>() && "This instance has a different active member.");
133  return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(
134  getVoidPtr());
135  }
136 
137  /// If the tag is zero and the pointer's value isn't changed when being
138  /// stored, get the address of the stored value type-punned to the zero-tag's
139  /// pointer type.
140  typename HelperT::template Lookup<HelperT::MinTag>::PointerT const *
142  return const_cast<PointerSumType *>(this)->getAddrOfZeroTagPointer();
143  }
144 
145  /// If the tag is zero and the pointer's value isn't changed when being
146  /// stored, get the address of the stored value type-punned to the zero-tag's
147  /// pointer type.
148  typename HelperT::template Lookup<HelperT::MinTag>::PointerT *
150  static_assert(HelperT::MinTag == 0, "Non-zero minimum tag value!");
151  assert(is<HelperT::MinTag>() && "The active tag is not zero!");
152  // Store the initial value of the pointer when read out of our storage.
153  auto InitialPtr = get<HelperT::MinTag>();
154  // Now update the active member of the union to be the actual pointer-typed
155  // member so that accessing it indirectly through the returned address is
156  // valid.
157  Storage.MinTagPointer = InitialPtr;
158  // Finally, validate that this was a no-op as expected by reading it back
159  // out using the same underlying-storage read as above.
160  assert(InitialPtr == get<HelperT::MinTag>() &&
161  "Switching to typed storage changed the pointer returned!");
162  // Now we can correctly return an address to typed storage.
163  return &Storage.MinTagPointer;
164  }
165 
166  explicit operator bool() const {
168  }
169  bool operator==(const PointerSumType &R) const {
170  return getOpaqueValue() == R.getOpaqueValue();
171  }
172  bool operator!=(const PointerSumType &R) const {
173  return getOpaqueValue() != R.getOpaqueValue();
174  }
175  bool operator<(const PointerSumType &R) const {
176  return getOpaqueValue() < R.getOpaqueValue();
177  }
178  bool operator>(const PointerSumType &R) const {
179  return getOpaqueValue() > R.getOpaqueValue();
180  }
181  bool operator<=(const PointerSumType &R) const {
182  return getOpaqueValue() <= R.getOpaqueValue();
183  }
184  bool operator>=(const PointerSumType &R) const {
185  return getOpaqueValue() >= R.getOpaqueValue();
186  }
187 
188  uintptr_t getOpaqueValue() const {
189  // Read the underlying storage of the union, regardless of the active
190  // member.
191  return bit_cast<uintptr_t>(Storage);
192  }
193 
194 protected:
195  void *getVoidPtr() const {
196  return reinterpret_cast<void *>(getOpaqueValue() & HelperT::PointerMask);
197  }
198 };
199 
200 namespace detail {
201 
202 /// A helper template for implementing \c PointerSumType. It provides fast
203 /// compile-time lookup of the member from a particular tag value, along with
204 /// useful constants and compile time checking infrastructure..
205 template <typename TagT, typename... MemberTs>
206 struct PointerSumTypeHelper : MemberTs... {
207  // First we use a trick to allow quickly looking up information about
208  // a particular member of the sum type. This works because we arranged to
209  // have this type derive from all of the member type templates. We can select
210  // the matching member for a tag using type deduction during overload
211  // resolution.
212  template <TagT N, typename PointerT, typename TraitsT>
213  static PointerSumTypeMember<N, PointerT, TraitsT>
214  LookupOverload(PointerSumTypeMember<N, PointerT, TraitsT> *);
215  template <TagT N> static void LookupOverload(...);
216  template <TagT N> struct Lookup {
217  // Compute a particular member type by resolving the lookup helper overload.
218  using MemberT = decltype(
219  LookupOverload<N>(static_cast<PointerSumTypeHelper *>(nullptr)));
220 
221  /// The Nth member's pointer type.
222  using PointerT = typename MemberT::PointerT;
223 
224  /// The Nth member's traits type.
225  using TraitsT = typename MemberT::TraitsT;
226  };
227 
228  // Next we need to compute the number of bits available for the discriminant
229  // by taking the min of the bits available for each member. Much of this
230  // would be amazingly easier with good constexpr support.
231  template <uintptr_t V, uintptr_t... Vs>
232  struct Min : std::integral_constant<
233  uintptr_t, (V < Min<Vs...>::value ? V : Min<Vs...>::value)> {
234  };
235  template <uintptr_t V>
236  struct Min<V> : std::integral_constant<uintptr_t, V> {};
237  enum { NumTagBits = Min<MemberTs::TraitsT::NumLowBitsAvailable...>::value };
238 
239  // Also compute the smallest discriminant and various masks for convenience.
240  constexpr static TagT MinTag =
241  static_cast<TagT>(Min<MemberTs::Tag...>::value);
242  enum : uint64_t {
243  PointerMask = static_cast<uint64_t>(-1) << NumTagBits,
244  TagMask = ~PointerMask
245  };
246 
247  // Finally we need a recursive template to do static checks of each
248  // member.
249  template <typename MemberT, typename... InnerMemberTs>
250  struct Checker : Checker<InnerMemberTs...> {
251  static_assert(MemberT::Tag < (1 << NumTagBits),
252  "This discriminant value requires too many bits!");
253  };
254  template <typename MemberT> struct Checker<MemberT> : std::true_type {
255  static_assert(MemberT::Tag < (1 << NumTagBits),
256  "This discriminant value requires too many bits!");
257  };
258  static_assert(Checker<MemberTs...>::value,
259  "Each member must pass the checker.");
260 };
261 
262 } // end namespace detail
263 
264 // Teach DenseMap how to use PointerSumTypes as keys.
265 template <typename TagT, typename... MemberTs>
266 struct DenseMapInfo<PointerSumType<TagT, MemberTs...>> {
267  using SumType = PointerSumType<TagT, MemberTs...>;
268  using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
269  enum { SomeTag = HelperT::MinTag };
270  using SomePointerT =
271  typename HelperT::template Lookup<HelperT::MinTag>::PointerT;
272  using SomePointerInfo = DenseMapInfo<SomePointerT>;
273 
274  static inline SumType getEmptyKey() {
275  return SumType::create<SomeTag>(SomePointerInfo::getEmptyKey());
276  }
277 
278  static inline SumType getTombstoneKey() {
279  return SumType::create<SomeTag>(SomePointerInfo::getTombstoneKey());
280  }
281 
282  static unsigned getHashValue(const SumType &Arg) {
283  uintptr_t OpaqueValue = Arg.getOpaqueValue();
284  return DenseMapInfo<uintptr_t>::getHashValue(OpaqueValue);
285  }
286 
287  static bool isEqual(const SumType &LHS, const SumType &RHS) {
288  return LHS == RHS;
289  }
290 };
291 
292 } // end namespace llvm
293 
294 #endif // LLVM_ADT_POINTERSUMTYPE_H
llvm::PointerSumType::operator>=
bool operator>=(const PointerSumType &R) const
Definition: PointerSumType.h:184
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::detail::PointerSumTypeHelper::Lookup::PointerT
typename MemberT::PointerT PointerT
The Nth member's pointer type.
Definition: PointerSumType.h:222
llvm::detail::PointerSumTypeHelper::Lookup::MemberT
decltype(LookupOverload< N >(static_cast< PointerSumTypeHelper * >(nullptr))) MemberT
Definition: PointerSumType.h:219
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::PointerSumType::set
void set(typename HelperT::template Lookup< N >::PointerT Pointer)
A typed setter to a given tagged member of the sum type.
Definition: PointerSumType.h:100
llvm::detail::PointerSumTypeHelper::TagMask
@ TagMask
Definition: PointerSumType.h:244
llvm::detail::PointerSumTypeHelper::PointerMask
@ PointerMask
Definition: PointerSumType.h:243
llvm::PointerSumType::getTag
TagT getTag() const
Definition: PointerSumType.h:119
llvm::PointerSumType::getAddrOfZeroTagPointer
HelperT::template const Lookup< HelperT::MinTag >::PointerT * getAddrOfZeroTagPointer() const
If the tag is zero and the pointer's value isn't changed when being stored, get the address of the st...
Definition: PointerSumType.h:141
llvm::PointerSumType::is
bool is() const
Definition: PointerSumType.h:123
llvm::PointerSumType::getVoidPtr
void * getVoidPtr() const
Definition: PointerSumType.h:195
llvm::PointerSumType::operator!=
bool operator!=(const PointerSumType &R) const
Definition: PointerSumType.h:172
PointerLikeTypeTraits.h
llvm::detail::PointerSumTypeHelper::Min
Definition: PointerSumType.h:232
llvm::PointerSumTypeMember::Tag
@ Tag
Definition: PointerSumType.h:28
llvm::detail::PointerSumTypeHelper::LookupOverload
static PointerSumTypeMember< N, PointerT, TraitsT > LookupOverload(PointerSumTypeMember< N, PointerT, TraitsT > *)
llvm::PointerSumType::operator<
bool operator<(const PointerSumType &R) const
Definition: PointerSumType.h:175
llvm::PointerSumType::getOpaqueValue
uintptr_t getOpaqueValue() const
Definition: PointerSumType.h:188
llvm::PointerSumTypeMember
A compile time pair of an integer tag and the pointer-like type which it indexes within a sum type.
Definition: PointerSumType.h:27
llvm::PointerSumType::getAddrOfZeroTagPointer
HelperT::template Lookup< HelperT::MinTag >::PointerT * getAddrOfZeroTagPointer()
If the tag is zero and the pointer's value isn't changed when being stored, get the address of the st...
Definition: PointerSumType.h:149
llvm::PointerSumType::clear
void clear()
Clear the value to null with the min tag type.
Definition: PointerSumType.h:117
llvm::PointerSumType::operator==
bool operator==(const PointerSumType &R) const
Definition: PointerSumType.h:169
llvm::detail::PointerSumTypeHelper::MinTag
constexpr static TagT MinTag
Definition: PointerSumType.h:240
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
TraitsT
llvm::PointerSumType
A sum type over pointer-like types.
Definition: PointerSumType.h:70
llvm::detail::PointerSumTypeHelper
A helper template for implementing PointerSumType.
Definition: PointerSumType.h:35
bit.h
llvm::PointerSumTypeMember::PointerT
PointerArgT PointerT
Definition: PointerSumType.h:29
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::PointerSumType::operator<=
bool operator<=(const PointerSumType &R) const
Definition: PointerSumType.h:181
llvm::PointerSumType::PointerSumType
constexpr PointerSumType()=default
N
#define N
llvm::PointerSumType::get
HelperT::template Lookup< N >::PointerT get() const
Definition: PointerSumType.h:125
DenseMapInfo.h
llvm::detail::PointerSumTypeHelper::Lookup
Definition: PointerSumType.h:216
llvm::PointerSumType::create
static PointerSumType create(typename HelperT::template Lookup< N >::PointerT Pointer)
A typed constructor for a specific tagged member of the sum type.
Definition: PointerSumType.h:110
llvm::PointerSumType::operator>
bool operator>(const PointerSumType &R) const
Definition: PointerSumType.h:178
llvm::PointerSumType::cast
HelperT::template Lookup< N >::PointerT cast() const
Definition: PointerSumType.h:131