[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/tools/llvm-jitlink/llvm-jitlink-macho.cpp b/llvm/tools/llvm-jitlink/llvm-jitlink-macho.cpp
index 067c38a..9488dfe 100644
--- a/llvm/tools/llvm-jitlink/llvm-jitlink-macho.cpp
+++ b/llvm/tools/llvm-jitlink/llvm-jitlink-macho.cpp
@@ -26,53 +26,55 @@
return S.getName() == "$__STUBS";
}
-static Expected<Edge &> getFirstRelocationEdge(AtomGraph &G, DefinedAtom &DA) {
- auto EItr = std::find_if(DA.edges().begin(), DA.edges().end(),
+static Expected<Edge &> getFirstRelocationEdge(LinkGraph &G, Block &B) {
+ auto EItr = std::find_if(B.edges().begin(), B.edges().end(),
[](Edge &E) { return E.isRelocation(); });
- if (EItr == DA.edges().end())
+ if (EItr == B.edges().end())
return make_error<StringError>("GOT entry in " + G.getName() + ", \"" +
- DA.getSection().getName() +
+ B.getSection().getName() +
"\" has no relocations",
inconvertibleErrorCode());
return *EItr;
}
-static Expected<Atom &> getMachOGOTTarget(AtomGraph &G, DefinedAtom &DA) {
- auto E = getFirstRelocationEdge(G, DA);
+static Expected<Symbol &> getMachOGOTTarget(LinkGraph &G, Block &B) {
+ auto E = getFirstRelocationEdge(G, B);
if (!E)
return E.takeError();
- auto &TA = E->getTarget();
- if (!TA.hasName())
- return make_error<StringError>("GOT entry in " + G.getName() + ", \"" +
- DA.getSection().getName() +
- "\" points to anonymous "
- "atom",
- inconvertibleErrorCode());
- if (TA.isDefined() || TA.isAbsolute())
+ auto &TargetSym = E->getTarget();
+ if (!TargetSym.hasName())
return make_error<StringError>(
- "GOT entry \"" + TA.getName() + "\" in " + G.getName() + ", \"" +
- DA.getSection().getName() + "\" does not point to an external atom",
+ "GOT entry in " + G.getName() + ", \"" +
+ TargetSym.getBlock().getSection().getName() +
+ "\" points to anonymous "
+ "symbol",
inconvertibleErrorCode());
- return TA;
+ if (TargetSym.isDefined() || TargetSym.isAbsolute())
+ return make_error<StringError>(
+ "GOT entry \"" + TargetSym.getName() + "\" in " + G.getName() + ", \"" +
+ TargetSym.getBlock().getSection().getName() +
+ "\" does not point to an external symbol",
+ inconvertibleErrorCode());
+ return TargetSym;
}
-static Expected<Atom &> getMachOStubTarget(AtomGraph &G, DefinedAtom &DA) {
- auto E = getFirstRelocationEdge(G, DA);
+static Expected<Symbol &> getMachOStubTarget(LinkGraph &G, Block &B) {
+ auto E = getFirstRelocationEdge(G, B);
if (!E)
return E.takeError();
- auto &GOTA = E->getTarget();
- if (!GOTA.isDefined() ||
- !isMachOGOTSection(static_cast<DefinedAtom &>(GOTA).getSection()))
- return make_error<StringError>("Stubs entry in " + G.getName() + ", \"" +
- DA.getSection().getName() +
- "\" does not point to GOT entry",
- inconvertibleErrorCode());
- return getMachOGOTTarget(G, static_cast<DefinedAtom &>(GOTA));
+ auto &GOTSym = E->getTarget();
+ if (!GOTSym.isDefined() || !isMachOGOTSection(GOTSym.getBlock().getSection()))
+ return make_error<StringError>(
+ "Stubs entry in " + G.getName() + ", \"" +
+ GOTSym.getBlock().getSection().getName() +
+ "\" does not point to GOT entry",
+ inconvertibleErrorCode());
+ return getMachOGOTTarget(G, GOTSym.getBlock());
}
namespace llvm {
-Error registerMachOStubsAndGOT(Session &S, AtomGraph &G) {
+Error registerMachOStubsAndGOT(Session &S, LinkGraph &G) {
auto FileName = sys::path::filename(G.getName());
if (S.FileInfos.count(FileName)) {
return make_error<StringError>("When -check is passed, file names must be "
@@ -88,12 +90,12 @@
for (auto &Sec : G.sections()) {
LLVM_DEBUG({
dbgs() << " Section \"" << Sec.getName() << "\": "
- << (Sec.atoms_empty() ? "empty. skipping." : "processing...")
+ << (Sec.symbols_empty() ? "empty. skipping." : "processing...")
<< "\n";
});
// Skip empty sections.
- if (Sec.atoms_empty())
+ if (Sec.symbols_empty())
continue;
if (FileInfo.SectionInfos.count(Sec.getName()))
@@ -105,54 +107,65 @@
bool isGOTSection = isMachOGOTSection(Sec);
bool isStubsSection = isMachOStubsSection(Sec);
- auto *FirstAtom = *Sec.atoms().begin();
- auto *LastAtom = FirstAtom;
- for (auto *DA : Sec.atoms()) {
- if (DA->getAddress() < FirstAtom->getAddress())
- FirstAtom = DA;
- if (DA->getAddress() > LastAtom->getAddress())
- LastAtom = DA;
+ bool SectionContainsContent = false;
+ bool SectionContainsZeroFill = false;
+
+ auto *FirstSym = *Sec.symbols().begin();
+ auto *LastSym = FirstSym;
+ for (auto *Sym : Sec.symbols()) {
+ if (Sym->getAddress() < FirstSym->getAddress())
+ FirstSym = Sym;
+ if (Sym->getAddress() > LastSym->getAddress())
+ LastSym = Sym;
if (isGOTSection) {
- if (Sec.isZeroFill())
- return make_error<StringError>("Content atom in zero-fill section",
+ if (Sym->isSymbolZeroFill())
+ return make_error<StringError>("zero-fill atom in GOT section",
inconvertibleErrorCode());
- if (auto TA = getMachOGOTTarget(G, *DA)) {
- FileInfo.GOTEntryInfos[TA->getName()] = {DA->getContent(),
- DA->getAddress()};
- } else
- return TA.takeError();
- } else if (isStubsSection) {
- if (Sec.isZeroFill())
- return make_error<StringError>("Content atom in zero-fill section",
- inconvertibleErrorCode());
-
- if (auto TA = getMachOStubTarget(G, *DA))
- FileInfo.StubInfos[TA->getName()] = {DA->getContent(),
- DA->getAddress()};
+ if (auto TS = getMachOGOTTarget(G, Sym->getBlock()))
+ FileInfo.GOTEntryInfos[TS->getName()] = {Sym->getSymbolContent(),
+ Sym->getAddress()};
else
- return TA.takeError();
- } else if (DA->hasName() && DA->isGlobal()) {
- if (DA->isZeroFill())
- S.SymbolInfos[DA->getName()] = {DA->getSize(), DA->getAddress()};
- else {
- if (Sec.isZeroFill())
- return make_error<StringError>("Content atom in zero-fill section",
- inconvertibleErrorCode());
- S.SymbolInfos[DA->getName()] = {DA->getContent(), DA->getAddress()};
+ return TS.takeError();
+ SectionContainsContent = true;
+ } else if (isStubsSection) {
+ if (Sym->isSymbolZeroFill())
+ return make_error<StringError>("zero-fill atom in Stub section",
+ inconvertibleErrorCode());
+
+ if (auto TS = getMachOStubTarget(G, Sym->getBlock()))
+ FileInfo.StubInfos[TS->getName()] = {Sym->getSymbolContent(),
+ Sym->getAddress()};
+ else
+ return TS.takeError();
+ SectionContainsContent = true;
+ } else if (Sym->hasName()) {
+ if (Sym->isSymbolZeroFill()) {
+ S.SymbolInfos[Sym->getName()] = {Sym->getSize(), Sym->getAddress()};
+ SectionContainsZeroFill = true;
+ } else {
+ S.SymbolInfos[Sym->getName()] = {Sym->getSymbolContent(),
+ Sym->getAddress()};
+ SectionContainsContent = true;
}
}
}
- JITTargetAddress SecAddr = FirstAtom->getAddress();
- uint64_t SecSize = (LastAtom->getAddress() + LastAtom->getSize()) -
- FirstAtom->getAddress();
+ JITTargetAddress SecAddr = FirstSym->getAddress();
+ uint64_t SecSize =
+ (LastSym->getBlock().getAddress() + LastSym->getBlock().getSize()) -
+ SecAddr;
- if (Sec.isZeroFill())
+ if (SectionContainsZeroFill && SectionContainsContent)
+ return make_error<StringError>("Mixed zero-fill and content sections not "
+ "supported yet",
+ inconvertibleErrorCode());
+ if (SectionContainsZeroFill)
FileInfo.SectionInfos[Sec.getName()] = {SecSize, SecAddr};
else
FileInfo.SectionInfos[Sec.getName()] = {
- StringRef(FirstAtom->getContent().data(), SecSize), SecAddr};
+ StringRef(FirstSym->getBlock().getContent().data(), SecSize),
+ SecAddr};
}
return Error::success();
diff --git a/llvm/tools/llvm-jitlink/llvm-jitlink.cpp b/llvm/tools/llvm-jitlink/llvm-jitlink.cpp
index dfee972..7edbea2 100644
--- a/llvm/tools/llvm-jitlink/llvm-jitlink.cpp
+++ b/llvm/tools/llvm-jitlink/llvm-jitlink.cpp
@@ -86,9 +86,9 @@
cl::desc("Print registered symbol, section, got and stub addresses"),
cl::init(false));
-static cl::opt<bool> ShowAtomGraph(
+static cl::opt<bool> ShowLinkGraph(
"show-graph",
- cl::desc("Print the atom graph after fixups have been applied"),
+ cl::desc("Print the link graph after fixups have been applied"),
cl::init(false));
static cl::opt<bool> ShowSizes(
@@ -151,17 +151,14 @@
return OS;
}
-static uint64_t computeTotalAtomSizes(AtomGraph &G) {
+static uint64_t computeTotalBlockSizes(LinkGraph &G) {
uint64_t TotalSize = 0;
- for (auto *DA : G.defined_atoms())
- if (DA->isZeroFill())
- TotalSize += DA->getZeroFillSize();
- else
- TotalSize += DA->getContent().size();
+ for (auto *B : G.blocks())
+ TotalSize += B->getSize();
return TotalSize;
}
-static void dumpSectionContents(raw_ostream &OS, AtomGraph &G) {
+static void dumpSectionContents(raw_ostream &OS, LinkGraph &G) {
constexpr JITTargetAddress DumpWidth = 16;
static_assert(isPowerOf2_64(DumpWidth), "DumpWidth must be a power of two");
@@ -172,56 +169,55 @@
std::sort(Sections.begin(), Sections.end(),
[](const Section *LHS, const Section *RHS) {
- if (LHS->atoms_empty() && RHS->atoms_empty())
+ if (LHS->symbols_empty() && RHS->symbols_empty())
return false;
- if (LHS->atoms_empty())
+ if (LHS->symbols_empty())
return false;
- if (RHS->atoms_empty())
+ if (RHS->symbols_empty())
return true;
- return (*LHS->atoms().begin())->getAddress() <
- (*RHS->atoms().begin())->getAddress();
+ SectionRange LHSRange(*LHS);
+ SectionRange RHSRange(*RHS);
+ return LHSRange.getStart() < RHSRange.getStart();
});
for (auto *S : Sections) {
OS << S->getName() << " content:";
- if (S->atoms_empty()) {
+ if (S->symbols_empty()) {
OS << "\n section empty\n";
continue;
}
- // Sort atoms into order, then render.
- std::vector<DefinedAtom *> Atoms(S->atoms().begin(), S->atoms().end());
- std::sort(Atoms.begin(), Atoms.end(),
- [](const DefinedAtom *LHS, const DefinedAtom *RHS) {
- return LHS->getAddress() < RHS->getAddress();
- });
+ // Sort symbols into order, then render.
+ std::vector<Symbol *> Syms(S->symbols().begin(), S->symbols().end());
+ llvm::sort(Syms, [](const Symbol *LHS, const Symbol *RHS) {
+ return LHS->getAddress() < RHS->getAddress();
+ });
- JITTargetAddress NextAddr = Atoms.front()->getAddress() & ~(DumpWidth - 1);
- for (auto *DA : Atoms) {
- bool IsZeroFill = DA->isZeroFill();
- JITTargetAddress AtomStart = DA->getAddress();
- JITTargetAddress AtomSize =
- IsZeroFill ? DA->getZeroFillSize() : DA->getContent().size();
- JITTargetAddress AtomEnd = AtomStart + AtomSize;
- const uint8_t *AtomData =
- IsZeroFill ? nullptr : DA->getContent().bytes_begin();
+ JITTargetAddress NextAddr = Syms.front()->getAddress() & ~(DumpWidth - 1);
+ for (auto *Sym : Syms) {
+ bool IsZeroFill = Sym->getBlock().isZeroFill();
+ JITTargetAddress SymStart = Sym->getAddress();
+ JITTargetAddress SymSize = Sym->getSize();
+ JITTargetAddress SymEnd = SymStart + SymSize;
+ const uint8_t *SymData =
+ IsZeroFill ? nullptr : Sym->getSymbolContent().bytes_begin();
- // Pad any space before the atom starts.
- while (NextAddr != AtomStart) {
+ // Pad any space before the symbol starts.
+ while (NextAddr != SymStart) {
if (NextAddr % DumpWidth == 0)
OS << formatv("\n{0:x16}:", NextAddr);
OS << " ";
++NextAddr;
}
- // Render the atom content.
- while (NextAddr != AtomEnd) {
+ // Render the symbol content.
+ while (NextAddr != SymEnd) {
if (NextAddr % DumpWidth == 0)
OS << formatv("\n{0:x16}:", NextAddr);
if (IsZeroFill)
OS << " 00";
else
- OS << formatv(" {0:x-2}", AtomData[NextAddr - AtomStart]);
+ OS << formatv(" {0:x-2}", SymData[NextAddr - SymStart]);
++NextAddr;
}
}
@@ -291,18 +287,17 @@
for (auto &KV : Request) {
auto &Seg = KV.second;
- if (Seg.getContentAlignment() > PageSize)
+ if (Seg.getAlignment() > PageSize)
return make_error<StringError>("Cannot request higher than page "
"alignment",
inconvertibleErrorCode());
- if (PageSize % Seg.getContentAlignment() != 0)
+ if (PageSize % Seg.getAlignment() != 0)
return make_error<StringError>("Page size is not a multiple of "
"alignment",
inconvertibleErrorCode());
- uint64_t ZeroFillStart =
- alignTo(Seg.getContentSize(), Seg.getZeroFillAlignment());
+ uint64_t ZeroFillStart = Seg.getContentSize();
uint64_t SegmentSize = ZeroFillStart + Seg.getZeroFillSize();
// Round segment size up to page boundary.
@@ -427,7 +422,7 @@
void Session::modifyPassConfig(const Triple &FTT,
PassConfiguration &PassConfig) {
if (!CheckFiles.empty())
- PassConfig.PostFixupPasses.push_back([this](AtomGraph &G) {
+ PassConfig.PostFixupPasses.push_back([this](LinkGraph &G) {
if (TT.getObjectFormat() == Triple::MachO)
return registerMachOStubsAndGOT(*this, G);
return make_error<StringError>("Unsupported object format for GOT/stub "
@@ -435,27 +430,26 @@
inconvertibleErrorCode());
});
- if (ShowAtomGraph)
- PassConfig.PostFixupPasses.push_back([](AtomGraph &G) -> Error {
- outs() << "Atom graph post-fixup:\n";
+ if (ShowLinkGraph)
+ PassConfig.PostFixupPasses.push_back([](LinkGraph &G) -> Error {
+ outs() << "Link graph post-fixup:\n";
G.dump(outs());
return Error::success();
});
-
if (ShowSizes) {
- PassConfig.PrePrunePasses.push_back([this](AtomGraph &G) -> Error {
- SizeBeforePruning += computeTotalAtomSizes(G);
- return Error::success();
- });
- PassConfig.PostFixupPasses.push_back([this](AtomGraph &G) -> Error {
- SizeAfterFixups += computeTotalAtomSizes(G);
- return Error::success();
- });
+ PassConfig.PrePrunePasses.push_back([this](LinkGraph &G) -> Error {
+ SizeBeforePruning += computeTotalBlockSizes(G);
+ return Error::success();
+ });
+ PassConfig.PostFixupPasses.push_back([this](LinkGraph &G) -> Error {
+ SizeAfterFixups += computeTotalBlockSizes(G);
+ return Error::success();
+ });
}
if (ShowRelocatedSectionContents)
- PassConfig.PostFixupPasses.push_back([](AtomGraph &G) -> Error {
+ PassConfig.PostFixupPasses.push_back([](LinkGraph &G) -> Error {
outs() << "Relocated section contents for " << G.getName() << ":\n";
dumpSectionContents(outs(), G);
return Error::success();
@@ -757,8 +751,8 @@
static void dumpSessionStats(Session &S) {
if (ShowSizes)
- outs() << "Total size of all atoms before pruning: " << S.SizeBeforePruning
- << "\nTotal size of all atoms after fixups: " << S.SizeAfterFixups
+ outs() << "Total size of all blocks before pruning: " << S.SizeBeforePruning
+ << "\nTotal size of all blocks after fixups: " << S.SizeAfterFixups
<< "\n";
}
diff --git a/llvm/tools/llvm-jitlink/llvm-jitlink.h b/llvm/tools/llvm-jitlink/llvm-jitlink.h
index 269597a..f94a509 100644
--- a/llvm/tools/llvm-jitlink/llvm-jitlink.h
+++ b/llvm/tools/llvm-jitlink/llvm-jitlink.h
@@ -65,7 +65,7 @@
uint64_t SizeAfterFixups = 0;
};
-Error registerMachOStubsAndGOT(Session &S, jitlink::AtomGraph &G);
+Error registerMachOStubsAndGOT(Session &S, jitlink::LinkGraph &G);
} // end namespace llvm