contrib/llvm/include/llvm/ADT/FunctionExtras.h

   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   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
 173 public:
 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