Index: include/lld/Passes/LayoutPass.h =================================================================== --- include/lld/Passes/LayoutPass.h +++ /dev/null @@ -1,94 +0,0 @@ -//===------ Passes/LayoutPass.h - Handles Layout of atoms ------------------===// -// -// The LLVM Linker -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#ifndef LLD_PASSES_LAYOUT_PASS_H -#define LLD_PASSES_LAYOUT_PASS_H - -#include "lld/Core/File.h" -#include "lld/Core/Pass.h" -#include "lld/Core/Reader.h" -#include "llvm/ADT/DenseMap.h" -#include -#include -#include - -namespace lld { -class DefinedAtom; -class MutableFile; - -/// This linker pass does the layout of the atoms. The pass is done after the -/// order their .o files were found on the command line, then by order of the -/// atoms (address) in the .o file. But some atoms have a preferred location -/// in their section (such as pinned to the start or end of the section), so -/// the sort must take that into account too. -class LayoutPass : public Pass { -public: - struct SortKey { - SortKey(const DefinedAtom *atom, const DefinedAtom *root, uint64_t override) - : _atom(atom), _root(root), _override(override) {} - const DefinedAtom *_atom; - const DefinedAtom *_root; - uint64_t _override; - }; - - typedef std::function SortOverride; - - LayoutPass(const Registry ®istry, SortOverride sorter=nullptr); - - /// Sorts atoms in mergedFile by content type then by command line order. - void perform(std::unique_ptr &mergedFile) override; - - virtual ~LayoutPass() {} - -private: - // Build the followOn atoms chain as specified by the kindLayoutAfter - // reference type - void buildFollowOnTable(MutableFile::DefinedAtomRange &range); - - // Build a map of Atoms to ordinals for sorting the atoms - void buildOrdinalOverrideMap(MutableFile::DefinedAtomRange &range); - - const Registry &_registry; - SortOverride _customSorter; - - typedef llvm::DenseMap AtomToAtomT; - typedef llvm::DenseMap AtomToOrdinalT; - - // A map to be used to sort atoms. It represents the order of atoms in the - // result; if Atom X is mapped to atom Y in this map, X will be located - // immediately before Y in the output file. Y might be mapped to another - // atom, constructing a follow-on chain. An atom cannot be mapped to more - // than one atom unless all but one atom are of size zero. - AtomToAtomT _followOnNexts; - - // A map to be used to sort atoms. It's a map from an atom to its root of - // follow-on chain. A root atom is mapped to itself. If an atom is not in - // _followOnNexts, the atom is not in this map, and vice versa. - AtomToAtomT _followOnRoots; - - AtomToOrdinalT _ordinalOverrideMap; - - // Helper methods for buildFollowOnTable(). - const DefinedAtom *findAtomFollowedBy(const DefinedAtom *targetAtom); - bool checkAllPrevAtomsZeroSize(const DefinedAtom *targetAtom); - - void setChainRoot(const DefinedAtom *targetAtom, const DefinedAtom *root); - - std::vector decorate(MutableFile::DefinedAtomRange &atomRange) const; - void undecorate(MutableFile::DefinedAtomRange &atomRange, - std::vector &keys) const; - - // Check if the follow-on graph is a correct structure. For debugging only. - void checkFollowonChain(MutableFile::DefinedAtomRange &range); -}; - -} // namespace lld - -#endif // LLD_PASSES_LAYOUT_PASS_H Index: include/lld/ReaderWriter/MachOLinkingContext.h =================================================================== --- include/lld/ReaderWriter/MachOLinkingContext.h +++ include/lld/ReaderWriter/MachOLinkingContext.h @@ -293,13 +293,14 @@ void maybeSortInputFiles() override; + bool customAtomOrderer(const DefinedAtom *left, const DefinedAtom *right, + bool &leftBeforeRight) const; + private: Writer &writer() const override; mach_o::MachODylibFile* loadIndirectDylib(StringRef path); void checkExportWhiteList(const DefinedAtom *atom) const; void checkExportBlackList(const DefinedAtom *atom) const; - bool customAtomOrderer(const DefinedAtom *left, const DefinedAtom *right, - bool &leftBeforeRight); struct ArchInfo { StringRef archName; MachOLinkingContext::Arch arch; Index: lib/Passes/CMakeLists.txt =================================================================== --- lib/Passes/CMakeLists.txt +++ lib/Passes/CMakeLists.txt @@ -1,5 +1,4 @@ add_llvm_library(lldPasses - LayoutPass.cpp RoundTripNativePass.cpp RoundTripYAMLPass.cpp LINK_LIBS Index: lib/Passes/LayoutPass.cpp =================================================================== --- lib/Passes/LayoutPass.cpp +++ /dev/null @@ -1,478 +0,0 @@ -//===--Passes/LayoutPass.cpp - Layout atoms -------------------------------===// -// -// The LLVM Linker -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "lld/Passes/LayoutPass.h" -#include "lld/Core/Instrumentation.h" -#include "lld/Core/Parallel.h" -#include "llvm/ADT/Twine.h" -#include "llvm/Support/Debug.h" -#include -#include - -using namespace lld; - -#define DEBUG_TYPE "LayoutPass" - -static bool compareAtoms(const LayoutPass::SortKey &, - const LayoutPass::SortKey &, - LayoutPass::SortOverride customSorter=nullptr); - -#ifndef NDEBUG -// Return "reason (leftval, rightval)" -static std::string formatReason(StringRef reason, int leftVal, int rightVal) { - return (Twine(reason) + " (" + Twine(leftVal) + ", " + Twine(rightVal) + ")") - .str(); -} - -// Less-than relationship of two atoms must be transitive, which is, if a < b -// and b < c, a < c must be true. This function checks the transitivity by -// checking the sort results. -static void checkTransitivity(std::vector &vec) { - for (auto i = vec.begin(), e = vec.end(); (i + 1) != e; ++i) { - for (auto j = i + 1; j != e; ++j) { - assert(compareAtoms(*i, *j)); - assert(!compareAtoms(*j, *i)); - } - } -} - -// Helper functions to check follow-on graph. -typedef llvm::DenseMap AtomToAtomT; - -static std::string atomToDebugString(const Atom *atom) { - const DefinedAtom *definedAtom = dyn_cast(atom); - std::string str; - llvm::raw_string_ostream s(str); - if (definedAtom->name().empty()) - s << ""; - else - s << definedAtom->name(); - s << " in "; - if (definedAtom->customSectionName().empty()) - s << ""; - else - s << definedAtom->customSectionName(); - s.flush(); - return str; -} - -static void showCycleDetectedError(const Registry ®istry, - AtomToAtomT &followOnNexts, - const DefinedAtom *atom) { - const DefinedAtom *start = atom; - llvm::dbgs() << "There's a cycle in a follow-on chain!\n"; - do { - llvm::dbgs() << " " << atomToDebugString(atom) << "\n"; - for (const Reference *ref : *atom) { - StringRef kindValStr; - if (!registry.referenceKindToString(ref->kindNamespace(), ref->kindArch(), - ref->kindValue(), kindValStr)) { - kindValStr = ""; - } - llvm::dbgs() << " " << kindValStr - << ": " << atomToDebugString(ref->target()) << "\n"; - } - atom = followOnNexts[atom]; - } while (atom != start); - llvm::report_fatal_error("Cycle detected"); -} - -/// Exit if there's a cycle in a followon chain reachable from the -/// given root atom. Uses the tortoise and hare algorithm to detect a -/// cycle. -static void checkNoCycleInFollowonChain(const Registry ®istry, - AtomToAtomT &followOnNexts, - const DefinedAtom *root) { - const DefinedAtom *tortoise = root; - const DefinedAtom *hare = followOnNexts[root]; - while (true) { - if (!tortoise || !hare) - return; - if (tortoise == hare) - showCycleDetectedError(registry, followOnNexts, tortoise); - tortoise = followOnNexts[tortoise]; - hare = followOnNexts[followOnNexts[hare]]; - } -} - -static void checkReachabilityFromRoot(AtomToAtomT &followOnRoots, - const DefinedAtom *atom) { - if (!atom) return; - auto i = followOnRoots.find(atom); - if (i == followOnRoots.end()) { - llvm_unreachable(((Twine("Atom <") + atomToDebugString(atom) + - "> has no follow-on root!")) - .str() - .c_str()); - } - const DefinedAtom *ap = i->second; - while (true) { - const DefinedAtom *next = followOnRoots[ap]; - if (!next) { - llvm_unreachable((Twine("Atom <" + atomToDebugString(atom) + - "> is not reachable from its root!")) - .str() - .c_str()); - } - if (next == ap) - return; - ap = next; - } -} - -static void printDefinedAtoms(const MutableFile::DefinedAtomRange &atomRange) { - for (const DefinedAtom *atom : atomRange) { - llvm::dbgs() << " file=" << atom->file().path() - << ", name=" << atom->name() - << ", size=" << atom->size() - << ", type=" << atom->contentType() - << ", ordinal=" << atom->ordinal() - << "\n"; - } -} - -/// Verify that the followon chain is sane. Should not be called in -/// release binary. -void LayoutPass::checkFollowonChain(MutableFile::DefinedAtomRange &range) { - ScopedTask task(getDefaultDomain(), "LayoutPass::checkFollowonChain"); - - // Verify that there's no cycle in follow-on chain. - std::set roots; - for (const auto &ai : _followOnRoots) - roots.insert(ai.second); - for (const DefinedAtom *root : roots) - checkNoCycleInFollowonChain(_registry, _followOnNexts, root); - - // Verify that all the atoms in followOnNexts have references to - // their roots. - for (const auto &ai : _followOnNexts) { - checkReachabilityFromRoot(_followOnRoots, ai.first); - checkReachabilityFromRoot(_followOnRoots, ai.second); - } -} -#endif // #ifndef NDEBUG - -/// The function compares atoms by sorting atoms in the following order -/// a) Sorts atoms by Section position preference -/// b) Sorts atoms by their ordinal overrides (layout-after/ingroup) -/// c) Sorts atoms by their permissions -/// d) Sorts atoms by their content -/// e) If custom sorter provided, let it sort -/// f) Sorts atoms on how they appear using File Ordinality -/// g) Sorts atoms on how they appear within the File -static bool compareAtomsSub(const LayoutPass::SortKey &lc, - const LayoutPass::SortKey &rc, - LayoutPass::SortOverride customSorter, - std::string &reason) { - const DefinedAtom *left = lc._atom; - const DefinedAtom *right = rc._atom; - if (left == right) { - reason = "same"; - return false; - } - - // Sort by section position preference. - DefinedAtom::SectionPosition leftPos = left->sectionPosition(); - DefinedAtom::SectionPosition rightPos = right->sectionPosition(); - - bool leftSpecialPos = (leftPos != DefinedAtom::sectionPositionAny); - bool rightSpecialPos = (rightPos != DefinedAtom::sectionPositionAny); - if (leftSpecialPos || rightSpecialPos) { - if (leftPos != rightPos) { - DEBUG(reason = formatReason("sectionPos", (int)leftPos, (int)rightPos)); - return leftPos < rightPos; - } - } - - // Find the root of the chain if it is a part of a follow-on chain. - const DefinedAtom *leftRoot = lc._root; - const DefinedAtom *rightRoot = rc._root; - - // Sort atoms by their ordinal overrides only if they fall in the same - // chain. - if (leftRoot == rightRoot) { - DEBUG(reason = formatReason("override", lc._override, rc._override)); - return lc._override < rc._override; - } - - // Sort same permissions together. - DefinedAtom::ContentPermissions leftPerms = leftRoot->permissions(); - DefinedAtom::ContentPermissions rightPerms = rightRoot->permissions(); - - if (leftPerms != rightPerms) { - DEBUG(reason = - formatReason("contentPerms", (int)leftPerms, (int)rightPerms)); - return leftPerms < rightPerms; - } - - // Sort same content types together. - DefinedAtom::ContentType leftType = leftRoot->contentType(); - DefinedAtom::ContentType rightType = rightRoot->contentType(); - - if (leftType != rightType) { - DEBUG(reason = formatReason("contentType", (int)leftType, (int)rightType)); - return leftType < rightType; - } - - // Use custom sorter if supplied. - if (customSorter) { - bool leftBeforeRight; - if (customSorter(leftRoot, rightRoot, leftBeforeRight)) - return leftBeforeRight; - } - - // Sort by .o order. - const File *leftFile = &leftRoot->file(); - const File *rightFile = &rightRoot->file(); - - if (leftFile != rightFile) { - DEBUG(reason = formatReason(".o order", (int)leftFile->ordinal(), - (int)rightFile->ordinal())); - return leftFile->ordinal() < rightFile->ordinal(); - } - - // Sort by atom order with .o file. - uint64_t leftOrdinal = leftRoot->ordinal(); - uint64_t rightOrdinal = rightRoot->ordinal(); - - if (leftOrdinal != rightOrdinal) { - DEBUG(reason = formatReason("ordinal", (int)leftRoot->ordinal(), - (int)rightRoot->ordinal())); - return leftOrdinal < rightOrdinal; - } - - llvm::errs() << "Unordered: <" << left->name() << "> <" - << right->name() << ">\n"; - llvm_unreachable("Atoms with Same Ordinal!"); -} - -static bool compareAtoms(const LayoutPass::SortKey &lc, - const LayoutPass::SortKey &rc, - LayoutPass::SortOverride customSorter) { - std::string reason; - bool result = compareAtomsSub(lc, rc, customSorter, reason); - DEBUG({ - StringRef comp = result ? "<" : ">="; - llvm::dbgs() << "Layout: '" << lc._atom->name() << "' " << comp << " '" - << rc._atom->name() << "' (" << reason << ")\n"; - }); - return result; -} - -LayoutPass::LayoutPass(const Registry ®istry, SortOverride sorter) - : _registry(registry), _customSorter(sorter) {} - -// Returns the atom immediately followed by the given atom in the followon -// chain. -const DefinedAtom *LayoutPass::findAtomFollowedBy( - const DefinedAtom *targetAtom) { - // Start from the beginning of the chain and follow the chain until - // we find the targetChain. - const DefinedAtom *atom = _followOnRoots[targetAtom]; - while (true) { - const DefinedAtom *prevAtom = atom; - AtomToAtomT::iterator targetFollowOnAtomsIter = _followOnNexts.find(atom); - // The target atom must be in the chain of its root. - assert(targetFollowOnAtomsIter != _followOnNexts.end()); - atom = targetFollowOnAtomsIter->second; - if (atom == targetAtom) - return prevAtom; - } -} - -// Check if all the atoms followed by the given target atom are of size zero. -// When this method is called, an atom being added is not of size zero and -// will be added to the head of the followon chain. All the atoms between the -// atom and the targetAtom (specified by layout-after) need to be of size zero -// in this case. Otherwise the desired layout is impossible. -bool LayoutPass::checkAllPrevAtomsZeroSize(const DefinedAtom *targetAtom) { - const DefinedAtom *atom = _followOnRoots[targetAtom]; - while (true) { - if (atom == targetAtom) - return true; - if (atom->size() != 0) - // TODO: print warning that an impossible layout is being desired by the - // user. - return false; - AtomToAtomT::iterator targetFollowOnAtomsIter = _followOnNexts.find(atom); - // The target atom must be in the chain of its root. - assert(targetFollowOnAtomsIter != _followOnNexts.end()); - atom = targetFollowOnAtomsIter->second; - } -} - -// Set the root of all atoms in targetAtom's chain to the given root. -void LayoutPass::setChainRoot(const DefinedAtom *targetAtom, - const DefinedAtom *root) { - // Walk through the followon chain and override each node's root. - while (true) { - _followOnRoots[targetAtom] = root; - AtomToAtomT::iterator targetFollowOnAtomsIter = - _followOnNexts.find(targetAtom); - if (targetFollowOnAtomsIter == _followOnNexts.end()) - return; - targetAtom = targetFollowOnAtomsIter->second; - } -} - -/// This pass builds the followon tables described by two DenseMaps -/// followOnRoots and followonNexts. -/// The followOnRoots map contains a mapping of a DefinedAtom to its root -/// The followOnNexts map contains a mapping of what DefinedAtom follows the -/// current Atom -/// The algorithm follows a very simple approach -/// a) If the atom is first seen, then make that as the root atom -/// b) The targetAtom which this Atom contains, has the root thats set to the -/// root of the current atom -/// c) If the targetAtom is part of a different tree and the root of the -/// targetAtom is itself, Chain all the atoms that are contained in the tree -/// to the current Tree -/// d) If the targetAtom is part of a different chain and the root of the -/// targetAtom until the targetAtom has all atoms of size 0, then chain the -/// targetAtoms and its tree to the current chain -void LayoutPass::buildFollowOnTable(MutableFile::DefinedAtomRange &range) { - ScopedTask task(getDefaultDomain(), "LayoutPass::buildFollowOnTable"); - // Set the initial size of the followon and the followonNext hash to the - // number of atoms that we have. - _followOnRoots.resize(range.size()); - _followOnNexts.resize(range.size()); - for (const DefinedAtom *ai : range) { - for (const Reference *r : *ai) { - if (r->kindNamespace() != lld::Reference::KindNamespace::all || - r->kindValue() != lld::Reference::kindLayoutAfter) - continue; - const DefinedAtom *targetAtom = dyn_cast(r->target()); - _followOnNexts[ai] = targetAtom; - - // If we find a followon for the first time, let's make that atom as the - // root atom. - if (_followOnRoots.count(ai) == 0) - _followOnRoots[ai] = ai; - - auto iter = _followOnRoots.find(targetAtom); - if (iter == _followOnRoots.end()) { - // If the targetAtom is not a root of any chain, let's make the root of - // the targetAtom to the root of the current chain. - - // The expression m[i] = m[j] where m is a DenseMap and i != j is not - // safe. m[j] returns a reference, which would be invalidated when a - // rehashing occurs. If rehashing occurs to make room for m[i], m[j] - // becomes invalid, and that invalid reference would be used as the RHS - // value of the expression. - // Copy the value to workaround. - const DefinedAtom *tmp = _followOnRoots[ai]; - _followOnRoots[targetAtom] = tmp; - continue; - } - if (iter->second == targetAtom) { - // If the targetAtom is the root of a chain, the chain becomes part of - // the current chain. Rewrite the subchain's root to the current - // chain's root. - setChainRoot(targetAtom, _followOnRoots[ai]); - continue; - } - // The targetAtom is already a part of a chain. If the current atom is - // of size zero, we can insert it in the middle of the chain just - // before the target atom, while not breaking other atom's followon - // relationships. If it's not, we can only insert the current atom at - // the beginning of the chain. All the atoms followed by the target - // atom must be of size zero in that case to satisfy the followon - // relationships. - size_t currentAtomSize = ai->size(); - if (currentAtomSize == 0) { - const DefinedAtom *targetPrevAtom = findAtomFollowedBy(targetAtom); - _followOnNexts[targetPrevAtom] = ai; - const DefinedAtom *tmp = _followOnRoots[targetPrevAtom]; - _followOnRoots[ai] = tmp; - continue; - } - if (!checkAllPrevAtomsZeroSize(targetAtom)) - break; - _followOnNexts[ai] = _followOnRoots[targetAtom]; - setChainRoot(_followOnRoots[targetAtom], _followOnRoots[ai]); - } - } -} - -/// Build an ordinal override map by traversing the followon chain, and -/// assigning ordinals to each atom, if the atoms have their ordinals -/// already assigned skip the atom and move to the next. This is the -/// main map thats used to sort the atoms while comparing two atoms together -void LayoutPass::buildOrdinalOverrideMap(MutableFile::DefinedAtomRange &range) { - ScopedTask task(getDefaultDomain(), "LayoutPass::buildOrdinalOverrideMap"); - uint64_t index = 0; - for (const DefinedAtom *ai : range) { - const DefinedAtom *atom = ai; - if (_ordinalOverrideMap.find(atom) != _ordinalOverrideMap.end()) - continue; - AtomToAtomT::iterator start = _followOnRoots.find(atom); - if (start == _followOnRoots.end()) - continue; - for (const DefinedAtom *nextAtom = start->second; nextAtom != NULL; - nextAtom = _followOnNexts[nextAtom]) { - AtomToOrdinalT::iterator pos = _ordinalOverrideMap.find(nextAtom); - if (pos == _ordinalOverrideMap.end()) - _ordinalOverrideMap[nextAtom] = index++; - } - } -} - -std::vector -LayoutPass::decorate(MutableFile::DefinedAtomRange &atomRange) const { - std::vector ret; - for (const DefinedAtom *atom : atomRange) { - auto ri = _followOnRoots.find(atom); - auto oi = _ordinalOverrideMap.find(atom); - const DefinedAtom *root = (ri == _followOnRoots.end()) ? atom : ri->second; - uint64_t override = (oi == _ordinalOverrideMap.end()) ? 0 : oi->second; - ret.push_back(SortKey(atom, root, override)); - } - return ret; -} - -void LayoutPass::undecorate(MutableFile::DefinedAtomRange &atomRange, - std::vector &keys) const { - size_t i = 0; - for (SortKey &k : keys) - atomRange[i++] = k._atom; -} - -/// Perform the actual pass -void LayoutPass::perform(std::unique_ptr &mergedFile) { - // sort the atoms - ScopedTask task(getDefaultDomain(), "LayoutPass"); - MutableFile::DefinedAtomRange atomRange = mergedFile->definedAtoms(); - - // Build follow on tables - buildFollowOnTable(atomRange); - - // Check the structure of followon graph if running in debug mode. - DEBUG(checkFollowonChain(atomRange)); - - // Build override maps - buildOrdinalOverrideMap(atomRange); - - DEBUG({ - llvm::dbgs() << "unsorted atoms:\n"; - printDefinedAtoms(atomRange); - }); - - std::vector vec = decorate(atomRange); - parallel_sort(vec.begin(), vec.end(), - [&](const LayoutPass::SortKey &l, const LayoutPass::SortKey &r) -> bool { - return compareAtoms(l, r, _customSorter); - }); - DEBUG(checkTransitivity(vec)); - undecorate(atomRange, vec); - - DEBUG({ - llvm::dbgs() << "sorted atoms:\n"; - printDefinedAtoms(atomRange); - }); -} Index: lib/ReaderWriter/CoreLinkingContext.cpp =================================================================== --- lib/ReaderWriter/CoreLinkingContext.cpp +++ lib/ReaderWriter/CoreLinkingContext.cpp @@ -7,12 +7,13 @@ // //===----------------------------------------------------------------------===// -#include "lld/ReaderWriter/CoreLinkingContext.h" +#include "lld/Core/DefinedAtom.h" +#include "lld/Core/File.h" #include "lld/Core/Pass.h" #include "lld/Core/PassManager.h" #include "lld/Core/Simple.h" -#include "lld/Passes/LayoutPass.h" #include "lld/Passes/RoundTripYAMLPass.h" +#include "lld/ReaderWriter/CoreLinkingContext.h" #include "llvm/ADT/ArrayRef.h" using namespace lld; @@ -157,6 +158,15 @@ } }; +class OrderPass : public Pass { +public: + /// Sorts atoms by position + void perform(std::unique_ptr &file) override { + MutableFile::DefinedAtomRange defined = file->definedAtoms(); + std::sort(defined.begin(), defined.end(), DefinedAtom::compareByPosition); + } +}; + } // anonymous namespace CoreLinkingContext::CoreLinkingContext() {} @@ -168,8 +178,8 @@ void CoreLinkingContext::addPasses(PassManager &pm) { for (StringRef name : _passNames) { - if (name.equals("layout")) - pm.add(std::unique_ptr(new LayoutPass(registry()))); + if (name.equals("order")) + pm.add(std::unique_ptr(new OrderPass())); else llvm_unreachable("bad pass name"); } Index: lib/ReaderWriter/MachO/CMakeLists.txt =================================================================== --- lib/ReaderWriter/MachO/CMakeLists.txt +++ lib/ReaderWriter/MachO/CMakeLists.txt @@ -6,6 +6,7 @@ ArchHandler_x86_64.cpp CompactUnwindPass.cpp GOTPass.cpp + LayoutPass.cpp MachOLinkingContext.cpp MachONormalizedFileBinaryReader.cpp MachONormalizedFileBinaryWriter.cpp Index: lib/ReaderWriter/MachO/LayoutPass.h =================================================================== --- /dev/null +++ lib/ReaderWriter/MachO/LayoutPass.h @@ -0,0 +1,97 @@ +//===------ lib/ReaderWriter/MachO/LayoutPass.h - Handles Layout of atoms -===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_READER_WRITER_MACHO_LAYOUT_PASS_H +#define LLD_READER_WRITER_MACHO_LAYOUT_PASS_H + +#include "lld/Core/File.h" +#include "lld/Core/Pass.h" +#include "lld/Core/Reader.h" +#include "llvm/ADT/DenseMap.h" +#include +#include +#include + +namespace lld { +class DefinedAtom; +class MutableFile; + +namespace mach_o { + +/// This linker pass does the layout of the atoms. The pass is done after the +/// order their .o files were found on the command line, then by order of the +/// atoms (address) in the .o file. But some atoms have a preferred location +/// in their section (such as pinned to the start or end of the section), so +/// the sort must take that into account too. +class LayoutPass : public Pass { +public: + struct SortKey { + SortKey(const DefinedAtom *atom, const DefinedAtom *root, uint64_t override) + : _atom(atom), _root(root), _override(override) {} + const DefinedAtom *_atom; + const DefinedAtom *_root; + uint64_t _override; + }; + + typedef std::function SortOverride; + + LayoutPass(const Registry ®istry, SortOverride sorter=nullptr); + + /// Sorts atoms in mergedFile by content type then by command line order. + void perform(std::unique_ptr &mergedFile) override; + + virtual ~LayoutPass() {} + +private: + // Build the followOn atoms chain as specified by the kindLayoutAfter + // reference type + void buildFollowOnTable(MutableFile::DefinedAtomRange &range); + + // Build a map of Atoms to ordinals for sorting the atoms + void buildOrdinalOverrideMap(MutableFile::DefinedAtomRange &range); + + const Registry &_registry; + SortOverride _customSorter; + + typedef llvm::DenseMap AtomToAtomT; + typedef llvm::DenseMap AtomToOrdinalT; + + // A map to be used to sort atoms. It represents the order of atoms in the + // result; if Atom X is mapped to atom Y in this map, X will be located + // immediately before Y in the output file. Y might be mapped to another + // atom, constructing a follow-on chain. An atom cannot be mapped to more + // than one atom unless all but one atom are of size zero. + AtomToAtomT _followOnNexts; + + // A map to be used to sort atoms. It's a map from an atom to its root of + // follow-on chain. A root atom is mapped to itself. If an atom is not in + // _followOnNexts, the atom is not in this map, and vice versa. + AtomToAtomT _followOnRoots; + + AtomToOrdinalT _ordinalOverrideMap; + + // Helper methods for buildFollowOnTable(). + const DefinedAtom *findAtomFollowedBy(const DefinedAtom *targetAtom); + bool checkAllPrevAtomsZeroSize(const DefinedAtom *targetAtom); + + void setChainRoot(const DefinedAtom *targetAtom, const DefinedAtom *root); + + std::vector decorate(MutableFile::DefinedAtomRange &atomRange) const; + void undecorate(MutableFile::DefinedAtomRange &atomRange, + std::vector &keys) const; + + // Check if the follow-on graph is a correct structure. For debugging only. + void checkFollowonChain(MutableFile::DefinedAtomRange &range); +}; + +} // namespace mach_o +} // namespace lld + +#endif // LLD_READER_WRITER_MACHO_LAYOUT_PASS_H Index: lib/ReaderWriter/MachO/LayoutPass.cpp =================================================================== --- /dev/null +++ lib/ReaderWriter/MachO/LayoutPass.cpp @@ -0,0 +1,495 @@ +//===-- ReaderWriter/MachO/LayoutPass.cpp - Layout atoms ------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "LayoutPass.h" +#include "lld/Core/Instrumentation.h" +#include "lld/Core/Parallel.h" +#include "lld/Core/PassManager.h" +#include "lld/ReaderWriter/MachOLinkingContext.h" +#include "llvm/ADT/Twine.h" +#include "llvm/Support/Debug.h" +#include +#include + +using namespace lld; + +#define DEBUG_TYPE "LayoutPass" + +namespace lld { +namespace mach_o { + +static bool compareAtoms(const LayoutPass::SortKey &, + const LayoutPass::SortKey &, + LayoutPass::SortOverride customSorter=nullptr); + +#ifndef NDEBUG +// Return "reason (leftval, rightval)" +static std::string formatReason(StringRef reason, int leftVal, int rightVal) { + return (Twine(reason) + " (" + Twine(leftVal) + ", " + Twine(rightVal) + ")") + .str(); +} + +// Less-than relationship of two atoms must be transitive, which is, if a < b +// and b < c, a < c must be true. This function checks the transitivity by +// checking the sort results. +static void checkTransitivity(std::vector &vec) { + for (auto i = vec.begin(), e = vec.end(); (i + 1) != e; ++i) { + for (auto j = i + 1; j != e; ++j) { + assert(compareAtoms(*i, *j)); + assert(!compareAtoms(*j, *i)); + } + } +} + +// Helper functions to check follow-on graph. +typedef llvm::DenseMap AtomToAtomT; + +static std::string atomToDebugString(const Atom *atom) { + const DefinedAtom *definedAtom = dyn_cast(atom); + std::string str; + llvm::raw_string_ostream s(str); + if (definedAtom->name().empty()) + s << ""; + else + s << definedAtom->name(); + s << " in "; + if (definedAtom->customSectionName().empty()) + s << ""; + else + s << definedAtom->customSectionName(); + s.flush(); + return str; +} + +static void showCycleDetectedError(const Registry ®istry, + AtomToAtomT &followOnNexts, + const DefinedAtom *atom) { + const DefinedAtom *start = atom; + llvm::dbgs() << "There's a cycle in a follow-on chain!\n"; + do { + llvm::dbgs() << " " << atomToDebugString(atom) << "\n"; + for (const Reference *ref : *atom) { + StringRef kindValStr; + if (!registry.referenceKindToString(ref->kindNamespace(), ref->kindArch(), + ref->kindValue(), kindValStr)) { + kindValStr = ""; + } + llvm::dbgs() << " " << kindValStr + << ": " << atomToDebugString(ref->target()) << "\n"; + } + atom = followOnNexts[atom]; + } while (atom != start); + llvm::report_fatal_error("Cycle detected"); +} + +/// Exit if there's a cycle in a followon chain reachable from the +/// given root atom. Uses the tortoise and hare algorithm to detect a +/// cycle. +static void checkNoCycleInFollowonChain(const Registry ®istry, + AtomToAtomT &followOnNexts, + const DefinedAtom *root) { + const DefinedAtom *tortoise = root; + const DefinedAtom *hare = followOnNexts[root]; + while (true) { + if (!tortoise || !hare) + return; + if (tortoise == hare) + showCycleDetectedError(registry, followOnNexts, tortoise); + tortoise = followOnNexts[tortoise]; + hare = followOnNexts[followOnNexts[hare]]; + } +} + +static void checkReachabilityFromRoot(AtomToAtomT &followOnRoots, + const DefinedAtom *atom) { + if (!atom) return; + auto i = followOnRoots.find(atom); + if (i == followOnRoots.end()) { + llvm_unreachable(((Twine("Atom <") + atomToDebugString(atom) + + "> has no follow-on root!")) + .str() + .c_str()); + } + const DefinedAtom *ap = i->second; + while (true) { + const DefinedAtom *next = followOnRoots[ap]; + if (!next) { + llvm_unreachable((Twine("Atom <" + atomToDebugString(atom) + + "> is not reachable from its root!")) + .str() + .c_str()); + } + if (next == ap) + return; + ap = next; + } +} + +static void printDefinedAtoms(const MutableFile::DefinedAtomRange &atomRange) { + for (const DefinedAtom *atom : atomRange) { + llvm::dbgs() << " file=" << atom->file().path() + << ", name=" << atom->name() + << ", size=" << atom->size() + << ", type=" << atom->contentType() + << ", ordinal=" << atom->ordinal() + << "\n"; + } +} + +/// Verify that the followon chain is sane. Should not be called in +/// release binary. +void LayoutPass::checkFollowonChain(MutableFile::DefinedAtomRange &range) { + ScopedTask task(getDefaultDomain(), "LayoutPass::checkFollowonChain"); + + // Verify that there's no cycle in follow-on chain. + std::set roots; + for (const auto &ai : _followOnRoots) + roots.insert(ai.second); + for (const DefinedAtom *root : roots) + checkNoCycleInFollowonChain(_registry, _followOnNexts, root); + + // Verify that all the atoms in followOnNexts have references to + // their roots. + for (const auto &ai : _followOnNexts) { + checkReachabilityFromRoot(_followOnRoots, ai.first); + checkReachabilityFromRoot(_followOnRoots, ai.second); + } +} +#endif // #ifndef NDEBUG + +/// The function compares atoms by sorting atoms in the following order +/// a) Sorts atoms by Section position preference +/// b) Sorts atoms by their ordinal overrides (layout-after/ingroup) +/// c) Sorts atoms by their permissions +/// d) Sorts atoms by their content +/// e) If custom sorter provided, let it sort +/// f) Sorts atoms on how they appear using File Ordinality +/// g) Sorts atoms on how they appear within the File +static bool compareAtomsSub(const LayoutPass::SortKey &lc, + const LayoutPass::SortKey &rc, + LayoutPass::SortOverride customSorter, + std::string &reason) { + const DefinedAtom *left = lc._atom; + const DefinedAtom *right = rc._atom; + if (left == right) { + reason = "same"; + return false; + } + + // Sort by section position preference. + DefinedAtom::SectionPosition leftPos = left->sectionPosition(); + DefinedAtom::SectionPosition rightPos = right->sectionPosition(); + + bool leftSpecialPos = (leftPos != DefinedAtom::sectionPositionAny); + bool rightSpecialPos = (rightPos != DefinedAtom::sectionPositionAny); + if (leftSpecialPos || rightSpecialPos) { + if (leftPos != rightPos) { + DEBUG(reason = formatReason("sectionPos", (int)leftPos, (int)rightPos)); + return leftPos < rightPos; + } + } + + // Find the root of the chain if it is a part of a follow-on chain. + const DefinedAtom *leftRoot = lc._root; + const DefinedAtom *rightRoot = rc._root; + + // Sort atoms by their ordinal overrides only if they fall in the same + // chain. + if (leftRoot == rightRoot) { + DEBUG(reason = formatReason("override", lc._override, rc._override)); + return lc._override < rc._override; + } + + // Sort same permissions together. + DefinedAtom::ContentPermissions leftPerms = leftRoot->permissions(); + DefinedAtom::ContentPermissions rightPerms = rightRoot->permissions(); + + if (leftPerms != rightPerms) { + DEBUG(reason = + formatReason("contentPerms", (int)leftPerms, (int)rightPerms)); + return leftPerms < rightPerms; + } + + // Sort same content types together. + DefinedAtom::ContentType leftType = leftRoot->contentType(); + DefinedAtom::ContentType rightType = rightRoot->contentType(); + + if (leftType != rightType) { + DEBUG(reason = formatReason("contentType", (int)leftType, (int)rightType)); + return leftType < rightType; + } + + // Use custom sorter if supplied. + if (customSorter) { + bool leftBeforeRight; + if (customSorter(leftRoot, rightRoot, leftBeforeRight)) + return leftBeforeRight; + } + + // Sort by .o order. + const File *leftFile = &leftRoot->file(); + const File *rightFile = &rightRoot->file(); + + if (leftFile != rightFile) { + DEBUG(reason = formatReason(".o order", (int)leftFile->ordinal(), + (int)rightFile->ordinal())); + return leftFile->ordinal() < rightFile->ordinal(); + } + + // Sort by atom order with .o file. + uint64_t leftOrdinal = leftRoot->ordinal(); + uint64_t rightOrdinal = rightRoot->ordinal(); + + if (leftOrdinal != rightOrdinal) { + DEBUG(reason = formatReason("ordinal", (int)leftRoot->ordinal(), + (int)rightRoot->ordinal())); + return leftOrdinal < rightOrdinal; + } + + llvm::errs() << "Unordered: <" << left->name() << "> <" + << right->name() << ">\n"; + llvm_unreachable("Atoms with Same Ordinal!"); +} + +static bool compareAtoms(const LayoutPass::SortKey &lc, + const LayoutPass::SortKey &rc, + LayoutPass::SortOverride customSorter) { + std::string reason; + bool result = compareAtomsSub(lc, rc, customSorter, reason); + DEBUG({ + StringRef comp = result ? "<" : ">="; + llvm::dbgs() << "Layout: '" << lc._atom->name() << "' " << comp << " '" + << rc._atom->name() << "' (" << reason << ")\n"; + }); + return result; +} + +LayoutPass::LayoutPass(const Registry ®istry, SortOverride sorter) + : _registry(registry), _customSorter(sorter) {} + +// Returns the atom immediately followed by the given atom in the followon +// chain. +const DefinedAtom *LayoutPass::findAtomFollowedBy( + const DefinedAtom *targetAtom) { + // Start from the beginning of the chain and follow the chain until + // we find the targetChain. + const DefinedAtom *atom = _followOnRoots[targetAtom]; + while (true) { + const DefinedAtom *prevAtom = atom; + AtomToAtomT::iterator targetFollowOnAtomsIter = _followOnNexts.find(atom); + // The target atom must be in the chain of its root. + assert(targetFollowOnAtomsIter != _followOnNexts.end()); + atom = targetFollowOnAtomsIter->second; + if (atom == targetAtom) + return prevAtom; + } +} + +// Check if all the atoms followed by the given target atom are of size zero. +// When this method is called, an atom being added is not of size zero and +// will be added to the head of the followon chain. All the atoms between the +// atom and the targetAtom (specified by layout-after) need to be of size zero +// in this case. Otherwise the desired layout is impossible. +bool LayoutPass::checkAllPrevAtomsZeroSize(const DefinedAtom *targetAtom) { + const DefinedAtom *atom = _followOnRoots[targetAtom]; + while (true) { + if (atom == targetAtom) + return true; + if (atom->size() != 0) + // TODO: print warning that an impossible layout is being desired by the + // user. + return false; + AtomToAtomT::iterator targetFollowOnAtomsIter = _followOnNexts.find(atom); + // The target atom must be in the chain of its root. + assert(targetFollowOnAtomsIter != _followOnNexts.end()); + atom = targetFollowOnAtomsIter->second; + } +} + +// Set the root of all atoms in targetAtom's chain to the given root. +void LayoutPass::setChainRoot(const DefinedAtom *targetAtom, + const DefinedAtom *root) { + // Walk through the followon chain and override each node's root. + while (true) { + _followOnRoots[targetAtom] = root; + AtomToAtomT::iterator targetFollowOnAtomsIter = + _followOnNexts.find(targetAtom); + if (targetFollowOnAtomsIter == _followOnNexts.end()) + return; + targetAtom = targetFollowOnAtomsIter->second; + } +} + +/// This pass builds the followon tables described by two DenseMaps +/// followOnRoots and followonNexts. +/// The followOnRoots map contains a mapping of a DefinedAtom to its root +/// The followOnNexts map contains a mapping of what DefinedAtom follows the +/// current Atom +/// The algorithm follows a very simple approach +/// a) If the atom is first seen, then make that as the root atom +/// b) The targetAtom which this Atom contains, has the root thats set to the +/// root of the current atom +/// c) If the targetAtom is part of a different tree and the root of the +/// targetAtom is itself, Chain all the atoms that are contained in the tree +/// to the current Tree +/// d) If the targetAtom is part of a different chain and the root of the +/// targetAtom until the targetAtom has all atoms of size 0, then chain the +/// targetAtoms and its tree to the current chain +void LayoutPass::buildFollowOnTable(MutableFile::DefinedAtomRange &range) { + ScopedTask task(getDefaultDomain(), "LayoutPass::buildFollowOnTable"); + // Set the initial size of the followon and the followonNext hash to the + // number of atoms that we have. + _followOnRoots.resize(range.size()); + _followOnNexts.resize(range.size()); + for (const DefinedAtom *ai : range) { + for (const Reference *r : *ai) { + if (r->kindNamespace() != lld::Reference::KindNamespace::all || + r->kindValue() != lld::Reference::kindLayoutAfter) + continue; + const DefinedAtom *targetAtom = dyn_cast(r->target()); + _followOnNexts[ai] = targetAtom; + + // If we find a followon for the first time, let's make that atom as the + // root atom. + if (_followOnRoots.count(ai) == 0) + _followOnRoots[ai] = ai; + + auto iter = _followOnRoots.find(targetAtom); + if (iter == _followOnRoots.end()) { + // If the targetAtom is not a root of any chain, let's make the root of + // the targetAtom to the root of the current chain. + + // The expression m[i] = m[j] where m is a DenseMap and i != j is not + // safe. m[j] returns a reference, which would be invalidated when a + // rehashing occurs. If rehashing occurs to make room for m[i], m[j] + // becomes invalid, and that invalid reference would be used as the RHS + // value of the expression. + // Copy the value to workaround. + const DefinedAtom *tmp = _followOnRoots[ai]; + _followOnRoots[targetAtom] = tmp; + continue; + } + if (iter->second == targetAtom) { + // If the targetAtom is the root of a chain, the chain becomes part of + // the current chain. Rewrite the subchain's root to the current + // chain's root. + setChainRoot(targetAtom, _followOnRoots[ai]); + continue; + } + // The targetAtom is already a part of a chain. If the current atom is + // of size zero, we can insert it in the middle of the chain just + // before the target atom, while not breaking other atom's followon + // relationships. If it's not, we can only insert the current atom at + // the beginning of the chain. All the atoms followed by the target + // atom must be of size zero in that case to satisfy the followon + // relationships. + size_t currentAtomSize = ai->size(); + if (currentAtomSize == 0) { + const DefinedAtom *targetPrevAtom = findAtomFollowedBy(targetAtom); + _followOnNexts[targetPrevAtom] = ai; + const DefinedAtom *tmp = _followOnRoots[targetPrevAtom]; + _followOnRoots[ai] = tmp; + continue; + } + if (!checkAllPrevAtomsZeroSize(targetAtom)) + break; + _followOnNexts[ai] = _followOnRoots[targetAtom]; + setChainRoot(_followOnRoots[targetAtom], _followOnRoots[ai]); + } + } +} + +/// Build an ordinal override map by traversing the followon chain, and +/// assigning ordinals to each atom, if the atoms have their ordinals +/// already assigned skip the atom and move to the next. This is the +/// main map thats used to sort the atoms while comparing two atoms together +void LayoutPass::buildOrdinalOverrideMap(MutableFile::DefinedAtomRange &range) { + ScopedTask task(getDefaultDomain(), "LayoutPass::buildOrdinalOverrideMap"); + uint64_t index = 0; + for (const DefinedAtom *ai : range) { + const DefinedAtom *atom = ai; + if (_ordinalOverrideMap.find(atom) != _ordinalOverrideMap.end()) + continue; + AtomToAtomT::iterator start = _followOnRoots.find(atom); + if (start == _followOnRoots.end()) + continue; + for (const DefinedAtom *nextAtom = start->second; nextAtom != NULL; + nextAtom = _followOnNexts[nextAtom]) { + AtomToOrdinalT::iterator pos = _ordinalOverrideMap.find(nextAtom); + if (pos == _ordinalOverrideMap.end()) + _ordinalOverrideMap[nextAtom] = index++; + } + } +} + +std::vector +LayoutPass::decorate(MutableFile::DefinedAtomRange &atomRange) const { + std::vector ret; + for (const DefinedAtom *atom : atomRange) { + auto ri = _followOnRoots.find(atom); + auto oi = _ordinalOverrideMap.find(atom); + const DefinedAtom *root = (ri == _followOnRoots.end()) ? atom : ri->second; + uint64_t override = (oi == _ordinalOverrideMap.end()) ? 0 : oi->second; + ret.push_back(SortKey(atom, root, override)); + } + return ret; +} + +void LayoutPass::undecorate(MutableFile::DefinedAtomRange &atomRange, + std::vector &keys) const { + size_t i = 0; + for (SortKey &k : keys) + atomRange[i++] = k._atom; +} + +/// Perform the actual pass +void LayoutPass::perform(std::unique_ptr &mergedFile) { + // sort the atoms + ScopedTask task(getDefaultDomain(), "LayoutPass"); + MutableFile::DefinedAtomRange atomRange = mergedFile->definedAtoms(); + + // Build follow on tables + buildFollowOnTable(atomRange); + + // Check the structure of followon graph if running in debug mode. + DEBUG(checkFollowonChain(atomRange)); + + // Build override maps + buildOrdinalOverrideMap(atomRange); + + DEBUG({ + llvm::dbgs() << "unsorted atoms:\n"; + printDefinedAtoms(atomRange); + }); + + std::vector vec = decorate(atomRange); + parallel_sort(vec.begin(), vec.end(), + [&](const LayoutPass::SortKey &l, const LayoutPass::SortKey &r) -> bool { + return compareAtoms(l, r, _customSorter); + }); + DEBUG(checkTransitivity(vec)); + undecorate(atomRange, vec); + + DEBUG({ + llvm::dbgs() << "sorted atoms:\n"; + printDefinedAtoms(atomRange); + }); +} + +void addLayoutPass(PassManager &pm, const MachOLinkingContext &ctx) { + pm.add(std::unique_ptr(new LayoutPass( + ctx.registry(), [&](const DefinedAtom * left, const DefinedAtom * right, + bool & leftBeforeRight) + ->bool { + return ctx.customAtomOrderer(left, right, leftBeforeRight); + }))); +} + +} // namespace mach_o +} // namespace lld Index: lib/ReaderWriter/MachO/MachOLinkingContext.cpp =================================================================== --- lib/ReaderWriter/MachO/MachOLinkingContext.cpp +++ lib/ReaderWriter/MachO/MachOLinkingContext.cpp @@ -17,7 +17,6 @@ #include "lld/Core/Reader.h" #include "lld/Core/Writer.h" #include "lld/Driver/Driver.h" -#include "lld/Passes/LayoutPass.h" #include "lld/Passes/RoundTripYAMLPass.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/Triple.h" @@ -583,12 +582,7 @@ } void MachOLinkingContext::addPasses(PassManager &pm) { - pm.add(std::unique_ptr(new LayoutPass( - registry(), [&](const DefinedAtom * left, const DefinedAtom * right, - bool & leftBeforeRight) - ->bool { - return customAtomOrderer(left, right, leftBeforeRight); - }))); + mach_o::addLayoutPass(pm, *this); if (needsStubsPass()) mach_o::addStubsPass(pm, *this); if (needsCompactUnwindPass()) @@ -908,7 +902,7 @@ bool MachOLinkingContext::customAtomOrderer(const DefinedAtom *left, const DefinedAtom *right, - bool &leftBeforeRight) { + bool &leftBeforeRight) const { // No custom sorting if no order file entries. if (!_orderFileEntries) return false; Index: lib/ReaderWriter/MachO/MachOPasses.h =================================================================== --- lib/ReaderWriter/MachO/MachOPasses.h +++ lib/ReaderWriter/MachO/MachOPasses.h @@ -16,6 +16,7 @@ namespace lld { namespace mach_o { +void addLayoutPass(PassManager &pm, const MachOLinkingContext &ctx); void addStubsPass(PassManager &pm, const MachOLinkingContext &ctx); void addGOTPass(PassManager &pm, const MachOLinkingContext &ctx); void addCompactUnwindPass(PassManager &pm, const MachOLinkingContext &ctx); Index: test/core/layout-transitivity.objtxt =================================================================== --- test/core/layout-transitivity.objtxt +++ /dev/null @@ -1,34 +0,0 @@ -# REQUIRES: asserts -# RUN: lld -core --add-pass layout -mllvm -debug %s 2> /dev/null | FileCheck %s - ---- -defined-atoms: - - name: fn3 - scope: global - - name: fn2 - scope: global - references: - - kind: layout-after - offset: 0 - target: fn3 - - name: fn - scope: global - references: - - kind: layout-after - offset: 0 - target: fn1 - - name: fn4 - scope: global - - name: fn1 - scope: global - references: - - kind: layout-after - offset: 0 - target: fn2 -... - -# CHECK: - name: fn -# CHECK: - name: fn1 -# CHECK: - name: fn2 -# CHECK: - name: fn3 -# CHECK: - name: fn4 Index: test/core/layoutafter-test.objtxt =================================================================== --- test/core/layoutafter-test.objtxt +++ /dev/null @@ -1,30 +0,0 @@ -# RUN: lld -core --add-pass layout %s | FileCheck %s -check-prefix=CHKORDER - ---- -defined-atoms: - - name: fn3 - scope: global - - name: fn2 - scope: global - references: - - kind: layout-after - offset: 0 - target: fn3 - - name: fn - scope: global - references: - - kind: layout-after - offset: 0 - target: fn1 - - name: fn1 - scope: global - references: - - kind: layout-after - offset: 0 - target: fn2 -... - -# CHKORDER: - name: fn -# CHKORDER: - name: fn1 -# CHKORDER: - name: fn2 -# CHKORDER: - name: fn3 Index: test/core/section-position.objtxt =================================================================== --- test/core/section-position.objtxt +++ /dev/null @@ -1,85 +0,0 @@ -# RUN: lld -core --add-pass layout %s | FileCheck %s -check-prefix=CHKORDER -# RUN: lld -core %s | FileCheck %s -check-prefix=CHKUNORD - -# -# Test that atoms with section position requirements are sorted properly. -# - ---- -defined-atoms: - - name: data_end - type: data - section-position: end - - - name: some_data - type: data - content: [ 01, 02 ] - - - name: early_data - type: data - section-position: early - content: [ 00, 00, 00, 00 ] - - - name: data_start - type: data - section-position: start - ---- -defined-atoms: - - name: data_end_too - type: data - section-position: end - - - name: some_more_data - type: data - content: [ 03, 04 ] - ---- -defined-atoms: - - name: early_data_too - type: data - section-position: early - content: [ 00, 00, 00, 01 ] - -... - - -# CHKUNORD: defined-atoms: -# CHKUNORD: - name: data_end -# CHKUNORD: section-position: end -# CHKUNORD: - name: some_data -# CHKUNORD: content: [ 01, 02 ] -# CHKUNORD: - name: early_data -# CHKUNORD: content: [ 00, 00, 00, 00 ] -# CHKUNORD: section-position: early -# CHKUNORD: - name: data_start -# CHKUNORD: section-position: start -# CHKUNORD: - name: data_end_too -# CHKUNORD: section-position: end -# CHKUNORD: - name: some_more_data -# CHKUNORD: content: [ 03, 04 ] -# CHKUNORD: - name: early_data_too -# CHKUNORD: content: [ 00, 00, 00, 01 ] -# CHKUNORD: section-position: early -# CHKUNORD: ... - -# CHKORDER: defined-atoms: -# CHKORDER: - name: data_start -# CHKORDER: section-position: start -# CHKORDER: - name: early_data -# CHKORDER: content: [ 00, 00, 00, 00 ] -# CHKORDER: section-position: early -# CHKORDER: - name: early_data_too -# CHKORDER: content: [ 00, 00, 00, 01 ] -# CHKORDER: section-position: early -# CHKORDER: - name: some_data -# CHKORDER: content: [ 01, 02 ] -# CHKORDER: - name: some_more_data -# CHKORDER: content: [ 03, 04 ] -# CHKORDER: - name: data_end -# CHKORDER: section-position: end -# CHKORDER: - name: data_end_too -# CHKORDER: section-position: end -# CHKORDER: ... - -