Merge llvm trunk r366426, resolve conflicts, and update FREEBSD-Xlist.

1 files changed, 481 insertions, 0 deletions

diff --git a/contrib/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp b/contrib/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
new file mode 100644
index 000000000000..96e074da122b
--- /dev/null
+++ b/contrib/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
@@ -0,0 +1,481 @@
+//===--------- JITLinkGeneric.cpp - Generic JIT linker utilities ----------===//
+//
+// 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 JITLinker utility class.
+//
+//===----------------------------------------------------------------------===//
+
+#include "JITLinkGeneric.h"
+#include "EHFrameSupportImpl.h"
+
+#include "llvm/Support/BinaryStreamReader.h"
+#include "llvm/Support/MemoryBuffer.h"
+
+#define DEBUG_TYPE "jitlink"
+
+namespace llvm {
+namespace jitlink {
+
+JITLinkerBase::~JITLinkerBase() {}
+
+void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) {
+
+  // Build the atom graph.
+  if (auto GraphOrErr = buildGraph(Ctx->getObjectBuffer()))
+    G = std::move(*GraphOrErr);
+  else
+    return Ctx->notifyFailed(GraphOrErr.takeError());
+  assert(G && "Graph should have been created by buildGraph above");
+
+  // Prune and optimize the graph.
+  if (auto Err = runPasses(Passes.PrePrunePasses, *G))
+    return Ctx->notifyFailed(std::move(Err));
+
+  LLVM_DEBUG({
+    dbgs() << "Atom graph \"" << G->getName() << "\" pre-pruning:\n";
+    dumpGraph(dbgs());
+  });
+
+  prune(*G);
+
+  LLVM_DEBUG({
+    dbgs() << "Atom graph \"" << G->getName() << "\" post-pruning:\n";
+    dumpGraph(dbgs());
+  });
+
+  // Run post-pruning passes.
+  if (auto Err = runPasses(Passes.PostPrunePasses, *G))
+    return Ctx->notifyFailed(std::move(Err));
+
+  // Sort atoms into segments.
+  layOutAtoms();
+
+  // Allocate memory for segments.
+  if (auto Err = allocateSegments(Layout))
+    return Ctx->notifyFailed(std::move(Err));
+
+  // Notify client that the defined atoms have been assigned addresses.
+  Ctx->notifyResolved(*G);
+
+  auto ExternalSymbols = getExternalSymbolNames();
+
+  // We're about to hand off ownership of ourself to the continuation. Grab a
+  // pointer to the context so that we can call it to initiate the lookup.
+  //
+  // FIXME: Once callee expressions are defined to be sequenced before argument
+  // expressions (c++17) we can simplify all this to:
+  //
+  // Ctx->lookup(std::move(UnresolvedExternals),
+  //             [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
+  //               Self->linkPhase2(std::move(Self), std::move(Result));
+  //             });
+  //
+  // FIXME: Use move capture once we have c++14.
+  auto *TmpCtx = Ctx.get();
+  auto *UnownedSelf = Self.release();
+  auto Phase2Continuation =
+      [UnownedSelf](Expected<AsyncLookupResult> LookupResult) {
+        std::unique_ptr<JITLinkerBase> Self(UnownedSelf);
+        UnownedSelf->linkPhase2(std::move(Self), std::move(LookupResult));
+      };
+  TmpCtx->lookup(std::move(ExternalSymbols), std::move(Phase2Continuation));
+}
+
+void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
+                               Expected<AsyncLookupResult> LR) {
+  // If the lookup failed, bail out.
+  if (!LR)
+    return deallocateAndBailOut(LR.takeError());
+
+  // Assign addresses to external atoms.
+  applyLookupResult(*LR);
+
+  LLVM_DEBUG({
+    dbgs() << "Atom graph \"" << G->getName() << "\" before copy-and-fixup:\n";
+    dumpGraph(dbgs());
+  });
+
+  // Copy atom content to working memory and fix up.
+  if (auto Err = copyAndFixUpAllAtoms(Layout, *Alloc))
+    return deallocateAndBailOut(std::move(Err));
+
+  LLVM_DEBUG({
+    dbgs() << "Atom graph \"" << G->getName() << "\" after copy-and-fixup:\n";
+    dumpGraph(dbgs());
+  });
+
+  if (auto Err = runPasses(Passes.PostFixupPasses, *G))
+    return deallocateAndBailOut(std::move(Err));
+
+  // FIXME: Use move capture once we have c++14.
+  auto *UnownedSelf = Self.release();
+  auto Phase3Continuation = [UnownedSelf](Error Err) {
+    std::unique_ptr<JITLinkerBase> Self(UnownedSelf);
+    UnownedSelf->linkPhase3(std::move(Self), std::move(Err));
+  };
+
+  Alloc->finalizeAsync(std::move(Phase3Continuation));
+}
+
+void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self, Error Err) {
+  if (Err)
+    return deallocateAndBailOut(std::move(Err));
+  Ctx->notifyFinalized(std::move(Alloc));
+}
+
+Error JITLinkerBase::runPasses(AtomGraphPassList &Passes, AtomGraph &G) {
+  for (auto &P : Passes)
+    if (auto Err = P(G))
+      return Err;
+  return Error::success();
+}
+
+void JITLinkerBase::layOutAtoms() {
+  // Group sections by protections, and whether or not they're zero-fill.
+  for (auto &S : G->sections()) {
+
+    // Skip empty sections.
+    if (S.atoms_empty())
+      continue;
+
+    auto &SL = Layout[S.getProtectionFlags()];
+    if (S.isZeroFill())
+      SL.ZeroFillSections.push_back(SegmentLayout::SectionLayout(S));
+    else
+      SL.ContentSections.push_back(SegmentLayout::SectionLayout(S));
+  }
+
+  // Sort sections within the layout by ordinal.
+  {
+    auto CompareByOrdinal = [](const SegmentLayout::SectionLayout &LHS,
+                               const SegmentLayout::SectionLayout &RHS) {
+      return LHS.S->getSectionOrdinal() < RHS.S->getSectionOrdinal();
+    };
+    for (auto &KV : Layout) {
+      auto &SL = KV.second;
+      std::sort(SL.ContentSections.begin(), SL.ContentSections.end(),
+                CompareByOrdinal);
+      std::sort(SL.ZeroFillSections.begin(), SL.ZeroFillSections.end(),
+                CompareByOrdinal);
+    }
+  }
+
+  // Add atoms to the sections.
+  for (auto &KV : Layout) {
+    auto &SL = KV.second;
+    for (auto *SIList : {&SL.ContentSections, &SL.ZeroFillSections}) {
+      for (auto &SI : *SIList) {
+        // First build the set of layout-heads (i.e. "heads" of layout-next
+        // chains) by copying the section atoms, then eliminating any that
+        // appear as layout-next targets.
+        DenseSet<DefinedAtom *> LayoutHeads;
+        for (auto *DA : SI.S->atoms())
+          LayoutHeads.insert(DA);
+
+        for (auto *DA : SI.S->atoms())
+          if (DA->hasLayoutNext())
+            LayoutHeads.erase(&DA->getLayoutNext());
+
+        // Next, sort the layout heads by address order.
+        std::vector<DefinedAtom *> OrderedLayoutHeads;
+        OrderedLayoutHeads.reserve(LayoutHeads.size());
+        for (auto *DA : LayoutHeads)
+          OrderedLayoutHeads.push_back(DA);
+
+        // Now sort the list of layout heads by address.
+        std::sort(OrderedLayoutHeads.begin(), OrderedLayoutHeads.end(),
+                  [](const DefinedAtom *LHS, const DefinedAtom *RHS) {
+                    return LHS->getAddress() < RHS->getAddress();
+                  });
+
+        // Now populate the SI.Atoms field by appending each of the chains.
+        for (auto *DA : OrderedLayoutHeads) {
+          SI.Atoms.push_back(DA);
+          while (DA->hasLayoutNext()) {
+            auto &Next = DA->getLayoutNext();
+            SI.Atoms.push_back(&Next);
+            DA = &Next;
+          }
+        }
+      }
+    }
+  }
+
+  LLVM_DEBUG({
+    dbgs() << "Segment ordering:\n";
+    for (auto &KV : Layout) {
+      dbgs() << "  Segment "
+             << static_cast<sys::Memory::ProtectionFlags>(KV.first) << ":\n";
+      auto &SL = KV.second;
+      for (auto &SIEntry :
+           {std::make_pair(&SL.ContentSections, "content sections"),
+            std::make_pair(&SL.ZeroFillSections, "zero-fill sections")}) {
+        auto &SIList = *SIEntry.first;
+        dbgs() << "    " << SIEntry.second << ":\n";
+        for (auto &SI : SIList) {
+          dbgs() << "      " << SI.S->getName() << ":\n";
+          for (auto *DA : SI.Atoms)
+            dbgs() << "        " << *DA << "\n";
+        }
+      }
+    }
+  });
+}
+
+Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) {
+
+  // Compute segment sizes and allocate memory.
+  LLVM_DEBUG(dbgs() << "JIT linker requesting: { ");
+  JITLinkMemoryManager::SegmentsRequestMap Segments;
+  for (auto &KV : Layout) {
+    auto &Prot = KV.first;
+    auto &SegLayout = KV.second;
+
+    // Calculate segment content size.
+    size_t SegContentSize = 0;
+    for (auto &SI : SegLayout.ContentSections) {
+      assert(!SI.S->atoms_empty() && "Sections in layout must not be empty");
+      assert(!SI.Atoms.empty() && "Section layouts must not be empty");
+
+      // Bump to section alignment before processing atoms.
+      SegContentSize = alignTo(SegContentSize, SI.S->getAlignment());
+
+      for (auto *DA : SI.Atoms) {
+        SegContentSize = alignTo(SegContentSize, DA->getAlignment());
+        SegContentSize += DA->getSize();
+      }
+    }
+
+    // Get segment content alignment.
+    unsigned SegContentAlign = 1;
+    if (!SegLayout.ContentSections.empty()) {
+      auto &FirstContentSection = SegLayout.ContentSections.front();
+      SegContentAlign =
+          std::max(FirstContentSection.S->getAlignment(),
+                   FirstContentSection.Atoms.front()->getAlignment());
+    }
+
+    // Calculate segment zero-fill size.
+    uint64_t SegZeroFillSize = 0;
+    for (auto &SI : SegLayout.ZeroFillSections) {
+      assert(!SI.S->atoms_empty() && "Sections in layout must not be empty");
+      assert(!SI.Atoms.empty() && "Section layouts must not be empty");
+
+      // Bump to section alignment before processing atoms.
+      SegZeroFillSize = alignTo(SegZeroFillSize, SI.S->getAlignment());
+
+      for (auto *DA : SI.Atoms) {
+        SegZeroFillSize = alignTo(SegZeroFillSize, DA->getAlignment());
+        SegZeroFillSize += DA->getSize();
+      }
+    }
+
+    // Calculate segment zero-fill alignment.
+    uint32_t SegZeroFillAlign = 1;
+
+    if (!SegLayout.ZeroFillSections.empty()) {
+      auto &FirstZeroFillSection = SegLayout.ZeroFillSections.front();
+      SegZeroFillAlign =
+          std::max(FirstZeroFillSection.S->getAlignment(),
+                   FirstZeroFillSection.Atoms.front()->getAlignment());
+    }
+
+    if (SegContentSize == 0)
+      SegContentAlign = SegZeroFillAlign;
+
+    if (SegContentAlign % SegZeroFillAlign != 0)
+      return make_error<JITLinkError>("First content atom alignment does not "
+                                      "accommodate first zero-fill atom "
+                                      "alignment");
+
+    Segments[Prot] = {SegContentSize, SegContentAlign, SegZeroFillSize,
+                      SegZeroFillAlign};
+
+    LLVM_DEBUG({
+      dbgs() << (&KV == &*Layout.begin() ? "" : "; ")
+             << static_cast<sys::Memory::ProtectionFlags>(Prot) << ": "
+             << SegContentSize << " content bytes (alignment "
+             << SegContentAlign << ") + " << SegZeroFillSize
+             << " zero-fill bytes (alignment " << SegZeroFillAlign << ")";
+    });
+  }
+  LLVM_DEBUG(dbgs() << " }\n");
+
+  if (auto AllocOrErr = Ctx->getMemoryManager().allocate(Segments))
+    Alloc = std::move(*AllocOrErr);
+  else
+    return AllocOrErr.takeError();
+
+  LLVM_DEBUG({
+    dbgs() << "JIT linker got working memory:\n";
+    for (auto &KV : Layout) {
+      auto Prot = static_cast<sys::Memory::ProtectionFlags>(KV.first);
+      dbgs() << "  " << Prot << ": "
+             << (const void *)Alloc->getWorkingMemory(Prot).data() << "\n";
+    }
+  });
+
+  // Update atom target addresses.
+  for (auto &KV : Layout) {
+    auto &Prot = KV.first;
+    auto &SL = KV.second;
+
+    JITTargetAddress AtomTargetAddr =
+        Alloc->getTargetMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
+
+    for (auto *SIList : {&SL.ContentSections, &SL.ZeroFillSections})
+      for (auto &SI : *SIList) {
+        AtomTargetAddr = alignTo(AtomTargetAddr, SI.S->getAlignment());
+        for (auto *DA : SI.Atoms) {
+          AtomTargetAddr = alignTo(AtomTargetAddr, DA->getAlignment());
+          DA->setAddress(AtomTargetAddr);
+          AtomTargetAddr += DA->getSize();
+        }
+      }
+  }
+
+  return Error::success();
+}
+
+DenseSet<StringRef> JITLinkerBase::getExternalSymbolNames() const {
+  // Identify unresolved external atoms.
+  DenseSet<StringRef> UnresolvedExternals;
+  for (auto *DA : G->external_atoms()) {
+    assert(DA->getAddress() == 0 &&
+           "External has already been assigned an address");
+    assert(DA->getName() != StringRef() && DA->getName() != "" &&
+           "Externals must be named");
+    UnresolvedExternals.insert(DA->getName());
+  }
+  return UnresolvedExternals;
+}
+
+void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
+  for (auto &KV : Result) {
+    Atom &A = G->getAtomByName(KV.first);
+    assert(A.getAddress() == 0 && "Atom already resolved");
+    A.setAddress(KV.second.getAddress());
+  }
+
+  LLVM_DEBUG({
+    dbgs() << "Externals after applying lookup result:\n";
+    for (auto *A : G->external_atoms())
+      dbgs() << "  " << A->getName() << ": "
+             << formatv("{0:x16}", A->getAddress()) << "\n";
+  });
+  assert(llvm::all_of(G->external_atoms(),
+                      [](Atom *A) { return A->getAddress() != 0; }) &&
+         "All atoms should have been resolved by this point");
+}
+
+void JITLinkerBase::deallocateAndBailOut(Error Err) {
+  assert(Err && "Should not be bailing out on success value");
+  assert(Alloc && "can not call deallocateAndBailOut before allocation");
+  Ctx->notifyFailed(joinErrors(std::move(Err), Alloc->deallocate()));
+}
+
+void JITLinkerBase::dumpGraph(raw_ostream &OS) {
+  assert(G && "Graph is not set yet");
+  G->dump(dbgs(), [this](Edge::Kind K) { return getEdgeKindName(K); });
+}
+
+void prune(AtomGraph &G) {
+  std::vector<DefinedAtom *> Worklist;
+  DenseMap<DefinedAtom *, std::vector<Edge *>> EdgesToUpdate;
+
+  // Build the initial worklist from all atoms initially live.
+  for (auto *DA : G.defined_atoms()) {
+    if (!DA->isLive() || DA->shouldDiscard())
+      continue;
+
+    for (auto &E : DA->edges()) {
+      if (!E.getTarget().isDefined())
+        continue;
+
+      auto &EDT = static_cast<DefinedAtom &>(E.getTarget());
+
+      if (EDT.shouldDiscard())
+        EdgesToUpdate[&EDT].push_back(&E);
+      else if (E.isKeepAlive() && !EDT.isLive())
+        Worklist.push_back(&EDT);
+    }
+  }
+
+  // Propagate live flags to all atoms reachable from the initial live set.
+  while (!Worklist.empty()) {
+    DefinedAtom &NextLive = *Worklist.back();
+    Worklist.pop_back();
+
+    assert(!NextLive.shouldDiscard() &&
+           "should-discard nodes should never make it into the worklist");
+
+    // If this atom has already been marked as live, or is marked to be
+    // discarded, then skip it.
+    if (NextLive.isLive())
+      continue;
+
+    // Otherwise set it as live and add any non-live atoms that it points to
+    // to the worklist.
+    NextLive.setLive(true);
+
+    for (auto &E : NextLive.edges()) {
+      if (!E.getTarget().isDefined())
+        continue;
+
+      auto &EDT = static_cast<DefinedAtom &>(E.getTarget());
+
+      if (EDT.shouldDiscard())
+        EdgesToUpdate[&EDT].push_back(&E);
+      else if (E.isKeepAlive() && !EDT.isLive())
+        Worklist.push_back(&EDT);
+    }
+  }
+
+  // Collect atoms to remove, then remove them from the graph.
+  std::vector<DefinedAtom *> AtomsToRemove;
+  for (auto *DA : G.defined_atoms())
+    if (DA->shouldDiscard() || !DA->isLive())
+      AtomsToRemove.push_back(DA);
+
+  LLVM_DEBUG(dbgs() << "Pruning atoms:\n");
+  for (auto *DA : AtomsToRemove) {
+    LLVM_DEBUG(dbgs() << "  " << *DA << "... ");
+
+    // Check whether we need to replace this atom with an external atom.
+    //
+    // We replace if all of the following hold:
+    //   (1) The atom is marked should-discard,
+    //   (2) it has live edges (i.e. edges from live atoms) pointing to it.
+    //
+    // Otherwise we simply delete the atom.
+
+    G.removeDefinedAtom(*DA);
+
+    auto EdgesToUpdateItr = EdgesToUpdate.find(DA);
+    if (EdgesToUpdateItr != EdgesToUpdate.end()) {
+      auto &ExternalReplacement = G.addExternalAtom(DA->getName());
+      for (auto *EdgeToUpdate : EdgesToUpdateItr->second)
+        EdgeToUpdate->setTarget(ExternalReplacement);
+      LLVM_DEBUG(dbgs() << "replaced with " << ExternalReplacement << "\n");
+    } else
+      LLVM_DEBUG(dbgs() << "deleted\n");
+  }
+
+  // Finally, discard any absolute symbols that were marked should-discard.
+  {
+    std::vector<Atom *> AbsoluteAtomsToRemove;
+    for (auto *A : G.absolute_atoms())
+      if (A->shouldDiscard() || A->isLive())
+        AbsoluteAtomsToRemove.push_back(A);
+    for (auto *A : AbsoluteAtomsToRemove)
+      G.removeAbsoluteAtom(*A);
+  }
+}
+
+} // end namespace jitlink
+} // end namespace llvm