[MachO] Implement -order_file as a separate ordering pass.

[ruiu]

Summary

On Mac OS you can pass a text file as an argument for -order_file
command line option. That file contains a list of symbols, and the
linker sorts these symbols in the same order as in the order file.

That custom ordering was implemented by adding a "custom" comparator
function to the LayoutPass. That made the comparator function in the
LayoutPass, which does too much stuff already, more complex.

I'm trying to make the pass simpler and faster. I found that if we
implement the feature as a separate pass, it becomes easy to understand.

In this patch, I added a new pass, OrderPass, which sorts atoms
according to the order file. Because it uses stable sort, it preserves
symbol order if they are not mentioned in the order file. We already
took similar approach in PE/COFF (PECOFF/GroupSectionPass.h).

This patch has no change in functionality.

[kledzik]

There maybe lots of other parts of this LayoutPass that mach-o needs but ELF does not. Why not just prune away at this until you get pass that is fast enough for ELF. Then split this in to two passes. One for mach-o and one for ELF, and let the drivers choose the pass to use.

[ruiu]

My understanding is that in all architectures we basically want to sort atoms in the same order as they are ordered in the command line (file order and then in-file order). I looked at the history of the LayoutPass and found that the pass actually did that before. I think we want to restore that behavior, and apply that pass for all archs.

Each arch then optionally run a pass to (stable-) sort atoms after the LayoutPass to tweak the sort result.

I think this separation should work for all architectures and I think this separation is clean and nice.

[kledzik]

Sure two passes is conceptually clean, but if it turns out that running sort() twice for mach-o makes linking slower for mach-o than it currently is, then that is not ideal.

The other way would be to have one layout pass that uses a base class for the comparator which the ELF layout pass uses as-is, but there is a (non virtual) way for mach-o to supply a more complex comparator (today's comparator).

[ruiu]

I feel that discussing performance on the two-pass solution at this point
could lead to a premature optimization> Maybe we should run a benchmark to
see if it's going to be a real issue. Second sort can be faster than first
sort because second sort sorts a mostly-sorted array. But sure, sort is
O(log n). Run that stuff twice is not optimal. We may want to avoid that if
possible.

I carefully read the code for ELF and found that the functionality that the
LayoutPass provides is overkill for that architecture. We don't need that
amount of code.

Currently the LayoutPass is applied unconditionally to all architectures.
Maybe we should stop doing that and let each arch to define its own layout
pass. The current LayoutPass can be simplified to <10 lines of code, so it
wouldn't worth abstracting.

[kledzik]

Leaving this pass as-is and adding a new simple pass that ELF (and maybe COFF) uses instead is fine with me.

[ruiu]

If you want that way, that works for me too. But could you elaborate a bit on which part of the the LayoutPass Mach-O needs? I don't expect Mach-O needs all features that the pass provides.

[kledzik]

All those comparisons in compareAtomSub() are part of the system linker on darwin. See:

http://www.opensource.apple.com/source/ld64/ld64-123.2.1/src/ld/passes/order_file.cpp

[ruiu]

I see. Thanks for the pointer! I now understood that that ordering is needed.

From that file, it looks to me that it doesn't need "sort by lc._override an rc._override if both rhs and lhs are in the same layout-after chain" feature. The file actually consists of the code to prepare for that comparison.

[shankarke]

This needs to be part of LayoutPass, as its something that I wanted to add to the Gnu flavor too.

[ruiu]

Why? If you think we need a feature, please at least briefly explain why we
need that, too.

[shankarke]

Several of our customers want this functionality of ordering functions/data(without linker scripts) to just take an order file and order them appropriately.

[ruiu]

Currently there's no way to specify symbol orders. If someone wants to
reorder symbols in a special manner, one needs to use LLD as a library and
write a custom pass to enforce some specific ordering. That means they can
reorder symbols in their pass, rather than doing tricky things with layout
references and let the LayoutPass to sort them. The LayoutPass is
overdesigned and hard to use. Let's not depend on that too much.

include/lld/Passes/LayoutPass.h

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);
+  LayoutPass(const Registry &registry);
 
   /// 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 the followOn atoms chain as specified by the kindInGroup
   // reference type
   void buildInGroupTable(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

include/lld/ReaderWriter/MachOLinkingContext.h

enum class ExportMode {
     blackList   // -unexported_symbol[s_list], no listed symbol exported.
   };
 
   enum class DebugInfoMode {
     addDebugMap,    // Default
     noDebugMap      // -S option
   };
 
+  struct OrderFileNode {
+    StringRef fileFilter;
+    unsigned  order;
+  };
+
   /// Initializes the context to sane default values given the specified output
   /// file type, arch, os, and minimum os version.  This should be called before
   /// other setXXX() methods.
   void configure(HeaderFileType type, Arch arch, OS os, uint32_t minOSVersion);
 
   void addPasses(PassManager &pm) override;
   bool validateImpl(raw_ostream &diagnostics) override;
   std::string demangle(StringRef symbolName) const override;
public:
   bool needsShimPass() const;
 
   /// Magic symbol name stubs will need to help lazy bind.
   StringRef binderSymbolName() const;
 
   /// Used to keep track of direct and indirect dylibs.
   void registerDylib(mach_o::MachODylibFile *dylib, bool upward) const;
 
+  const llvm::StringMap<std::vector<OrderFileNode>> &getOrderFiles() const {
+    return _orderFiles;
+  }
+
   // Reads a file from disk to memory. Returns only a needed chunk
   // if a fat binary.
   ErrorOr<std::unique_ptr<MemoryBuffer>> getMemoryBuffer(StringRef path);
 
   /// Used to find indirect dylibs. Instantiates a MachODylibFile if one
   /// has not already been made for the requested dylib.  Uses -L and -F
   /// search paths to allow indirect dylibs to be overridden.
   mach_o::MachODylibFile* findIndirectDylib(StringRef path);
private:
   };
 
   struct SectionAlign {
     StringRef segmentName;
     StringRef sectionName;
     uint8_t   align2;
   };
 
