This is an archive of the discontinued LLVM Phabricator instance.

Differential D7311

MachO: Move LayoutPass to MachO directory.
Needs ReviewPublic

Authored by ruiu on Jan 30 2015, 6:53 PM.

Download Raw Diff

Details

Reviewers

kledzik

Summary

The real user of the LayoutPass is now only Mach-O, so move that
pass out of the common directory to Mach-O directory.

"Core" architecture were using the LayoutPass. I modified that
to use a simple OrderPass. I think no one actually have authority
what feature should be in Core and what's not, but I believe the
LayoutPass is not very suitable for Core. Before more code starts
depending on the complex pass, it's better to remove that from
Core.

I could have simplified that pass because Mach-O is the only user
of the LayoutPass. For example, the second parameter of the
LayoutPass constructor can be converted from optional to mandatory.
I didn't do that in this patch to keep it simple. I'll do in a
followup patch.

Diff Detail

Event Timeline

ruiu updated this revision to Diff 19076.Jan 30 2015, 6:53 PM

ruiu retitled this revision from to MachO: Move LayoutPass to MachO directory..

ruiu updated this object.

ruiu edited the test plan for this revision. (Show Details)

ruiu added a reviewer: kledzik.

ruiu added a project: lld.

ruiu added a subscriber: Unknown Object (MLST).

Again, This pass is needed by ELF to adopt atom order file like macho at which time ELF will use it.

It's not correct to say we need that pass to layout atoms for order file. It's perhaps needless to say, but the LayoutPass is not the only way to sort atoms. If we need to sort atoms in some order, we can add code to elf::OrderPass to directly sort atoms in that pass.

That would be so much easier than hacking with layout references for the LayoutPass to let the LayoutPass to interpret that result.

It's just like the InputGraph design that we have just eliminated. We had complex code to set up data for the InputGraph, and the InputGraph does some very complex thing in it. That was not a good design after all, so let's not over-think this time too. When we need to tweak sort order, we can always change "compare" function in elf::OrderPass.

Ping.

Ping?

LGTM

Revision Contents

Path

Size

include/

lld/

Passes/

LayoutPass.h

ReaderWriter/

MachOLinkingContext.h

5 lines

lib/

Passes/

CMakeLists.txt

1 line

LayoutPass.cpp

ReaderWriter/

CoreLinkingContext.cpp

18 lines

MachO/

CMakeLists.txt

1 line

LayoutPass.h

97 lines

LayoutPass.cpp

495 lines

MachOLinkingContext.cpp

10 lines

MachOPasses.h

1 line

test/

core/

layout-transitivity.objtxt

layoutafter-test.objtxt

section-position.objtxt

Diff 19076

include/lld/Passes/LayoutPass.h

