LLVM  10.0.0svn
FunctionExtras.h
Go to the documentation of this file.
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 
36 #include "llvm/ADT/PointerUnion.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 &&
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 =
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.
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 
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 
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 
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.
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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
PointerTy getPointer() const
unique_function & operator=(unique_function &&RHS) noexcept
unique_function(unique_function &&RHS) noexcept
IntType getInt() const
An implementation of std::is_trivially_move_constructible since we have users with STLs that don&#39;t ye...
Definition: type_traits.h:110
PointerIntPair - This class implements a pair of a pointer and small integer.
An implementation of std::is_trivially_copy_constructible since we have users with STLs that don&#39;t ye...
Definition: type_traits.h:99
uint32_t Size
Definition: Profile.cpp:46
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:156