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