Subclass InputGraph to get darwin linker library semantics

The darwin linker operates differently than the gnu linker with respect to
libraries. The darwin linker first links in all object files from the command
line, then to resolve any remaining undefines, it repeatedly iterates over
libraries on the command line until either all undefines are resolved or no
undefines were resolved in the last pass.

When Shankar made the InputGraph model, the plan for darwin was for the darwin
driver to place all libraries in a group at the end of the InputGraph. Thus
making the darwin model a subset of the gnu model. But it turns out that does
not work because the driver cannot tell if a file is an object or library until
it has been loaded, which happens later.

This solution is to subclass InputGraph for darwin and just iterate the graph
the way darwin linker needs.

llvm-svn: 220330

9 files changed, 157 insertions, 8 deletions

diff --git a/lld/include/lld/Core/InputGraph.h b/lld/include/lld/Core/InputGraph.h
index d662c14be61..ef408f07b6f 100644
--- a/lld/include/lld/Core/InputGraph.h
+++ b/lld/include/lld/Core/InputGraph.h
@@ -50,19 +50,20 @@ public:
 
   /// \brief Initialize the inputgraph
   InputGraph() : _nextElementIndex(0), _currentInputElement(nullptr) {}
+  virtual ~InputGraph();
 
   /// getNextFile returns the next file that needs to be processed by
   /// the resolver. When there are no more files to be processed, an
   /// appropriate InputGraphError is returned. Ordinals are assigned
   /// to files returned by getNextFile, which means ordinals would be
   /// assigned in the way files are resolved.
-  ErrorOr<File &> getNextFile();
+  virtual ErrorOr<File &> getNextFile();
 
   /// Notifies the current input element of Resolver made some progress on
   /// resolving undefined symbols using the current file. Group (representing
   /// --start-group and --end-group) uses that notification to make a decision
   /// whether it should iterate over again or terminate or not.
-  void notifyProgress();
+  virtual void notifyProgress();
 
   /// Adds an observer of getNextFile(). Each time a new file is about to be
   /// returned from getNextFile(), registered observers are called with the file
