[clang-scan-deps] Implementation of dependency scanner over minimized sources

This commit implements the fast dependency scanning mode in clang-scan-deps: the
preprocessing is done on files that are minimized using the dependency directives source minimizer.

A shared file system cache is used to ensure that the file system requests and source minimization
is performed only once. The cache assumes that the underlying filesystem won't change during the course
of the scan (or if it will, it will not affect the output), and it can't be evicted. This means that the
service and workers can be used for a single run of a dependency scanner, and can't be reused across multiple,
incremental runs. This is something that we'll most likely support in the future though.
Note that the driver still utilizes the underlying real filesystem.

This commit is also still missing the fast skipped PP block skipping optimization that I mentioned at EuroLLVM talk.
Additionally, the file manager is still not reused by the threads as well.

Differential Revision: https://reviews.llvm.org/D63907

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@368086 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 279 insertions, 13 deletions

diff --git a/lib/Tooling/DependencyScanning/CMakeLists.txt b/lib/Tooling/DependencyScanning/CMakeLists.txt
index 699954d26d..0b2c882e59 100644
--- a/lib/Tooling/DependencyScanning/CMakeLists.txt
+++ b/lib/Tooling/DependencyScanning/CMakeLists.txt
@@ -4,6 +4,8 @@ set(LLVM_LINK_COMPONENTS
   )
 
 add_clang_library(clangDependencyScanning
+  DependencyScanningFilesystem.cpp
+  DependencyScanningService.cpp
   DependencyScanningWorker.cpp
 
   DEPENDS
diff --git a/lib/Tooling/DependencyScanning/DependencyScanningFilesystem.cpp b/lib/Tooling/DependencyScanning/DependencyScanningFilesystem.cpp
new file mode 100644
index 0000000000..d26a97e182
--- /dev/null
+++ b/lib/Tooling/DependencyScanning/DependencyScanningFilesystem.cpp
@@ -0,0 +1,218 @@
+//===- DependencyScanningFilesystem.cpp - clang-scan-deps fs --------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/DependencyScanning/DependencyScanningFilesystem.h"
+#include "clang/Lex/DependencyDirectivesSourceMinimizer.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Threading.h"
+
+using namespace clang;
+using namespace tooling;
+using namespace dependencies;
+
+CachedFileSystemEntry CachedFileSystemEntry::createFileEntry(
+    StringRef Filename, llvm::vfs::FileSystem &FS, bool Minimize) {
+  // Load the file and its content from the file system.
+  llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>> MaybeFile =
+      FS.openFileForRead(Filename);
+  if (!MaybeFile)
+    return MaybeFile.getError();
+  llvm::ErrorOr<llvm::vfs::Status> Stat = (*MaybeFile)->status();
+  if (!Stat)
+    return Stat.getError();
+
+  llvm::vfs::File &F = **MaybeFile;
+  llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> MaybeBuffer =
+      F.getBuffer(Stat->getName());
+  if (!MaybeBuffer)
+    return MaybeBuffer.getError();
+
+  llvm::SmallString<1024> MinimizedFileContents;
+  // Minimize the file down to directives that might affect the dependencies.
+  const auto &Buffer = *MaybeBuffer;
+  SmallVector<minimize_source_to_dependency_directives::Token, 64> Tokens;
+  if (!Minimize || minimizeSourceToDependencyDirectives(
+                       Buffer->getBuffer(), MinimizedFileContents, Tokens)) {
+    // Use the original file unless requested otherwise, or
+    // if the minimization failed.
+    // FIXME: Propage the diagnostic if desired by the client.
+    CachedFileSystemEntry Result;
+    Result.MaybeStat = std::move(*Stat);
+    Result.Contents.reserve(Buffer->getBufferSize() + 1);
+    Result.Contents.append(Buffer->getBufferStart(), Buffer->getBufferEnd());
+    // Implicitly null terminate the contents for Clang's lexer.
+    Result.Contents.push_back('\0');
+    Result.Contents.pop_back();
+    return Result;
+  }
+
+  CachedFileSystemEntry Result;
+  size_t Size = MinimizedFileContents.size();
+  Result.MaybeStat = llvm::vfs::Status(Stat->getName(), Stat->getUniqueID(),
+                                       Stat->getLastModificationTime(),
+                                       Stat->getUser(), Stat->getGroup(), Size,
+                                       Stat->getType(), Stat->getPermissions());
+  // The contents produced by the minimizer must be null terminated.
+  assert(MinimizedFileContents.data()[MinimizedFileContents.size()] == '\0' &&
+         "not null terminated contents");
+  // Even though there's an implicit null terminator in the minimized contents,
+  // we want to temporarily make it explicit. This will ensure that the
+  // std::move will preserve it even if it needs to do a copy if the
+  // SmallString still has the small capacity.
+  MinimizedFileContents.push_back('\0');
+  Result.Contents = std::move(MinimizedFileContents);
+  // Now make the null terminator implicit again, so that Clang's lexer can find
+  // it right where the buffer ends.
+  Result.Contents.pop_back();
+  return Result;
+}
+
+CachedFileSystemEntry
+CachedFileSystemEntry::createDirectoryEntry(llvm::vfs::Status &&Stat) {
+  assert(Stat.isDirectory() && "not a directory!");
+  auto Result = CachedFileSystemEntry();
+  Result.MaybeStat = std::move(Stat);
+  return Result;
+}
+
+DependencyScanningFilesystemSharedCache::
+    DependencyScanningFilesystemSharedCache() {
+  // This heuristic was chosen using a empirical testing on a
+  // reasonably high core machine (iMacPro 18 cores / 36 threads). The cache
+  // sharding gives a performance edge by reducing the lock contention.
+  // FIXME: A better heuristic might also consider the OS to account for
+  // the different cost of lock contention on different OSes.
+  NumShards = std::max(2u, llvm::hardware_concurrency() / 4);
+  CacheShards = llvm::make_unique<CacheShard[]>(NumShards);
+}
+
+/// Returns a cache entry for the corresponding key.
+///
+/// A new cache entry is created if the key is not in the cache. This is a
+/// thread safe call.
+DependencyScanningFilesystemSharedCache::SharedFileSystemEntry &
+DependencyScanningFilesystemSharedCache::get(StringRef Key) {
+  CacheShard &Shard = CacheShards[llvm::hash_value(Key) % NumShards];
+  std::unique_lock<std::mutex> LockGuard(Shard.CacheLock);
+  auto It = Shard.Cache.try_emplace(Key);
+  return It.first->getValue();
+}
+
+llvm::ErrorOr<llvm::vfs::Status>
+DependencyScanningWorkerFilesystem::status(const Twine &Path) {
+  SmallString<256> OwnedFilename;
+  StringRef Filename = Path.toStringRef(OwnedFilename);
+
+  // Check the local cache first.
+  if (const CachedFileSystemEntry *Entry = getCachedEntry(Filename))
+    return Entry->getStatus();
+
+  // FIXME: Handle PCM/PCH files.
+  // FIXME: Handle module map files.
+
+  bool KeepOriginalSource = IgnoredFiles.count(Filename);
+  DependencyScanningFilesystemSharedCache::SharedFileSystemEntry
+      &SharedCacheEntry = SharedCache.get(Filename);
+  const CachedFileSystemEntry *Result;
+  {
+    std::unique_lock<std::mutex> LockGuard(SharedCacheEntry.ValueLock);
+    CachedFileSystemEntry &CacheEntry = SharedCacheEntry.Value;
+
+    if (!CacheEntry.isValid()) {
+      llvm::vfs::FileSystem &FS = getUnderlyingFS();
+      auto MaybeStatus = FS.status(Filename);
+      if (!MaybeStatus)
+        CacheEntry = CachedFileSystemEntry(MaybeStatus.getError());
+      else if (MaybeStatus->isDirectory())
+        CacheEntry = CachedFileSystemEntry::createDirectoryEntry(
+            std::move(*MaybeStatus));
+      else
+        CacheEntry = CachedFileSystemEntry::createFileEntry(
+            Filename, FS, !KeepOriginalSource);
+    }
+
+    Result = &CacheEntry;
+  }
+
+  // Store the result in the local cache.
+  setCachedEntry(Filename, Result);
+  return Result->getStatus();
+}
+
+namespace {
+
+/// The VFS that is used by clang consumes the \c CachedFileSystemEntry using
+/// this subclass.
+class MinimizedVFSFile final : public llvm::vfs::File {
+public:
+  MinimizedVFSFile(std::unique_ptr<llvm::MemoryBuffer> Buffer,
+                   llvm::vfs::Status Stat)
+      : Buffer(std::move(Buffer)), Stat(std::move(Stat)) {}
+
+  llvm::ErrorOr<llvm::vfs::Status> status() override { return Stat; }
+
+  const llvm::MemoryBuffer *getBufferPtr() const { return Buffer.get(); }
+
+  llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>
+  getBuffer(const Twine &Name, int64_t FileSize, bool RequiresNullTerminator,
+            bool IsVolatile) override {
+    return std::move(Buffer);
+  }
+
+  std::error_code close() override { return {}; }
+
+private:
+  std::unique_ptr<llvm::MemoryBuffer> Buffer;
+  llvm::vfs::Status Stat;
+};
+
+llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>>
+createFile(const CachedFileSystemEntry *Entry) {
+  llvm::ErrorOr<StringRef> Contents = Entry->getContents();
+  if (!Contents)
+    return Contents.getError();
+  return llvm::make_unique<MinimizedVFSFile>(
+      llvm::MemoryBuffer::getMemBuffer(*Contents, Entry->getName(),
+                                       /*RequiresNullTerminator=*/false),
+      *Entry->getStatus());
+}
+
+} // end anonymous namespace
+
+llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>>
+DependencyScanningWorkerFilesystem::openFileForRead(const Twine &Path) {
+  SmallString<256> OwnedFilename;
+  StringRef Filename = Path.toStringRef(OwnedFilename);
+
+  // Check the local cache first.
+  if (const CachedFileSystemEntry *Entry = getCachedEntry(Filename))
+    return createFile(Entry);
+
+  // FIXME: Handle PCM/PCH files.
+  // FIXME: Handle module map files.
+
+  bool KeepOriginalSource = IgnoredFiles.count(Filename);
+  DependencyScanningFilesystemSharedCache::SharedFileSystemEntry
+      &SharedCacheEntry = SharedCache.get(Filename);
+  const CachedFileSystemEntry *Result;
+  {
+    std::unique_lock<std::mutex> LockGuard(SharedCacheEntry.ValueLock);
+    CachedFileSystemEntry &CacheEntry = SharedCacheEntry.Value;
+
+    if (!CacheEntry.isValid()) {
+      CacheEntry = CachedFileSystemEntry::createFileEntry(
+          Filename, getUnderlyingFS(), !KeepOriginalSource);
+    }
+
+    Result = &CacheEntry;
+  }
+
+  // Store the result in the local cache.
+  setCachedEntry(Filename, Result);
+  return createFile(Result);
+}
diff --git a/lib/Tooling/DependencyScanning/DependencyScanningService.cpp b/lib/Tooling/DependencyScanning/DependencyScanningService.cpp
new file mode 100644
index 0000000000..48aa68218c
--- /dev/null
+++ b/lib/Tooling/DependencyScanning/DependencyScanningService.cpp
@@ -0,0 +1,16 @@
+//===- DependencyScanningService.cpp - clang-scan-deps service ------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/DependencyScanning/DependencyScanningService.h"
+
+using namespace clang;
+using namespace tooling;
+using namespace dependencies;
+
+DependencyScanningService::DependencyScanningService(ScanningMode Mode)
+    : Mode(Mode) {}
diff --git a/lib/Tooling/DependencyScanning/DependencyScanningWorker.cpp b/lib/Tooling/DependencyScanning/DependencyScanningWorker.cpp
index 4868f26637..f546719278 100644
--- a/lib/Tooling/DependencyScanning/DependencyScanningWorker.cpp
+++ b/lib/Tooling/DependencyScanning/DependencyScanningWorker.cpp
@@ -8,9 +8,11 @@
 
 #include "clang/Tooling/DependencyScanning/DependencyScanningWorker.h"
 #include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Frontend/TextDiagnosticPrinter.h"
 #include "clang/Frontend/Utils.h"
+#include "clang/Tooling/DependencyScanning/DependencyScanningService.h"
 #include "clang/Tooling/Tooling.h"
 
 using namespace clang;
@@ -62,10 +64,12 @@ private:
 /// dependency scanning for the given compiler invocation.
 class DependencyScanningAction : public tooling::ToolAction {
 public:
-  DependencyScanningAction(StringRef WorkingDirectory,
-                           std::string &DependencyFileContents)
+  DependencyScanningAction(
+      StringRef WorkingDirectory, std::string &DependencyFileContents,
+      llvm::IntrusiveRefCntPtr<DependencyScanningWorkerFilesystem> DepFS)
       : WorkingDirectory(WorkingDirectory),
-        DependencyFileContents(DependencyFileContents) {}
+        DependencyFileContents(DependencyFileContents),
+        DepFS(std::move(DepFS)) {}
 
   bool runInvocation(std::shared_ptr<CompilerInvocation> Invocation,
                      FileManager *FileMgr,
@@ -74,8 +78,6 @@ public:
     // Create a compiler instance to handle the actual work.
     CompilerInstance Compiler(std::move(PCHContainerOps));
     Compiler.setInvocation(std::move(Invocation));
-    FileMgr->getFileSystemOpts().WorkingDir = WorkingDirectory;
-    Compiler.setFileManager(FileMgr);
 
     // Don't print 'X warnings and Y errors generated'.
     Compiler.getDiagnosticOpts().ShowCarets = false;
@@ -84,6 +86,27 @@ public:
     if (!Compiler.hasDiagnostics())
       return false;
 
+    // Use the dependency scanning optimized file system if we can.
+    if (DepFS) {
+      // FIXME: Purge the symlink entries from the stat cache in the FM.
+      const CompilerInvocation &CI = Compiler.getInvocation();
+      // Add any filenames that were explicity passed in the build settings and
+      // that might be opened, as we want to ensure we don't run source
+      // minimization on them.
+      DepFS->IgnoredFiles.clear();
+      for (const auto &Entry : CI.getHeaderSearchOpts().UserEntries)
+        DepFS->IgnoredFiles.insert(Entry.Path);
+      for (const auto &Entry : CI.getHeaderSearchOpts().VFSOverlayFiles)
+        DepFS->IgnoredFiles.insert(Entry);
+
+      // Support for virtual file system overlays on top of the caching
+      // filesystem.
+      FileMgr->setVirtualFileSystem(createVFSFromCompilerInvocation(
+          CI, Compiler.getDiagnostics(), DepFS));
+    }
+
+    FileMgr->getFileSystemOpts().WorkingDir = WorkingDirectory;
+    Compiler.setFileManager(FileMgr);
     Compiler.createSourceManager(*FileMgr);
 
     // Create the dependency collector that will collect the produced
@@ -103,7 +126,8 @@ public:
 
     auto Action = llvm::make_unique<PreprocessOnlyAction>();
     const bool Result = Compiler.ExecuteAction(*Action);
-    FileMgr->clearStatCache();
+    if (!DepFS)
+      FileMgr->clearStatCache();
     return Result;
   }
 
@@ -111,16 +135,19 @@ private:
   StringRef WorkingDirectory;
   /// The dependency file will be written to this string.
   std::string &DependencyFileContents;
+  llvm::IntrusiveRefCntPtr<DependencyScanningWorkerFilesystem> DepFS;
 };
 
 } // end anonymous namespace
 
