include/llvm/ADT/FunctionExtras.h

   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