diff --git a/lld/include/lld/Driver/DarwinInputGraph.h b/lld/include/lld/Driver/DarwinInputGraph.h
index fb7ba565b8d..27289c16306 100644
--- a/lld/include/lld/Driver/DarwinInputGraph.h
+++ b/lld/include/lld/Driver/DarwinInputGraph.h
@@ -22,6 +22,18 @@
 
 namespace lld {
 
+
+class DarwinInputGraph : public InputGraph {
+public:
+  DarwinInputGraph() : _librariesPhase(false), _repeatLibraries(false) { }
+  ErrorOr<File &> getNextFile() override;
+  void notifyProgress() override;
+private:
+  bool _librariesPhase;
+  bool _repeatLibraries;
+};
+
+
 /// \brief Represents a MachO File
 class MachOFileNode : public FileNode {
 public:
diff --git a/lld/lib/Core/InputGraph.cpp b/lld/lib/Core/InputGraph.cpp
index f4f5e5a6782..27cbcbbcedf 100644
--- a/lld/lib/Core/InputGraph.cpp
+++ b/lld/lib/Core/InputGraph.cpp
@@ -13,6 +13,8 @@
 
 using namespace lld;
 
+InputGraph::~InputGraph() { }
+
 ErrorOr<File &> InputGraph::getNextFile() {
   // Try to get the next file of _currentInputElement. If the current input
   // element points to an archive file, and there's a file left in the archive,
diff --git a/lld/lib/Driver/DarwinInputGraph.cpp b/lld/lib/Driver/DarwinInputGraph.cpp
index ef246b66ad1..f5f086f84d3 100644
--- a/lld/lib/Driver/DarwinInputGraph.cpp
+++ b/lld/lib/Driver/DarwinInputGraph.cpp
@@ -17,6 +17,49 @@
 
 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 e7ffcd8f30f..500e292ec50 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<InputGraph> &inputGraph,
+static void addFile(StringRef path, std::unique_ptr<DarwinInputGraph> &inputGraph,
                     MachOLinkingContext &ctx, bool loadWholeArchive,
                     bool upwardDylib) {
   auto node = llvm::make_unique<MachOFileNode>(path, ctx);
@@ -132,7 +132,7 @@ static std::error_code parseExportsList(StringRef exportFilePath,
 // per line. The <dir> prefix is prepended to each partial path.
 //
 static std::error_code parseFileList(StringRef fileListPath,
-                                     std::unique_ptr<InputGraph> &inputGraph,
+                                     std::unique_ptr<DarwinInputGraph> &inputGraph,
                                      MachOLinkingContext &ctx, bool forceLoad,
                                      raw_ostream &diagnostics) {
   // If there is a comma, split off <dir>.
@@ -468,7 +468,7 @@ bool DarwinLdDriver::parse(int argc, const char *argv[],
     }
   }
 
-  std::unique_ptr<InputGraph> inputGraph(new InputGraph());
+  std::unique_ptr<DarwinInputGraph> inputGraph(new DarwinInputGraph());
 
   // Now construct the set of library search directories, following ld64's
   // baroque set of accumulated hacks. Mostly, the algorithm constructs
diff --git a/lld/test/mach-o/Inputs/libbar.a b/lld/test/mach-o/Inputs/libbar.a
new file mode 100644
index 00000000000..64cae6c749e
--- /dev/null
+++ b/lld/test/mach-o/Inputs/libbar.a
diff --git a/lld/test/mach-o/lib-search-paths.yaml b/lld/test/mach-o/lib-search-paths.yaml
index 88c4b5151e8..5005f016857 100644
--- a/lld/test/mach-o/lib-search-paths.yaml
+++ b/lld/test/mach-o/lib-search-paths.yaml
@@ -1,4 +1,4 @@
-# RUN: lld -flavor darwin -arch x86_64 %s -syslibroot %p/Inputs/lib-search-paths -lmyshared -lmystatic -lfile.o -print_atoms 2>&1 -r | FileCheck %s
+# RUN: lld -flavor darwin -arch x86_64 %s -syslibroot %p/Inputs/lib-search-paths -lmyshared -lmystatic -lfile.o -r -print_atoms 2>&1  | FileCheck %s
 
 --- !native
 undefined-atoms:
@@ -7,10 +7,10 @@ undefined-atoms:
     - name: _from_fileo
 
 # CHECK: defined-atoms:
-# CHECK:   - name:            _from_mystatic
-# CHECK:     content:         [ 02, 00, 00, 00 ]
 # CHECK:   - name:            _from_fileo
 # CHECK:     content:         [ 2A, 00, 00, 00 ]
+# CHECK:   - name:            _from_mystatic
+# CHECK:     content:         [ 02, 00, 00, 00 ]
 # CHECK: shared-library-atoms:
 # CHECK:   - name:            _from_myshared
 # CHECK:     load-name:       libmyshared.dylib
diff --git a/lld/test/mach-o/library-order.yaml b/lld/test/mach-o/library-order.yaml
new file mode 100644
index 00000000000..23e9f687313
--- /dev/null
+++ b/lld/test/mach-o/library-order.yaml
@@ -0,0 +1,45 @@
+# RUN: lld -flavor darwin -arch x86_64 %p/Inputs/libfoo.a %s -o %t \
+# RUN:    %p/Inputs/libSystem.yaml
+# RUN: llvm-nm -m -n %t | FileCheck %s
+#
+# Test that if library is before object file on command line, it still is used.
+#
+
+--- !mach-o
+arch:            x86_64
+file-type:       MH_OBJECT
+flags:           [ MH_SUBSECTIONS_VIA_SYMBOLS ]
+sections:
+  - segment:         __TEXT
+    section:         __text
+    type:            S_REGULAR
+    attributes:      [ S_ATTR_PURE_INSTRUCTIONS, S_ATTR_SOME_INSTRUCTIONS ]
+    alignment:       4
+    address:         0x0000000000000000
+    content:         [ 0x55, 0x48, 0x89, 0xE5, 0x48, 0x83, 0xEC, 0x10, 
+                       0xC7, 0x45, 0xFC, 0x00, 0x00, 0x00, 0x00, 0xB0, 
+                       0x00, 0xE8, 0x00, 0x00, 0x00, 0x00, 0x31, 0xC0, 
+                       0x48, 0x83, 0xC4, 0x10, 0x5D, 0xC3 ]
+    relocations:
+      - offset:          0x00000012
+        type:            X86_64_RELOC_BRANCH
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          1
+global-symbols:
+  - name:            _main
+    type:            N_SECT
+    scope:           [ N_EXT ]
+    sect:            1
+    value:           0x0000000000000000
+undefined-symbols:
+  - name:            _foo
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+
+...
+
+# CHECK:	{{[0-9a-f]+}} (__TEXT,__text) external _main
+# CHECK:	{{[0-9a-f]+}} (__TEXT,__text) external _foo
diff --git a/lld/test/mach-o/library-rescan.yaml b/lld/test/mach-o/library-rescan.yaml
new file mode 100644
index 00000000000..a58d763fff0
--- /dev/null
+++ b/lld/test/mach-o/library-rescan.yaml
@@ -0,0 +1,46 @@
+# RUN: lld -flavor darwin -arch x86_64 %p/Inputs/libfoo.a %p/Inputs/libbar.a \
+# RUN:    %s -o %t  %p/Inputs/libSystem.yaml
+# RUN: llvm-nm -m -n %t | FileCheck %s
+#
+# Test that static libraries are automatically rescanned (bar needs foo).
+#
+
+--- !mach-o
+arch:            x86_64
+file-type:       MH_OBJECT
+flags:           [ MH_SUBSECTIONS_VIA_SYMBOLS ]
+sections:
+  - segment:         __TEXT
+    section:         __text
+    type:            S_REGULAR
+    attributes:      [ S_ATTR_PURE_INSTRUCTIONS, S_ATTR_SOME_INSTRUCTIONS ]
+    alignment:       4
+    address:         0x0000000000000000
+    content:         [ 0x55, 0x48, 0x89, 0xE5, 0x48, 0x83, 0xEC, 0x10, 
+                       0xC7, 0x45, 0xFC, 0x00, 0x00, 0x00, 0x00, 0xB0, 
+                       0x00, 0xE8, 0x00, 0x00, 0x00, 0x00, 0x31, 0xC0, 
+                       0x48, 0x83, 0xC4, 0x10, 0x5D, 0xC3 ]
+    relocations:
+      - offset:          0x00000012
+        type:            X86_64_RELOC_BRANCH
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          1
+global-symbols:
+  - name:            _main
+    type:            N_SECT
+    scope:           [ N_EXT ]
+    sect:            1
+    value:           0x0000000000000000
+undefined-symbols:
+  - name:            _bar
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+
+...
+
+# CHECK:	{{[0-9a-f]+}} (__TEXT,__text) external _main
+# CHECK:	{{[0-9a-f]+}} (__TEXT,__text) external _bar
+# CHECK:	{{[0-9a-f]+}} (__TEXT,__text) external _foo