Index: lld/trunk/COFF/Driver.h =================================================================== --- lld/trunk/COFF/Driver.h +++ lld/trunk/COFF/Driver.h @@ -16,6 +16,7 @@ #include "lld/Core/Reproduce.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/StringRef.h" +#include "llvm/Object/Archive.h" #include "llvm/Object/COFF.h" #include "llvm/Option/Arg.h" #include "llvm/Option/ArgList.h" @@ -65,12 +66,16 @@ // Used by the resolver to parse .drectve section contents. void parseDirectives(StringRef S); - std::unique_ptr Cpio; // for /linkrepro + // Used by ArchiveFile to enqueue members. + void enqueueArchiveMember(const Archive::Child &C, StringRef SymName, + StringRef ParentName); private: ArgParser Parser; SymbolTable Symtab; + std::unique_ptr Cpio; // for /linkrepro + // Opens a file. Path has to be resolved already. MemoryBufferRef openFile(StringRef Path); @@ -100,9 +105,23 @@ StringRef findDefaultEntry(); WindowsSubsystem inferSubsystem(); + MemoryBufferRef takeBuffer(std::unique_ptr MB); + void addBuffer(std::unique_ptr MB); + void addArchiveBuffer(MemoryBufferRef MBRef, StringRef SymName, + StringRef ParentName); + + void enqueuePath(StringRef Path); + + void enqueueTask(std::function Task); + bool run(); + // Driver is the owner of all opened files. // InputFiles have MemoryBufferRefs to them. std::vector> OwningMBs; + + std::list> TaskQueue; + std::vector FilePaths; + std::vector Resources; }; void parseModuleDefs(MemoryBufferRef MB); Index: lld/trunk/COFF/Driver.cpp =================================================================== --- lld/trunk/COFF/Driver.cpp +++ lld/trunk/COFF/Driver.cpp @@ -30,6 +30,13 @@ #include #include +#ifdef _MSC_VER +// depends on for __uncaught_exception. +#include +#endif + +#include + using namespace llvm; using namespace llvm::COFF; using llvm::sys::Process; @@ -58,33 +65,123 @@ return (S.substr(0, S.rfind('.')) + E).str(); } -// Opens a file. Path has to be resolved already. -// Newly created memory buffers are owned by this driver. -MemoryBufferRef LinkerDriver::openFile(StringRef Path) { - std::unique_ptr MB = - check(MemoryBuffer::getFile(Path), "could not open " + Path); - MemoryBufferRef MBRef = MB->getMemBufferRef(); - OwningMBs.push_back(std::move(MB)); // take ownership +// ErrorOr is not default constructible, so it cannot be used as the type +// parameter of a future. +// FIXME: We could open the file in createFutureForFile and avoid needing to +// return an error here, but for the moment that would cost us a file descriptor +// (a limited resource on Windows) for the duration that the future is pending. +typedef std::pair, std::error_code> MBErrPair; + +// Create a std::future that opens and maps a file using the best strategy for +// the host platform. +static std::future createFutureForFile(std::string Path) { +#if LLVM_ON_WIN32 + // On Windows, file I/O is relatively slow so it is best to do this + // asynchronously. + auto Strategy = std::launch::async; +#else + auto Strategy = std::launch::deferred; +#endif + return std::async(Strategy, [=]() { + auto MBOrErr = MemoryBuffer::getFile(Path); + if (!MBOrErr) + return MBErrPair{nullptr, MBOrErr.getError()}; + return MBErrPair{std::move(*MBOrErr), std::error_code()}; + }); +} + +MemoryBufferRef LinkerDriver::takeBuffer(std::unique_ptr MB) { + MemoryBufferRef MBRef = *MB; + OwningMBs.push_back(std::move(MB)); + + if (Driver->Cpio) + Driver->Cpio->append(relativeToRoot(MBRef.getBufferIdentifier()), + MBRef.getBuffer()); + return MBRef; } -static InputFile *createFile(MemoryBufferRef MB) { - if (Driver->Cpio) - Driver->Cpio->append(relativeToRoot(MB.getBufferIdentifier()), - MB.getBuffer()); +void LinkerDriver::addBuffer(std::unique_ptr MB) { + MemoryBufferRef MBRef = takeBuffer(std::move(MB)); // File type is detected by contents, not by file extension. - file_magic Magic = identify_magic(MB.getBuffer()); + file_magic Magic = identify_magic(MBRef.getBuffer()); + if (Magic == file_magic::windows_resource) { + Resources.push_back(MBRef); + return; + } + + FilePaths.push_back(MBRef.getBufferIdentifier()); if (Magic == file_magic::archive) - return make(MB); + return Symtab.addFile(make(MBRef)); if (Magic == file_magic::bitcode) - return make(MB); + return Symtab.addFile(make(MBRef)); if (Magic == file_magic::coff_cl_gl_object) - fatal(MB.getBufferIdentifier() + ": is not a native COFF file. " + fatal(MBRef.getBufferIdentifier() + ": is not a native COFF file. " "Recompile without /GL"); + Symtab.addFile(make(MBRef)); +} + +void LinkerDriver::enqueuePath(StringRef Path) { + auto Future = + std::make_shared>(createFutureForFile(Path)); + std::string PathStr = Path; + enqueueTask([=]() { + auto MBOrErr = Future->get(); + if (MBOrErr.second) + fatal(MBOrErr.second, "could not open " + PathStr); + Driver->addBuffer(std::move(MBOrErr.first)); + }); + if (Config->OutputFile == "") - Config->OutputFile = getOutputPath(MB.getBufferIdentifier()); - return make(MB); + Config->OutputFile = getOutputPath(Path); +} + +void LinkerDriver::addArchiveBuffer(MemoryBufferRef MB, StringRef SymName, + StringRef ParentName) { + file_magic Magic = identify_magic(MB.getBuffer()); + if (Magic == file_magic::coff_import_library) { + Symtab.addFile(make(MB)); + return; + } + + InputFile *Obj; + if (Magic == file_magic::coff_object) + Obj = make(MB); + else if (Magic == file_magic::bitcode) + Obj = make(MB); + else + fatal("unknown file type: " + MB.getBufferIdentifier()); + + Obj->ParentName = ParentName; + Symtab.addFile(Obj); + if (Config->Verbose) + outs() << "Loaded " << toString(Obj) << " for " << SymName << "\n"; +} + +void LinkerDriver::enqueueArchiveMember(const Archive::Child &C, + StringRef SymName, + StringRef ParentName) { + if (!C.getParent()->isThin()) { + MemoryBufferRef MB = check( + C.getMemoryBufferRef(), + "could not get the buffer for the member defining symbol " + SymName); + enqueueTask([=]() { Driver->addArchiveBuffer(MB, SymName, ParentName); }); + return; + } + + auto Future = std::make_shared>(createFutureForFile( + check(C.getFullName(), + "could not get the filename for the member defining symbol " + + SymName))); + enqueueTask([=]() { + auto MBOrErr = Future->get(); + if (MBOrErr.second) + fatal(MBOrErr.second, + "could not get the buffer for the member defining " + SymName); + Driver->addArchiveBuffer(takeBuffer(std::move(MBOrErr.first)), SymName, + ParentName); + }); } static bool isDecorated(StringRef Sym) { @@ -102,10 +199,8 @@ parseAlternateName(Arg->getValue()); break; case OPT_defaultlib: - if (Optional Path = findLib(Arg->getValue())) { - MemoryBufferRef MB = openFile(*Path); - Symtab.addFile(createFile(MB)); - } + if (Optional Path = findLib(Arg->getValue())) + enqueuePath(*Path); break; case OPT_export: { Export E = parseExport(Arg->getValue()); @@ -255,7 +350,7 @@ } static std::string createResponseFile(const opt::InputArgList &Args, - ArrayRef MBs, + ArrayRef FilePaths, ArrayRef SearchPaths) { SmallString<0> Data; raw_svector_ostream OS(Data); @@ -277,10 +372,8 @@ OS << "/libpath:" << quote(RelPath) << "\n"; } - for (MemoryBufferRef MB : MBs) { - std::string InputPath = relativeToRoot(MB.getBufferIdentifier()); - OS << quote(InputPath) << "\n"; - } + for (StringRef Path : FilePaths) + OS << quote(relativeToRoot(Path)) << "\n"; return Data.str(); } @@ -319,6 +412,19 @@ return (OutFile.substr(0, OutFile.rfind('.')) + ".map").str(); } +void LinkerDriver::enqueueTask(std::function Task) { + TaskQueue.push_back(std::move(Task)); +} + +bool LinkerDriver::run() { + bool DidWork = !TaskQueue.empty(); + while (!TaskQueue.empty()) { + TaskQueue.front()(); + TaskQueue.pop_front(); + } + return DidWork; +} + void LinkerDriver::link(ArrayRef ArgsArr) { // If the first command line argument is "/lib", link.exe acts like lib.exe. // We call our own implementation of lib.exe that understands bitcode files. @@ -544,40 +650,20 @@ // Create a list of input files. Files can be given as arguments // for /defaultlib option. - std::vector Paths; std::vector MBs; for (auto *Arg : Args.filtered(OPT_INPUT)) if (Optional Path = findFile(Arg->getValue())) - Paths.push_back(*Path); + enqueuePath(*Path); for (auto *Arg : Args.filtered(OPT_defaultlib)) if (Optional Path = findLib(Arg->getValue())) - Paths.push_back(*Path); - for (StringRef Path : Paths) - MBs.push_back(openFile(Path)); + enqueuePath(*Path); // Windows specific -- Create a resource file containing a manifest file. - if (Config->Manifest == Configuration::Embed) { - std::unique_ptr MB = createManifestRes(); - MBs.push_back(MB->getMemBufferRef()); - OwningMBs.push_back(std::move(MB)); // take ownership - } - - // Windows specific -- Input files can be Windows resource files (.res files). - // We invoke cvtres.exe to convert resource files to a regular COFF file - // then link the result file normally. - std::vector Resources; - auto NotResource = [](MemoryBufferRef MB) { - return identify_magic(MB.getBuffer()) != file_magic::windows_resource; - }; - auto It = std::stable_partition(MBs.begin(), MBs.end(), NotResource); - if (It != MBs.end()) { - Resources.insert(Resources.end(), It, MBs.end()); - MBs.erase(It, MBs.end()); - } + if (Config->Manifest == Configuration::Embed) + addBuffer(createManifestRes()); // Read all input files given via the command line. - for (MemoryBufferRef MB : MBs) - Symtab.addFile(createFile(MB)); + run(); // We should have inferred a machine type by now from the input files, but if // not we assume x64. @@ -586,18 +672,15 @@ Config->Machine = AMD64; } - // Windows specific -- Convert Windows resource files to a COFF file. - if (!Resources.empty()) { - std::unique_ptr MB = convertResToCOFF(Resources); - Symtab.addFile(createFile(MB->getMemBufferRef())); - - MBs.push_back(MB->getMemBufferRef()); - OwningMBs.push_back(std::move(MB)); // take ownership - } + // Windows specific -- Input files can be Windows resource files (.res files). + // We invoke cvtres.exe to convert resource files to a regular COFF file + // then link the result file normally. + if (!Resources.empty()) + addBuffer(convertResToCOFF(Resources)); if (Cpio) Cpio->append("response.txt", - createResponseFile(Args, MBs, + createResponseFile(Args, FilePaths, ArrayRef(SearchPaths).slice(1))); // Handle /largeaddressaware @@ -640,9 +723,10 @@ // Handle /def if (auto *Arg = Args.getLastArg(OPT_deffile)) { - MemoryBufferRef MB = openFile(Arg->getValue()); // parseModuleDefs mutates Config object. - parseModuleDefs(MB); + parseModuleDefs( + takeBuffer(check(MemoryBuffer::getFile(Arg->getValue()), + Twine("could not open ") + Arg->getValue()))); } // Handle /delayload @@ -671,40 +755,46 @@ Symtab.addAbsolute(mangle("__guard_fids_count"), 0); Symtab.addAbsolute(mangle("__guard_flags"), 0x100); - // Windows specific -- if entry point is not found, - // search for its mangled names. - if (Config->Entry) - Symtab.mangleMaybe(Config->Entry); - - // Windows specific -- Make sure we resolve all dllexported symbols. - for (Export &E : Config->Exports) { - if (!E.ForwardTo.empty()) - continue; - E.Sym = addUndefined(E.Name); - if (!E.Directives) - Symtab.mangleMaybe(E.Sym); - } - - // Add weak aliases. Weak aliases is a mechanism to give remaining - // undefined symbols final chance to be resolved successfully. - for (auto Pair : Config->AlternateNames) { - StringRef From = Pair.first; - StringRef To = Pair.second; - Symbol *Sym = Symtab.find(From); - if (!Sym) - continue; - if (auto *U = dyn_cast(Sym->body())) - if (!U->WeakAlias) - U->WeakAlias = Symtab.addUndefined(To); - } - - // Windows specific -- if __load_config_used can be resolved, resolve it. - if (Symtab.findUnderscore("_load_config_used")) - addUndefined(mangle("_load_config_used")); + // This code may add new undefined symbols to the link, which may enqueue more + // symbol resolution tasks, so we need to continue executing tasks until we + // converge. + do { + // Windows specific -- if entry point is not found, + // search for its mangled names. + if (Config->Entry) + Symtab.mangleMaybe(Config->Entry); + + // Windows specific -- Make sure we resolve all dllexported symbols. + for (Export &E : Config->Exports) { + if (!E.ForwardTo.empty()) + continue; + E.Sym = addUndefined(E.Name); + if (!E.Directives) + Symtab.mangleMaybe(E.Sym); + } + + // Add weak aliases. Weak aliases is a mechanism to give remaining + // undefined symbols final chance to be resolved successfully. + for (auto Pair : Config->AlternateNames) { + StringRef From = Pair.first; + StringRef To = Pair.second; + Symbol *Sym = Symtab.find(From); + if (!Sym) + continue; + if (auto *U = dyn_cast(Sym->body())) + if (!U->WeakAlias) + U->WeakAlias = Symtab.addUndefined(To); + } + + // Windows specific -- if __load_config_used can be resolved, resolve it. + if (Symtab.findUnderscore("_load_config_used")) + addUndefined(mangle("_load_config_used")); + } while (run()); // Do LTO by compiling bitcode input files to a set of native COFF files then // link those files. Symtab.addCombinedLTOObjects(); + run(); // Make sure we have resolved all symbols. Symtab.reportRemainingUndefines(); Index: lld/trunk/COFF/InputFiles.h =================================================================== --- lld/trunk/COFF/InputFiles.h +++ lld/trunk/COFF/InputFiles.h @@ -83,10 +83,10 @@ static bool classof(const InputFile *F) { return F->kind() == ArchiveKind; } void parse() override; - // Returns an input file for a given symbol. A null pointer is returned if we - // have already returned the same input file. (So that we don't instantiate - // the same member more than once.) - InputFile *getMember(const Archive::Symbol *Sym); + // Enqueues an archive member load for the given symbol. If we've already + // enqueued a load for the same archive member, this function does nothing, + // which ensures that we don't load the same member more than once. + void addMember(const Archive::Symbol *Sym); private: std::unique_ptr File; Index: lld/trunk/COFF/InputFiles.cpp =================================================================== --- lld/trunk/COFF/InputFiles.cpp +++ lld/trunk/COFF/InputFiles.cpp @@ -61,37 +61,16 @@ } // Returns a buffer pointing to a member file containing a given symbol. -InputFile *ArchiveFile::getMember(const Archive::Symbol *Sym) { +void ArchiveFile::addMember(const Archive::Symbol *Sym) { const Archive::Child &C = check(Sym->getMember(), "could not get the member for symbol " + Sym->getName()); // Return an empty buffer if we have already returned the same buffer. if (!Seen.insert(C.getChildOffset()).second) - return nullptr; - - MemoryBufferRef MB = - check(C.getMemoryBufferRef(), - "could not get the buffer for the member defining symbol " + - Sym->getName()); - if (C.getParent()->isThin() && Driver->Cpio) - Driver->Cpio->append(relativeToRoot(check(C.getFullName())), - MB.getBuffer()); - - file_magic Magic = identify_magic(MB.getBuffer()); - if (Magic == file_magic::coff_import_library) - return make(MB); - - InputFile *Obj; - if (Magic == file_magic::coff_object) - Obj = make(MB); - else if (Magic == file_magic::bitcode) - Obj = make(MB); - else - fatal("unknown file type: " + MB.getBufferIdentifier()); + return; - Obj->ParentName = getName(); - return Obj; + Driver->enqueueArchiveMember(C, Sym->getName(), getName()); } void ObjectFile::parse() { Index: lld/trunk/COFF/SymbolTable.h =================================================================== --- lld/trunk/COFF/SymbolTable.h +++ lld/trunk/COFF/SymbolTable.h @@ -17,11 +17,6 @@ #include "llvm/Support/Allocator.h" #include "llvm/Support/raw_ostream.h" -#ifdef _MSC_VER -// depends on for __uncaught_exception. -#include -#endif - namespace llvm { struct LTOCodeGenerator; } @@ -117,7 +112,6 @@ std::pair insert(StringRef Name); StringRef findByPrefix(StringRef Prefix); - void addMemberFile(ArchiveFile *F, const Archive::Symbol Sym); void addCombinedLTOObject(ObjectFile *Obj); std::vector createLTOObjects(llvm::LTOCodeGenerator *CG); Index: lld/trunk/COFF/SymbolTable.cpp =================================================================== --- lld/trunk/COFF/SymbolTable.cpp +++ lld/trunk/COFF/SymbolTable.cpp @@ -122,6 +122,7 @@ return {Sym, false}; Sym = make(); Sym->IsUsedInRegularObj = false; + Sym->PendingArchiveLoad = false; return {Sym, true}; } @@ -136,8 +137,12 @@ replaceBody(S, Name); return S; } - if (auto *L = dyn_cast(S->body())) - addMemberFile(L->File, L->Sym); + if (auto *L = dyn_cast(S->body())) { + if (!S->PendingArchiveLoad) { + S->PendingArchiveLoad = true; + L->File->addMember(&L->Sym); + } + } return S; } @@ -151,9 +156,10 @@ return; } auto *U = dyn_cast(S->body()); - if (!U || U->WeakAlias) + if (!U || U->WeakAlias || S->PendingArchiveLoad) return; - addMemberFile(F, Sym); + S->PendingArchiveLoad = true; + F->addMember(&Sym); } void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) { @@ -279,19 +285,6 @@ return S; } -// Reads an archive member file pointed by a given symbol. -void SymbolTable::addMemberFile(ArchiveFile *F, const Archive::Symbol Sym) { - InputFile *File = F->getMember(&Sym); - - // getMember returns an empty buffer if the member was already - // read from the library. - if (!File) - return; - if (Config->Verbose) - outs() << "Loaded " << toString(File) << " for " << Sym.getName() << "\n"; - addFile(File); -} - std::vector SymbolTable::getChunks() { std::vector Res; for (ObjectFile *File : ObjectFiles) { @@ -371,13 +364,8 @@ // DefinedBitcode symbols with the definitions in the object file. LTOCodeGenerator CG(BitcodeFile::Context); CG.setOptLevel(Config->LTOOptLevel); - std::vector Objs = createLTOObjects(&CG); - - size_t NumBitcodeFiles = BitcodeFiles.size(); - for (ObjectFile *Obj : Objs) + for (ObjectFile *Obj : createLTOObjects(&CG)) Obj->parse(); - if (BitcodeFiles.size() != NumBitcodeFiles) - fatal("LTO: late loaded symbol created new bitcode reference"); } // Combine and compile bitcode files and then return the result Index: lld/trunk/COFF/Symbols.h =================================================================== --- lld/trunk/COFF/Symbols.h +++ lld/trunk/COFF/Symbols.h @@ -393,6 +393,11 @@ // True if this symbol was referenced by a regular (non-bitcode) object. unsigned IsUsedInRegularObj : 1; + // True if we've seen both a lazy and an undefined symbol with this symbol + // name, which means that we have enqueued an archive member load and should + // not load any more archive members to resolve the same symbol. + unsigned PendingArchiveLoad : 1; + // This field is used to store the Symbol's SymbolBody. This instantiation of // AlignedCharArrayUnion gives us a struct with a char array field that is // large and aligned enough to store any derived class of SymbolBody. Index: lld/trunk/test/COFF/order.test =================================================================== --- lld/trunk/test/COFF/order.test +++ lld/trunk/test/COFF/order.test @@ -10,6 +10,6 @@ CHECK: order.test.tmp1.obj CHECK: order.test.tmp2.lib -CHECK: order.test.tmp2.lib(order.test.tmp2.obj) for foo CHECK: order.test.tmp3.obj CHECK: order.test.tmp3.lib +CHECK: order.test.tmp2.lib(order.test.tmp2.obj) for foo