1 files changed, 292 insertions, 0 deletions
diff --git a/third_party/llvm-project/include/llvm/ADT/FunctionExtras.h b/third_party/llvm-project/include/llvm/ADT/FunctionExtras.h
new file mode 100644
index 000000000..121aa527a
--- /dev/null
+++ b/third_party/llvm-project/include/llvm/ADT/FunctionExtras.h
@@ -0,0 +1,292 @@
+//===- FunctionExtras.h - Function type erasure utilities -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file provides a collection of function (or more generally, callable)
+/// type erasure utilities supplementing those provided by the standard library
+/// in `<function>`.
+///
+/// It provides `unique_function`, which works like `std::function` but supports
+/// move-only callable objects.
+///
+/// Future plans:
+/// - Add a `function` that provides const, volatile, and ref-qualified support,
+///   which doesn't work with `std::function`.
+/// - Provide support for specifying multiple signatures to type erase callable
+///   objects with an overload set, such as those produced by generic lambdas.
+/// - Expand to include a copyable utility that directly replaces std::function
+///   but brings the above improvements.
+///
+/// Note that LLVM's utilities are greatly simplified by not supporting
+/// allocators.
+///
+/// If the standard library ever begins to provide comparable facilities we can
+/// consider switching to those.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_FUNCTION_EXTRAS_H
+#define LLVM_ADT_FUNCTION_EXTRAS_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/PointerUnion.h"
+#include "llvm/Support/type_traits.h"
+#include <memory>
+
+namespace llvm {
+
+template <typename FunctionT> class unique_function;
+
+template <typename ReturnT, typename... ParamTs>
+class unique_function<ReturnT(ParamTs...)> {
+  static constexpr size_t InlineStorageSize = sizeof(void *) * 3;
+
+  // MSVC has a bug and ICEs if we give it a particular dependent value
+  // expression as part of the `std::conditional` below. To work around this,
+  // we build that into a template struct's constexpr bool.
+  template <typename T> struct IsSizeLessThanThresholdT {
+    static constexpr bool value = sizeof(T) <= (2 * sizeof(void *));
+  };
+
+  // Provide a type function to map parameters that won't observe extra copies
+  // or moves and which are small enough to likely pass in register to values
+  // and all other types to l-value reference types. We use this to compute the
+  // types used in our erased call utility to minimize copies and moves unless
+  // doing so would force things unnecessarily into memory.
+  //
+  // The heuristic used is related to common ABI register passing conventions.
+  // It doesn't have to be exact though, and in one way it is more strict
+  // because we want to still be able to observe either moves *or* copies.
+  template <typename T>
+  using AdjustedParamT = typename std::conditional<
+      !std::is_reference<T>::value &&
+          llvm::is_trivially_copy_constructible<T>::value &&
+          llvm::is_trivially_move_constructible<T>::value &&
+          IsSizeLessThanThresholdT<T>::value,
+      T, T &>::type;
+
+  // The type of the erased function pointer we use as a callback to dispatch to
+  // the stored callable when it is trivial to move and destroy.
+  using CallPtrT = ReturnT (*)(void *CallableAddr,
+                               AdjustedParamT<ParamTs>... Params);
+  using MovePtrT = void (*)(void *LHSCallableAddr, void *RHSCallableAddr);
+  using DestroyPtrT = void (*)(void *CallableAddr);
+
+  /// A struct to hold a single trivial callback with sufficient alignment for
+  /// our bitpacking.
+  struct alignas(8) TrivialCallback {
+    CallPtrT CallPtr;
+  };
+
+  /// A struct we use to aggregate three callbacks when we need full set of
+  /// operations.
+  struct alignas(8) NonTrivialCallbacks {
+    CallPtrT CallPtr;
+    MovePtrT MovePtr;
+    DestroyPtrT DestroyPtr;
+  };
+
+  // Create a pointer union between either a pointer to a static trivial call
+  // pointer in a struct or a pointer to a static struct of the call, move, and
+  // destroy pointers.
+  using CallbackPointerUnionT =
+      PointerUnion<TrivialCallback *, NonTrivialCallbacks *>;
+
+  // The main storage buffer. This will either have a pointer to out-of-line
+  // storage or an inline buffer storing the callable.
+  union StorageUnionT {
+    // For out-of-line storage we keep a pointer to the underlying storage and
+    // the size. This is enough to deallocate the memory.
+    struct OutOfLineStorageT {
+      void *StoragePtr;
+      size_t Size;
+      size_t Alignment;
+    } OutOfLineStorage;
+    static_assert(
+        sizeof(OutOfLineStorageT) <= InlineStorageSize,
+        "Should always use all of the out-of-line storage for inline storage!");
+
+    // For in-line storage, we just provide an aligned character buffer. We
+    // provide three pointers worth of storage here.
+    typename std::aligned_storage<InlineStorageSize, alignof(void *)>::type
+        InlineStorage;
+  } StorageUnion;
+
+  // A compressed pointer to either our dispatching callback or our table of
+  // dispatching callbacks and the flag for whether the callable itself is
+  // stored inline or not.
+  PointerIntPair<CallbackPointerUnionT, 1, bool> CallbackAndInlineFlag;
+
+  bool isInlineStorage() const { return CallbackAndInlineFlag.getInt(); }
+
+  bool isTrivialCallback() const {
+    return CallbackAndInlineFlag.getPointer().template is<TrivialCallback *>();
+  }
+
+  CallPtrT getTrivialCallback() const {
+    return CallbackAndInlineFlag.getPointer().template get<TrivialCallback *>()->CallPtr;
+  }
+
+  NonTrivialCallbacks *getNonTrivialCallbacks() const {
+    return CallbackAndInlineFlag.getPointer()
+        .template get<NonTrivialCallbacks *>();
+  }
+
+  void *getInlineStorage() { return &StorageUnion.InlineStorage; }
+
+  void *getOutOfLineStorage() {
+    return StorageUnion.OutOfLineStorage.StoragePtr;
+  }
+  size_t getOutOfLineStorageSize() const {
+    return StorageUnion.OutOfLineStorage.Size;
+  }
+  size_t getOutOfLineStorageAlignment() const {
+    return StorageUnion.OutOfLineStorage.Alignment;
+  }
+
+  void setOutOfLineStorage(void *Ptr, size_t Size, size_t Alignment) {
+    StorageUnion.OutOfLineStorage = {Ptr, Size, Alignment};
+  }
+
+  template <typename CallableT>
+  static ReturnT CallImpl(void *CallableAddr, AdjustedParamT<ParamTs>... Params) {
+    return (*reinterpret_cast<CallableT *>(CallableAddr))(
+        std::forward<ParamTs>(Params)...);
+  }
+
+  template <typename CallableT>
+  static void MoveImpl(void *LHSCallableAddr, void *RHSCallableAddr) noexcept {
+    new (LHSCallableAddr)
+        CallableT(std::move(*reinterpret_cast<CallableT *>(RHSCallableAddr)));
+  }
+
+  template <typename CallableT>
+  static void DestroyImpl(void *CallableAddr) noexcept {
+    reinterpret_cast<CallableT *>(CallableAddr)->~CallableT();
+  }
+
+public:
+  unique_function() = default;
+  unique_function(std::nullptr_t /*null_callable*/) {}
+
+  ~unique_function() {
+    if (!CallbackAndInlineFlag.getPointer())
+      return;
+
+    // Cache this value so we don't re-check it after type-erased operations.
+    bool IsInlineStorage = isInlineStorage();
+
+    if (!isTrivialCallback())
+      getNonTrivialCallbacks()->DestroyPtr(
+          IsInlineStorage ? getInlineStorage() : getOutOfLineStorage());
+
+    if (!IsInlineStorage)
+      deallocate_buffer(getOutOfLineStorage(), getOutOfLineStorageSize(),
+                        getOutOfLineStorageAlignment());
+  }
+
+  unique_function(unique_function &&RHS) noexcept {
+    // Copy the callback and inline flag.
+    CallbackAndInlineFlag = RHS.CallbackAndInlineFlag;
+
+    // If the RHS is empty, just copying the above is sufficient.
+    if (!RHS)
+      return;
+
+    if (!isInlineStorage()) {
+      // The out-of-line case is easiest to move.
+      StorageUnion.OutOfLineStorage = RHS.StorageUnion.OutOfLineStorage;
+    } else if (isTrivialCallback()) {
+      // Move is trivial, just memcpy the bytes across.
+      memcpy(getInlineStorage(), RHS.getInlineStorage(), InlineStorageSize);
+    } else {
+      // Non-trivial move, so dispatch to a type-erased implementation.
+      getNonTrivialCallbacks()->MovePtr(getInlineStorage(),
+                                        RHS.getInlineStorage());
+    }
+
+    // Clear the old callback and inline flag to get back to as-if-null.
+    RHS.CallbackAndInlineFlag = {};
+
+#ifndef NDEBUG
+    // In debug builds, we also scribble across the rest of the storage.
+    memset(RHS.getInlineStorage(), 0xAD, InlineStorageSize);
+#endif
+  }
+
+  unique_function &operator=(unique_function &&RHS) noexcept {
+    if (this == &RHS)
+      return *this;
+
+    // Because we don't try to provide any exception safety guarantees we can
+    // implement move assignment very simply by first destroying the current
+    // object and then move-constructing over top of it.
+    this->~unique_function();
+    new (this) unique_function(std::move(RHS));
+    return *this;
+  }
+
+  template <typename CallableT> unique_function(CallableT Callable) {
+    bool IsInlineStorage = true;
+    void *CallableAddr = getInlineStorage();
+    if (sizeof(CallableT) > InlineStorageSize ||
+        alignof(CallableT) > alignof(decltype(StorageUnion.InlineStorage))) {
+      IsInlineStorage = false;
+      // Allocate out-of-line storage. FIXME: Use an explicit alignment
+      // parameter in C++17 mode.
+      auto Size = sizeof(CallableT);
+      auto Alignment = alignof(CallableT);
+      CallableAddr = allocate_buffer(Size, Alignment);
+      setOutOfLineStorage(CallableAddr, Size, Alignment);
+    }
+
+    // Now move into the storage.
+    new (CallableAddr) CallableT(std::move(Callable));
+
+    // See if we can create a trivial callback. We need the callable to be
+    // trivially moved and trivially destroyed so that we don't have to store
+    // type erased callbacks for those operations.
+    //
+    // FIXME: We should use constexpr if here and below to avoid instantiating
+    // the non-trivial static objects when unnecessary. While the linker should
+    // remove them, it is still wasteful.
+    if (llvm::is_trivially_move_constructible<CallableT>::value &&
+        std::is_trivially_destructible<CallableT>::value) {
+      // We need to create a nicely aligned object. We use a static variable
+      // for this because it is a trivial struct.
+      static TrivialCallback Callback = { &CallImpl<CallableT> };
+
+      CallbackAndInlineFlag = {&Callback, IsInlineStorage};
+      return;
+    }
+
+    // Otherwise, we need to point at an object that contains all the different
+    // type erased behaviors needed. Create a static instance of the struct type
+    // here and then use a pointer to that.
+    static NonTrivialCallbacks Callbacks = {
+        &CallImpl<CallableT>, &MoveImpl<CallableT>, &DestroyImpl<CallableT>};
+
+    CallbackAndInlineFlag = {&Callbacks, IsInlineStorage};
+  }
+
+  ReturnT operator()(ParamTs... Params) {
+    void *CallableAddr =
+        isInlineStorage() ? getInlineStorage() : getOutOfLineStorage();
+
+    return (isTrivialCallback()
+                ? getTrivialCallback()
+                : getNonTrivialCallbacks()->CallPtr)(CallableAddr, Params...);
+  }
+
+  explicit operator bool() const {
+    return (bool)CallbackAndInlineFlag.getPointer();
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_FUNCTION_H