Add DarwinInputGraph

[kledzik]

Summary

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.

My next thought was to "sort" the graph after all input files had been opened. The problem with that is that a yaml file can contain a mix of object files and library files and there is no way to sort out the sub files of an InputElement.

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

BTW, I was hoping to also rework the graph walk to be more C++11 styled and use a separate iterator with begin/end. But the notifyProgess() model does not fit in because it would need to be a method on the iterator object and C++11 hides that.

[shankarke]

LGTM.

[ruiu]

I'm not still sure whether or not "InputGraph" thing was after all the right way to abstract the input file list. That often makes easy things hard. In this case, sorting a list of input files became that hard. When I proposed the idea I was thinking that would make this kind of things easier to handle. I don't think the current shape of the API is not desirable at least. Or the fundamental idea was not very good.

One thing we probably should consider is, in my opinion, we are pushing too hard to separate all ports. We are trying to write any architecture-dependent code into architecture-specific file. But the natural border of API doesn't always fit to the architecture dependent/independent border. We should probably relax that constraint a bit where that makes sense and write code that's short and easier to understand.

That being said, the InputGraph already exists there, and if I use that I'd do that way. This patch doesn't make things worse, so LGTM.

[kledzik]

committed in r220330

include/lld/Core/InputGraph.h

 
   /// \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

include/lld/Driver/DarwinInputGraph.h

 
 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:

lib/Core/InputGraph.cpp

 
 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,

lib/Driver/DarwinInputGraph.cpp

 
 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)  {

lib/Driver/DarwinLdDriver.cpp

   }
 }
 
-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);

 // 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>.

     }
   }
 
-  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

test/mach-o/lib-search-paths.yaml

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

     - 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

test/mach-o/library-order.yaml

+# 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

test/mach-o/library-rescan.yaml

+# 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