This file was deleted.

	//===------ 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 <map>
	#include <string>
	#include <vector>

	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<bool (const DefinedAtom left, const DefinedAtom right,
	bool &leftBeforeRight)> SortOverride;

	LayoutPass(const Registry &registry, SortOverride sorter=nullptr);

	/// Sorts atoms in mergedFile by content type then by command line order.
	void perform(std::unique_ptr<MutableFile> &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<const DefinedAtom , const DefinedAtom > AtomToAtomT;
	typedef llvm::DenseMap<const DefinedAtom *, uint64_t> 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<SortKey> decorate(MutableFile::DefinedAtomRange &atomRange) const;
	void undecorate(MutableFile::DefinedAtomRange &atomRange,
	std::vector<SortKey> &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

include/lld/ReaderWriter/MachOLinkingContext.h

Show First 20 Lines • Show All 287 Lines • ▼ Show 20 Lines	public:
static bool isBigEndian(Arch arch);		static bool isBigEndian(Arch arch);

/// Construct 32-bit value from string "X.Y.Z" where		/// Construct 32-bit value from string "X.Y.Z" where
/// bits are xxxx.yy.zz. Largest number is 65535.255.255		/// bits are xxxx.yy.zz. Largest number is 65535.255.255
static bool parsePackedVersion(StringRef str, uint32_t &result);		static bool parsePackedVersion(StringRef str, uint32_t &result);

void maybeSortInputFiles() override;		void maybeSortInputFiles() override;

		bool customAtomOrderer(const DefinedAtom left, const DefinedAtom right,
		bool &leftBeforeRight) const;

private:		private:
Writer &writer() const override;		Writer &writer() const override;
mach_o::MachODylibFile* loadIndirectDylib(StringRef path);		mach_o::MachODylibFile* loadIndirectDylib(StringRef path);
void checkExportWhiteList(const DefinedAtom *atom) const;		void checkExportWhiteList(const DefinedAtom *atom) const;
void checkExportBlackList(const DefinedAtom *atom) const;		void checkExportBlackList(const DefinedAtom *atom) const;
bool customAtomOrderer(const DefinedAtom left, const DefinedAtom right,
bool &leftBeforeRight);
struct ArchInfo {		struct ArchInfo {
StringRef archName;		StringRef archName;
MachOLinkingContext::Arch arch;		MachOLinkingContext::Arch arch;
bool littleEndian;		bool littleEndian;
uint32_t cputype;		uint32_t cputype;
uint32_t cpusubtype;		uint32_t cpusubtype;
};		};

▲ Show 20 Lines • Show All 58 Lines • Show Last 20 Lines

lib/Passes/CMakeLists.txt

	add_llvm_library(lldPasses			add_llvm_library(lldPasses
	LayoutPass.cpp
	RoundTripNativePass.cpp			RoundTripNativePass.cpp
	RoundTripYAMLPass.cpp			RoundTripYAMLPass.cpp
	LINK_LIBS			LINK_LIBS
	lldCore			lldCore
	lldNative			lldNative
	lldYAML			lldYAML
	LLVMSupport			LLVMSupport
	)			)

lib/Passes/LayoutPass.cpp

This file was deleted.

	//===--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 <algorithm>
	#include <set>

	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<LayoutPass::SortKey> &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<const DefinedAtom , const DefinedAtom > AtomToAtomT;

	static std::string atomToDebugString(const Atom *atom) {
	const DefinedAtom *definedAtom = dyn_cast<DefinedAtom>(atom);
	std::string str;
	llvm::raw_string_ostream s(str);
	if (definedAtom->name().empty())
	s << "<anonymous " << definedAtom << ">";
	else
	s << definedAtom->name();
	s << " in ";
	if (definedAtom->customSectionName().empty())
	s << "<anonymous>";
	else
	s << definedAtom->customSectionName();
	s.flush();
	return str;
	}

	static void showCycleDetectedError(const Registry &registry,
	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 = "<unknown>";
	}
	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 &registry,
	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<const DefinedAtom *> 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 &registry, 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<DefinedAtom>(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::SortKey>
	LayoutPass::decorate(MutableFile::DefinedAtomRange &atomRange) const {
	std::vector<SortKey> 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<SortKey> &keys) const {
	size_t i = 0;
	for (SortKey &k : keys)
	atomRange[i++] = k._atom;
	}

	/// Perform the actual pass
	void LayoutPass::perform(std::unique_ptr<MutableFile> &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<LayoutPass::SortKey> 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);
	});
	}

lib/ReaderWriter/CoreLinkingContext.cpp

//===- lib/ReaderWriter/CoreLinkingContext.cpp ----------------------------===//		//===- lib/ReaderWriter/CoreLinkingContext.cpp ----------------------------===//
//		//
// The LLVM Linker		// The LLVM Linker
//		//
// This file is distributed under the University of Illinois Open Source		// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.		// License. See LICENSE.TXT for details.
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

#include "lld/ReaderWriter/CoreLinkingContext.h"		#include "lld/Core/DefinedAtom.h"
		#include "lld/Core/File.h"
#include "lld/Core/Pass.h"		#include "lld/Core/Pass.h"
#include "lld/Core/PassManager.h"		#include "lld/Core/PassManager.h"
#include "lld/Core/Simple.h"		#include "lld/Core/Simple.h"
#include "lld/Passes/LayoutPass.h"
#include "lld/Passes/RoundTripYAMLPass.h"		#include "lld/Passes/RoundTripYAMLPass.h"
		#include "lld/ReaderWriter/CoreLinkingContext.h"
#include "llvm/ADT/ArrayRef.h"		#include "llvm/ADT/ArrayRef.h"

