[LLD] COFF: Make link order compatible with MSVC link.exe.

[ruiu]

Summary

Previously, we added files in directive sections to the symbol
table as we read the sections, so the link order was depth-first.
That's not compatible with MSVC link.exe nor the old LLD.

This patch is to queue files so that new files are added to the
end of the queue and processed last. Now addFile() doesn't parse
files nor resolve symbols. You need to call run() to process
queued files.

[pcc]

COFF/SymbolTable.cpp

289

If we move the call to run() below this loop, it should make the code a little easier to reason about, as run() will never see a symbol table that has only been partially processed by the loop.

test/COFF/order.test

2

Did you forget to add these input files?

[ruiu]

Address pcc's comments.

test/COFF/order.test

2

I reused files for an existing test.

[pcc]

COFF/SymbolTable.cpp

293

Huh, does this compile? BitcodeFiles.end() is an iterator, right?

[ruiu]

COFF/SymbolTable.cpp

293

Ah, sorry, I intended to write auto instead of size_t. (And if we make that change, all tests pass.)

[pcc]

LGTM with my suggested change.

COFF/SymbolTable.cpp

293

I don't think it is correct to compare iterators like this because the standard library may invalidate iterators if elements are appended to the vector. Can we make this use size as before?

[ruiu]

COFF/SymbolTable.cpp

293

You are correct. Updated the code to use size as before.

[pcc]

COFF/SymbolTable.cpp

290

Sorry, missed this; you need error checking here.

[ruiu]

COFF/SymbolTable.cpp

290

Feel free to do this yourself. (I could do that but I guess that would be faster.)

[pcc]

COFF/SymbolTable.cpp

290

Done

290

Done

[Eugene.Zelenko]

Committed in r240483.

COFF/Driver.h

 //===- Driver.h -----------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_COFF_DRIVER_H
 #define LLD_COFF_DRIVER_H
 
 #include "Config.h"
+#include "SymbolTable.h"
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Support/StringSaver.h"
 #include <memory>
public:
 
   // Tokenizes a given string and then parses as command line options.
   ErrorOr<llvm::opt::InputArgList> parse(StringRef S) {
     return parse(tokenize(S));
   }
 
 private:
   ErrorOr<llvm::opt::InputArgList> parse(std::vector<const char *> Argv);
