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
41namespace llvm {
42
43template <typename FunctionT> class unique_function;
44
45template <typename ReturnT, typename... ParamTs>
46class 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 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 return CallbackAndInlineFlag.getPointer().template get<TrivialCallback *>()->CallPtr;
133 }
134
135 NonTrivialCallbacks *getNonTrivialCallbacks() const {
136 return CallbackAndInlineFlag.getPointer()
137 .template get<NonTrivialCallbacks *>();
138 }
139
140 void *getInlineStorage() { return &StorageUnion.InlineStorage; }
141
142 void *getOutOfLineStorage() {
143 return StorageUnion.OutOfLineStorage.StoragePtr;
144 }
145 size_t getOutOfLineStorageSize() const {
146 return StorageUnion.OutOfLineStorage.Size;
147 }
148 size_t getOutOfLineStorageAlignment() const {
149 return StorageUnion.OutOfLineStorage.Alignment;
150 }
151
152 void setOutOfLineStorage(void *Ptr, size_t Size, size_t Alignment) {
153 StorageUnion.OutOfLineStorage = {Ptr, Size, Alignment};
154 }
155
156 template <typename CallableT>
157 static ReturnT CallImpl(void *CallableAddr, AdjustedParamT<ParamTs>... Params) {
158 return (*reinterpret_cast<CallableT *>(CallableAddr))(
159 std::forward<ParamTs>(Params)...);
160 }
161
162 template <typename CallableT>
163 static void MoveImpl(void *LHSCallableAddr, void *RHSCallableAddr) noexcept {
164 new (LHSCallableAddr)
165 CallableT(std::move(*reinterpret_cast<CallableT *>(RHSCallableAddr)));
166 }
167
168 template <typename CallableT>
169 static void DestroyImpl(void *CallableAddr) noexcept {
170 reinterpret_cast<CallableT *>(CallableAddr)->~CallableT();
171 }
172
173public:
174 unique_function() = default;
175 unique_function(std::nullptr_t /*null_callable*/) {}
176
177 ~unique_function() {
178 if (!CallbackAndInlineFlag.getPointer())
179 return;
180
181 // Cache this value so we don't re-check it after type-erased operations.
182 bool IsInlineStorage = isInlineStorage();
183
184 if (!isTrivialCallback())
185 getNonTrivialCallbacks()->DestroyPtr(
186 IsInlineStorage ? getInlineStorage() : getOutOfLineStorage());
187
188 if (!IsInlineStorage)
189 deallocate_buffer(getOutOfLineStorage(), getOutOfLineStorageSize(),
190 getOutOfLineStorageAlignment());
191 }
192
193 unique_function(unique_function &&RHS) noexcept {
194 // Copy the callback and inline flag.
195 CallbackAndInlineFlag = RHS.CallbackAndInlineFlag;
196
197 // If the RHS is empty, just copying the above is sufficient.
198 if (!RHS)
199 return;
200
201 if (!isInlineStorage()) {
202 // The out-of-line case is easiest to move.
203 StorageUnion.OutOfLineStorage = RHS.StorageUnion.OutOfLineStorage;
204 } else if (isTrivialCallback()) {
205 // Move is trivial, just memcpy the bytes across.
206 memcpy(getInlineStorage(), RHS.getInlineStorage(), InlineStorageSize);
207 } else {
208 // Non-trivial move, so dispatch to a type-erased implementation.
209 getNonTrivialCallbacks()->MovePtr(getInlineStorage(),
210 RHS.getInlineStorage());
211 }
212
213 // Clear the old callback and inline flag to get back to as-if-null.
214 RHS.CallbackAndInlineFlag = {};
215
216#ifndef NDEBUG
217 // In debug builds, we also scribble across the rest of the storage.
218 memset(RHS.getInlineStorage(), 0xAD, InlineStorageSize);
219#endif
220 }
221
222 unique_function &operator=(unique_function &&RHS) noexcept {
223 if (this == &RHS)
224 return *this;
225
226 // Because we don't try to provide any exception safety guarantees we can
227 // implement move assignment very simply by first destroying the current
228 // object and then move-constructing over top of it.
229 this->~unique_function();
230 new (this) unique_function(std::move(RHS));
231 return *this;
232 }
233
234 template <typename CallableT> unique_function(CallableT Callable) {
235 bool IsInlineStorage = true;
236 void *CallableAddr = getInlineStorage();
237 if (sizeof(CallableT) > InlineStorageSize ||
238 alignof(CallableT) > alignof(decltype(StorageUnion.InlineStorage))) {
239 IsInlineStorage = false;
240 // Allocate out-of-line storage. FIXME: Use an explicit alignment
241 // parameter in C++17 mode.
242 auto Size = sizeof(CallableT);
243 auto Alignment = alignof(CallableT);
244 CallableAddr = allocate_buffer(Size, Alignment);
245 setOutOfLineStorage(CallableAddr, Size, Alignment);
246 }
247
248 // Now move into the storage.
249 new (CallableAddr) CallableT(std::move(Callable));
250
251 // See if we can create a trivial callback. We need the callable to be
252 // trivially moved and trivially destroyed so that we don't have to store
253 // type erased callbacks for those operations.
254 //
255 // FIXME: We should use constexpr if here and below to avoid instantiating
256 // the non-trivial static objects when unnecessary. While the linker should
257 // remove them, it is still wasteful.
258 if (llvm::is_trivially_move_constructible<CallableT>::value &&
259 std::is_trivially_destructible<CallableT>::value) {
260 // We need to create a nicely aligned object. We use a static variable
261 // for this because it is a trivial struct.
262 static TrivialCallback Callback = { &CallImpl<CallableT> };
263
264 CallbackAndInlineFlag = {&Callback, IsInlineStorage};
265 return;
266 }
267
268 // Otherwise, we need to point at an object that contains all the different
269 // type erased behaviors needed. Create a static instance of the struct type
270 // here and then use a pointer to that.
271 static NonTrivialCallbacks Callbacks = {
272 &CallImpl<CallableT>, &MoveImpl<CallableT>, &DestroyImpl<CallableT>};
273
274 CallbackAndInlineFlag = {&Callbacks, IsInlineStorage};
275 }
276
277 ReturnT operator()(ParamTs... Params) {
278 void *CallableAddr =
279 isInlineStorage() ? getInlineStorage() : getOutOfLineStorage();
280
281 return (isTrivialCallback()
282 ? getTrivialCallback()
283 : getNonTrivialCallbacks()->CallPtr)(CallableAddr, Params...);
284 }
285
286 explicit operator bool() const {
287 return (bool)CallbackAndInlineFlag.getPointer();
288 }
289};
290
291} // end namespace llvm
292
293#endif // LLVM_ADT_FUNCTION_H
294