using namespace lld;		using namespace lld;

namespace {		namespace {

/// \brief Simple atom created by the stubs pass.		/// \brief Simple atom created by the stubs pass.
class TestingStubAtom : public DefinedAtom {		class TestingStubAtom : public DefinedAtom {
▲ Show 20 Lines • Show All 128 Lines • ▼ Show 20 Lines	public:
void addAtom(const Atom &atom) override {		void addAtom(const Atom &atom) override {
if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(&atom))		if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(&atom))
_definedAtoms._atoms.push_back(defAtom);		_definedAtoms._atoms.push_back(defAtom);
else		else
llvm_unreachable("atom has unknown definition kind");		llvm_unreachable("atom has unknown definition kind");
}		}
};		};

		class OrderPass : public Pass {
		public:
		/// Sorts atoms by position
		void perform(std::unique_ptr<MutableFile> &file) override {
		MutableFile::DefinedAtomRange defined = file->definedAtoms();
		std::sort(defined.begin(), defined.end(), DefinedAtom::compareByPosition);
		}
		};

} // anonymous namespace		} // anonymous namespace

CoreLinkingContext::CoreLinkingContext() {}		CoreLinkingContext::CoreLinkingContext() {}

bool CoreLinkingContext::validateImpl(raw_ostream &) {		bool CoreLinkingContext::validateImpl(raw_ostream &) {
_writer = createWriterYAML(*this);		_writer = createWriterYAML(*this);
return true;		return true;
}		}

void CoreLinkingContext::addPasses(PassManager &pm) {		void CoreLinkingContext::addPasses(PassManager &pm) {
for (StringRef name : _passNames) {		for (StringRef name : _passNames) {
if (name.equals("layout"))		if (name.equals("order"))
pm.add(std::unique_ptr<Pass>(new LayoutPass(registry())));		pm.add(std::unique_ptr<Pass>(new OrderPass()));
else		else
llvm_unreachable("bad pass name");		llvm_unreachable("bad pass name");
}		}
}		}

Writer &CoreLinkingContext::writer() const { return *_writer; }		Writer &CoreLinkingContext::writer() const { return *_writer; }