-
   std::vector<const char *> tokenize(StringRef S);
 
   ErrorOr<std::vector<const char *>>
   replaceResponseFiles(std::vector<const char *>);
 
   llvm::BumpPtrAllocator AllocAux;
   llvm::BumpPtrStringSaver Alloc;
 };
 
 class LinkerDriver {
 public:
   LinkerDriver() : Alloc(AllocAux) {}
   bool link(llvm::ArrayRef<const char *> Args);
 
   // Used by the resolver to parse .drectve section contents.
-  std::error_code
-  parseDirectives(StringRef S, std::vector<std::unique_ptr<InputFile>> *Res);
+  std::error_code parseDirectives(StringRef S);
 
 private:
   llvm::BumpPtrAllocator AllocAux;
   llvm::BumpPtrStringSaver Alloc;
   ArgParser Parser;
+  SymbolTable Symtab;
 
   // Opens a file. Path has to be resolved already.
   ErrorOr<MemoryBufferRef> openFile(StringRef Path);
 
   // Searches a file from search paths.
   Optional<StringRef> findFile(StringRef Filename);
   Optional<StringRef> findLib(StringRef Filename);
   StringRef doFindFile(StringRef Filename);

COFF/Driver.cpp

static std::unique_ptr<InputFile> createFile(MemoryBufferRef MB) {
   if (Config->OutputFile == "")
     Config->OutputFile = getOutputPath(MB.getBufferIdentifier());
   return std::unique_ptr<InputFile>(new ObjectFile(MB));
 }
 
 // Parses .drectve section contents and returns a list of files
 // specified by /defaultlib.
 std::error_code
-LinkerDriver::parseDirectives(StringRef S,
-                              std::vector<std::unique_ptr<InputFile>> *Res) {
+LinkerDriver::parseDirectives(StringRef S) {
   auto ArgsOrErr = Parser.parse(S);
   if (auto EC = ArgsOrErr.getError())
     return EC;
   llvm::opt::InputArgList Args = std::move(ArgsOrErr.get());
 
   for (auto *Arg : Args) {
     switch (Arg->getOption().getID()) {
     case OPT_alternatename:
       if (auto EC = parseAlternateName(Arg->getValue()))
         return EC;
       break;
     case OPT_defaultlib:
       if (Optional<StringRef> Path = findLib(Arg->getValue())) {
         ErrorOr<MemoryBufferRef> MBOrErr = openFile(*Path);
         if (auto EC = MBOrErr.getError())
           return EC;
-        std::unique_ptr<InputFile> File = createFile(MBOrErr.get());
-        Res->push_back(std::move(File));
+        Symtab.addFile(createFile(MBOrErr.get()));
       }
       break;
     case OPT_export: {
       ErrorOr<Export> E = parseExport(Arg->getValue());
       if (auto EC = E.getError())
         return EC;
       Config->Exports.push_back(E.get());
       break;
for (StringRef Path : InputPaths) {
     ErrorOr<MemoryBufferRef> MBOrErr = openFile(Path);
     if (auto EC = MBOrErr.getError()) {
       llvm::errs() << "cannot open " << Path << ": " << EC.message() << "\n";
       return false;
     }
     Inputs.push_back(MBOrErr.get());
   }
 
-  // Create a symbol table.
-  SymbolTable Symtab;
-
   // Windows specific -- Create a resource file containing a manifest file.
   if (Config->Manifest == Configuration::Embed) {
     auto MBOrErr = createManifestRes();
     if (MBOrErr.getError())
       return false;
     std::unique_ptr<MemoryBuffer> MB = std::move(MBOrErr.get());
     Inputs.push_back(MB->getMemBufferRef());
     OwningMBs.push_back(std::move(MB)); // take ownership
if (It != Inputs.begin()) {
     std::unique_ptr<MemoryBuffer> MB = std::move(MBOrErr.get());
     Inputs = std::vector<MemoryBufferRef>(It, Inputs.end());
     Inputs.push_back(MB->getMemBufferRef());
     OwningMBs.push_back(std::move(MB)); // take ownership
   }
 
   // Parse all input files and put all symbols to the symbol table.
   // The symbol table will take care of name resolution.
-  for (MemoryBufferRef MB : Inputs) {
-    std::unique_ptr<InputFile> File = createFile(MB);
-    if (Config->Verbose)
-      llvm::outs() << "Reading " << File->getName() << "\n";
-    if (auto EC = Symtab.addFile(std::move(File))) {
-      llvm::errs() << MB.getBufferIdentifier() << ": " << EC.message() << "\n";
-      return false;
-    }
-  }
+  for (MemoryBufferRef MB : Inputs)
+    Symtab.addFile(createFile(MB));
+  if (auto EC = Symtab.run()) {
+    llvm::errs() << EC.message() << "\n";
 
   // Resolve auxiliary symbols until converge.
   // (Trying to resolve a symbol may trigger a Lazy symbol to load a new file.
   // A new file may contain a directive section to add new command line options.
   // That's why we have to repeat until converge.)
   for (;;) {
     size_t Ver = Symtab.getVersion();
 
for (;;) {
     if (Config->EntryName.empty()) {
       auto EntryOrErr = Symtab.findDefaultEntry();
       if (auto EC = EntryOrErr.getError()) {
         llvm::errs() << EC.message() << "\n";
         return false;
       }
       Config->EntryName = EntryOrErr.get();
     }
+    Symtab.addUndefined(Config->EntryName);
+
+    if (auto EC = Symtab.run()) {
+      llvm::errs() << EC.message() << "\n";
+      return false;
+    }
     if (Ver == Symtab.getVersion())
       break;
   }
 
   // Make sure we have resolved all symbols.
   if (Symtab.reportRemainingUndefines())
     return false;
 

COFF/SymbolTable.h

 // SymbolTable selects the "best" symbols if there are name
 // conflicts. For example, obviously, a defined symbol is better than
 // an undefined symbol. Or, if there's a conflict between a lazy and a
 // undefined, it'll read an archive member to read a real definition
 // to replace the lazy symbol. The logic is implemented in resolve().
 class SymbolTable {
 public:
   SymbolTable();
-  std::error_code addFile(std::unique_ptr<InputFile> File);
+  void addFile(std::unique_ptr<InputFile> File);
+  std::error_code run();
   size_t getVersion() { return Version; }
 
   // Print an error message on undefined symbols.
   bool reportRemainingUndefines();
 
   // Returns a list of chunks of selected symbols.
   std::vector<Chunk *> getChunks();
 
public:
 
   // Build a COFF object representing the combined contents of BitcodeFiles
   // and add it to the symbol table. Called after all files are added and
   // before the writer writes results to a file.
   std::error_code addCombinedLTOObject();
 
   // The writer needs to handle DLL import libraries specially in
   // order to create the import descriptor table.
-  std::vector<std::unique_ptr<ImportFile>> ImportFiles;
+  std::vector<ImportFile *> ImportFiles;
 
   // The writer needs to infer the machine type from the object files.
-  std::vector<std::unique_ptr<ObjectFile>> ObjectFiles;
+  std::vector<ObjectFile *> ObjectFiles;
 
   // Creates an Undefined symbol for a given name.
   std::error_code addUndefined(StringRef Name);
 
   // Rename From -> To in the symbol table.
   std::error_code rename(StringRef From, StringRef To);
 
 private:
-  std::error_code addDirectives(InputFile *File);
-
   std::error_code resolve(SymbolBody *Body);
   std::error_code resolveLazy(StringRef Name);
   std::error_code addMemberFile(Lazy *Body);
   ErrorOr<ObjectFile *> createLTOObject(llvm::LTOCodeGenerator *CG);
 
   std::unordered_map<StringRef, Symbol *> Symtab;
-  std::vector<std::unique_ptr<ArchiveFile>> ArchiveFiles;
-  std::vector<std::unique_ptr<BitcodeFile>> BitcodeFiles;
+  std::vector<std::unique_ptr<InputFile>> Files;
+  size_t FileIdx = 0;
+  std::vector<ArchiveFile *> ArchiveFiles;
+  std::vector<BitcodeFile *> BitcodeFiles;
   std::unique_ptr<MemoryBuffer> LTOMB;
   llvm::BumpPtrAllocator Alloc;
 
   // This variable is incremented every time Symtab is updated.
   size_t Version = 0;
 };
 
 } // namespace coff
 } // namespace lld
 
 #endif

COFF/SymbolTable.cpp

 namespace coff {
 
 SymbolTable::SymbolTable() {
   resolve(new (Alloc) DefinedAbsolute("__ImageBase", Config->ImageBase));
   if (!Config->EntryName.empty())
     resolve(new (Alloc) Undefined(Config->EntryName));
 }
 
-std::error_code SymbolTable::addFile(std::unique_ptr<InputFile> File) {
-  if (auto EC = File->parse())
+void SymbolTable::addFile(std::unique_ptr<InputFile> File) {
+  Files.push_back(std::move(File));
+}
+
+std::error_code SymbolTable::run() {
+  while (FileIdx < Files.size()) {
+    InputFile *F = Files[FileIdx++].get();
+    if (Config->Verbose)
+      llvm::outs() << "Reading " << F->getShortName() << "\n";
+    if (auto EC = F->parse())
       return EC;
-  InputFile *F = File.release();
     if (auto *P = dyn_cast<ObjectFile>(F)) {
-    ObjectFiles.emplace_back(P);
+      ObjectFiles.push_back(P);
     } else if (auto *P = dyn_cast<ArchiveFile>(F)) {
-    ArchiveFiles.emplace_back(P);
+      ArchiveFiles.push_back(P);
     } else if (auto *P = dyn_cast<BitcodeFile>(F)) {
-    BitcodeFiles.emplace_back(P);
+      BitcodeFiles.push_back(P);
     } else {
-    ImportFiles.emplace_back(cast<ImportFile>(F));
+      ImportFiles.push_back(cast<ImportFile>(F));
     }
 
     for (SymbolBody *B : F->getSymbols())
       if (B->isExternal())
         if (auto EC = resolve(B))
           return EC;
 
     // If a object file contains .drectve section,
     // read that and add files listed there.
-  return addDirectives(F);
-}
-
-std::error_code SymbolTable::addDirectives(InputFile *File) {
-  StringRef S = File->getDirectives();
-  if (S.empty())
-    return std::error_code();
-  std::vector<std::unique_ptr<InputFile>> Libs;
-  if (auto EC = Driver->parseDirectives(S, &Libs))
+    StringRef S = F->getDirectives();
+    if (!S.empty())
+      if (auto EC = Driver->parseDirectives(S))
         return EC;
-  for (std::unique_ptr<InputFile> &Lib : Libs) {
-    if (Config->Verbose) {
-      llvm::outs() << "Reading " << Lib->getName()
-                   << " for " << File->getName() << "\n";
-    }
-    addFile(std::move(Lib));
   }
   return std::error_code();
 }
 
 bool SymbolTable::reportRemainingUndefines() {
   bool Ret = false;
   for (auto &I : Symtab) {
     Symbol *Sym = I.second;
std::error_code SymbolTable::addMemberFile(Lazy *Body) {
 
   // getMember returns an empty buffer if the member was already
   // read from the library.
   if (!File)
     return std::error_code();
   if (Config->Verbose)
     llvm::outs() << "Loaded " << File->getShortName() << " for "
                  << Body->getName() << "\n";
-  return addFile(std::move(File));
+  addFile(std::move(File));
+  return std::error_code();
 }
 
 std::vector<Chunk *> SymbolTable::getChunks() {
   std::vector<Chunk *> Res;
-  for (std::unique_ptr<ObjectFile> &File : ObjectFiles) {
+  for (ObjectFile *File : ObjectFiles) {
     std::vector<Chunk *> &V = File->getChunks();
     Res.insert(Res.end(), V.begin(), V.end());
   }
   return Res;
 }
 
 Defined *SymbolTable::find(StringRef Name) {
   auto It = Symtab.find(Name);
   if (It == Symtab.end())
     return nullptr;
   if (auto *Def = dyn_cast<Defined>(It->second->Body))
     return Def;
   return nullptr;
 }
 
 std::error_code SymbolTable::resolveLazy(StringRef Name) {
   auto It = Symtab.find(Name);
-  if (It != Symtab.end())
-    if (auto *B = dyn_cast<Lazy>(It->second->Body))
-      return addMemberFile(B);
+  if (It == Symtab.end())
+    return std::error_code();
+  if (auto *B = dyn_cast<Lazy>(It->second->Body)) {
+    if (auto EC = addMemberFile(B))
+      return EC;
+    return run();
+  }
   return std::error_code();
 }
 
 // Windows specific -- Link default entry point name.
 ErrorOr<StringRef> SymbolTable::findDefaultEntry() {
   // If it's DLL, the rule is easy.
   if (Config->DLL) {
     StringRef Sym = "_DllMainCRTStartup";
std::error_code SymbolTable::addCombinedLTOObject() {
   // Create an object file and add it to the symbol table by replacing any
   // DefinedBitcode symbols with the definitions in the object file.
   LTOCodeGenerator CG;
   auto FileOrErr = createLTOObject(&CG);
   if (auto EC = FileOrErr.getError())
     return EC;
   ObjectFile *Obj = FileOrErr.get();
 
+  // Skip the combined object file as the file is processed below
+  // rather than by run().
+  ++FileIdx;
+
   for (SymbolBody *Body : Obj->getSymbols()) {
     if (!Body->isExternal())
       continue;
     // Find an existing Symbol. We should not see any new undefined symbols at
     // this point.
     StringRef Name = Body->getName();
     Symbol *&Sym = Symtab[Name];
     if (!Sym) {
if (isa<DefinedBitcode>(Sym->Body)) {
       if (comp == 0) {
         llvm::errs() << "LTO: unexpected duplicate symbol: " << Name << "\n";
         return make_error_code(LLDError::BrokenFile);
       }
     }
 
     // We may see new references to runtime library symbols such as __chkstk
     // here. These symbols must be wholly defined in non-bitcode files.
-    if (auto *B = dyn_cast<Lazy>(Sym->Body)) {
-      size_t NumBitcodeFiles = BitcodeFiles.size();
-      if (auto EC = addMemberFile(B))
-        return EC;
-      if (BitcodeFiles.size() != NumBitcodeFiles) {
-        llvm::errs()
-            << "LTO: late loaded symbol created new bitcode reference: " << Name
-            << "\n";
-        return make_error_code(LLDError::BrokenFile);
-      }
-    }
-  }
+    if (auto *B = dyn_cast<Lazy>(Sym->Body))
+      addMemberFile(B);
+  }
+
+  size_t End = BitcodeFiles.end();
+  if (auto EC = run())
+  if (End != BitcodeFiles.end()) {
+    llvm::errs() << "LTO: late loaded symbol created new bitcode reference\n";
 
   // New runtime library symbol references may have created undefined references.
   if (reportRemainingUndefines())
     return make_error_code(LLDError::BrokenFile);
   return std::error_code();
 }
 
 // Combine and compile bitcode files and then return the result
 // as a regular COFF object file.
 ErrorOr<ObjectFile *> SymbolTable::createLTOObject(LTOCodeGenerator *CG) {
   // All symbols referenced by non-bitcode objects must be preserved.
-  for (std::unique_ptr<ObjectFile> &File : ObjectFiles)
+  for (ObjectFile *File : ObjectFiles)
     for (SymbolBody *Body : File->getSymbols())
       if (auto *S = dyn_cast<DefinedBitcode>(Body->getReplacement()))
         CG->addMustPreserveSymbol(S->getName());
 
   // Likewise for bitcode symbols which we initially resolved to non-bitcode.
-  for (std::unique_ptr<BitcodeFile> &File : BitcodeFiles)
+  for (BitcodeFile *File : BitcodeFiles)
     for (SymbolBody *Body : File->getSymbols())
       if (isa<DefinedBitcode>(Body) &&
           !isa<DefinedBitcode>(Body->getReplacement()))
         CG->addMustPreserveSymbol(Body->getName());
 
   // Likewise for other symbols that must be preserved.
   for (StringRef Name : Config->GCRoots)
     if (isa<DefinedBitcode>(Symtab[Name]->Body))
       CG->addMustPreserveSymbol(Name);
 
   CG->setModule(BitcodeFiles[0]->releaseModule());
   for (unsigned I = 1, E = BitcodeFiles.size(); I != E; ++I)
     CG->addModule(BitcodeFiles[I]->getModule());
 
   std::string ErrMsg;
   LTOMB = CG->compile(false, false, false, ErrMsg); // take MB ownership
   if (!LTOMB) {
     llvm::errs() << ErrMsg << '\n';
     return make_error_code(LLDError::BrokenFile);
   }
-  auto Obj = new ObjectFile(LTOMB->getMemBufferRef());
-  ObjectFiles.emplace_back(Obj);
+  auto *Obj = new ObjectFile(LTOMB->getMemBufferRef());
+  Files.emplace_back(Obj);
+  ObjectFiles.push_back(Obj);
   if (auto EC = Obj->parse())
     return EC;
   return Obj;
 }
 
 } // namespace coff
 } // namespace lld

COFF/Writer.cpp

 // Create .idata section for the DLL-imported symbol table.
 // The format of this section is inherently Windows-specific.
 // IdataContents class abstracted away the details for us,
 // so we just let it create chunks and add them to the section.
 void Writer::createImportTables() {
   if (Symtab->ImportFiles.empty())
     return;
   OutputSection *Text = createSection(".text");
-  for (std::unique_ptr<ImportFile> &File : Symtab->ImportFiles) {
+  for (ImportFile *File : Symtab->ImportFiles) {
     for (SymbolBody *B : File->getSymbols()) {
       auto *Import = dyn_cast<DefinedImportData>(B);
       if (!Import) {
         // Linker-created function thunks for DLL symbols are added to
         // .text section.
         Text->addChunk(cast<DefinedImportThunk>(B)->getChunk());
         continue;
       }
for (OutputSection *Sec : OutputSections) {
     FileOff += RoundUpToAlignment(Sec->getRawSize(), FileAlignment);
   }
   SizeOfImage = SizeOfHeaders + RoundUpToAlignment(RVA - 0x1000, PageSize);
   FileSize = SizeOfHeaders +
              RoundUpToAlignment(FileOff - SizeOfHeaders, FileAlignment);
 }
 
 static MachineTypes
-inferMachineType(std::vector<std::unique_ptr<ObjectFile>> &ObjectFiles) {
-  for (std::unique_ptr<ObjectFile> &File : ObjectFiles) {
+inferMachineType(const std::vector<ObjectFile *> &Files) {
+  for (ObjectFile *F : Files) {
     // Try to infer machine type from the magic byte of the object file.
-    auto MT = static_cast<MachineTypes>(File->getCOFFObj()->getMachine());
+    auto MT = static_cast<MachineTypes>(F->getCOFFObj()->getMachine());
     if (MT != IMAGE_FILE_MACHINE_UNKNOWN)
       return MT;
   }
   return IMAGE_FILE_MACHINE_UNKNOWN;
 }
 
 void Writer::writeHeader() {
   // Write DOS stub

test/COFF/order.test

+# RUN: yaml2obj < %p/Inputs/include1a.yaml > %t1.obj
+# RUN: yaml2obj < %p/Inputs/include1b.yaml > %t2.obj
+# RUN: yaml2obj < %p/Inputs/include1c.yaml > %t3.obj
+# RUN: rm -f %t2.lib %t3.lib
+# RUN: llvm-ar cru %t2.lib %t2.obj
+# RUN: llvm-ar cru %t3.lib %t3.obj
+# RUN: lld -flavor link2 /out:%t.exe %t1.obj %t2.lib %t3.obj %t3.lib /verbose >& %t.log
+# RUN: FileCheck %s < %t.log
+
+CHECK: order.test.tmp1.obj
+CHECK: order.test.tmp2.lib
+CHECK: order.test.tmp3.obj
+CHECK: order.test.tmp3.lib
+CHECK: order.test.tmp2.lib(order.test.tmp2.obj) for foo