-  struct OrderFileNode {
-    StringRef fileFilter;
-    unsigned  order;
-  };
-
-  static bool findOrderOrdinal(const std::vector<OrderFileNode> &nodes,
-                             const DefinedAtom *atom, unsigned &ordinal);
-
   static ArchInfo _s_archInfos[];
 
   std::set<StringRef> _existingPaths; // For testing only.
   StringRefVector _searchDirs;
   StringRefVector _syslibRoots;
   StringRefVector _frameworkDirs;
   HeaderFileType _outputMachOType;   // e.g MH_EXECUTE
   bool _outputMachOTypeStatic; // Disambiguate static vs dynamic prog

lib/Passes/LayoutPass.cpp

 #include <algorithm>
 #include <set>
 
 using namespace lld;
 
 #define DEBUG_TYPE "LayoutPass"
 
 static bool compareAtoms(const LayoutPass::SortKey &,
-                         const LayoutPass::SortKey &,
-                         LayoutPass::SortOverride customSorter=nullptr);
+                         const LayoutPass::SortKey &);
 
 #ifndef NDEBUG
 // Return "reason (leftval, rightval)"
 static std::string formatReason(StringRef reason, int leftVal, int rightVal) {
   return (Twine(reason) + " (" + Twine(leftVal) + ", " + Twine(rightVal) + ")")
       .str();
 }
 

 }
 #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;
   }
 
static bool compareAtomsSub(const LayoutPass::SortKey &lc,
   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();
static bool compareAtomsSub(const LayoutPass::SortKey &lc,
   }
 
   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) {
+                         const LayoutPass::SortKey &rc) {
   std::string reason;
-  bool result = compareAtomsSub(lc, rc, customSorter, reason);
+  bool result = compareAtomsSub(lc, rc, 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) {}
+LayoutPass::LayoutPass(const Registry &registry) : _registry(registry) {}
 
 // 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];
void LayoutPass::perform(std::unique_ptr<MutableFile> &mergedFile) {
   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);
-      });
+  parallel_sort(vec.begin(), vec.end(), compareAtoms);
   DEBUG(checkTransitivity(vec));
   undecorate(atomRange, vec);
 
   DEBUG({
     llvm::dbgs() << "sorted atoms:\n";
     printDefinedAtoms(atomRange);
   });
 }

lib/ReaderWriter/MachO/CMakeLists.txt

 add_llvm_library(lldMachO
   ArchHandler.cpp
   ArchHandler_arm.cpp
   ArchHandler_arm64.cpp
   ArchHandler_x86.cpp
   ArchHandler_x86_64.cpp
   CompactUnwindPass.cpp
   GOTPass.cpp
   MachOLinkingContext.cpp
   MachONormalizedFileBinaryReader.cpp
   MachONormalizedFileBinaryWriter.cpp
   MachONormalizedFileFromAtoms.cpp
   MachONormalizedFileToAtoms.cpp
   MachONormalizedFileYAML.cpp
+  OrderPass.cpp
   ShimPass.cpp
   StubsPass.cpp
   WriterMachO.cpp
   LINK_LIBS
     lldCore
     lldPasses
     lldYAML
     LLVMObject
     LLVMSupport
   )
 
 include_directories(.)