lib/ReaderWriter/MachO/CMakeLists.txt

	add_llvm_library(lldMachO			add_llvm_library(lldMachO
	ArchHandler.cpp			ArchHandler.cpp
	ArchHandler_arm.cpp			ArchHandler_arm.cpp
	ArchHandler_arm64.cpp			ArchHandler_arm64.cpp
	ArchHandler_x86.cpp			ArchHandler_x86.cpp
	ArchHandler_x86_64.cpp			ArchHandler_x86_64.cpp
	CompactUnwindPass.cpp			CompactUnwindPass.cpp
	GOTPass.cpp			GOTPass.cpp
				LayoutPass.cpp
	MachOLinkingContext.cpp			MachOLinkingContext.cpp
	MachONormalizedFileBinaryReader.cpp			MachONormalizedFileBinaryReader.cpp
	MachONormalizedFileBinaryWriter.cpp			MachONormalizedFileBinaryWriter.cpp
	MachONormalizedFileFromAtoms.cpp			MachONormalizedFileFromAtoms.cpp
	MachONormalizedFileToAtoms.cpp			MachONormalizedFileToAtoms.cpp
	MachONormalizedFileYAML.cpp			MachONormalizedFileYAML.cpp
	ShimPass.cpp			ShimPass.cpp
	StubsPass.cpp			StubsPass.cpp
	Show All 10 Lines

lib/ReaderWriter/MachO/LayoutPass.h

This file was added.

				//===------ 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 <map>
				#include <string>
				#include <vector>

				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<bool (const DefinedAtom left, const DefinedAtom right,
				bool &leftBeforeRight)> SortOverride;

				LayoutPass(const Registry &registry, SortOverride sorter=nullptr);

				/// Sorts atoms in mergedFile by content type then by command line order.
				void perform(std::unique_ptr<MutableFile> &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<const DefinedAtom , const DefinedAtom > AtomToAtomT;
				typedef llvm::DenseMap<const DefinedAtom *, uint64_t> 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<SortKey> decorate(MutableFile::DefinedAtomRange &atomRange) const;
				void undecorate(MutableFile::DefinedAtomRange &atomRange,
				std::vector<SortKey> &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

lib/ReaderWriter/MachO/LayoutPass.cpp

This file was added.

				//===-- 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 <algorithm>
				#include <set>

				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<LayoutPass::SortKey> &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<const DefinedAtom , const DefinedAtom > AtomToAtomT;

				static std::string atomToDebugString(const Atom *atom) {
				const DefinedAtom *definedAtom = dyn_cast<DefinedAtom>(atom);
				std::string str;
				llvm::raw_string_ostream s(str);
				if (definedAtom->name().empty())
				s << "<anonymous " << definedAtom << ">";
				else
				s << definedAtom->name();
				s << " in ";
				if (definedAtom->customSectionName().empty())
				s << "<anonymous>";
				else
				s << definedAtom->customSectionName();
				s.flush();
				return str;
				}

				static void showCycleDetectedError(const Registry &registry,
				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 = "<unknown>";
				}
				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 &registry,
				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<const DefinedAtom *> 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 &registry, 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<DefinedAtom>(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::SortKey>
				LayoutPass::decorate(MutableFile::DefinedAtomRange &atomRange) const {
				std::vector<SortKey> 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<SortKey> &keys) const {
				size_t i = 0;
				for (SortKey &k : keys)
				atomRange[i++] = k._atom;
				}

				/// Perform the actual pass
				void LayoutPass::perform(std::unique_ptr<MutableFile> &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<LayoutPass::SortKey> 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<Pass>(new LayoutPass(
				ctx.registry(), [&](const DefinedAtom * left, const DefinedAtom * right,
				bool & leftBeforeRight)
				->bool {
				return ctx.customAtomOrderer(left, right, leftBeforeRight);
				})));
				}

				} // namespace mach_o
				} // namespace lld

lib/ReaderWriter/MachO/MachOLinkingContext.cpp

Show All 11 Lines
#include "File.h"		#include "File.h"
#include "MachONormalizedFile.h"		#include "MachONormalizedFile.h"
#include "MachOPasses.h"		#include "MachOPasses.h"
#include "lld/Core/ArchiveLibraryFile.h"		#include "lld/Core/ArchiveLibraryFile.h"
#include "lld/Core/PassManager.h"		#include "lld/Core/PassManager.h"
#include "lld/Core/Reader.h"		#include "lld/Core/Reader.h"
#include "lld/Core/Writer.h"		#include "lld/Core/Writer.h"
#include "lld/Driver/Driver.h"		#include "lld/Driver/Driver.h"
#include "lld/Passes/LayoutPass.h"
#include "lld/Passes/RoundTripYAMLPass.h"		#include "lld/Passes/RoundTripYAMLPass.h"
#include "llvm/ADT/StringExtras.h"		#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/Triple.h"		#include "llvm/ADT/Triple.h"
#include "llvm/Config/config.h"		#include "llvm/Config/config.h"
#include "llvm/Support/Debug.h"		#include "llvm/Support/Debug.h"
#include "llvm/Support/Errc.h"		#include "llvm/Support/Errc.h"
#include "llvm/Support/Host.h"		#include "llvm/Support/Host.h"
#include "llvm/Support/MachO.h"		#include "llvm/Support/MachO.h"
▲ Show 20 Lines • Show All 549 Lines • ▼ Show 20 Lines	bool MachOLinkingContext::validateImpl(raw_ostream &diagnostics) {
}		}

addOutputFileDependency(outputPath());		addOutputFileDependency(outputPath());

return true;		return true;
}		}

