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