PECOFF: Do not use LayoutPass and instead use simpler one.

The LayoutPass is one of the slowest pass. This change is to skip
that pass. This change not only improve performance but also improve
maintainability of the code because the LayoutPass is pretty complex.

Previously we used the LayoutPass to sort all atoms in a specific way,
and reorder them again for PE/COFF in GroupedSectionPass.

I spent time on improving and fixing bugs in the LayoutPass (e.g.
r193029), but the pass is still hard to understand and hard to use.
It's better not to depend on that if we don't need. For PE/COFF, we
just wanted to sort atoms in the same order as the file order in the
command line.

The feature we used in the LayoutPass is now simplified to
compareByPosition function in OrderPass.cpp. The function is just 5
lines.

This patch changes the order of final output because it changes the
sort order a bit. The output is still correct, though.

llvm-svn: 227500

2 files changed, 30 insertions, 15 deletions

diff --git a/lld/lib/ReaderWriter/PECOFF/GroupedSectionsPass.h b/lld/lib/ReaderWriter/PECOFF/OrderPass.h
index ab902eff9ea..8f8b4082421 100644
--- a/lld/lib/ReaderWriter/PECOFF/GroupedSectionsPass.h
+++ b/lld/lib/ReaderWriter/PECOFF/OrderPass.h
@@ -1,4 +1,4 @@
-//===- lib/ReaderWriter/PECOFF/GroupedSectionsPass.h ----------------------===//
+//===- lib/ReaderWriter/PECOFF/OrderPass.h -------------------------------===//
 //
 //                             The LLVM Linker
 //
@@ -26,30 +26,46 @@
 ///
 //===----------------------------------------------------------------------===//
 
-#ifndef LLD_READER_WRITER_PE_COFF_GROUPED_SECTIONS_PASS_H
-#define LLD_READER_WRITER_PE_COFF_GROUPED_SECTIONS_PASS_H
+#ifndef LLD_READER_WRITER_PE_COFF_ORDER_PASS_H
+#define LLD_READER_WRITER_PE_COFF_ORDER_PASS_H
 
 #include "Atoms.h"
+#include "lld/Core/Parallel.h"
 #include "lld/Core/Pass.h"
 #include <algorithm>
 
 namespace lld {
 namespace pecoff {
 
-static bool compare(const DefinedAtom *left, const DefinedAtom *right) {
-  if (left->sectionChoice() == DefinedAtom::sectionCustomRequired &&
-      right->sectionChoice() == DefinedAtom::sectionCustomRequired) {
-    return left->customSectionName().compare(right->customSectionName()) < 0;
+static bool compareByPosition(const DefinedAtom *lhs, const DefinedAtom *rhs) {
+  const File *lhsFile = &lhs->file();
+  const File *rhsFile = &rhs->file();
+  if (lhsFile->ordinal() != rhsFile->ordinal())
+    return lhsFile->ordinal() < rhsFile->ordinal();
+  return lhs->ordinal() < rhs->ordinal();
+}
+
+static bool compare(const DefinedAtom *lhs, const DefinedAtom *rhs) {
+  bool lhsCustom = (lhs->sectionChoice() == DefinedAtom::sectionCustomRequired);
+  bool rhsCustom = (rhs->sectionChoice() == DefinedAtom::sectionCustomRequired);
+  if (lhsCustom && rhsCustom) {
+    int cmp = lhs->customSectionName().compare(rhs->customSectionName());
+    if (cmp != 0)
+      return cmp < 0;
+    return compareByPosition(lhs, rhs);
   }
-  return left->sectionChoice() == DefinedAtom::sectionCustomRequired &&
-         right->sectionChoice() != DefinedAtom::sectionCustomRequired;
+  if (lhsCustom && !rhsCustom)
+    return true;
+  if (!lhsCustom && rhsCustom)
+    return false;
+  return compareByPosition(lhs, rhs);
 }
 
-class GroupedSectionsPass : public lld::Pass {
+class OrderPass : public lld::Pass {
 public:
   void perform(std::unique_ptr<MutableFile> &file) override {
-    auto definedAtoms = file->definedAtoms();
-    std::stable_sort(definedAtoms.begin(), definedAtoms.end(), compare);
+    MutableFile::DefinedAtomRange defined = file->definedAtoms();
+    parallel_sort(defined.begin(), defined.end(), compare);
   }
 };
 
diff --git a/lld/lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp b/lld/lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp
index b1159697894..a139e958774 100644
--- a/lld/lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp
+++ b/lld/lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp
@@ -9,11 +9,11 @@
 
 #include "Atoms.h"
 #include "EdataPass.h"
-#include "GroupedSectionsPass.h"
 #include "IdataPass.h"
 #include "InferSubsystemPass.h"
 #include "LinkerGeneratedSymbolFile.h"
 #include "LoadConfigPass.h"
+#include "OrderPass.h"
 #include "PDBPass.h"
 #include "lld/Core/PassManager.h"
 #include "lld/Core/Reader.h"
@@ -351,9 +351,8 @@ void PECOFFLinkingContext::addPasses(PassManager &pm) {
   pm.add(std::unique_ptr<Pass>(new pecoff::PDBPass(*this)));
   pm.add(std::unique_ptr<Pass>(new pecoff::EdataPass(*this)));
   pm.add(std::unique_ptr<Pass>(new pecoff::IdataPass(*this)));
-  pm.add(std::unique_ptr<Pass>(new LayoutPass(registry())));
+  pm.add(std::unique_ptr<Pass>(new pecoff::OrderPass()));
   pm.add(std::unique_ptr<Pass>(new pecoff::LoadConfigPass(*this)));
-  pm.add(std::unique_ptr<Pass>(new pecoff::GroupedSectionsPass()));
   pm.add(std::unique_ptr<Pass>(new pecoff::InferSubsystemPass(*this)));
 }