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

1262

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.

1262

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

1278

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

1262

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

1278

This expression correctly checks for that condition, no?

[rnk]

lld/COFF/Driver.cpp

134

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.

1267–1268

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?

1278

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

[ruiu]

lld/COFF/Driver.cpp

1267–1268

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

1267–1268

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

1267–1268

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

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

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 ↗

(On Diff #151041)

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

lld/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:
   void enqueueTask(std::function<void()> Task);
   bool run();
 
   std::list<std::function<void()>> TaskQueue;
   std::vector<StringRef> FilePaths;
   std::vector<MemoryBufferRef> Resources;
 
   llvm::StringSet<> DirectivesExports;
+
+  bool equivalentPath(StringRef A, StringRef B);
+  llvm::sys::fs::file_status getFileStatus(StringRef Path);
+
+  // Pathnames to their stat() results. Since stat() is slow,
+  // we want to cache.
+  llvm::DenseMap<StringRef, llvm::sys::fs::file_status> StatCache;
 };
 
 // Functions below this line are defined in DriverUtils.cpp.
 
 void printHelp(const char *Argv0);
 
 // For /machine option.
 MachineTypes getMachineType(StringRef Arg);

lld/COFF/Driver.cpp

Driver->Tar->append(relativeToRoot(MBRef.getBufferIdentifier()),
                         MBRef.getBuffer());
   return MBRef;
 }
 
 void LinkerDriver::addBuffer(std::unique_ptr<MemoryBuffer> MB,
                              bool WholeArchive) {
   StringRef Filename = MB->getBufferIdentifier();
 
+  // A file shouldn't be parsed more than once even if it is
+  // represented in different paths.
+  for (StringRef Path : FilePaths) {
+    if (equivalentPath(Path, Filename)) {
+      warn(Filename + ": object specified more than once");
+      return;
+    }
+  }
+
   MemoryBufferRef MBRef = takeBuffer(std::move(MB));
   FilePaths.push_back(Filename);
 
   // File type is detected by contents, not by file extension.
   switch (identify_magic(MBRef.getBuffer())) {
   case file_magic::windows_resource:
     Resources.push_back(MBRef);
     break;
void LinkerDriver::invokeMSVC(opt::InputArgList &Args) {
   for (StringRef Path : Temps)
     sys::fs::remove(Path);
 }
 
 void LinkerDriver::enqueueTask(std::function<void()> Task) {
   TaskQueue.push_back(std::move(Task));
 }
 
+bool LinkerDriver::equivalentPath(StringRef A, StringRef B) {
+  return sys::fs::equivalent(getFileStatus(A), getFileStatus(B));
+}
+
+// A cached warpper for stat().
+sys::fs::file_status LinkerDriver::getFileStatus(StringRef Path) {
+  auto It = StatCache.find(Path);
+  if (It != StatCache.end())
+    return It->second;
+
+  // We ignore an error as we'll report it when we try to open a file.
+  sys::fs::file_status Ret;
+  sys::fs::status(Path, Ret);
+  StatCache[Path] = Ret;
+  return Ret;
+}
+
 bool LinkerDriver::run() {
   ScopedTimer T(InputFileTimer);
 
   bool DidWork = !TaskQueue.empty();
   while (!TaskQueue.empty()) {
     TaskQueue.front()();
     TaskQueue.pop_front();
   }
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);
+  // 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) {
+    if (Args.hasArg(OPT_wholearchive_flag))
+      return true;
+    for (auto *Arg : Args.filtered(OPT_wholearchive_file))
+      if (equivalentPath(Path, Arg->getValue()))
+        return true;
+    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/test/COFF/wholearchive.s

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