Re-commit r223330: Rewrite InputGraph's Group

llvm-svn: 223867

10 files changed, 170 insertions, 133 deletions

diff --git a/lld/lib/Core/InputGraph.cpp b/lld/lib/Core/InputGraph.cpp
index 27cbcbbcedf..cde4127e067 100644
--- a/lld/lib/Core/InputGraph.cpp
+++ b/lld/lib/Core/InputGraph.cpp
@@ -36,8 +36,6 @@ ErrorOr<File &> InputGraph::getNextFile() {
   }
 }
 
-void InputGraph::notifyProgress() { _currentInputElement->notifyProgress(); }
-
 void InputGraph::registerObserver(std::function<void(File *)> fn) {
   _observers.push_back(fn);
 }
@@ -61,12 +59,13 @@ bool InputGraph::dump(raw_ostream &diagnostics) {
 ErrorOr<InputElement *> InputGraph::getNextInputElement() {
   if (_nextElementIndex >= _inputArgs.size())
     return make_error_code(InputGraphError::no_more_elements);
-  return _inputArgs[_nextElementIndex++].get();
+  InputElement *elem = _inputArgs[_nextElementIndex++].get();
+  if (isa<GroupEnd>(elem))
+    return getNextInputElement();
+  return elem;
 }
 
 void InputGraph::normalize() {
-  for (std::unique_ptr<InputElement> &elt : _inputArgs)
-    elt->expand();
   std::vector<std::unique_ptr<InputElement>> vec;
   for (std::unique_ptr<InputElement> &elt : _inputArgs) {
     if (elt->getReplacements(vec))
@@ -76,6 +75,25 @@ void InputGraph::normalize() {
   _inputArgs = std::move(vec);
 }
 
+// If we are at the end of a group, return its size (which indicates
+// how many files we need to go back in the command line).
+// Returns 0 if we are not at the end of a group.
+int InputGraph::getGroupSize() {
+  if (_nextElementIndex >= _inputArgs.size())
+    return 0;
+  InputElement *elem = _inputArgs[_nextElementIndex].get();
+  if (const GroupEnd *group = dyn_cast<GroupEnd>(elem))
+    return group->getSize();
+  return 0;
+}
+
+void InputGraph::skipGroup() {
+  if (_nextElementIndex >= _inputArgs.size())
+    return;
+  if (isa<GroupEnd>(_inputArgs[_nextElementIndex].get()))
+    _nextElementIndex++;
+}
+
 /// \brief Read the file into _buffer.
 std::error_code FileNode::getBuffer(StringRef filePath) {
   // Create a memory buffer
@@ -87,32 +105,10 @@ std::error_code FileNode::getBuffer(StringRef filePath) {
   return std::error_code();
 }
 
-/// \brief Return the next file that need to be processed by the resolver.
-/// This also processes input elements depending on the resolve status
-/// of the input elements contained in the group.
-ErrorOr<File &> Group::getNextFile() {
-  // If there are no elements, move on to the next input element
-  if (_elements.empty())
-    return make_error_code(InputGraphError::no_more_files);
-
-  for (;;) {
-    // If we have processed all the elements, and have made no progress on
-    // linking, we cannot resolve any symbol from this group. Continue to the
-    // next one by returning no_more_files.
-    if (_nextElementIndex == _elements.size()) {
-      if (!_madeProgress)
-        return make_error_code(InputGraphError::no_more_files);
-      resetNextIndex();
-    }
-
-    _currentElementIndex = _nextElementIndex;
-    auto file = _elements[_nextElementIndex]->getNextFile();
-    // Move on to the next element if we have finished processing all
-    // the files in the input element
-    if (file.getError() == InputGraphError::no_more_files) {
-      _nextElementIndex++;
-      continue;
-    }
-    return *file;
-  }
+bool FileNode::getReplacements(InputGraph::InputElementVectorT &result) {
+  if (_files.size() < 2)
+    return false;
+  for (std::unique_ptr<File> &file : _files)
+    result.push_back(llvm::make_unique<SimpleFileNode>(_path, std::move(file)));
+  return true;
 }
diff --git a/lld/lib/Core/Resolver.cpp b/lld/lib/Core/Resolver.cpp
index e4a1b53cc33..c991b8cffa7 100644
--- a/lld/lib/Core/Resolver.cpp
+++ b/lld/lib/Core/Resolver.cpp
@@ -27,7 +27,7 @@
 
 namespace lld {
 
-void Resolver::handleFile(const File &file) {
+bool Resolver::handleFile(const File &file) {
   bool undefAdded = false;
   for (const DefinedAtom *atom : file.defined())
     doDefinedAtom(*atom);
@@ -38,13 +38,7 @@ void Resolver::handleFile(const File &file) {
     doSharedLibraryAtom(*atom);
   for (const AbsoluteAtom *atom : file.absolute())
     doAbsoluteAtom(*atom);
-
-  // Notify the input file manager of the fact that we have made some progress
-  // on linking using the current input file. It may want to know the fact for
-  // --start-group/--end-group.
-  if (undefAdded) {
-    _context.getInputGraph().notifyProgress();
-  }
+  return undefAdded;
 }
 
 void Resolver::forEachUndefines(bool searchForOverrides,
@@ -76,17 +70,19 @@ void Resolver::forEachUndefines(bool searchForOverrides,
   } while (undefineGenCount != _symbolTable.size());
 }
 
-void Resolver::handleArchiveFile(const File &file) {
+bool Resolver::handleArchiveFile(const File &file) {
   const ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file);
   bool searchForOverrides =
       _context.searchArchivesToOverrideTentativeDefinitions();
+  bool undefAdded = false;
   forEachUndefines(searchForOverrides,
                    [&](StringRef undefName, bool dataSymbolOnly) {
     if (const File *member = archiveFile->find(undefName, dataSymbolOnly)) {
       member->setOrdinal(_context.getNextOrdinalAndIncrement());
-      handleFile(*member);
+      undefAdded = handleFile(*member) || undefAdded;
     }
   });
+  return undefAdded;
 }
 
 void Resolver::handleSharedLibrary(const File &file) {
@@ -233,31 +229,66 @@ void Resolver::addAtoms(const std::vector<const DefinedAtom *> &newAtoms) {
     doDefinedAtom(*newAtom);
 }
 
+// Returns true if at least one of N previous files has created an
+// undefined symbol.
+bool Resolver::undefinesAdded(int n) {
+  for (size_t i = _fileIndex - n; i < _fileIndex; ++i)
+    if (_newUndefinesAdded[_files[i]])
+      return true;
+  return false;
+}
+
+ErrorOr<File &> Resolver::nextFile(bool &inGroup) {
+  if (size_t groupSize = _context.getInputGraph().getGroupSize()) {
+    // We are at the end of the current group. If one or more new
+    // undefined atom has been added in the last groupSize files, we
+    // reiterate over the files.
+    if (undefinesAdded(groupSize))
+      _fileIndex -= groupSize;
+    _context.getInputGraph().skipGroup();
+    return nextFile(inGroup);
+  }
+  if (_fileIndex < _files.size()) {
+    // We are still in the current group.
+    inGroup = true;
+    return *_files[_fileIndex++];
+  }
+  // We are not in a group. Get a new file.
+  ErrorOr<File &> file = _context.getInputGraph().getNextFile();
+  if (std::error_code ec = file.getError()) {
+    if (ec != InputGraphError::no_more_files)
+      llvm::errs() << "Error occurred in getNextFile: " << ec.message() << "\n";
+    return ec;
+  }
+  _files.push_back(&*file);
+  ++_fileIndex;
+  inGroup = false;
+  return *file;
+}
+
 // Keep adding atoms until _context.getNextFile() returns an error. This
 // function is where undefined atoms are resolved.
 bool Resolver::resolveUndefines() {
   ScopedTask task(getDefaultDomain(), "resolveUndefines");
 
   for (;;) {
-    ErrorOr<File &> file = _context.getInputGraph().getNextFile();
-    std::error_code ec = file.getError();
-    if (ec == InputGraphError::no_more_files)
-      return true;
-    if (!file) {
-      llvm::errs() << "Error occurred in getNextFile: " << ec.message() << "\n";
-      return false;
-    }
-
+    bool inGroup = false;
+    bool undefAdded = false;
+    ErrorOr<File &> file = nextFile(inGroup);
+    if (std::error_code ec = file.getError())
+      return ec == InputGraphError::no_more_files;
     switch (file->kind()) {
     case File::kindObject:
+      if (inGroup)
+        break;
       assert(!file->hasOrdinal());
       file->setOrdinal(_context.getNextOrdinalAndIncrement());
-      handleFile(*file);
+      undefAdded = handleFile(*file);
       break;
     case File::kindArchiveLibrary:
       if (!file->hasOrdinal())
         file->setOrdinal(_context.getNextOrdinalAndIncrement());
-      handleArchiveFile(*file);
+      undefAdded = handleArchiveFile(*file);
       break;
     case File::kindSharedLibrary:
       if (!file->hasOrdinal())
@@ -265,6 +296,7 @@ bool Resolver::resolveUndefines() {
       handleSharedLibrary(*file);
       break;
     }
+    _newUndefinesAdded[&*file] = undefAdded;
   }
 }
 
diff --git a/lld/lib/Driver/DarwinInputGraph.cpp b/lld/lib/Driver/DarwinInputGraph.cpp
index 29466323b28..5bfa29586aa 100644
--- a/lld/lib/Driver/DarwinInputGraph.cpp
+++ b/lld/lib/Driver/DarwinInputGraph.cpp
@@ -18,48 +18,6 @@
 namespace lld {
 
 
-ErrorOr<File &> DarwinInputGraph::getNextFile() {
-  // The darwin linker processes input files in two phases.  The first phase
-  // links in all object (.o) files in command line order. The second phase
-  // links in libraries in command line order. If there are still UndefinedAtoms
-  // the second phase is repeated until notifyProgress() is not called by
-  // resolver.
-  for (;;) {
-    if (_currentInputElement) {
-      for(;;) {
-        ErrorOr<File &> next = _currentInputElement->getNextFile();
-        if (next.getError())
-          break;
-        File *file = &next.get();
-        bool fileIsLibrary = isa<SharedLibraryFile>(file) ||
-                             isa<ArchiveLibraryFile>(file);
-        if (fileIsLibrary == _librariesPhase) {
-          // Return library in library phase and object files in non-lib mode.
-          return *file;
-        }
-      }
-    }
-
-    if (_nextElementIndex >= _inputArgs.size()) {
-      // If no more elements, done unless we need to repeat library scan.
-      if (_librariesPhase && !_repeatLibraries)
-        return make_error_code(InputGraphError::no_more_files);
-      // Clear iterations and only look for libraries.
-      _librariesPhase = true;
-      _repeatLibraries = false;
-      _nextElementIndex = 0;
-      for (auto &ie : _inputArgs) {
-        ie->resetNextIndex();
-      }
-    }
-    _currentInputElement = _inputArgs[_nextElementIndex++].get();
-  }
-}
-
-void DarwinInputGraph::notifyProgress() {
-  _repeatLibraries = true;
-}
-
 /// \brief Parse the input file to lld::File.
 std::error_code MachOFileNode::parse(const LinkingContext &ctx,
                                      raw_ostream &diagnostics)  {
diff --git a/lld/lib/Driver/DarwinLdDriver.cpp b/lld/lib/Driver/DarwinLdDriver.cpp
index 21cd691a578..6c80c5c8e65 100644
--- a/lld/lib/Driver/DarwinLdDriver.cpp
+++ b/lld/lib/Driver/DarwinLdDriver.cpp
@@ -83,7 +83,7 @@ static std::string canonicalizePath(StringRef path) {
   }
 }
 
-static void addFile(StringRef path, std::unique_ptr<DarwinInputGraph> &inputGraph,
+static void addFile(StringRef path, std::unique_ptr<InputGraph> &inputGraph,
                     MachOLinkingContext &ctx, bool loadWholeArchive,
                     bool upwardDylib) {
   auto node = llvm::make_unique<MachOFileNode>(path, ctx);
@@ -185,7 +185,7 @@ static std::error_code parseOrderFile(StringRef orderFilePath,
 // per line. The <dir> prefix is prepended to each partial path.
 //
 static std::error_code parseFileList(StringRef fileListPath,
-                                     std::unique_ptr<DarwinInputGraph> &inputGraph,
+                                     std::unique_ptr<InputGraph> &inputGraph,
                                      MachOLinkingContext &ctx, bool forceLoad,
                                      raw_ostream &diagnostics) {
   // If there is a comma, split off <dir>.
@@ -521,7 +521,7 @@ bool DarwinLdDriver::parse(int argc, const char *argv[],
     }
   }
 
-  std::unique_ptr<DarwinInputGraph> inputGraph(new DarwinInputGraph());
+  std::unique_ptr<InputGraph> inputGraph(new InputGraph());
 
   // Now construct the set of library search directories, following ld64's
   // baroque set of accumulated hacks. Mostly, the algorithm constructs
diff --git a/lld/lib/Driver/Driver.cpp b/lld/lib/Driver/Driver.cpp
index 148d1003218..b26ab251659 100644
--- a/lld/lib/Driver/Driver.cpp
+++ b/lld/lib/Driver/Driver.cpp
@@ -62,9 +62,6 @@ bool Driver::link(LinkingContext &context, raw_ostream &diagnostics) {
       if (std::error_code ec = ie->parse(context, stream)) {
         if (FileNode *fileNode = dyn_cast<FileNode>(ie.get()))
           stream << fileNode->errStr(ec) << "\n";
-        else if (dyn_cast<Group>(ie.get()))
-          // FIXME: We need a better diagnostics here
-          stream << "Cannot parse group input element\n";
         else
           llvm_unreachable("Unknown type of input element");
         fail = true;
@@ -83,21 +80,24 @@ bool Driver::link(LinkingContext &context, raw_ostream &diagnostics) {
   if (fail)
     return false;
 
-  std::unique_ptr<SimpleFileNode> fileNode(
-      new SimpleFileNode("Internal Files"));
-
   InputGraph::FileVectorT internalFiles;
   context.createInternalFiles(internalFiles);
-
-  if (internalFiles.size())
-    fileNode->addFiles(std::move(internalFiles));
+  for (auto i = internalFiles.rbegin(), e = internalFiles.rend(); i != e; ++i) {
+    context.getInputGraph().addInputElementFront(
+        llvm::make_unique<SimpleFileNode>("internal", std::move(*i)));
+  }
 
   // Give target a chance to add files.
   InputGraph::FileVectorT implicitFiles;
   context.createImplicitFiles(implicitFiles);
-  if (implicitFiles.size())
-    fileNode->addFiles(std::move(implicitFiles));
-  context.getInputGraph().addInputElementFront(std::move(fileNode));
+  for (auto i = implicitFiles.rbegin(), e = implicitFiles.rend(); i != e; ++i) {
+    context.getInputGraph().addInputElementFront(
+        llvm::make_unique<SimpleFileNode>("implicit", std::move(*i)));
+  }
+
+  // Give target a chance to sort the input files.
+  // Mach-O uses this chance to move all object files before library files.
+  context.maybeSortInputFiles();
 
   // Do core linking.
   ScopedTask resolveTask(getDefaultDomain(), "Resolve");
diff --git a/lld/lib/Driver/GnuLdDriver.cpp b/lld/lib/Driver/GnuLdDriver.cpp
index c309e652082..aab08741d38 100644
--- a/lld/lib/Driver/GnuLdDriver.cpp
+++ b/lld/lib/Driver/GnuLdDriver.cpp
@@ -295,7 +295,8 @@ bool GnuLdDriver::parse(int argc, const char *argv[],
   }
 
   std::unique_ptr<InputGraph> inputGraph(new InputGraph());
-  std::stack<Group *> groupStack;
+  std::stack<int> groupStack;
+  int numfiles = 0;
 
   ELFFileNode::Attributes attributes;
 
@@ -468,16 +469,21 @@ bool GnuLdDriver::parse(int argc, const char *argv[],
       break;
     }
 
-    case OPT_start_group: {
-      std::unique_ptr<Group> group(new Group());
-      groupStack.push(group.get());
-      inputGraph->addInputElement(std::move(group));
+    case OPT_start_group:
+      groupStack.push(numfiles);
       break;
-    }
 
-    case OPT_end_group:
+    case OPT_end_group: {
+      if (groupStack.empty()) {
+        diagnostics << "stray --end-group\n";
+        return false;
+      }
+      int startGroupPos = groupStack.top();
+      inputGraph->addInputElement(
+          llvm::make_unique<GroupEnd>(numfiles - startGroupPos));
       groupStack.pop();
       break;
+    }
 
     case OPT_z: {
       StringRef extOpt = inputArg->getValue();
@@ -552,11 +558,8 @@ bool GnuLdDriver::parse(int argc, const char *argv[],
         }
       }
       std::unique_ptr<InputElement> inputFile(inputNode);
-      if (groupStack.empty()) {
-        inputGraph->addInputElement(std::move(inputFile));
-      } else {
-        groupStack.top()->addFile(std::move(inputFile));
-      }
+      ++numfiles;
+      inputGraph->addInputElement(std::move(inputFile));
       break;
     }
 
diff --git a/lld/lib/Driver/GnuLdInputGraph.cpp b/lld/lib/Driver/GnuLdInputGraph.cpp
index 6fd1ebd08e8..f1a09220b5c 100644
--- a/lld/lib/Driver/GnuLdInputGraph.cpp
+++ b/lld/lib/Driver/GnuLdInputGraph.cpp
@@ -91,7 +91,7 @@ std::error_code ELFGNULdScript::parse(const LinkingContext &ctx,
     auto *group = dyn_cast<script::Group>(c);
     if (!group)
       continue;
-    std::unique_ptr<Group> groupStart(new Group());
+    size_t numfiles = 0;
     for (const script::Path &path : group->getPaths()) {
       // TODO : Propagate Set WholeArchive/dashlPrefix
       attributes.setAsNeeded(path._asNeeded);
@@ -100,9 +100,10 @@ std::error_code ELFGNULdScript::parse(const LinkingContext &ctx,
           _elfLinkingContext, _elfLinkingContext.allocateString(path._path),
           attributes);
       std::unique_ptr<InputElement> inputFile(inputNode);
-      groupStart.get()->addFile(std::move(inputFile));
+      _expandElements.push_back(std::move(inputFile));
+      ++numfiles;
     }
-    _expandElements.push_back(std::move(groupStart));
+    _expandElements.push_back(llvm::make_unique<GroupEnd>(numfiles));
   }
   return std::error_code();
 }
diff --git a/lld/lib/Driver/WinLinkDriver.cpp b/lld/lib/Driver/WinLinkDriver.cpp
index dc6cc79a9dc..2d98c9fe205 100644
--- a/lld/lib/Driver/WinLinkDriver.cpp
+++ b/lld/lib/Driver/WinLinkDriver.cpp
@@ -781,7 +781,7 @@ static bool hasLibrary(const PECOFFLinkingContext &ctx, FileNode *fileNode) {
   ErrorOr<StringRef> path = fileNode->getPath(ctx);
   if (!path)
     return false;
-  for (std::unique_ptr<InputElement> &p : ctx.getLibraryGroup()->elements())
+  for (std::unique_ptr<InputElement> &p : ctx.getInputGraph().inputElements())
     if (auto *f = dyn_cast<FileNode>(p.get()))
       if (*path == *f->getPath(ctx))
         return true;
@@ -1397,10 +1397,8 @@ bool WinLinkDriver::parse(int argc, const char *argv[],
     ctx.setEntryNode(entry.get());
     ctx.getInputGraph().addInputElement(std::move(entry));
 
-    // The container for all library files.
-    std::unique_ptr<Group> group(new PECOFFGroup(ctx));
-    ctx.setLibraryGroup(group.get());
-    ctx.getInputGraph().addInputElement(std::move(group));
+    // Add a group-end marker.
+    ctx.getInputGraph().addInputElement(llvm::make_unique<GroupEnd>(0));
   }
 
   // Add the library files to the library group.
@@ -1409,7 +1407,7 @@ bool WinLinkDriver::parse(int argc, const char *argv[],
       if (isReadingDirectiveSection)
         if (lib->parse(ctx, diag))
           return false;
-      ctx.getLibraryGroup()->addFile(std::move(lib));
+      ctx.addLibraryFile(std::move(lib));
     }
   }
 
diff --git a/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp b/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
index 3e91e4a56b3..b129c033740 100644
--- a/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
@@ -22,6 +22,7 @@
 #include "llvm/ADT/Triple.h"
 #include "llvm/Config/config.h"
 #include "llvm/Support/Errc.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/MachO.h"
 #include "llvm/Support/Path.h"
@@ -923,4 +924,35 @@ bool MachOLinkingContext::customAtomOrderer(const DefinedAtom *left,
   return true;
 }
 
+static File *getFirstFile(const std::unique_ptr<InputElement> &elem) {
+  FileNode *e = dyn_cast<FileNode>(const_cast<InputElement *>(elem.get()));
+  if (!e || e->files().empty())
+    return nullptr;
+  return e->files()[0].get();
+}
+
+static bool isLibrary(const std::unique_ptr<InputElement> &elem) {
+  File *f = getFirstFile(elem);
+  return f && (isa<SharedLibraryFile>(f) || isa<ArchiveLibraryFile>(f));
+}
+
+// The darwin linker processes input files in two phases.  The first phase
+// links in all object (.o) files in command line order. The second phase
+// links in libraries in command line order.
+// In this function we reorder the input files so that all the object files
+// comes before any library file. We also make a group for the library files
+// so that the Resolver will reiterate over the libraries as long as we find
+// new undefines from libraries.
+void MachOLinkingContext::maybeSortInputFiles() {
+  std::vector<std::unique_ptr<InputElement>> &elements
+      = getInputGraph().inputElements();
+  std::stable_sort(elements.begin(), elements.end(),
+                   [](const std::unique_ptr<InputElement> &a,
+                      const std::unique_ptr<InputElement> &b) {
+                     return !isLibrary(a) && isLibrary(b);
+                   });
+  size_t numLibs = std::count_if(elements.begin(), elements.end(), isLibrary);
+  elements.push_back(llvm::make_unique<GroupEnd>(numLibs));
+}
+
 } // end namespace lld
diff --git a/lld/lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp b/lld/lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp
index ae236f475ba..7dc64d3fd5e 100644
--- a/lld/lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp
+++ b/lld/lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp
@@ -87,6 +87,23 @@ std::unique_ptr<File> PECOFFLinkingContext::createUndefinedSymbolFile() const {
       "<command line option /include>");
 }
 
+void PECOFFLinkingContext::addLibraryFile(std::unique_ptr<FileNode> file) {
+  GroupEnd *currentGroupEnd;
+  int pos = -1;
+  std::vector<std::unique_ptr<InputElement>> &elements
+      = getInputGraph().inputElements();
+  for (int i = 0, e = elements.size(); i < e; ++i) {
+    if ((currentGroupEnd = dyn_cast<GroupEnd>(elements[i].get()))) {
+      pos = i;
+      break;
+    }
+  }
+  assert(pos >= 0);
+  elements.insert(elements.begin() + pos, std::move(file));
+  elements[pos + 1] = llvm::make_unique<GroupEnd>(
+      currentGroupEnd->getSize() + 1);
+}
+
 bool PECOFFLinkingContext::createImplicitFiles(
     std::vector<std::unique_ptr<File>> &) {
   // Create a file for __ImageBase.
@@ -109,7 +126,7 @@ bool PECOFFLinkingContext::createImplicitFiles(
   auto exportNode = llvm::make_unique<SimpleFileNode>("<export>");
   exportNode->appendInputFile(
       llvm::make_unique<pecoff::ExportedSymbolRenameFile>(*this, syms));
-  getLibraryGroup()->addFile(std::move(exportNode));
+  addLibraryFile(std::move(exportNode));
 
   // Create a file for the entry point function.
   getEntryNode()->appendInputFile(