diff options
Diffstat (limited to 'lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp')
-rw-r--r-- | lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp | 385 |
1 files changed, 131 insertions, 254 deletions
diff --git a/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp b/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp index 96e074da122b..d4270b5aa796 100644 --- a/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp +++ b/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp @@ -11,7 +11,6 @@ //===----------------------------------------------------------------------===// #include "JITLinkGeneric.h" -#include "EHFrameSupportImpl.h" #include "llvm/Support/BinaryStreamReader.h" #include "llvm/Support/MemoryBuffer.h" @@ -25,7 +24,7 @@ JITLinkerBase::~JITLinkerBase() {} void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) { - // Build the atom graph. + // Build the link graph. if (auto GraphOrErr = buildGraph(Ctx->getObjectBuffer())) G = std::move(*GraphOrErr); else @@ -33,33 +32,33 @@ void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) { assert(G && "Graph should have been created by buildGraph above"); // Prune and optimize the graph. - if (auto Err = runPasses(Passes.PrePrunePasses, *G)) + if (auto Err = runPasses(Passes.PrePrunePasses)) return Ctx->notifyFailed(std::move(Err)); LLVM_DEBUG({ - dbgs() << "Atom graph \"" << G->getName() << "\" pre-pruning:\n"; + dbgs() << "Link graph \"" << G->getName() << "\" pre-pruning:\n"; dumpGraph(dbgs()); }); prune(*G); LLVM_DEBUG({ - dbgs() << "Atom graph \"" << G->getName() << "\" post-pruning:\n"; + dbgs() << "Link graph \"" << G->getName() << "\" post-pruning:\n"; dumpGraph(dbgs()); }); // Run post-pruning passes. - if (auto Err = runPasses(Passes.PostPrunePasses, *G)) + if (auto Err = runPasses(Passes.PostPrunePasses)) return Ctx->notifyFailed(std::move(Err)); - // Sort atoms into segments. - layOutAtoms(); + // Sort blocks into segments. + auto Layout = layOutBlocks(); // 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. + // Notify client that the defined symbols have been assigned addresses. Ctx->notifyResolved(*G); auto ExternalSymbols = getExternalSymbolNames(); @@ -74,42 +73,42 @@ void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) { // [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)); + TmpCtx->lookup(std::move(ExternalSymbols), + createLookupContinuation( + [S = std::move(Self), L = std::move(Layout)]( + Expected<AsyncLookupResult> LookupResult) mutable { + auto &TmpSelf = *S; + TmpSelf.linkPhase2(std::move(S), std::move(LookupResult), + std::move(L)); + })); } void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self, - Expected<AsyncLookupResult> LR) { + Expected<AsyncLookupResult> LR, + SegmentLayoutMap Layout) { // If the lookup failed, bail out. if (!LR) return deallocateAndBailOut(LR.takeError()); - // Assign addresses to external atoms. + // Assign addresses to external addressables. applyLookupResult(*LR); LLVM_DEBUG({ - dbgs() << "Atom graph \"" << G->getName() << "\" before copy-and-fixup:\n"; + dbgs() << "Link 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)) + // Copy block content to working memory and fix up. + if (auto Err = copyAndFixUpBlocks(Layout, *Alloc)) return deallocateAndBailOut(std::move(Err)); LLVM_DEBUG({ - dbgs() << "Atom graph \"" << G->getName() << "\" after copy-and-fixup:\n"; + dbgs() << "Link graph \"" << G->getName() << "\" after copy-and-fixup:\n"; dumpGraph(dbgs()); }); - if (auto Err = runPasses(Passes.PostFixupPasses, *G)) + if (auto Err = runPasses(Passes.PostFixupPasses)) return deallocateAndBailOut(std::move(Err)); // FIXME: Use move capture once we have c++14. @@ -128,82 +127,38 @@ void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self, Error Err) { Ctx->notifyFinalized(std::move(Alloc)); } -Error JITLinkerBase::runPasses(AtomGraphPassList &Passes, AtomGraph &G) { +Error JITLinkerBase::runPasses(LinkGraphPassList &Passes) { for (auto &P : Passes) - if (auto Err = P(G)) + 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()) { +JITLinkerBase::SegmentLayoutMap JITLinkerBase::layOutBlocks() { - // Skip empty sections. - if (S.atoms_empty()) - continue; + SegmentLayoutMap Layout; - auto &SL = Layout[S.getProtectionFlags()]; - if (S.isZeroFill()) - SL.ZeroFillSections.push_back(SegmentLayout::SectionLayout(S)); + /// Partition blocks based on permissions and content vs. zero-fill. + for (auto *B : G->blocks()) { + auto &SegLists = Layout[B->getSection().getProtectionFlags()]; + if (!B->isZeroFill()) + SegLists.ContentBlocks.push_back(B); else - SL.ContentSections.push_back(SegmentLayout::SectionLayout(S)); + SegLists.ZeroFillBlocks.push_back(B); } - // Sort sections within the layout by ordinal. - { - auto CompareByOrdinal = [](const SegmentLayout::SectionLayout &LHS, - const SegmentLayout::SectionLayout &RHS) { - return LHS.S->getSectionOrdinal() < RHS.S->getSectionOrdinal(); + /// Sort blocks within each list. + for (auto &KV : Layout) { + + auto CompareBlocks = [](const Block *LHS, const Block *RHS) { + if (LHS->getSection().getOrdinal() != RHS->getSection().getOrdinal()) + return LHS->getSection().getOrdinal() < RHS->getSection().getOrdinal(); + return LHS->getOrdinal() < RHS->getOrdinal(); }; - 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; - } - } - } - } + auto &SegLists = KV.second; + llvm::sort(SegLists.ContentBlocks, CompareBlocks); + llvm::sort(SegLists.ZeroFillBlocks, CompareBlocks); } LLVM_DEBUG({ @@ -213,18 +168,16 @@ void JITLinkerBase::layOutAtoms() { << 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; + {std::make_pair(&SL.ContentBlocks, "content block"), + std::make_pair(&SL.ZeroFillBlocks, "zero-fill block")}) { dbgs() << " " << SIEntry.second << ":\n"; - for (auto &SI : SIList) { - dbgs() << " " << SI.S->getName() << ":\n"; - for (auto *DA : SI.Atoms) - dbgs() << " " << *DA << "\n"; - } + for (auto *B : *SIEntry.first) + dbgs() << " " << *B << "\n"; } } }); + + return Layout; } Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) { @@ -234,74 +187,36 @@ Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) { JITLinkMemoryManager::SegmentsRequestMap Segments; for (auto &KV : Layout) { auto &Prot = KV.first; - auto &SegLayout = KV.second; + auto &SegLists = KV.second; + + uint64_t SegAlign = 1; // 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(); - } + for (auto *B : SegLists.ContentBlocks) { + SegAlign = std::max(SegAlign, B->getAlignment()); + SegContentSize = alignToBlock(SegContentSize, *B); + SegContentSize += B->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()); - } + uint64_t SegZeroFillStart = SegContentSize; + uint64_t SegZeroFillEnd = SegZeroFillStart; - // 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()); + for (auto *B : SegLists.ZeroFillBlocks) { + SegAlign = std::max(SegAlign, B->getAlignment()); + SegZeroFillEnd = alignToBlock(SegZeroFillEnd, *B); + SegZeroFillEnd += B->getSize(); } - 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}; + Segments[Prot] = {SegAlign, SegContentSize, + SegZeroFillEnd - SegZeroFillStart}; LLVM_DEBUG({ dbgs() << (&KV == &*Layout.begin() ? "" : "; ") - << static_cast<sys::Memory::ProtectionFlags>(Prot) << ": " - << SegContentSize << " content bytes (alignment " - << SegContentAlign << ") + " << SegZeroFillSize - << " zero-fill bytes (alignment " << SegZeroFillAlign << ")"; + << static_cast<sys::Memory::ProtectionFlags>(Prot) + << ": alignment = " << SegAlign + << ", content size = " << SegContentSize + << ", zero-fill size = " << (SegZeroFillEnd - SegZeroFillStart); }); } LLVM_DEBUG(dbgs() << " }\n"); @@ -320,22 +235,19 @@ Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) { } }); - // Update atom target addresses. + // Update block target addresses. for (auto &KV : Layout) { auto &Prot = KV.first; auto &SL = KV.second; - JITTargetAddress AtomTargetAddr = + JITTargetAddress NextBlockAddr = 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(); - } + for (auto *SIList : {&SL.ContentBlocks, &SL.ZeroFillBlocks}) + for (auto *B : *SIList) { + NextBlockAddr = alignToBlock(NextBlockAddr, *B); + B->setAddress(NextBlockAddr); + NextBlockAddr += B->getSize(); } } @@ -343,34 +255,35 @@ Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) { } DenseSet<StringRef> JITLinkerBase::getExternalSymbolNames() const { - // Identify unresolved external atoms. + // Identify unresolved external symbols. DenseSet<StringRef> UnresolvedExternals; - for (auto *DA : G->external_atoms()) { - assert(DA->getAddress() == 0 && + for (auto *Sym : G->external_symbols()) { + assert(Sym->getAddress() == 0 && "External has already been assigned an address"); - assert(DA->getName() != StringRef() && DA->getName() != "" && + assert(Sym->getName() != StringRef() && Sym->getName() != "" && "Externals must be named"); - UnresolvedExternals.insert(DA->getName()); + UnresolvedExternals.insert(Sym->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()); + for (auto *Sym : G->external_symbols()) { + assert(Sym->getAddress() == 0 && "Symbol already resolved"); + assert(!Sym->isDefined() && "Symbol being resolved is already defined"); + assert(Result.count(Sym->getName()) && "Missing resolution for symbol"); + Sym->getAddressable().setAddress(Result[Sym->getName()].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"; + for (auto *Sym : G->external_symbols()) + dbgs() << " " << Sym->getName() << ": " + << formatv("{0:x16}", Sym->getAddress()) << "\n"; }); - assert(llvm::all_of(G->external_atoms(), - [](Atom *A) { return A->getAddress() != 0; }) && - "All atoms should have been resolved by this point"); + assert(llvm::all_of(G->external_symbols(), + [](Symbol *Sym) { return Sym->getAddress() != 0; }) && + "All symbols should have been resolved by this point"); } void JITLinkerBase::deallocateAndBailOut(Error Err) { @@ -384,96 +297,60 @@ void JITLinkerBase::dumpGraph(raw_ostream &OS) { 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; +void prune(LinkGraph &G) { + std::vector<Symbol *> Worklist; + DenseSet<Block *> VisitedBlocks; - auto &EDT = static_cast<DefinedAtom &>(E.getTarget()); + // Build the initial worklist from all symbols initially live. + for (auto *Sym : G.defined_symbols()) + if (Sym->isLive()) + Worklist.push_back(Sym); - 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. + // Propagate live flags to all symbols reachable from the initial live set. while (!Worklist.empty()) { - DefinedAtom &NextLive = *Worklist.back(); + auto *Sym = Worklist.back(); Worklist.pop_back(); - assert(!NextLive.shouldDiscard() && - "should-discard nodes should never make it into the worklist"); + auto &B = Sym->getBlock(); - // If this atom has already been marked as live, or is marked to be - // discarded, then skip it. - if (NextLive.isLive()) + // Skip addressables that we've visited before. + if (VisitedBlocks.count(&B)) 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; + VisitedBlocks.insert(&B); - 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); + for (auto &E : Sym->getBlock().edges()) { + if (E.getTarget().isDefined() && !E.getTarget().isLive()) { + E.getTarget().setLive(true); + Worklist.push_back(&E.getTarget()); + } } } - // 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"); + // Collect all the symbols to remove, then remove them. + { + LLVM_DEBUG(dbgs() << "Dead-stripping symbols:\n"); + std::vector<Symbol *> SymbolsToRemove; + for (auto *Sym : G.defined_symbols()) + if (!Sym->isLive()) + SymbolsToRemove.push_back(Sym); + for (auto *Sym : SymbolsToRemove) { + LLVM_DEBUG(dbgs() << " " << *Sym << "...\n"); + G.removeDefinedSymbol(*Sym); + } } - // Finally, discard any absolute symbols that were marked should-discard. + // Delete any unused blocks. { - 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); + LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n"); + std::vector<Block *> BlocksToRemove; + for (auto *B : G.blocks()) + if (!VisitedBlocks.count(B)) + BlocksToRemove.push_back(B); + for (auto *B : BlocksToRemove) { + LLVM_DEBUG(dbgs() << " " << *B << "...\n"); + G.removeBlock(*B); + } } } |