Line data Source code
1 : //===- FunctionExtras.h - Function type erasure utilities -------*- 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 : /// \file
10 : /// This file provides a collection of function (or more generally, callable)
11 : /// type erasure utilities supplementing those provided by the standard library
12 : /// in `<function>`.
13 : ///
14 : /// It provides `unique_function`, which works like `std::function` but supports
15 : /// move-only callable objects.
16 : ///
17 : /// Future plans:
18 : /// - Add a `function` that provides const, volatile, and ref-qualified support,
19 : /// which doesn't work with `std::function`.
20 : /// - Provide support for specifying multiple signatures to type erase callable
21 : /// objects with an overload set, such as those produced by generic lambdas.
22 : /// - Expand to include a copyable utility that directly replaces std::function
23 : /// but brings the above improvements.
24 : ///
25 : /// Note that LLVM's utilities are greatly simplified by not supporting
26 : /// allocators.
27 : ///
28 : /// If the standard library ever begins to provide comparable facilities we can
29 : /// consider switching to those.
30 : ///
31 : //===----------------------------------------------------------------------===//
32 :
33 : #ifndef LLVM_ADT_FUNCTION_EXTRAS_H
34 : #define LLVM_ADT_FUNCTION_EXTRAS_H
35 :
36 : #include "llvm/ADT/PointerIntPair.h"
37 : #include "llvm/ADT/PointerUnion.h"
38 : #include "llvm/Support/type_traits.h"
39 : #include <memory>
40 :
41 : namespace llvm {
42 :
43 : template <typename FunctionT> class unique_function;
44 :
45 : template <typename ReturnT, typename... ParamTs>
46 : class unique_function<ReturnT(ParamTs...)> {
47 : static constexpr size_t InlineStorageSize = sizeof(void *) * 3;
48 :
49 : // MSVC has a bug and ICEs if we give it a particular dependent value
50 : // expression as part of the `std::conditional` below. To work around this,
51 : // we build that into a template struct's constexpr bool.
52 : template <typename T> struct IsSizeLessThanThresholdT {
53 : static constexpr bool value = sizeof(T) <= (2 * sizeof(void *));
54 : };
55 :
56 : // Provide a type function to map parameters that won't observe extra copies
57 : // or moves and which are small enough to likely pass in register to values
58 : // and all other types to l-value reference types. We use this to compute the
59 : // types used in our erased call utility to minimize copies and moves unless
60 : // doing so would force things unnecessarily into memory.
61 : //
62 : // The heuristic used is related to common ABI register passing conventions.
63 : // It doesn't have to be exact though, and in one way it is more strict
64 : // because we want to still be able to observe either moves *or* copies.
65 : template <typename T>
66 : using AdjustedParamT = typename std::conditional<
67 : !std::is_reference<T>::value &&
68 : llvm::is_trivially_copy_constructible<T>::value &&
69 : llvm::is_trivially_move_constructible<T>::value &&
70 : IsSizeLessThanThresholdT<T>::value,
71 : T, T &>::type;
72 :
73 : // The type of the erased function pointer we use as a callback to dispatch to
74 : // the stored callable when it is trivial to move and destroy.
75 : using CallPtrT = ReturnT (*)(void *CallableAddr,
76 : AdjustedParamT<ParamTs>... Params);
77 : using MovePtrT = void (*)(void *LHSCallableAddr, void *RHSCallableAddr);
78 : using DestroyPtrT = void (*)(void *CallableAddr);
79 :
80 : /// A struct to hold a single trivial callback with sufficient alignment for
81 : /// our bitpacking.
82 : struct alignas(8) TrivialCallback {
83 : CallPtrT CallPtr;
84 : };
85 :
86 : /// A struct we use to aggregate three callbacks when we need full set of
87 : /// operations.
88 : struct alignas(8) NonTrivialCallbacks {
89 : CallPtrT CallPtr;
90 : MovePtrT MovePtr;
91 : DestroyPtrT DestroyPtr;
92 : };
93 :
94 : // Create a pointer union between either a pointer to a static trivial call
95 : // pointer in a struct or a pointer to a static struct of the call, move, and
96 : // destroy pointers.
97 : using CallbackPointerUnionT =
98 : PointerUnion<TrivialCallback *, NonTrivialCallbacks *>;
99 :
100 : // The main storage buffer. This will either have a pointer to out-of-line
101 : // storage or an inline buffer storing the callable.
102 : union StorageUnionT {
103 : // For out-of-line storage we keep a pointer to the underlying storage and
104 : // the size. This is enough to deallocate the memory.
105 : struct OutOfLineStorageT {
106 : void *StoragePtr;
107 : size_t Size;
108 : size_t Alignment;
109 : } OutOfLineStorage;
110 : static_assert(
111 : sizeof(OutOfLineStorageT) <= InlineStorageSize,
112 : "Should always use all of the out-of-line storage for inline storage!");
113 :
114 : // For in-line storage, we just provide an aligned character buffer. We
115 : // provide three pointers worth of storage here.
116 : typename std::aligned_storage<InlineStorageSize, alignof(void *)>::type
117 : InlineStorage;
118 : } StorageUnion;
119 :
120 : // A compressed pointer to either our dispatching callback or our table of
121 : // dispatching callbacks and the flag for whether the callable itself is
122 : // stored inline or not.
123 : PointerIntPair<CallbackPointerUnionT, 1, bool> CallbackAndInlineFlag;
124 :
125 1507 : bool isInlineStorage() const { return CallbackAndInlineFlag.getInt(); }
126 :
127 : bool isTrivialCallback() const {
128 : return CallbackAndInlineFlag.getPointer().template is<TrivialCallback *>();
129 : }
130 :
131 : CallPtrT getTrivialCallback() const {
132 1096 : return CallbackAndInlineFlag.getPointer().template get<TrivialCallback *>()->CallPtr;
133 : }
134 :
135 : NonTrivialCallbacks *getNonTrivialCallbacks() const {
136 : return CallbackAndInlineFlag.getPointer()
137 : .template get<NonTrivialCallbacks *>();
138 : }
139 :
140 1081 : void *getInlineStorage() { return &StorageUnion.InlineStorage; }
141 :
142 0 : void *getOutOfLineStorage() {
143 0 : return StorageUnion.OutOfLineStorage.StoragePtr;
144 : }
145 0 : size_t getOutOfLineStorageSize() const {
146 0 : return StorageUnion.OutOfLineStorage.Size;
147 : }
148 0 : size_t getOutOfLineStorageAlignment() const {
149 0 : return StorageUnion.OutOfLineStorage.Alignment;
150 : }
151 0 :
152 0 : void setOutOfLineStorage(void *Ptr, size_t Size, size_t Alignment) {
153 : StorageUnion.OutOfLineStorage = {Ptr, Size, Alignment};
154 0 : }
155 0 :
156 : template <typename CallableT>
157 0 : static ReturnT CallImpl(void *CallableAddr, AdjustedParamT<ParamTs>... Params) {
158 0 : return (*reinterpret_cast<CallableT *>(CallableAddr))(
159 0 : std::forward<ParamTs>(Params)...);
160 0 : }
161 0 :
162 : template <typename CallableT>
163 0 : static void MoveImpl(void *LHSCallableAddr, void *RHSCallableAddr) noexcept {
164 0 : new (LHSCallableAddr)
165 : CallableT(std::move(*reinterpret_cast<CallableT *>(RHSCallableAddr)));
166 0 : }
167 0 :
168 : template <typename CallableT>
169 0 : static void DestroyImpl(void *CallableAddr) noexcept {
170 0 : reinterpret_cast<CallableT *>(CallableAddr)->~CallableT();
171 0 : }
172 0 :
173 0 : public:
174 : unique_function() = default;
175 1064 : unique_function(std::nullptr_t /*null_callable*/) {}
176 1156 :
177 1111 : ~unique_function() {
178 94 : if (!CallbackAndInlineFlag.getPointer())
179 270 : return;
180 345 :
181 270 : // Cache this value so we don't re-check it after type-erased operations.
182 0 : bool IsInlineStorage = isInlineStorage();
183 198 :
184 262 : if (!isTrivialCallback())
185 292 : getNonTrivialCallbacks()->DestroyPtr(
186 47 : IsInlineStorage ? getInlineStorage() : getOutOfLineStorage());
187 296 :
188 343 : if (!IsInlineStorage)
189 343 : deallocate_buffer(getOutOfLineStorage(), getOutOfLineStorageSize(),
190 0 : getOutOfLineStorageAlignment());
191 347 : }
192 300 :
193 300 : unique_function(unique_function &&RHS) noexcept {
194 0 : // Copy the callback and inline flag.
195 20 : CallbackAndInlineFlag = RHS.CallbackAndInlineFlag;
196 40 :
197 0 : // If the RHS is empty, just copying the above is sufficient.
198 47 : if (!RHS)
199 0 : return;
200 0 :
201 0 : if (!isInlineStorage()) {
202 67 : // The out-of-line case is easiest to move.
203 28 : StorageUnion.OutOfLineStorage = RHS.StorageUnion.OutOfLineStorage;
204 103 : } else if (isTrivialCallback()) {
205 14 : // Move is trivial, just memcpy the bytes across.
206 20 : memcpy(getInlineStorage(), RHS.getInlineStorage(), InlineStorageSize);
207 0 : } else {
208 0 : // Non-trivial move, so dispatch to a type-erased implementation.
209 20 : getNonTrivialCallbacks()->MovePtr(getInlineStorage(),
210 30 : RHS.getInlineStorage());
211 64 : }
212 64 :
213 0 : // Clear the old callback and inline flag to get back to as-if-null.
214 14 : RHS.CallbackAndInlineFlag = {};
215 14 :
216 0 : #ifndef NDEBUG
217 30 : // In debug builds, we also scribble across the rest of the storage.
218 42 : memset(RHS.getInlineStorage(), 0xAD, InlineStorageSize);
219 0 : #endif
220 10 : }
221 16 :
222 69 : unique_function &operator=(unique_function &&RHS) noexcept {
223 0 : if (this == &RHS)
224 53 : return *this;
225 36 :
226 32 : // Because we don't try to provide any exception safety guarantees we can
227 48 : // implement move assignment very simply by first destroying the current
228 0 : // object and then move-constructing over top of it.
229 0 : this->~unique_function();
230 0 : new (this) unique_function(std::move(RHS));
231 : return *this;
232 4 : }
233 52 :
234 56 : template <typename CallableT> unique_function(CallableT Callable) {
235 14 : bool IsInlineStorage = true;
236 4 : void *CallableAddr = getInlineStorage();
237 24 : if (sizeof(CallableT) > InlineStorageSize ||
238 0 : alignof(CallableT) > alignof(decltype(StorageUnion.InlineStorage))) {
239 4 : IsInlineStorage = false;
240 38 : // Allocate out-of-line storage. FIXME: Use an explicit alignment
241 8 : // parameter in C++17 mode.
242 16 : auto Size = sizeof(CallableT);
243 0 : auto Alignment = alignof(CallableT);
244 14 : CallableAddr = allocate_buffer(Size, Alignment);
245 14 : setOutOfLineStorage(CallableAddr, Size, Alignment);
246 0 : }
247 14 :
248 8 : // Now move into the storage.
249 14 : new (CallableAddr) CallableT(std::move(Callable));
250 0 :
251 14 : // See if we can create a trivial callback. We need the callable to be
252 73 : // trivially moved and trivially destroyed so that we don't have to store
253 0 : // type erased callbacks for those operations.
254 14 : //
255 8 : // FIXME: We should use constexpr if here and below to avoid instantiating
256 64 : // the non-trivial static objects when unnecessary. While the linker should
257 50 : // remove them, it is still wasteful.
258 64 : if (llvm::is_trivially_move_constructible<CallableT>::value &&
259 14 : std::is_trivially_destructible<CallableT>::value) {
260 1 : // We need to create a nicely aligned object. We use a static variable
261 0 : // for this because it is a trivial struct.
262 48 : static TrivialCallback Callback = { &CallImpl<CallableT> };
263 0 :
264 49 : CallbackAndInlineFlag = {&Callback, IsInlineStorage};
265 0 : return;
266 2 : }
267 0 :
268 2 : // Otherwise, we need to point at an object that contains all the different
269 0 : // type erased behaviors needed. Create a static instance of the struct type
270 157 : // here and then use a pointer to that.
271 0 : static NonTrivialCallbacks Callbacks = {
272 1 : &CallImpl<CallableT>, &MoveImpl<CallableT>, &DestroyImpl<CallableT>};
273 0 :
274 185 : CallbackAndInlineFlag = {&Callbacks, IsInlineStorage};
275 123 : }
276 189 :
277 83 : ReturnT operator()(ParamTs... Params) {
278 21 : void *CallableAddr =
279 97 : isInlineStorage() ? getInlineStorage() : getOutOfLineStorage();
280 16 :
281 0 : return (isTrivialCallback()
282 95 : ? getTrivialCallback()
283 1042 : : getNonTrivialCallbacks()->CallPtr)(CallableAddr, Params...);
284 5 : }
285 996 :
286 5 : explicit operator bool() const {
287 0 : return (bool)CallbackAndInlineFlag.getPointer();
288 2191 : }
289 1386 : };
290 163 :
291 0 : } // end namespace llvm
292 18 :
293 0 : #endif // LLVM_ADT_FUNCTION_H
|
