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, 579 insertions, 0 deletions

diff --git a/third_party/llvm-project/include/llvm/Object/ObjectFile.h b/third_party/llvm-project/include/llvm/Object/ObjectFile.h
new file mode 100644
index 000000000..d53c9b49c
--- /dev/null
+++ b/third_party/llvm-project/include/llvm/Object/ObjectFile.h
@@ -0,0 +1,579 @@
+//===- ObjectFile.h - File format independent object file -------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file declares a file format independent ObjectFile class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_OBJECT_OBJECTFILE_H
+#define LLVM_OBJECT_OBJECTFILE_H
+
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Triple.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/BinaryFormat/Magic.h"
+#include "llvm/MC/SubtargetFeature.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/Error.h"
+#include "llvm/Object/SymbolicFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include <cassert>
+#include <cstdint>
+#include <memory>
+#include <system_error>
+
+namespace llvm {
+
+class ARMAttributeParser;
+
+namespace object {
+
+class COFFObjectFile;
+class MachOObjectFile;
+class ObjectFile;
+class SectionRef;
+class SymbolRef;
+class symbol_iterator;
+class WasmObjectFile;
+
+using section_iterator = content_iterator<SectionRef>;
+
+/// This is a value type class that represents a single relocation in the list
+/// of relocations in the object file.
+class RelocationRef {
+  DataRefImpl RelocationPimpl;
+  const ObjectFile *OwningObject = nullptr;
+
+public:
+  RelocationRef() = default;
+  RelocationRef(DataRefImpl RelocationP, const ObjectFile *Owner);
+
+  bool operator==(const RelocationRef &Other) const;
+
+  void moveNext();
+
+  uint64_t getOffset() const;
+  symbol_iterator getSymbol() const;
+  uint64_t getType() const;
+
+  /// Get a string that represents the type of this relocation.
+  ///
+  /// This is for display purposes only.
+  void getTypeName(SmallVectorImpl<char> &Result) const;
+
+  DataRefImpl getRawDataRefImpl() const;
+  const ObjectFile *getObject() const;
+};
+
+using relocation_iterator = content_iterator<RelocationRef>;
+
+/// This is a value type class that represents a single section in the list of
+/// sections in the object file.
+class SectionRef {
+  friend class SymbolRef;
+
+  DataRefImpl SectionPimpl;
+  const ObjectFile *OwningObject = nullptr;
+
+public:
+  SectionRef() = default;
+  SectionRef(DataRefImpl SectionP, const ObjectFile *Owner);
+
+  bool operator==(const SectionRef &Other) const;
+  bool operator!=(const SectionRef &Other) const;
+  bool operator<(const SectionRef &Other) const;
+
+  void moveNext();
+
+  Expected<StringRef> getName() const;
+  uint64_t getAddress() const;
+  uint64_t getIndex() const;
+  uint64_t getSize() const;
+  Expected<StringRef> getContents() const;
+
+  /// Get the alignment of this section as the actual value (not log 2).
+  uint64_t getAlignment() const;
+
+  bool isCompressed() const;
+  /// Whether this section contains instructions.
+  bool isText() const;
+  /// Whether this section contains data, not instructions.
+  bool isData() const;
+  /// Whether this section contains BSS uninitialized data.
+  bool isBSS() const;
+  bool isVirtual() const;
+  bool isBitcode() const;
+  bool isStripped() const;
+
+  /// Whether this section will be placed in the text segment, according to the
+  /// Berkeley size format. This is true if the section is allocatable, and
+  /// contains either code or readonly data.
+  bool isBerkeleyText() const;
+  /// Whether this section will be placed in the data segment, according to the
+  /// Berkeley size format. This is true if the section is allocatable and
+  /// contains data (e.g. PROGBITS), but is not text.
+  bool isBerkeleyData() const;
+
+  bool containsSymbol(SymbolRef S) const;
+
+  relocation_iterator relocation_begin() const;
+  relocation_iterator relocation_end() const;
+  iterator_range<relocation_iterator> relocations() const {
+    return make_range(relocation_begin(), relocation_end());
+  }
+  Expected<section_iterator> getRelocatedSection() const;
+
+  DataRefImpl getRawDataRefImpl() const;
+  const ObjectFile *getObject() const;
+};
+
+struct SectionedAddress {
+  const static uint64_t UndefSection = UINT64_MAX;
+
+  uint64_t Address = 0;
+  uint64_t SectionIndex = UndefSection;
+};
+
+inline bool operator<(const SectionedAddress &LHS,
+                      const SectionedAddress &RHS) {
+  return std::tie(LHS.SectionIndex, LHS.Address) <
+         std::tie(RHS.SectionIndex, RHS.Address);
+}
+
+inline bool operator==(const SectionedAddress &LHS,
+                       const SectionedAddress &RHS) {
+  return std::tie(LHS.SectionIndex, LHS.Address) ==
+         std::tie(RHS.SectionIndex, RHS.Address);
+}
+
+/// This is a value type class that represents a single symbol in the list of
+/// symbols in the object file.
+class SymbolRef : public BasicSymbolRef {
+  friend class SectionRef;
+
+public:
+  enum Type {
+    ST_Unknown, // Type not specified
+    ST_Data,
+    ST_Debug,
+    ST_File,
+    ST_Function,
+    ST_Other
+  };
+
+  SymbolRef() = default;
+  SymbolRef(DataRefImpl SymbolP, const ObjectFile *Owner);
+  SymbolRef(const BasicSymbolRef &B) : BasicSymbolRef(B) {
+    assert(isa<ObjectFile>(BasicSymbolRef::getObject()));
+  }
+
+  Expected<StringRef> getName() const;
+  /// Returns the symbol virtual address (i.e. address at which it will be
+  /// mapped).
+  Expected<uint64_t> getAddress() const;
+
+  /// Return the value of the symbol depending on the object this can be an
+  /// offset or a virtual address.
+  uint64_t getValue() const;
+
+  /// Get the alignment of this symbol as the actual value (not log 2).
+  uint32_t getAlignment() const;
+  uint64_t getCommonSize() const;
+  Expected<SymbolRef::Type> getType() const;
+
+  /// Get section this symbol is defined in reference to. Result is
+  /// end_sections() if it is undefined or is an absolute symbol.
+  Expected<section_iterator> getSection() const;
+
+  const ObjectFile *getObject() const;
+};
+
+class symbol_iterator : public basic_symbol_iterator {
+public:
+  symbol_iterator(SymbolRef Sym) : basic_symbol_iterator(Sym) {}
+  symbol_iterator(const basic_symbol_iterator &B)
+      : basic_symbol_iterator(SymbolRef(B->getRawDataRefImpl(),
+                                        cast<ObjectFile>(B->getObject()))) {}
+
+  const SymbolRef *operator->() const {
+    const BasicSymbolRef &P = basic_symbol_iterator::operator *();
+    return static_cast<const SymbolRef*>(&P);
+  }
+
+  const SymbolRef &operator*() const {
+    const BasicSymbolRef &P = basic_symbol_iterator::operator *();
+    return static_cast<const SymbolRef&>(P);
+  }
+};
+
+/// This class is the base class for all object file types. Concrete instances
+/// of this object are created by createObjectFile, which figures out which type
+/// to create.
+class ObjectFile : public SymbolicFile {
+  virtual void anchor();
+
+protected:
+  ObjectFile(unsigned int Type, MemoryBufferRef Source);
+
+  const uint8_t *base() const {
+    return reinterpret_cast<const uint8_t *>(Data.getBufferStart());
+  }
+
+  // These functions are for SymbolRef to call internally. The main goal of
+  // this is to allow SymbolRef::SymbolPimpl to point directly to the symbol
+  // entry in the memory mapped object file. SymbolPimpl cannot contain any
+  // virtual functions because then it could not point into the memory mapped
+  // file.
+  //
+  // Implementations assume that the DataRefImpl is valid and has not been
+  // modified externally. It's UB otherwise.
+  friend class SymbolRef;
+
+  virtual Expected<StringRef> getSymbolName(DataRefImpl Symb) const = 0;
+  Error printSymbolName(raw_ostream &OS,
+                                  DataRefImpl Symb) const override;
+  virtual Expected<uint64_t> getSymbolAddress(DataRefImpl Symb) const = 0;
+  virtual uint64_t getSymbolValueImpl(DataRefImpl Symb) const = 0;
+  virtual uint32_t getSymbolAlignment(DataRefImpl Symb) const;
+  virtual uint64_t getCommonSymbolSizeImpl(DataRefImpl Symb) const = 0;
+  virtual Expected<SymbolRef::Type> getSymbolType(DataRefImpl Symb) const = 0;
+  virtual Expected<section_iterator>
+  getSymbolSection(DataRefImpl Symb) const = 0;
+
+  // Same as above for SectionRef.
+  friend class SectionRef;
+
+  virtual void moveSectionNext(DataRefImpl &Sec) const = 0;
+  virtual Expected<StringRef> getSectionName(DataRefImpl Sec) const = 0;
+  virtual uint64_t getSectionAddress(DataRefImpl Sec) const = 0;
+  virtual uint64_t getSectionIndex(DataRefImpl Sec) const = 0;
+  virtual uint64_t getSectionSize(DataRefImpl Sec) const = 0;
+  virtual Expected<ArrayRef<uint8_t>>
+  getSectionContents(DataRefImpl Sec) const = 0;
+  virtual uint64_t getSectionAlignment(DataRefImpl Sec) const = 0;
+  virtual bool isSectionCompressed(DataRefImpl Sec) const = 0;
+  virtual bool isSectionText(DataRefImpl Sec) const = 0;
+  virtual bool isSectionData(DataRefImpl Sec) const = 0;
+  virtual bool isSectionBSS(DataRefImpl Sec) const = 0;
+  // A section is 'virtual' if its contents aren't present in the object image.
+  virtual bool isSectionVirtual(DataRefImpl Sec) const = 0;
+  virtual bool isSectionBitcode(DataRefImpl Sec) const;
+  virtual bool isSectionStripped(DataRefImpl Sec) const;
+  virtual bool isBerkeleyText(DataRefImpl Sec) const;
+  virtual bool isBerkeleyData(DataRefImpl Sec) const;
+  virtual relocation_iterator section_rel_begin(DataRefImpl Sec) const = 0;
+  virtual relocation_iterator section_rel_end(DataRefImpl Sec) const = 0;
+  virtual Expected<section_iterator> getRelocatedSection(DataRefImpl Sec) const;
+
+  // Same as above for RelocationRef.
+  friend class RelocationRef;
+  virtual void moveRelocationNext(DataRefImpl &Rel) const = 0;
+  virtual uint64_t getRelocationOffset(DataRefImpl Rel) const = 0;
+  virtual symbol_iterator getRelocationSymbol(DataRefImpl Rel) const = 0;
+  virtual uint64_t getRelocationType(DataRefImpl Rel) const = 0;
+  virtual void getRelocationTypeName(DataRefImpl Rel,
+                                     SmallVectorImpl<char> &Result) const = 0;
+
+  uint64_t getSymbolValue(DataRefImpl Symb) const;
+
+public:
+  ObjectFile() = delete;
+  ObjectFile(const ObjectFile &other) = delete;
+
+  uint64_t getCommonSymbolSize(DataRefImpl Symb) const {
+    assert(getSymbolFlags(Symb) & SymbolRef::SF_Common);
+    return getCommonSymbolSizeImpl(Symb);
+  }
+
+  virtual std::vector<SectionRef> dynamic_relocation_sections() const {
+    return std::vector<SectionRef>();
+  }
+
+  using symbol_iterator_range = iterator_range<symbol_iterator>;
+  symbol_iterator_range symbols() const {
+    return symbol_iterator_range(symbol_begin(), symbol_end());
+  }
+
+  virtual section_iterator section_begin() const = 0;
+  virtual section_iterator section_end() const = 0;
+
+  using section_iterator_range = iterator_range<section_iterator>;
+  section_iterator_range sections() const {
+    return section_iterator_range(section_begin(), section_end());
+  }
+
+  /// The number of bytes used to represent an address in this object
+  ///        file format.
+  virtual uint8_t getBytesInAddress() const = 0;
+
+  virtual StringRef getFileFormatName() const = 0;
+  virtual Triple::ArchType getArch() const = 0;
+  virtual SubtargetFeatures getFeatures() const = 0;
+  virtual void setARMSubArch(Triple &TheTriple) const { }
+  virtual Expected<uint64_t> getStartAddress() const {
+    // XXX BINARYEN
+    llvm_unreachable("getStartAddress");
+    //return errorCodeToError(object_error::parse_failed);
+  };
+
+  /// Create a triple from the data in this object file.
+  Triple makeTriple() const;
+
+  /// Maps a debug section name to a standard DWARF section name.
+  virtual StringRef mapDebugSectionName(StringRef Name) const { return Name; }
+
+  /// True if this is a relocatable object (.o/.obj).
+  virtual bool isRelocatableObject() const = 0;
+
+  /// @returns Pointer to ObjectFile subclass to handle this type of object.
+  /// @param ObjectPath The path to the object file. ObjectPath.isObject must
+  ///        return true.
+  /// Create ObjectFile from path.
+  static Expected<OwningBinary<ObjectFile>>
+  createObjectFile(StringRef ObjectPath);
+
+  static Expected<std::unique_ptr<ObjectFile>>
+  createObjectFile(MemoryBufferRef Object, llvm::file_magic Type);
+  static Expected<std::unique_ptr<ObjectFile>>
+  createObjectFile(MemoryBufferRef Object) {
+    return createObjectFile(Object, llvm::file_magic::unknown);
+  }
+
+  static bool classof(const Binary *v) {
+    return v->isObject();
+  }
+
+  static Expected<std::unique_ptr<COFFObjectFile>>
+  createCOFFObjectFile(MemoryBufferRef Object);
+
+  static Expected<std::unique_ptr<ObjectFile>>
+  createXCOFFObjectFile(MemoryBufferRef Object, unsigned FileType);
+
+  static Expected<std::unique_ptr<ObjectFile>>
+  createELFObjectFile(MemoryBufferRef Object);
+
+  static Expected<std::unique_ptr<MachOObjectFile>>
+  createMachOObjectFile(MemoryBufferRef Object,
+                        uint32_t UniversalCputype = 0,
+                        uint32_t UniversalIndex = 0);
+
+  static Expected<std::unique_ptr<WasmObjectFile>>
+  createWasmObjectFile(MemoryBufferRef Object);
+};
+
+// Inline function definitions.
+inline SymbolRef::SymbolRef(DataRefImpl SymbolP, const ObjectFile *Owner)
+    : BasicSymbolRef(SymbolP, Owner) {}
+
+inline Expected<StringRef> SymbolRef::getName() const {
+  return getObject()->getSymbolName(getRawDataRefImpl());
+}
+
+inline Expected<uint64_t> SymbolRef::getAddress() const {
+  return getObject()->getSymbolAddress(getRawDataRefImpl());
+}
+
+inline uint64_t SymbolRef::getValue() const {
+  return getObject()->getSymbolValue(getRawDataRefImpl());
+}
+
+inline uint32_t SymbolRef::getAlignment() const {
+  return getObject()->getSymbolAlignment(getRawDataRefImpl());
+}
+
+inline uint64_t SymbolRef::getCommonSize() const {
+  return getObject()->getCommonSymbolSize(getRawDataRefImpl());
+}
+
+inline Expected<section_iterator> SymbolRef::getSection() const {
+  return getObject()->getSymbolSection(getRawDataRefImpl());
+}
+
+inline Expected<SymbolRef::Type> SymbolRef::getType() const {
+  return getObject()->getSymbolType(getRawDataRefImpl());
+}
+
+inline const ObjectFile *SymbolRef::getObject() const {
+  const SymbolicFile *O = BasicSymbolRef::getObject();
+  return cast<ObjectFile>(O);
+}
+
+/// SectionRef
+inline SectionRef::SectionRef(DataRefImpl SectionP,
+                              const ObjectFile *Owner)
+  : SectionPimpl(SectionP)
+  , OwningObject(Owner) {}
+
+inline bool SectionRef::operator==(const SectionRef &Other) const {
+  return OwningObject == Other.OwningObject &&
+         SectionPimpl == Other.SectionPimpl;
+}
+
+inline bool SectionRef::operator!=(const SectionRef &Other) const {
+  return !(*this == Other);
+}
+
+inline bool SectionRef::operator<(const SectionRef &Other) const {
+  assert(OwningObject == Other.OwningObject);
+  return SectionPimpl < Other.SectionPimpl;
+}
+
+inline void SectionRef::moveNext() {
+  return OwningObject->moveSectionNext(SectionPimpl);
+}
+
+inline Expected<StringRef> SectionRef::getName() const {
+  return OwningObject->getSectionName(SectionPimpl);
+}
+
+inline uint64_t SectionRef::getAddress() const {
+  return OwningObject->getSectionAddress(SectionPimpl);
+}
+
+inline uint64_t SectionRef::getIndex() const {
+  return OwningObject->getSectionIndex(SectionPimpl);
+}
+
+inline uint64_t SectionRef::getSize() const {
+  return OwningObject->getSectionSize(SectionPimpl);
+}
+
+inline Expected<StringRef> SectionRef::getContents() const {
+  Expected<ArrayRef<uint8_t>> Res =
+      OwningObject->getSectionContents(SectionPimpl);
+  if (!Res)
+    return Res.takeError();
+  return StringRef(reinterpret_cast<const char *>(Res->data()), Res->size());
+}
+
+inline uint64_t SectionRef::getAlignment() const {
+  return OwningObject->getSectionAlignment(SectionPimpl);
+}
+
+inline bool SectionRef::isCompressed() const {
+  return OwningObject->isSectionCompressed(SectionPimpl);
+}
+
+inline bool SectionRef::isText() const {
+  return OwningObject->isSectionText(SectionPimpl);
+}
+
+inline bool SectionRef::isData() const {
+  return OwningObject->isSectionData(SectionPimpl);
+}
+
+inline bool SectionRef::isBSS() const {
+  return OwningObject->isSectionBSS(SectionPimpl);
+}
+
+inline bool SectionRef::isVirtual() const {
+  return OwningObject->isSectionVirtual(SectionPimpl);
+}
+
+inline bool SectionRef::isBitcode() const {
+  return OwningObject->isSectionBitcode(SectionPimpl);
+}
+
+inline bool SectionRef::isStripped() const {
+  return OwningObject->isSectionStripped(SectionPimpl);
+}
+
+inline bool SectionRef::isBerkeleyText() const {
+  return OwningObject->isBerkeleyText(SectionPimpl);
+}
+
+inline bool SectionRef::isBerkeleyData() const {
+  return OwningObject->isBerkeleyData(SectionPimpl);
+}
+
+inline relocation_iterator SectionRef::relocation_begin() const {
+  return OwningObject->section_rel_begin(SectionPimpl);
+}
+
+inline relocation_iterator SectionRef::relocation_end() const {
+  return OwningObject->section_rel_end(SectionPimpl);
+}
+
+inline Expected<section_iterator> SectionRef::getRelocatedSection() const {
+  return OwningObject->getRelocatedSection(SectionPimpl);
+}
+
+inline DataRefImpl SectionRef::getRawDataRefImpl() const {
+  return SectionPimpl;
+}
+
+inline const ObjectFile *SectionRef::getObject() const {
+  return OwningObject;
+}
+
+/// RelocationRef
+inline RelocationRef::RelocationRef(DataRefImpl RelocationP,
+                              const ObjectFile *Owner)
+  : RelocationPimpl(RelocationP)
+  , OwningObject(Owner) {}
+
+inline bool RelocationRef::operator==(const RelocationRef &Other) const {
+  return RelocationPimpl == Other.RelocationPimpl;
+}
+
+inline void RelocationRef::moveNext() {
+  return OwningObject->moveRelocationNext(RelocationPimpl);
+}
+
+inline uint64_t RelocationRef::getOffset() const {
+  return OwningObject->getRelocationOffset(RelocationPimpl);
+}
+
+inline symbol_iterator RelocationRef::getSymbol() const {
+  return OwningObject->getRelocationSymbol(RelocationPimpl);
+}
+
+inline uint64_t RelocationRef::getType() const {
+  return OwningObject->getRelocationType(RelocationPimpl);
+}
+
+inline void RelocationRef::getTypeName(SmallVectorImpl<char> &Result) const {
+  return OwningObject->getRelocationTypeName(RelocationPimpl, Result);
+}
+
+inline DataRefImpl RelocationRef::getRawDataRefImpl() const {
+  return RelocationPimpl;
+}
+
+inline const ObjectFile *RelocationRef::getObject() const {
+  return OwningObject;
+}
+
+} // end namespace object
+
+template <> struct DenseMapInfo<object::SectionRef> {
+  static bool isEqual(const object::SectionRef &A,
+                      const object::SectionRef &B) {
+    return A == B;
+  }
+  static object::SectionRef getEmptyKey() {
+    return object::SectionRef({}, nullptr);
+  }
+  static object::SectionRef getTombstoneKey() {
+    object::DataRefImpl TS;
+    TS.p = (uintptr_t)-1;
+    return object::SectionRef(TS, nullptr);
+  }
+  static unsigned getHashValue(const object::SectionRef &Sec) {
+    object::DataRefImpl Raw = Sec.getRawDataRefImpl();
+    return hash_combine(Raw.p, Raw.d.a, Raw.d.b);
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_OBJECT_OBJECTFILE_H