[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
diff --git a/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp b/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
index 877107f..d4270b5 100644
--- a/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
+++ b/llvm/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 @@
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 @@
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 @@
// [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 @@
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();
- };
- 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.
+ /// Sort blocks within each list.
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());
+ 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();
+ };
- // 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 @@
<< 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,61 +187,36 @@
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;
- uint32_t SegContentAlign = 1;
- 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());
- SegContentAlign = std::max(SegContentAlign, SI.S->getAlignment());
-
- for (auto *DA : SI.Atoms) {
- SegContentSize = alignTo(SegContentSize, DA->getAlignment());
- SegContentSize += DA->getSize();
- SegContentAlign = std::max(SegContentAlign, DA->getAlignment());
- }
+ for (auto *B : SegLists.ContentBlocks) {
+ SegAlign = std::max(SegAlign, B->getAlignment());
+ SegContentSize = alignToBlock(SegContentSize, *B);
+ SegContentSize += B->getSize();
}
- // Calculate segment zero-fill size.
- uint64_t SegZeroFillSize = 0;
- uint32_t SegZeroFillAlign = 1;
+ uint64_t SegZeroFillStart = SegContentSize;
+ uint64_t SegZeroFillEnd = SegZeroFillStart;
- 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());
- SegZeroFillAlign = std::max(SegZeroFillAlign, SI.S->getAlignment());
-
- for (auto *DA : SI.Atoms) {
- SegZeroFillSize = alignTo(SegZeroFillSize, DA->getAlignment());
- SegZeroFillSize += DA->getSize();
- SegZeroFillAlign = std::max(SegZeroFillAlign, SI.S->getAlignment());
- }
+ for (auto *B : SegLists.ZeroFillBlocks) {
+ SegAlign = std::max(SegAlign, B->getAlignment());
+ SegZeroFillEnd = alignToBlock(SegZeroFillEnd, *B);
+ SegZeroFillEnd += B->getSize();
}
- assert(isPowerOf2_32(SegContentAlign) &&
- "Expected content alignment to be power of 2");
- assert(isPowerOf2_32(SegZeroFillAlign) &&
- "Expected zero-fill alignment to be power of 2");
- // Round content alignment up to segment alignment.
- SegContentAlign = std::max(SegContentAlign, SegZeroFillAlign);
-
- 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");
@@ -307,22 +235,19 @@
}
});
- // 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();
}
}
@@ -330,34 +255,35 @@
}
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) {
@@ -371,96 +297,60 @@
G->dump(dbgs(), [this](Edge::Kind K) { return getEdgeKindName(K); });
}
-void prune(AtomGraph &G) {
- std::vector<DefinedAtom *> Worklist;
- DenseMap<DefinedAtom *, std::vector<Edge *>> EdgesToUpdate;
+void prune(LinkGraph &G) {
+ std::vector<Symbol *> Worklist;
+ DenseSet<Block *> VisitedBlocks;
- // Build the initial worklist from all atoms initially live.
- for (auto *DA : G.defined_atoms()) {
- if (!DA->isLive() || DA->shouldDiscard())
- continue;
+ // Build the initial worklist from all symbols initially live.
+ for (auto *Sym : G.defined_symbols())
+ if (Sym->isLive())
+ Worklist.push_back(Sym);
- 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.
+ // 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);
+ VisitedBlocks.insert(&B);
- 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);
+ 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);
+ }
}
}