DWARF parsing and writing support using LLVM (#2520)

This imports LLVM code for DWARF handling. That code has the
Apache 2 license like us. It's also the same code used to
emit DWARF in the common toolchain, so it seems like a safe choice.

This adds two passes: --dwarfdump which runs the same code LLVM
runs for llvm-dwarfdump. This shows we can parse it ok, and will
be useful for debugging. And --dwarfupdate writes out the DWARF
sections (unchanged from what we read, so it just roundtrips - for
updating we need #2515).

This puts LLVM in thirdparty which is added here.

All the LLVM code is behind USE_LLVM_DWARF, which is on
by default, but off in JS for now, as it increases code size by 20%.

This current approach imports the LLVM files directly. This is not
how they are intended to be used, so it required a bunch of
local changes - more than I expected actually, for the platform-specific
stuff. For now this seems to work, so it may be good enough, but
in the long term we may want to switch to linking against libllvm.
A downside to doing that is that binaryen users would need to
have an LLVM build, and even in the waterfall builds we'd have a
problem - while we ship LLVM there anyhow, we constantly update
it, which means that binaryen would need to be on latest llvm all
the time too (which otherwise, given DWARF is quite stable, we
might not need to constantly update).

An even larger issue is that as I did this work I learned about how
DWARF works in LLVM, and while the reading code is easy to
reuse, the writing code is trickier. The main code path is heavily
integrated with the MC layer, which we don't have - we might want
to create a "fake MC layer" for that, but it sounds hard. Instead,
there is the YAML path which is used mostly for testing, and which
can convert DWARF to and from YAML and from binary. Using
the non-YAML parts there, we can convert binary DWARF to
the YAML layer's nice Info data, then convert that to binary. This
works, however, this is not the path LLVM uses normally, and it
supports only some basic DWARF sections - I had to add ranges
support, in fact. So if we need more complex things, we may end
up needing to use the MC layer approach, or consider some other
DWARF library. However, hopefully that should not affect the core
binaryen code which just calls a library for DWARF stuff.

Helps #2400

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