void MachOLinkingContext::addPasses(PassManager &pm) {		void MachOLinkingContext::addPasses(PassManager &pm) {
pm.add(std::unique_ptr<Pass>(new LayoutPass(		mach_o::addLayoutPass(pm, *this);
registry(), [&](const DefinedAtom * left, const DefinedAtom * right,
bool & leftBeforeRight)
->bool {
return customAtomOrderer(left, right, leftBeforeRight);
})));
if (needsStubsPass())		if (needsStubsPass())
mach_o::addStubsPass(pm, *this);		mach_o::addStubsPass(pm, *this);
if (needsCompactUnwindPass())		if (needsCompactUnwindPass())
mach_o::addCompactUnwindPass(pm, *this);		mach_o::addCompactUnwindPass(pm, *this);
if (needsGOTPass())		if (needsGOTPass())
mach_o::addGOTPass(pm, *this);		mach_o::addGOTPass(pm, *this);
if (needsShimPass())		if (needsShimPass())
mach_o::addShimPass(pm, *this); // Shim pass must run after stubs pass.		mach_o::addShimPass(pm, *this); // Shim pass must run after stubs pass.
▲ Show 20 Lines • Show All 303 Lines • ▼ Show 20 Lines	if (info.fileFilter.equals(objName)) {
return true;		return true;
}		}
}		}
return false;		return false;
}		}

bool MachOLinkingContext::customAtomOrderer(const DefinedAtom *left,		bool MachOLinkingContext::customAtomOrderer(const DefinedAtom *left,
const DefinedAtom *right,		const DefinedAtom *right,
bool &leftBeforeRight) {		bool &leftBeforeRight) const {
// No custom sorting if no order file entries.		// No custom sorting if no order file entries.
if (!_orderFileEntries)		if (!_orderFileEntries)
return false;		return false;

// Order files can only order named atoms.		// Order files can only order named atoms.
StringRef leftName = left->name();		StringRef leftName = left->name();
StringRef rightName = right->name();		StringRef rightName = right->name();
if (leftName.empty() \|\| rightName.empty())		if (leftName.empty() \|\| rightName.empty())
▲ Show 20 Lines • Show All 56 Lines • Show Last 20 Lines

lib/ReaderWriter/MachO/MachOPasses.h

	Show All 10 Lines
	#define LLD_READER_WRITER_MACHO_PASSES_H			#define LLD_READER_WRITER_MACHO_PASSES_H

	#include "lld/Core/PassManager.h"			#include "lld/Core/PassManager.h"
	#include "lld/ReaderWriter/MachOLinkingContext.h"			#include "lld/ReaderWriter/MachOLinkingContext.h"

	namespace lld {			namespace lld {
	namespace mach_o {			namespace mach_o {

				void addLayoutPass(PassManager &pm, const MachOLinkingContext &ctx);
	void addStubsPass(PassManager &pm, const MachOLinkingContext &ctx);			void addStubsPass(PassManager &pm, const MachOLinkingContext &ctx);
	void addGOTPass(PassManager &pm, const MachOLinkingContext &ctx);			void addGOTPass(PassManager &pm, const MachOLinkingContext &ctx);
	void addCompactUnwindPass(PassManager &pm, const MachOLinkingContext &ctx);			void addCompactUnwindPass(PassManager &pm, const MachOLinkingContext &ctx);
	void addShimPass(PassManager &pm, const MachOLinkingContext &ctx);			void addShimPass(PassManager &pm, const MachOLinkingContext &ctx);

	} // namespace mach_o			} // namespace mach_o
	} // namespace lld			} // namespace lld

	#endif // LLD_READER_WRITER_MACHO_PASSES_H			#endif // LLD_READER_WRITER_MACHO_PASSES_H

test/core/layout-transitivity.objtxt

This file was deleted.

	# 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

test/core/layoutafter-test.objtxt

This file was deleted.

	# 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

test/core/section-position.objtxt

This file was deleted.

	# 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: ...

This is an archive of the discontinued LLVM Phabricator instance.

MachO: Move LayoutPass to MachO directory.Needs ReviewPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 19076

include/lld/Passes/LayoutPass.h

include/lld/ReaderWriter/MachOLinkingContext.h

lib/Passes/CMakeLists.txt

lib/Passes/LayoutPass.cpp

lib/ReaderWriter/CoreLinkingContext.cpp

lib/ReaderWriter/MachO/CMakeLists.txt

lib/ReaderWriter/MachO/LayoutPass.h

lib/ReaderWriter/MachO/LayoutPass.cpp

lib/ReaderWriter/MachO/MachOLinkingContext.cpp

lib/ReaderWriter/MachO/MachOPasses.h

test/core/layout-transitivity.objtxt

test/core/layoutafter-test.objtxt

test/core/section-position.objtxt

MachO: Move LayoutPass to MachO directory.
Needs ReviewPublic