-DependencyScanningWorker::DependencyScanningWorker() {
+DependencyScanningWorker::DependencyScanningWorker(
+    DependencyScanningService &Service) {
   DiagOpts = new DiagnosticOptions();
   PCHContainerOps = std::make_shared<PCHContainerOperations>();
-  /// FIXME: Use the shared file system from the service for fast scanning
-  /// mode.
-  WorkerFS = new ProxyFileSystemWithoutChdir(llvm::vfs::getRealFileSystem());
+  RealFS = new ProxyFileSystemWithoutChdir(llvm::vfs::getRealFileSystem());
+  if (Service.getMode() == ScanningMode::MinimizedSourcePreprocessing)
+    DepFS = new DependencyScanningWorkerFilesystem(Service.getSharedCache(),
+                                                   RealFS);
 }
 
 llvm::Expected<std::string>
@@ -133,14 +160,17 @@ DependencyScanningWorker::getDependencyFile(const std::string &Input,
   llvm::raw_string_ostream DiagnosticsOS(DiagnosticOutput);
   TextDiagnosticPrinter DiagPrinter(DiagnosticsOS, DiagOpts.get());
 
-  WorkerFS->setCurrentWorkingDirectory(WorkingDirectory);
-  tooling::ClangTool Tool(CDB, Input, PCHContainerOps, WorkerFS);
+  RealFS->setCurrentWorkingDirectory(WorkingDirectory);
+  /// Create the tool that uses the underlying file system to ensure that any
+  /// file system requests that are made by the driver do not go through the
+  /// dependency scanning filesystem.
+  tooling::ClangTool Tool(CDB, Input, PCHContainerOps, RealFS);
   Tool.clearArgumentsAdjusters();
   Tool.setRestoreWorkingDir(false);
   Tool.setPrintErrorMessage(false);
   Tool.setDiagnosticConsumer(&DiagPrinter);
   std::string Output;
-  DependencyScanningAction Action(WorkingDirectory, Output);
+  DependencyScanningAction Action(WorkingDirectory, Output, DepFS);
   if (Tool.run(&Action)) {
     return llvm::make_error<llvm::StringError>(DiagnosticsOS.str(),
                                                llvm::inconvertibleErrorCode());