Fix /WholeArchive bug.

[ruiu]

Summary

lld-link foo.lib /wholearchive:foo.lib should work the same way as
lld-link /wholearchive:foo.lib foo.lib. Previously, /wholearchive in
the former case was ignored.

[rnk]

lld/COFF/Driver.cpp

1234 ↗

(On Diff #149221)

I think we need to canonicalize the path a little to ensure that this works on case insensitive file systems:
$ lld-link foo.lib -wholearchive:Foo.lib

We shouldn't enqueue the same file twice, right?

Also, maybe we should just enqueue all whole archive inputs in this loop, up front, and then only process inputs later if the input wasn't already added as a whole archive input.

1234 ↗

(On Diff #149221)

I guess to make it easy to write a cross-platform test for path canonicalization, the test could use:
$ lld-link ./foo.lib -wholearchive:foo.lib

1242 ↗

(On Diff #149221)

I don't think Args.hasArg(OPT_wholearchive_flag) is the right check here, that asks if a whole archive flag appears anywhere on the command line, not if this particular flag is whole archive.

[ruiu]

• address review comments

[ruiu]

lld/COFF/Driver.cpp

1234 ↗

(On Diff #149221)

We shouldn't generally add the same file more than once. Added code to do that check.

1242 ↗

(On Diff #149221)

This expression correctly checks for that condition, no?

[rnk]

lld/COFF/Driver.cpp

134 ↗

(On Diff #149364)

I think O(n**2) stats on input object files is going to be too much. Once we have the FD, you can do fs::getUniqueId(FD) to get the inode number, and then build a set of those. I guess if it's not a file MemoryBuffer, don't do the inode check. It probably comes from a whole archive.

1248–1249 ↗

(On Diff #149364)

sys::fs::equivalent internally opens and closes a file handle for the purpose of doing a stat and comparing inodes. This will end up doing O(inputs * wholearchiveinputs) equivalency tests, and linkers have many input object files. Is there a way to avoid that?

1242 ↗

(On Diff #149221)

I see, I didn't understand how OPT_wholearchive_flag vs. file worked.

[ruiu]

lld/COFF/Driver.cpp

1248–1249 ↗

(On Diff #149364)

That's right, but I don't think there's a way to avoid that unless we implement some OS-dependent logic on our side. How operating system normalize pathname components depends on the operating system and the file system, and I believe the only reliable way to do that is to ask about it to the system.

Maybe we could cache stat's results along with filenames to reduce the number of system calls, but I'm not sure if we need it. If it turns out to be too slow, we could optimize, but probably we should do that later when it becomes a real problem.

In reality, what is the largest number of files you can think of you want to pass to the linker? For hundreds of files, this is probably fine. If you pass thousands of files, this is probably slow.

[smeenai]

lld/COFF/Driver.cpp

1248–1249 ↗

(On Diff #149364)

We have a library that's built from ~5,000 object files, so we care about the performance here :) I can try to get some numbers later today.

[ruiu]

I don't need the exact number as long as it is more than 5,000. :) I'll try to optimize this patch for a large number of input files.

[rnk]

lld/COFF/Driver.cpp

1248–1249 ↗

(On Diff #149364)

Right, O(n) stats should be fine, just use llvm::sys::fs::getUniqueId or whatever it's called, and it will be fine. That gets the inode (or its local equivalent).

[ruiu]

• cache stat() results

[ruiu]

lld/COFF/Driver.cpp

134 ↗

(On Diff #149364)

Since this is a MemoryBuffer and not a MemoryBufferRef, I think anything that comes to this function is a file and not a slice of a file.

[rnk]

lgtm

Sorry this got lost.

[smeenai]

lld/COFF/Driver.cpp

791 ↗

(On Diff #149509)

Typo: wrapper

[smeenai]

This diff results in a 30% link time regression for us (5.3 seconds to 6.8 seconds) when linking ~5,000 input files together. This is when cross-compiling on Linux; the results would probably be even worse on Windows, where I believe stat/the filesystem in general is slower.

Is there any way to make this less expensive? I notice we still have the O(n^2) loop comparing every input file to every other input file (using a cached stat result, but still). @rnk had previously suggested building up a set out of inode numbers, which should be O(n) instead; are there problems with that approach?

[ruiu]

Let me try. I'll make a change and upload shortly.

[ruiu]

• Remove O(n^2)-ness.

[smeenai]

This new version is much better; there doesn't actually appear to be any performance difference for my test case at all now (barring noise). Thank you!

[rnk]

lgtm

[rnk]

lld/trunk/COFF/Driver.cpp

1249–1250

We forgot to call findFile here. I'll go ahead and fix that. This caused https://crbug.com/852679

lld/trunk/COFF/Driver.h

 #include "lld/Common/Reproduce.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Option/ArgList.h"
+#include "llvm/Support/FileSystem.h"
 #include "llvm/Support/TarWriter.h"
 #include <memory>
 #include <set>
 #include <vector>
 
 namespace lld {
 namespace coff {
 
private:
   StringRef doFindFile(StringRef Filename);
   StringRef doFindLib(StringRef Filename);
 
   // Parses LIB environment which contains a list of search paths.
   void addLibSearchPaths();
 
   // Library search path. The first element is always "" (current directory).
   std::vector<StringRef> SearchPaths;
-  std::set<std::string> VisitedFiles;
+
+  // We don't want to add the same file more than once.
+  // Files are uniquified by their filesystem and file number.
+  std::set<llvm::sys::fs::UniqueID> VisitedFiles;
+
   std::set<std::string> VisitedLibs;
 
   Symbol *addUndefined(StringRef Sym);
   StringRef mangle(StringRef Sym);
 
   // Windows specific -- "main" is not the only main function in Windows.
   // You can choose one from these four -- {w,}{WinMain,main}.
   // There are four different entry point functions for them,

lld/trunk/COFF/Driver.cpp

if (!HasExt) {
       Path.append(".obj");
       if (sys::fs::exists(Path.str()))
         return Saver.save(Path.str());
     }
   }
   return Filename;
 }
 
+static Optional<sys::fs::UniqueID> getUniqueID(StringRef Path) {
+  sys::fs::UniqueID Ret;
+  if (sys::fs::getUniqueID(Path, Ret))
+    return None;
+  return Ret;
+}
+
 // Resolves a file path. This never returns the same path
 // (in that case, it returns None).
 Optional<StringRef> LinkerDriver::findFile(StringRef Filename) {
   StringRef Path = doFindFile(Filename);
-  bool Seen = !VisitedFiles.insert(Path.lower()).second;
+
+  if (Optional<sys::fs::UniqueID> ID = getUniqueID(Path)) {
+    bool Seen = !VisitedFiles.insert(*ID).second;
     if (Seen)
       return None;
+  }
+
   if (Path.endswith_lower(".lib"))
     VisitedLibs.insert(sys::path::filename(Path));
   return Path;
 }
 
 // Find library file from search path.
 StringRef LinkerDriver::doFindLib(StringRef Filename) {
   // Add ".lib" to Filename if that has no file extension.
   bool HasExt = Filename.contains('.');
   if (!HasExt)
     Filename = Saver.save(Filename + ".lib");
   return doFindFile(Filename);
 }
 
 // Resolves a library path. /nodefaultlib options are taken into
 // consideration. This never returns the same path (in that case,
 // it returns None).
 Optional<StringRef> LinkerDriver::findLib(StringRef Filename) {
   if (Config->NoDefaultLibAll)
     return None;
   if (!VisitedLibs.insert(Filename.lower()).second)
     return None;
+
   StringRef Path = doFindLib(Filename);
   if (Config->NoDefaultLibs.count(Path))
     return None;
-  if (!VisitedFiles.insert(Path.lower()).second)
+
+  if (Optional<sys::fs::UniqueID> ID = getUniqueID(Path))
+    if (!VisitedFiles.insert(*ID).second)
       return None;
   return Path;
 }
 
 // Parses LIB environment which contains a list of search paths.
 void LinkerDriver::addLibSearchPaths() {
   Optional<std::string> EnvOpt = Process::GetEnv("LIB");
   if (!EnvOpt.hasValue())
     return;
if (Config->Incremental && Config->DoICF) {
     warn("ignoring '/incremental' because ICF is enabled; use '/opt:noicf' to "
          "disable");
     Config->Incremental = false;
   }
 
   if (errorCount())
     return;
 
-  bool WholeArchiveFlag = Args.hasArg(OPT_wholearchive_flag);
+  std::set<sys::fs::UniqueID> WholeArchives;
+  for (auto *Arg : Args.filtered(OPT_wholearchive_file))
+    if (Optional<sys::fs::UniqueID> ID = getUniqueID(Arg->getValue()))
+      WholeArchives.insert(*ID);
+
+  // A predicate returning true if a given path is an argument for
+  // /wholearchive:, or /wholearchive is enabled globally.
+  // This function is a bit tricky because "foo.obj /wholearchive:././foo.obj"
+  // needs to be handled as "/wholearchive:foo.obj foo.obj".
+  auto IsWholeArchive = [&](StringRef Path) -> bool {
+    if (Args.hasArg(OPT_wholearchive_flag))
+      return true;
+    if (Optional<sys::fs::UniqueID> ID = getUniqueID(Path))
+      return WholeArchives.count(*ID);
+    return false;
+  };
+
   // Create a list of input files. Files can be given as arguments
   // for /defaultlib option.
-  std::vector<MemoryBufferRef> MBs;
-  for (auto *Arg : Args.filtered(OPT_INPUT, OPT_wholearchive_file)) {
-    switch (Arg->getOption().getID()) {
-    case OPT_INPUT:
-      if (Optional<StringRef> Path = findFile(Arg->getValue()))
-        enqueuePath(*Path, WholeArchiveFlag);
-      break;
-    case OPT_wholearchive_file:
-      if (Optional<StringRef> Path = findFile(Arg->getValue()))
-        enqueuePath(*Path, true);
-      break;
-    }
-  }
+  for (auto *Arg : Args.filtered(OPT_INPUT, OPT_wholearchive_file))
+      enqueuePath(*Path, IsWholeArchive(Arg->getValue()));
+
   for (auto *Arg : Args.filtered(OPT_defaultlib))
     if (Optional<StringRef> Path = findLib(Arg->getValue()))
       enqueuePath(*Path, false);
 
   // Windows specific -- Create a resource file containing a manifest file.
   if (Config->Manifest == Configuration::Embed)
     addBuffer(createManifestRes(), false);
 

lld/trunk/test/COFF/wholearchive.s

 # REQUIRES: x86
 
 # RUN: yaml2obj < %p/Inputs/export.yaml > %t.archive.obj
 # RUN: llvm-ar rcs %t.archive.lib %t.archive.obj
 # RUN: llvm-mc -triple=x86_64-windows-msvc %s -filetype=obj -o %t.main.obj
 
 # RUN: lld-link -dll -out:%t.dll -entry:main %t.main.obj -wholearchive:%t.archive.lib -implib:%t.lib
 # RUN: llvm-readobj %t.lib | FileCheck %s -check-prefix CHECK-IMPLIB
 
 # RUN: lld-link -dll -out:%t.dll -entry:main %t.main.obj -wholearchive %t.archive.lib -implib:%t.lib
 # RUN: llvm-readobj %t.lib | FileCheck %s -check-prefix CHECK-IMPLIB
 
+# RUN: lld-link -dll -out:%t.dll -entry:main %t.main.obj %t.archive.lib -wholearchive:%t.archive.lib -implib:%t.lib
+# RUN: llvm-readobj %t.lib | FileCheck %s -check-prefix CHECK-IMPLIB
+
+# RUN: mkdir -p %t.dir
+# RUN: cp %t.archive.lib %t.dir/foo.lib
+# RUN: lld-link -dll -out:%t.dll -entry:main %t.main.obj %t.dir/./foo.lib -wholearchive:%t.dir/foo.lib -implib:%t.lib
+# RUN: llvm-readobj %t.lib | FileCheck %s -check-prefix CHECK-IMPLIB
+
 # CHECK-IMPLIB: Symbol: __imp_exportfn3
 # CHECK-IMPLIB: Symbol: exportfn3
 
 .global main
 .text
 main:
   ret