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"
14#include "llvm/Support/PointerLikeTypeTraits.h"
15#include <cassert>
16#include <cstdint>
17#include <type_traits>
18
19namespace 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.
25template <uintptr_t N, typename PointerArgT,
26 typename TraitsArgT = PointerLikeTypeTraits<PointerArgT>>
27struct PointerSumTypeMember {
28 enum { Tag = N };
29 using PointerT = PointerArgT;
30 using TraitsT = TraitsArgT;
31};
32
33namespace detail {
34
35template <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.
70template <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
95public:
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 *
141 getAddrOfZeroTagPointer() 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 *
149 getAddrOfZeroTagPointer() {
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 {
167 return getOpaqueValue() & HelperT::PointerMask;
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
194protected:
195 void *getVoidPtr() const {
196 return reinterpret_cast<void *>(getOpaqueValue() & HelperT::PointerMask);
197 }
198};
199
200namespace 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..
205template <typename TagT, typename... MemberTs>
206struct 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.
265template <typename TagT, typename... MemberTs>
266struct 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::template create<SomeTag>(SomePointerInfo::getEmptyKey());
276 }
277
278 static inline SumType getTombstoneKey() {
279 return SumType::template create<SomeTag>(
280 SomePointerInfo::getTombstoneKey());
281 }
282
283 static unsigned getHashValue(const SumType &Arg) {
284 uintptr_t OpaqueValue = Arg.getOpaqueValue();
285 return DenseMapInfo<uintptr_t>::getHashValue(Val: OpaqueValue);
286 }
287
288 static bool isEqual(const SumType &LHS, const SumType &RHS) {
289 return LHS == RHS;
290 }
291};
292
293} // end namespace llvm
294
295#endif // LLVM_ADT_POINTERSUMTYPE_H
296