Index: include/lld/Core/InputGraph.h =================================================================== --- include/lld/Core/InputGraph.h +++ include/lld/Core/InputGraph.h @@ -59,12 +59,6 @@ /// assigned in the way files are resolved. virtual ErrorOr 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. - 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 /// being returned. @@ -80,10 +74,15 @@ /// it with getReplacements() results. void normalize(); - range inputElements() { - return make_range(_inputArgs.begin(), _inputArgs.end()); + InputElementVectorT &inputElements() { + return _inputArgs; } + // Returns the current group (in the sense of --start-group and + // --end-group) size if we are at an --end-group. Otherwise returns 0. + int getGroupSize(); + void skipGroup(); + // \brief Returns the number of input files. size_t size() const { return _inputArgs.size(); } @@ -108,8 +107,8 @@ public: /// Each input element in the graph can be a File or a control enum class Kind : uint8_t { - Group, // Represents a type associated with Group - File // Represents a type associated with File Nodes + File, // Represents a type associated with File Nodes + GroupEnd, }; InputElement(Kind type) : _kind(type) {} @@ -129,10 +128,6 @@ /// Get the next file to be processed by the resolver virtual ErrorOr getNextFile() = 0; - /// Refer InputGraph::notifyProgress(). By default, it does nothing. Only - /// Group is interested in this message. - virtual void notifyProgress() {}; - /// \brief Reset the next index virtual void resetNextIndex() = 0; @@ -148,73 +143,31 @@ Kind _kind; // The type of the Element }; -/// \brief A Control node which contains a group of InputElements -/// This affects the resolver so that it resolves undefined symbols -/// in the group completely before looking at other input files that -/// follow the group -class Group : public InputElement { +// This is a marker for --end-group. getSize() returns the number of +// files between the corresponding --start-group and this marker. +class GroupEnd : public InputElement { public: - Group() - : InputElement(InputElement::Kind::Group), _currentElementIndex(0), - _nextElementIndex(0), _madeProgress(false) {} + GroupEnd(int size) : InputElement(Kind::GroupEnd), _size(size) {} - static inline bool classof(const InputElement *a) { - return a->kind() == InputElement::Kind::Group; - } - - /// \brief Process input element and add it to the group - bool addFile(std::unique_ptr element) { - _elements.push_back(std::move(element)); - return true; - } - - range elements() { - return make_range(_elements.begin(), _elements.end()); - } + int getSize() const { return _size; } - void resetNextIndex() override { - _madeProgress = false; - _currentElementIndex = 0; - _nextElementIndex = 0; - for (std::unique_ptr &elem : _elements) - elem->resetNextIndex(); + static inline bool classof(const InputElement *a) { + return a->kind() == Kind::GroupEnd; } /// \brief Parse the group members. std::error_code parse(const LinkingContext &ctx, raw_ostream &diag) override { - for (std::unique_ptr &ei : _elements) - if (std::error_code ec = ei->parse(ctx, diag)) - return ec; return std::error_code(); } - /// If Resolver made a progress using the current file, it's ok to revisit - /// files in this group in future. - void notifyProgress() override { - for (std::unique_ptr &elem : _elements) - elem->notifyProgress(); - _madeProgress = true; + ErrorOr getNextFile() override { + llvm_unreachable("shouldn't be here."); } - ErrorOr getNextFile() override; - - void expand() override { - for (std::unique_ptr &elt : _elements) - elt->expand(); - std::vector> result; - for (std::unique_ptr &elt : _elements) { - if (elt->getReplacements(result)) - continue; - result.push_back(std::move(elt)); - } - _elements.swap(result); - } + void resetNextIndex() override {} -protected: - InputGraph::InputElementVectorT _elements; - uint32_t _currentElementIndex; - uint32_t _nextElementIndex; - bool _madeProgress; +private: + int _size; }; /// \brief Represents an Input file in the graph @@ -252,6 +205,8 @@ /// \brief add a file to the list of files virtual void addFiles(InputGraph::FileVectorT files) { + assert(files.size() == 1); + assert(_files.empty()); for (std::unique_ptr &ai : files) _files.push_back(std::move(ai)); } @@ -276,6 +231,10 @@ class SimpleFileNode : public FileNode { public: SimpleFileNode(StringRef path) : FileNode(path) {} + SimpleFileNode(StringRef path, std::unique_ptr f) + : FileNode(path) { + _files.push_back(std::move(f)); + } virtual ~SimpleFileNode() {} Index: include/lld/Core/LinkingContext.h =================================================================== --- include/lld/Core/LinkingContext.h +++ include/lld/Core/LinkingContext.h @@ -318,6 +318,10 @@ /// Return the next ordinal and Increment it. virtual uint64_t getNextOrdinalAndIncrement() const { return _nextOrdinal++; } + // This function is called just before the Resolver kicks in. + // Derived classes may use that chance to rearrange the input files. + virtual void maybeSortInputFiles() {} + /// @} protected: Index: include/lld/Core/Resolver.h =================================================================== --- include/lld/Core/Resolver.h +++ include/lld/Core/Resolver.h @@ -28,7 +28,8 @@ class Resolver { public: Resolver(LinkingContext &context) - : _context(context), _symbolTable(context), _result(new MergedFile()) {} + : _context(context), _symbolTable(context), _result(new MergedFile()), + _fileIndex(0) {} // InputFiles::Handler methods void doDefinedAtom(const DefinedAtom&); @@ -38,10 +39,10 @@ // Handle files, this adds atoms from the current file thats // being processed by the resolver - void handleFile(const File &); + bool handleFile(const File &); // Handle an archive library file. - void handleArchiveFile(const File &); + bool handleArchiveFile(const File &); // Handle a shared library file. void handleSharedLibrary(const File &); @@ -54,6 +55,8 @@ private: typedef std::function UndefCallback; + ErrorOr nextFile(bool &inGroup); + /// \brief Add section group/.gnu.linkonce if it does not exist previously. void maybeAddSectionGroupOrGnuLinkOnce(const DefinedAtom &atom); @@ -110,6 +113,12 @@ llvm::DenseSet _deadAtoms; std::unique_ptr _result; llvm::DenseMap> _reverseRef; + + // --start-group and --end-group + bool undefinesAdded(int count); + std::vector _files; + std::map _newUndefinesAdded; + size_t _fileIndex; }; } // namespace lld Index: include/lld/Driver/DarwinInputGraph.h =================================================================== --- include/lld/Driver/DarwinInputGraph.h +++ include/lld/Driver/DarwinInputGraph.h @@ -23,18 +23,6 @@ namespace lld { - -class DarwinInputGraph : public InputGraph { -public: - DarwinInputGraph() : _librariesPhase(false), _repeatLibraries(false) { } - ErrorOr getNextFile() override; - void notifyProgress() override; -private: - bool _librariesPhase; - bool _repeatLibraries; -}; - - /// \brief Represents a MachO File class MachOFileNode : public FileNode { public: Index: include/lld/Driver/WinLinkInputGraph.h =================================================================== --- include/lld/Driver/WinLinkInputGraph.h +++ include/lld/Driver/WinLinkInputGraph.h @@ -55,21 +55,6 @@ ErrorOr getPath(const LinkingContext &ctx) const override; }; -/// \brief Represents a ELF control node -class PECOFFGroup : public Group { -public: - PECOFFGroup(PECOFFLinkingContext &ctx) : Group(), _ctx(ctx) {} - - /// \brief Parse the group members. - std::error_code parse(const LinkingContext &ctx, raw_ostream &diag) override { - std::lock_guard lock(_ctx.getMutex()); - return Group::parse(ctx, diag); - } - -private: - PECOFFLinkingContext &_ctx; -}; - } // namespace lld #endif Index: include/lld/ReaderWriter/MachOLinkingContext.h =================================================================== --- include/lld/ReaderWriter/MachOLinkingContext.h +++ include/lld/ReaderWriter/MachOLinkingContext.h @@ -283,6 +283,8 @@ /// bits are xxxx.yy.zz. Largest number is 65535.255.255 static bool parsePackedVersion(StringRef str, uint32_t &result); + void maybeSortInputFiles() override; + private: Writer &writer() const override; mach_o::MachODylibFile* loadIndirectDylib(StringRef path); Index: include/lld/ReaderWriter/PECOFFLinkingContext.h =================================================================== --- include/lld/ReaderWriter/PECOFFLinkingContext.h +++ include/lld/ReaderWriter/PECOFFLinkingContext.h @@ -29,7 +29,6 @@ static const uint8_t DEFAULT_DOS_STUB[128] = {'M', 'Z'}; namespace lld { -class Group; class PECOFFLinkingContext : public LinkingContext { public: @@ -309,8 +308,7 @@ void setEntryNode(SimpleFileNode *node) { _entryNode = node; } SimpleFileNode *getEntryNode() const { return _entryNode; } - void setLibraryGroup(Group *group) { _libraryGroup = group; } - Group *getLibraryGroup() const { return _libraryGroup; } + void addLibraryFile(std::unique_ptr file); void setModuleDefinitionFile(const std::string val) { _moduleDefinitionFile = val; @@ -426,9 +424,6 @@ // The node containing the entry point file. SimpleFileNode *_entryNode; - // The PECOFFGroup that contains all the .lib files. - Group *_libraryGroup; - // Name of the temporary file for lib.exe subcommand. For debugging // only. std::string _moduleDefinitionFile; Index: lib/Core/InputGraph.cpp =================================================================== --- lib/Core/InputGraph.cpp +++ lib/Core/InputGraph.cpp @@ -36,8 +36,6 @@ } } -void InputGraph::notifyProgress() { _currentInputElement->notifyProgress(); } - void InputGraph::registerObserver(std::function fn) { _observers.push_back(fn); } @@ -61,7 +59,10 @@ ErrorOr 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(elem)) + return getNextInputElement(); + return elem; } void InputGraph::normalize() { @@ -76,6 +77,25 @@ _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(elem)) + return group->getSize(); + return 0; +} + +void InputGraph::skipGroup() { + if (_nextElementIndex >= _inputArgs.size()) + return; + if (isa(_inputArgs[_nextElementIndex].get())) + _nextElementIndex++; +} + /// \brief Read the file into _buffer. std::error_code FileNode::getBuffer(StringRef filePath) { // Create a memory buffer @@ -86,33 +106,3 @@ _buffer = std::move(mb.get()); 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 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; - } -} Index: lib/Core/Resolver.cpp =================================================================== --- lib/Core/Resolver.cpp +++ 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 @@ 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 @@ } while (undefineGenCount != _symbolTable.size()); } -void Resolver::handleArchiveFile(const File &file) { +bool Resolver::handleArchiveFile(const File &file) { const ArchiveLibraryFile *archiveFile = cast(&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); } }); + return undefAdded; } void Resolver::handleSharedLibrary(const File &file) { @@ -233,31 +229,66 @@ 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 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 = _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 = _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 = 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 @@ handleSharedLibrary(*file); break; } + _newUndefinesAdded[&*file] = undefAdded; } } Index: lib/Driver/DarwinInputGraph.cpp =================================================================== --- lib/Driver/DarwinInputGraph.cpp +++ lib/Driver/DarwinInputGraph.cpp @@ -18,48 +18,6 @@ namespace lld { -ErrorOr 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 next = _currentInputElement->getNextFile(); - if (next.getError()) - break; - File *file = &next.get(); - bool fileIsLibrary = isa(file) || - isa(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) { Index: lib/Driver/DarwinLdDriver.cpp =================================================================== --- lib/Driver/DarwinLdDriver.cpp +++ lib/Driver/DarwinLdDriver.cpp @@ -83,7 +83,7 @@ } } -static void addFile(StringRef path, std::unique_ptr &inputGraph, +static void addFile(StringRef path, std::unique_ptr &inputGraph, MachOLinkingContext &ctx, bool loadWholeArchive, bool upwardDylib) { auto node = llvm::make_unique(path, ctx); @@ -185,7 +185,7 @@ // per line. The prefix is prepended to each partial path. // static std::error_code parseFileList(StringRef fileListPath, - std::unique_ptr &inputGraph, + std::unique_ptr &inputGraph, MachOLinkingContext &ctx, bool forceLoad, raw_ostream &diagnostics) { // If there is a comma, split off . @@ -521,7 +521,7 @@ } } - std::unique_ptr inputGraph(new DarwinInputGraph()); + std::unique_ptr inputGraph(new InputGraph()); // Now construct the set of library search directories, following ld64's // baroque set of accumulated hacks. Mostly, the algorithm constructs Index: lib/Driver/Driver.cpp =================================================================== --- lib/Driver/Driver.cpp +++ lib/Driver/Driver.cpp @@ -63,9 +63,6 @@ if (std::error_code ec = ie->parse(context, stream)) { if (FileNode *fileNode = dyn_cast(ie.get())) stream << fileNode->errStr(ec) << "\n"; - else if (dyn_cast(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; @@ -84,21 +81,24 @@ if (fail) return false; - std::unique_ptr 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("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("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"); Index: lib/Driver/GnuLdDriver.cpp =================================================================== --- lib/Driver/GnuLdDriver.cpp +++ lib/Driver/GnuLdDriver.cpp @@ -295,7 +295,8 @@ } std::unique_ptr inputGraph(new InputGraph()); - std::stack groupStack; + std::stack groupStack; + int numfiles = 0; ELFFileNode::Attributes attributes; @@ -468,16 +469,21 @@ break; } - case OPT_start_group: { - std::unique_ptr 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(numfiles - startGroupPos)); groupStack.pop(); break; + } case OPT_z: { StringRef extOpt = inputArg->getValue(); @@ -552,11 +558,8 @@ } } std::unique_ptr inputFile(inputNode); - if (groupStack.empty()) { - inputGraph->addInputElement(std::move(inputFile)); - } else { - groupStack.top()->addFile(std::move(inputFile)); - } + ++numfiles; + inputGraph->addInputElement(std::move(inputFile)); break; } Index: lib/Driver/GnuLdInputGraph.cpp =================================================================== --- lib/Driver/GnuLdInputGraph.cpp +++ lib/Driver/GnuLdInputGraph.cpp @@ -91,7 +91,7 @@ auto *group = dyn_cast(c); if (!group) continue; - std::unique_ptr 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 @@ _elfLinkingContext, _elfLinkingContext.allocateString(path._path), attributes); std::unique_ptr 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(numfiles)); } return std::error_code(); } Index: lib/Driver/WinLinkDriver.cpp =================================================================== --- lib/Driver/WinLinkDriver.cpp +++ lib/Driver/WinLinkDriver.cpp @@ -781,7 +781,7 @@ ErrorOr path = fileNode->getPath(ctx); if (!path) return false; - for (std::unique_ptr &p : ctx.getLibraryGroup()->elements()) + for (std::unique_ptr &p : ctx.getInputGraph().inputElements()) if (auto *f = dyn_cast(p.get())) if (*path == *f->getPath(ctx)) return true; @@ -1391,10 +1391,8 @@ ctx.setEntryNode(entry.get()); ctx.getInputGraph().addInputElement(std::move(entry)); - // The container for all library files. - std::unique_ptr 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(0)); } // Add the library files to the library group. @@ -1403,7 +1401,7 @@ if (isReadingDirectiveSection) if (lib->parse(ctx, diag)) return false; - ctx.getLibraryGroup()->addFile(std::move(lib)); + ctx.addLibraryFile(std::move(lib)); } } Index: lib/ReaderWriter/MachO/MachOLinkingContext.cpp =================================================================== --- lib/ReaderWriter/MachO/MachOLinkingContext.cpp +++ lib/ReaderWriter/MachO/MachOLinkingContext.cpp @@ -923,4 +923,40 @@ return true; } +static File *getFirstFile(const std::unique_ptr &elem) { + FileNode *e = dyn_cast(const_cast(elem.get())); + if (!e || e->files().empty()) + return nullptr; + return e->files()[0].get(); +} + +static bool isFile(const std::unique_ptr &elem) { + File *f = getFirstFile(elem); + return f && isa(f); +} + +static bool isLibrary(const std::unique_ptr &elem) { + File *f = getFirstFile(elem); + return f && (isa(f) || isa(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> &elements + = getInputGraph().inputElements(); + std::stable_sort(elements.begin(), elements.end(), + [](const std::unique_ptr &a, + const std::unique_ptr &b) { + return isFile(a) && isLibrary(b); + }); + size_t numLibs = std::count_if(elements.begin(), elements.end(), isLibrary); + elements.push_back(llvm::make_unique(numLibs)); +} + } // end namespace lld Index: lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp =================================================================== --- lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp +++ lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp @@ -86,6 +86,23 @@ ""); } +void PECOFFLinkingContext::addLibraryFile(std::unique_ptr file) { + GroupEnd *currentGroupEnd; + int pos = -1; + std::vector> &elements + = getInputGraph().inputElements(); + for (int i = 0, e = elements.size(); i < e; ++i) { + if ((currentGroupEnd = dyn_cast(elements[i].get()))) { + pos = i; + break; + } + } + assert(pos >= 0); + elements.insert(elements.begin() + pos, std::move(file)); + elements[pos + 1] = llvm::make_unique( + currentGroupEnd->getSize() + 1); +} + bool PECOFFLinkingContext::createImplicitFiles( std::vector> &) { // Create a file for __ImageBase. @@ -108,7 +125,7 @@ auto exportNode = llvm::make_unique(""); exportNode->appendInputFile( llvm::make_unique(*this, syms)); - getLibraryGroup()->addFile(std::move(exportNode)); + addLibraryFile(std::move(exportNode)); // Create a file for the entry point function. getEntryNode()->appendInputFile( Index: unittests/DriverTests/DriverTest.h =================================================================== --- unittests/DriverTests/DriverTest.h +++ unittests/DriverTests/DriverTest.h @@ -37,18 +37,6 @@ llvm_unreachable("not handling other types of input files"); } - // Convenience method for getting i'th input files name. - std::string inputFile(int index1, int index2) { - Group *group = dyn_cast( - linkingContext()->getInputGraph().inputElements()[index1].get()); - if (!group) - llvm_unreachable("not handling other types of input files"); - FileNode *file = dyn_cast(group->elements()[index2].get()); - if (!file) - llvm_unreachable("not handling other types of input files"); - return *file->getPath(*linkingContext()); - } - // For unit tests to call driver with various command lines. bool parse(const char *args, ...) { // Construct command line options from varargs. Index: unittests/DriverTests/InputGraphTest.cpp =================================================================== --- unittests/DriverTests/InputGraphTest.cpp +++ unittests/DriverTests/InputGraphTest.cpp @@ -77,7 +77,7 @@ } // end anonymous namespace -static std::unique_ptr createFile1(StringRef name) { +static std::unique_ptr createFile(StringRef name) { std::vector> files; files.push_back(std::unique_ptr(new SimpleFile(name))); std::unique_ptr file(new TestFileNode("filenode")); @@ -85,109 +85,30 @@ return file; } -static std::unique_ptr createFile2(StringRef name1, - StringRef name2) { - std::vector> files; - files.push_back(std::unique_ptr(new SimpleFile(name1))); - files.push_back(std::unique_ptr(new SimpleFile(name2))); - std::unique_ptr file(new TestFileNode("filenode")); - file->addFiles(std::move(files)); - return file; -} - TEST_F(InputGraphTest, Empty) { expectEnd(); } TEST_F(InputGraphTest, File) { - _graph->addInputElement(createFile1("file1")); - EXPECT_EQ("file1", getNext()); - expectEnd(); -} - -TEST_F(InputGraphTest, Files) { - _graph->addInputElement(createFile2("file1", "file2")); + _graph->addInputElement(createFile("file1")); EXPECT_EQ("file1", getNext()); - EXPECT_EQ("file2", getNext()); - expectEnd(); -} - -TEST_F(InputGraphTest, Group) { - _graph->addInputElement(createFile2("file1", "file2")); - - std::unique_ptr group(new Group()); - group->addFile(createFile2("file3", "file4")); - group->addFile(createFile1("file5")); - group->addFile(createFile1("file6")); - _graph->addInputElement(std::move(group)); - - EXPECT_EQ("file1", getNext()); - EXPECT_EQ("file2", getNext()); - EXPECT_EQ("file3", getNext()); - EXPECT_EQ("file4", getNext()); - EXPECT_EQ("file5", getNext()); - EXPECT_EQ("file6", getNext()); - expectEnd(); -} - -// Iterate through the group -TEST_F(InputGraphTest, GroupIteration) { - _graph->addInputElement(createFile2("file1", "file2")); - - std::unique_ptr group(new Group()); - group->addFile(createFile2("file3", "file4")); - group->addFile(createFile1("file5")); - group->addFile(createFile1("file6")); - _graph->addInputElement(std::move(group)); - - EXPECT_EQ("file1", getNext()); - EXPECT_EQ("file2", getNext()); - - EXPECT_EQ("file3", getNext()); - EXPECT_EQ("file4", getNext()); - EXPECT_EQ("file5", getNext()); - EXPECT_EQ("file6", getNext()); - _graph->notifyProgress(); - - EXPECT_EQ("file3", getNext()); - EXPECT_EQ("file4", getNext()); - _graph->notifyProgress(); - EXPECT_EQ("file5", getNext()); - EXPECT_EQ("file6", getNext()); - - EXPECT_EQ("file3", getNext()); - EXPECT_EQ("file4", getNext()); - EXPECT_EQ("file5", getNext()); - EXPECT_EQ("file6", getNext()); expectEnd(); } // Node expansion tests TEST_F(InputGraphTest, Normalize) { - _graph->addInputElement(createFile2("file1", "file2")); + _graph->addInputElement(createFile("file1")); std::unique_ptr expandFile( new TestExpandFileNode("node")); - expandFile->addElement(createFile1("file3")); - expandFile->addElement(createFile1("file4")); + expandFile->addElement(createFile("file2")); + expandFile->addElement(createFile("file3")); _graph->addInputElement(std::move(expandFile)); - - std::unique_ptr group(new Group()); - std::unique_ptr expandFile2( - new TestExpandFileNode("node")); - expandFile2->addElement(createFile1("file5")); - group->addFile(std::move(expandFile2)); - _graph->addInputElement(std::move(group)); - - _graph->addInputElement(createFile1("file6")); _graph->normalize(); EXPECT_EQ("file1", getNext()); EXPECT_EQ("file2", getNext()); EXPECT_EQ("file3", getNext()); - EXPECT_EQ("file4", getNext()); - EXPECT_EQ("file5", getNext()); - EXPECT_EQ("file6", getNext()); expectEnd(); } @@ -195,8 +116,8 @@ std::vector files; _graph->registerObserver([&](File *file) { files.push_back(file->path()); }); - _graph->addInputElement(createFile1("file1")); - _graph->addInputElement(createFile1("file2")); + _graph->addInputElement(createFile("file1")); + _graph->addInputElement(createFile("file2")); EXPECT_EQ("file1", getNext()); EXPECT_EQ("file2", getNext()); expectEnd(); Index: unittests/DriverTests/WinLinkDriverTest.cpp =================================================================== --- unittests/DriverTests/WinLinkDriverTest.cpp +++ unittests/DriverTests/WinLinkDriverTest.cpp @@ -137,11 +137,11 @@ TEST_F(WinLinkParserTest, InputOrder) { EXPECT_TRUE(parse("link.exe", "a.lib", "b.obj", "c.obj", "a.lib", "d.obj", nullptr)); - EXPECT_EQ(5, inputFileCount()); + EXPECT_EQ(6, inputFileCount()); EXPECT_EQ("b.obj", inputFile(0)); EXPECT_EQ("c.obj", inputFile(1)); EXPECT_EQ("d.obj", inputFile(2)); - EXPECT_EQ("a.lib", inputFile(4, 0)); + EXPECT_EQ("a.lib", inputFile(4)); } // @@ -393,36 +393,36 @@ TEST_F(WinLinkParserTest, DefaultLib) { EXPECT_TRUE(parse("link.exe", "/defaultlib:user32.lib", "/defaultlib:kernel32", "a.obj", nullptr)); - EXPECT_EQ(3, inputFileCount()); + EXPECT_EQ(5, inputFileCount()); EXPECT_EQ("a.obj", inputFile(0)); - EXPECT_EQ("user32.lib", inputFile(2, 0)); - EXPECT_EQ("kernel32.lib", inputFile(2, 1)); + EXPECT_EQ("user32.lib", inputFile(2)); + EXPECT_EQ("kernel32.lib", inputFile(3)); } TEST_F(WinLinkParserTest, DefaultLibDuplicates) { EXPECT_TRUE(parse("link.exe", "/defaultlib:user32.lib", "/defaultlib:user32.lib", "a.obj", nullptr)); - EXPECT_EQ(3, inputFileCount()); + EXPECT_EQ(4, inputFileCount()); EXPECT_EQ("a.obj", inputFile(0)); - EXPECT_EQ("user32.lib", inputFile(2, 0)); + EXPECT_EQ("user32.lib", inputFile(2)); } TEST_F(WinLinkParserTest, NoDefaultLib) { EXPECT_TRUE(parse("link.exe", "/defaultlib:user32.lib", "/defaultlib:kernel32", "/nodefaultlib:user32.lib", "a.obj", nullptr)); - EXPECT_EQ(3, inputFileCount()); + EXPECT_EQ(4, inputFileCount()); EXPECT_EQ("a.obj", inputFile(0)); - EXPECT_EQ("kernel32.lib", inputFile(2, 0)); + EXPECT_EQ("kernel32.lib", inputFile(2)); } TEST_F(WinLinkParserTest, NoDefaultLibCase) { EXPECT_TRUE(parse("link.exe", "/defaultlib:user32", "/defaultlib:kernel32", "/nodefaultlib:USER32.LIB", "a.obj", nullptr)); - EXPECT_EQ(3, inputFileCount()); + EXPECT_EQ(4, inputFileCount()); EXPECT_EQ("a.obj", inputFile(0)); - EXPECT_EQ("kernel32.lib", inputFile(2, 0)); + EXPECT_EQ("kernel32.lib", inputFile(2)); } TEST_F(WinLinkParserTest, NoDefaultLibAll) { @@ -436,9 +436,9 @@ EXPECT_TRUE(parse("link.exe", "/defaultlib:user32.lib", "/defaultlib:kernel32", "/disallowlib:user32.lib", "a.obj", nullptr)); - EXPECT_EQ(3, inputFileCount()); + EXPECT_EQ(4, inputFileCount()); EXPECT_EQ("a.obj", inputFile(0)); - EXPECT_EQ("kernel32.lib", inputFile(2, 0)); + EXPECT_EQ("kernel32.lib", inputFile(2)); } //