lib/ReaderWriter/MachO/MachOLinkingContext.cpp

bool MachOLinkingContext::validateImpl(raw_ostream &diagnostics) {
   }
 
   addOutputFileDependency(outputPath());
 
   return true;
 }
 
 void MachOLinkingContext::addPasses(PassManager &pm) {
-  pm.add(std::unique_ptr<Pass>(new LayoutPass(
-      registry(), [&](const DefinedAtom * left, const DefinedAtom * right,
-                      bool & leftBeforeRight)
-                      ->bool {
-    return customAtomOrderer(left, right, leftBeforeRight);
-  })));
+  pm.add(std::unique_ptr<Pass>(new LayoutPass(registry())));
+  mach_o::addOrderPass(pm, *this);
   if (needsStubsPass())
     mach_o::addStubsPass(pm, *this);
   if (needsCompactUnwindPass())
     mach_o::addCompactUnwindPass(pm, *this);
   if (needsGOTPass())
     mach_o::addGOTPass(pm, *this);
   if (needsShimPass())
     mach_o::addShimPass(pm, *this); // Shim pass must run after stubs pass.
void MachOLinkingContext::appendOrderedSymbol(StringRef symbol,
   // of OrderFileNode each of which can specify a file prefix.
   OrderFileNode info;
   if (!filename.empty())
     info.fileFilter = copy(filename);
   info.order = _orderFileEntries++;
   _orderFiles[symbol].push_back(info);
 }
 
-bool
-MachOLinkingContext::findOrderOrdinal(const std::vector<OrderFileNode> &nodes,
-                                      const DefinedAtom *atom,
-                                      unsigned &ordinal) {
-  const File *objFile = &atom->file();
-  assert(objFile);
-  StringRef objName = objFile->path();
-  std::pair<StringRef, StringRef> dirAndLeaf = objName.rsplit('/');
-  if (!dirAndLeaf.second.empty())
-    objName = dirAndLeaf.second;
-  for (const OrderFileNode &info : nodes) {
-    if (info.fileFilter.empty()) {
-      // Have unprefixed symbol name in order file that matches this atom.
-      ordinal = info.order;
-      return true;
-    }
-    if (info.fileFilter.equals(objName)) {
-      // Have prefixed symbol name in order file that matches atom's path.
-      ordinal = info.order;
-      return true;
-    }
-  }
-  return false;
-}
-
-bool MachOLinkingContext::customAtomOrderer(const DefinedAtom *left,
-                                            const DefinedAtom *right,
-                                            bool &leftBeforeRight) {
-  // No custom sorting if no order file entries.
-  if (!_orderFileEntries)
-    return false;
-
-  // Order files can only order named atoms.
-  StringRef leftName = left->name();
-  StringRef rightName = right->name();
-  if (leftName.empty() || rightName.empty())
-    return false;
-
-  // If neither is in order file list, no custom sorter.
-  auto leftPos = _orderFiles.find(leftName);
-  auto rightPos = _orderFiles.find(rightName);
-  bool leftIsOrdered = (leftPos != _orderFiles.end());
-  bool rightIsOrdered = (rightPos != _orderFiles.end());
-  if (!leftIsOrdered && !rightIsOrdered)
-    return false;
-
-  // There could be multiple symbols with same name but different file prefixes.
-  unsigned leftOrder;
-  unsigned rightOrder;
-  bool foundLeft =
-      leftIsOrdered && findOrderOrdinal(leftPos->getValue(), left, leftOrder);
-  bool foundRight = rightIsOrdered &&
-                    findOrderOrdinal(rightPos->getValue(), right, rightOrder);
-  if (!foundLeft && !foundRight)
-    return false;
-
-  // If only one is in order file list, ordered one goes first.
-  if (foundLeft != foundRight)
-    leftBeforeRight = foundLeft;
-  else
-    leftBeforeRight = (leftOrder < rightOrder);
-
-  return true;
-}
-
 static bool isLibrary(const std::unique_ptr<Node> &elem) {
   if (FileNode *node = dyn_cast<FileNode>(const_cast<Node *>(elem.get()))) {
     File *file = node->getFile();
     return isa<SharedLibraryFile>(file) || isa<ArchiveLibraryFile>(file);
   }
   return false;
 }
 

lib/ReaderWriter/MachO/MachOPasses.h

 #define LLD_READER_WRITER_MACHO_PASSES_H
 
 #include "lld/Core/PassManager.h"
 #include "lld/ReaderWriter/MachOLinkingContext.h"
 
 namespace lld {
 namespace mach_o {
 
+void addOrderPass(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);
 void addShimPass(PassManager &pm, const MachOLinkingContext &ctx);
 
 } // namespace mach_o
 } // namespace lld
 
 #endif // LLD_READER_WRITER_MACHO_PASSES_H

lib/ReaderWriter/MachO/OrderPass.cpp

+//===- lib/ReaderWriter/MachO/OrderPass.cpp ------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// This is a pass to reorder atoms as specified by the custom order file
+/// given with -order_file.
+///
+//===----------------------------------------------------------------------===//
+
+#include "MachOPasses.h"
+#include "lld/Core/File.h"
+#include "lld/Core/Pass.h"
+#include "lld/ReaderWriter/MachOLinkingContext.h"
+#include <algorithm>
+#include <map>
+
+namespace lld {
+namespace mach_o {
+
+typedef MachOLinkingContext::OrderFileNode OrderFileNode;
+typedef llvm::StringMap<std::vector<OrderFileNode>> OrderFiles;
+
+static bool findOrderOrdinal(const std::vector<OrderFileNode> &nodes,
+                             const DefinedAtom *atom,
+                             unsigned &ordinal) {
+  const File *objFile = &atom->file();
+  assert(objFile);
+  StringRef objName = objFile->path();
+  std::pair<StringRef, StringRef> dirAndLeaf = objName.rsplit('/');
+  if (!dirAndLeaf.second.empty())
+    objName = dirAndLeaf.second;
+  for (const OrderFileNode &info : nodes) {
+    if (info.fileFilter.empty()) {
+      // Have unprefixed symbol name in order file that matches this atom.
+      ordinal = info.order;
+      return true;
+    }
+    if (info.fileFilter.equals(objName)) {
+      // Have prefixed symbol name in order file that matches atom's path.
+      ordinal = info.order;
+      return true;
+    }
+  }
+  return false;
+}
+
+static bool compare(const OrderFiles &orderFiles, const DefinedAtom *lhs,
+                    const DefinedAtom *rhs) {
+  // Order files can only order named atoms.
+  StringRef lhsName = lhs->name();
+  StringRef rhsName = rhs->name();
+  if (lhsName.empty() || rhsName.empty())
+    return false;
+
+  // If neither is in order file list, no custom sorter.
+  auto lhsPos = orderFiles.find(lhsName);
+  auto rhsPos = orderFiles.find(rhsName);
+  bool lhsIsOrdered = (lhsPos != orderFiles.end());
+  bool rhsIsOrdered = (rhsPos != orderFiles.end());
+  if (!lhsIsOrdered && !rhsIsOrdered)
+    return false;
+
+  // There could be multiple symbols with same name but different file prefixes.
+  unsigned lhsOrder;
+  unsigned rhsOrder;
+  bool foundLhs =
+      lhsIsOrdered && findOrderOrdinal(lhsPos->getValue(), lhs, lhsOrder);
+  bool foundRhs =
+      rhsIsOrdered && findOrderOrdinal(rhsPos->getValue(), rhs, rhsOrder);
+  if (!foundLhs && !foundRhs)
+    return false;
+
+  // If only one is in order file list, ordered one goes first.
+  if (foundLhs != foundRhs)
+    return foundLhs;
+  return lhsOrder < rhsOrder;
+}
+
+class OrderPass : public lld::Pass {
+public:
+  OrderPass(const MachOLinkingContext &ctx) : _ctx(ctx) {}
+
+  void perform(std::unique_ptr<MutableFile> &file) override {
+    const OrderFiles &orderFiles = _ctx.getOrderFiles();
+
+    // No custom sorting if no order file entries.
+    if (orderFiles.begin() == orderFiles.end())
+      return;
+
+    MutableFile::DefinedAtomRange defined = file->definedAtoms();
+    std::stable_sort(defined.begin(), defined.end(),
+                     [&](const DefinedAtom *lhs, const DefinedAtom *rhs) {
+                       return compare(orderFiles, lhs, rhs);
+                     });
+  }
+
+private:
+  const MachOLinkingContext &_ctx;
+};
+
+void addOrderPass(PassManager &pm, const MachOLinkingContext &ctx) {
+  pm.add(std::unique_ptr<Pass>(new OrderPass(ctx)));
+}
+
+} // namespace mach_o
+} // namespace lld