COFF: Cache the result of library searches.

[pcc]

Summary

File system operations were still dominating the profile on Windows. In this
case we were spending a significant amount of our time repeatedly searching
for libraries as a result of processing linker directives. Address this
by caching whether we have already found a library with a given name. For
chrome_child.dll:

Before: 10.53s
After: 6.88s

[ruiu]

LGTM. Impressive speedup! Maybe we could speed this up even more by caching directory contents we visited? I don't know how much time we still spend on file searching after this patch though.

lld/COFF/Driver.h

93

Write in two lines.

[pcc]

In D27840#624682, @ruiu wrote:

LGTM. Impressive speedup! Maybe we could speed this up even more by caching directory contents we visited? I don't know how much time we still spend on file searching after this patch though.

File system operations have now completely disappeared from the profile (other than mmap, which has already been moved off the hot path), so I think we're done optimizing our file system operations for now.

lld/COFF/Driver.h

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;
+  std::set<std::string> VisitedFiles, VisitedLibs;
 
   SymbolBody *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,
   // {w,}{WinMain,main}CRTStartup, respectively. The linker needs to

lld/COFF/Driver.cpp

 }
 
 // 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;
-  bool Seen = !VisitedFiles.insert(Path.lower()).second;
-  if (Seen)
+  if (!VisitedFiles.insert(Path.lower()).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())