[JITLink] Switch from an atom-based model to a "blocks and symbols" model.

In the Atom model the symbols, content and relocations of a relocatable object
file are represented as a graph of atoms, where each Atom represents a
contiguous block of content with a single name (or no name at all if the
content is anonymous), and where edges between Atoms represent relocations.
If more than one symbol is associated with a contiguous block of content then
the content is broken into multiple atoms and layout constraints (represented by
edges) are introduced to ensure that the content remains effectively contiguous.
These layout constraints must be kept in mind when examining the content
associated with a symbol (it may be spread over multiple atoms) or when applying
certain relocation types (e.g. MachO subtractors).

This patch replaces the Atom model in JITLink with a blocks-and-symbols model.
The blocks-and-symbols model represents relocatable object files as bipartite
graphs, with one set of nodes representing contiguous content (Blocks) and
another representing named or anonymous locations (Symbols) within a Block.
Relocations are represented as edges from Blocks to Symbols. This scheme
removes layout constraints (simplifying handling of MachO alt-entry symbols,
and hopefully ELF sections at some point in the future) and simplifies some
relocation logic.

llvm-svn: 373689

1 files changed, 269 insertions, 0 deletions

diff --git a/llvm/lib/ExecutionEngine/JITLink/MachOLinkGraphBuilder.h b/llvm/lib/ExecutionEngine/JITLink/MachOLinkGraphBuilder.h
new file mode 100644
index 00000000000..cba26e9494b
--- /dev/null
+++ b/llvm/lib/ExecutionEngine/JITLink/MachOLinkGraphBuilder.h
@@ -0,0 +1,269 @@
+//===----- MachOLinkGraphBuilder.h - MachO LinkGraph builder ----*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Generic MachO LinkGraph building code.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H
+#define LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H
+
+#include "llvm/ExecutionEngine/JITLink/JITLink.h"
+
+#include "EHFrameSupportImpl.h"
+#include "JITLinkGeneric.h"
+#include "llvm/Object/MachO.h"
+
+#include <list>
+
+namespace llvm {
+namespace jitlink {
+
+class MachOLinkGraphBuilder {
+public:
+  virtual ~MachOLinkGraphBuilder();
+  Expected<std::unique_ptr<LinkGraph>> buildGraph();
+
+protected:
+  class MachOEHFrameBinaryParser : public EHFrameBinaryParser {
+  public:
+    MachOEHFrameBinaryParser(MachOLinkGraphBuilder &Builder,
+                             JITTargetAddress EHFrameAddress,
+                             StringRef EHFrameContent, Section &EHFrameSection,
+                             uint64_t CIEAlignment, uint64_t FDEAlignment,
+                             Edge::Kind FDEToCIERelocKind,
+                             Edge::Kind FDEToTargetRelocKind)
+        : EHFrameBinaryParser(EHFrameAddress, EHFrameContent,
+                              Builder.getGraph().getPointerSize(),
+                              Builder.getGraph().getEndianness()),
+          Builder(Builder), EHFrameSection(EHFrameSection),
+          CIEAlignment(CIEAlignment), FDEAlignment(FDEAlignment),
+          FDEToCIERelocKind(FDEToCIERelocKind),
+          FDEToTargetRelocKind(FDEToTargetRelocKind) {}
+
+    Symbol *getSymbolAtAddress(JITTargetAddress Address) override {
+      if (auto *Sym = Builder.getSymbolByAddress(Address))
+        if (Sym->getAddress() == Address)
+          return Sym;
+      return nullptr;
+    }
+
+    Symbol &createCIERecord(JITTargetAddress RecordAddr,
+                            StringRef RecordContent) override {
+      auto &G = Builder.getGraph();
+      auto &B = G.createContentBlock(EHFrameSection, RecordContent, RecordAddr,
+                                     CIEAlignment, 0);
+      auto &CIESymbol =
+          G.addAnonymousSymbol(B, 0, RecordContent.size(), false, false);
+      Builder.setCanonicalSymbol(CIESymbol);
+      return CIESymbol;
+    }
+
+    Expected<Symbol &> createFDERecord(JITTargetAddress RecordAddr,
+                                       StringRef RecordContent, Symbol &CIE,
+                                       size_t CIEOffset, Symbol &Func,
+                                       size_t FuncOffset, Symbol *LSDA,
+                                       size_t LSDAOffset) override {
+      auto &G = Builder.getGraph();
+      auto &B = G.createContentBlock(EHFrameSection, RecordContent, RecordAddr,
+                                     FDEAlignment, 0);
+
+      // Add edges to CIE, Func, and (conditionally) LSDA.
+      B.addEdge(FDEToCIERelocKind, CIEOffset, CIE, 0);
+      B.addEdge(FDEToTargetRelocKind, FuncOffset, Func, 0);
+
+      if (LSDA)
+        B.addEdge(FDEToTargetRelocKind, LSDAOffset, *LSDA, 0);
+
+      auto &FDESymbol =
+          G.addAnonymousSymbol(B, 0, RecordContent.size(), false, false);
+
+      // Add a keep-alive relocation from the function to the FDE to ensure it
+      // is not dead stripped.
+      Func.getBlock().addEdge(Edge::KeepAlive, 0, FDESymbol, 0);
+
+      return FDESymbol;
+    }
+
+  private:
+    MachOLinkGraphBuilder &Builder;
+    Section &EHFrameSection;
+    uint64_t CIEAlignment;
+    uint64_t FDEAlignment;
+    Edge::Kind FDEToCIERelocKind;
+    Edge::Kind FDEToTargetRelocKind;
+  };
+
+  struct NormalizedSymbol {
+    friend class MachOLinkGraphBuilder;
+
+  private:
+    NormalizedSymbol(Optional<StringRef> Name, uint64_t Value, uint8_t Type,
+                     uint8_t Sect, uint16_t Desc, Linkage L, Scope S)
+        : Name(Name), Value(Value), Type(Type), Sect(Sect), Desc(Desc), L(L),
+          S(S) {
+      assert(!Name || !Name->empty() && "Name must be none or non-empty");
+    }
+
+  public:
+    NormalizedSymbol(const NormalizedSymbol &) = delete;
+    NormalizedSymbol &operator=(const NormalizedSymbol &) = delete;
+    NormalizedSymbol(NormalizedSymbol &&) = delete;
+    NormalizedSymbol &operator=(NormalizedSymbol &&) = delete;
+
+    Optional<StringRef> Name;
+    uint64_t Value = 0;
+    uint8_t Type = 0;
+    uint8_t Sect = 0;
+    uint16_t Desc = 0;
+    Linkage L = Linkage::Strong;
+    Scope S = Scope::Default;
+    Symbol *GraphSymbol = nullptr;
+  };
+
+  class NormalizedSection {
+    friend class MachOLinkGraphBuilder;
+
+  private:
+    NormalizedSection() = default;
+
+  public:
+    Section *GraphSection = nullptr;
+    uint64_t Address = 0;
+    uint64_t Size = 0;
+    uint64_t Alignment = 0;
+    uint32_t Flags = 0;
+    const char *Data = nullptr;
+  };
+
+  using SectionParserFunction = std::function<Error(NormalizedSection &S)>;
+
+  MachOLinkGraphBuilder(const object::MachOObjectFile &Obj);
+
+  LinkGraph &getGraph() const { return *G; }
+
+  const object::MachOObjectFile &getObject() const { return Obj; }
+
+  void addCustomSectionParser(StringRef SectionName,
+                              SectionParserFunction Parse);
+
+  virtual Error addRelocations() = 0;
+
+  /// Create a symbol.
+  template <typename... ArgTs>
+  NormalizedSymbol &createNormalizedSymbol(ArgTs &&... Args) {
+    NormalizedSymbol *Sym = reinterpret_cast<NormalizedSymbol *>(
+        Allocator.Allocate<NormalizedSymbol>());
+    new (Sym) NormalizedSymbol(std::forward<ArgTs>(Args)...);
+    return *Sym;
+  }
+
+  /// Index is zero-based (MachO section indexes are usually one-based) and
+  /// assumed to be in-range. Client is responsible for checking.
+  NormalizedSection &getSectionByIndex(unsigned Index) {
+    auto I = IndexToSection.find(Index);
+    assert(I != IndexToSection.end() && "No section recorded at index");
+    return I->second;
+  }
+
+  /// Try to get the section at the given index. Will return an error if the
+  /// given index is out of range, or if no section has been added for the given
+  /// index.
+  Expected<NormalizedSection &> findSectionByIndex(unsigned Index) {
+    auto I = IndexToSection.find(Index);
+    if (I == IndexToSection.end())
+      return make_error<JITLinkError>("No section recorded for index " +
+                                      formatv("{0:u}", Index));
+    return I->second;
+  }
+
+  /// Try to get the symbol at the given index. Will return an error if the
+  /// given index is out of range, or if no symbol has been added for the given
+  /// index.
+  Expected<NormalizedSymbol &> findSymbolByIndex(uint64_t Index) {
+    if (Index >= IndexToSymbol.size())
+      return make_error<JITLinkError>("Symbol index out of range");
+    auto *Sym = IndexToSymbol[Index];
+    if (!Sym)
+      return make_error<JITLinkError>("No symbol at index " +
+                                      formatv("{0:u}", Index));
+    return *Sym;
+  }
+
+  /// Returns the symbol with the highest address not greater than the search
+  /// address, or null if no such symbol exists.
+  Symbol *getSymbolByAddress(JITTargetAddress Address) {
+    auto I = AddrToCanonicalSymbol.upper_bound(Address);
+    if (I == AddrToCanonicalSymbol.begin())
+      return nullptr;
+    return std::prev(I)->second;
+  }
+
+  /// Returns the symbol with the highest address not greater than the search
+  /// address, or an error if no such symbol exists.
+  Expected<Symbol &> findSymbolByAddress(JITTargetAddress Address) {
+    auto *Sym = getSymbolByAddress(Address);
+    if (Sym)
+      if (Address < Sym->getAddress() + Sym->getSize())
+        return *Sym;
+    return make_error<JITLinkError>("No symbol covering address " +
+                                    formatv("{0:x16}", Address));
+  }
+
+  static Linkage getLinkage(uint16_t Desc);
+  static Scope getScope(StringRef Name, uint8_t Type);
+  static bool isAltEntry(const NormalizedSymbol &NSym);
+
+private:
+  static unsigned getPointerSize(const object::MachOObjectFile &Obj);
+  static support::endianness getEndianness(const object::MachOObjectFile &Obj);
+
+  void setCanonicalSymbol(Symbol &Sym) {
+    auto *&CanonicalSymEntry = AddrToCanonicalSymbol[Sym.getAddress()];
+    // There should be no symbol at this address, or, if there is,
+    // it should be a zero-sized symbol from an empty section (which
+    // we can safely override).
+    assert((!CanonicalSymEntry || CanonicalSymEntry->getSize() == 0) &&
+           "Duplicate canonical symbol at address");
+    CanonicalSymEntry = &Sym;
+  }
+
+  Section &getCommonSection();
+  void addSectionStartSymAndBlock(Section &GraphSec, uint64_t Address,
+                                  const char *Data, uint64_t Size,
+                                  uint32_t Alignment, bool IsLive);
+
+  Error createNormalizedSections();
+  Error createNormalizedSymbols();
+
+  /// Create graph blocks and symbols for externals, absolutes, commons and
+  /// all defined symbols in sections without custom parsers.
+  Error graphifyRegularSymbols();
+
+  /// Create graph blocks and symbols for all sections.
+  Error graphifySectionsWithCustomParsers();
+
+  // Put the BumpPtrAllocator first so that we don't free any of the underlying
+  // memory until the Symbol/Addressable destructors have been run.
+  BumpPtrAllocator Allocator;
+
+  const object::MachOObjectFile &Obj;
+  std::unique_ptr<LinkGraph> G;
+
+  DenseMap<unsigned, NormalizedSection> IndexToSection;
+  Section *CommonSection = nullptr;
+
+  DenseMap<uint32_t, NormalizedSymbol *> IndexToSymbol;
+  std::map<JITTargetAddress, Symbol *> AddrToCanonicalSymbol;
+  StringMap<SectionParserFunction> CustomSectionParserFunctions;
+};
+
+} // end namespace jitlink
+} // end namespace llvm
+
+#endif // LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H