[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

3 files changed, 230 insertions, 2 deletions

diff --git a/include/clang/Tooling/DependencyScanning/DependencyScanningFilesystem.h b/include/clang/Tooling/DependencyScanning/DependencyScanningFilesystem.h
new file mode 100644
index 0000000000..cc78a587e4
--- /dev/null
+++ b/include/clang/Tooling/DependencyScanning/DependencyScanningFilesystem.h
@@ -0,0 +1,168 @@
+//===- DependencyScanningFilesystem.h - clang-scan-deps fs ===---*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_FILESYSTEM_H
+#define LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_FILESYSTEM_H
+
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringSet.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/ErrorOr.h"
+#include "llvm/Support/VirtualFileSystem.h"
+#include <mutex>
+
+namespace clang {
+namespace tooling {
+namespace dependencies {
+
+/// An in-memory representation of a file system entity that is of interest to
+/// the dependency scanning filesystem.
+///
+/// It represents one of the following:
+/// - an opened source file with minimized contents and a stat value.
+/// - an opened source file with original contents and a stat value.
+/// - a directory entry with its stat value.
+/// - an error value to represent a file system error.
+/// - a placeholder with an invalid stat indicating a not yet initialized entry.
+class CachedFileSystemEntry {
+public:
+  /// Default constructor creates an entry with an invalid stat.
+  CachedFileSystemEntry() : MaybeStat(llvm::vfs::Status()) {}
+
+  CachedFileSystemEntry(std::error_code Error) : MaybeStat(std::move(Error)) {}
+
+  /// Create an entry that represents an opened source file with minimized or
+  /// original contents.
+  ///
+  /// The filesystem opens the file even for `stat` calls open to avoid the
+  /// issues with stat + open of minimized files that might lead to a
+  /// mismatching size of the file. If file is not minimized, the full file is
+  /// read and copied into memory to ensure that it's not memory mapped to avoid
+  /// running out of file descriptors.
+  static CachedFileSystemEntry createFileEntry(StringRef Filename,
+                                               llvm::vfs::FileSystem &FS,
+                                               bool Minimize = true);
+
+  /// Create an entry that represents a directory on the filesystem.
+  static CachedFileSystemEntry createDirectoryEntry(llvm::vfs::Status &&Stat);
+
+  /// \returns True if the entry is valid.
+  bool isValid() const { return !MaybeStat || MaybeStat->isStatusKnown(); }
+
+  /// \returns The error or the file's contents.
+  llvm::ErrorOr<StringRef> getContents() const {
+    if (!MaybeStat)
+      return MaybeStat.getError();
+    assert(!MaybeStat->isDirectory() && "not a file");
+    assert(isValid() && "not initialized");
+    return StringRef(Contents);
+  }
+
+  /// \returns The error or the status of the entry.
+  llvm::ErrorOr<llvm::vfs::Status> getStatus() const {
+    assert(isValid() && "not initialized");
+    return MaybeStat;
+  }
+
+  /// \returns the name of the file.
+  StringRef getName() const {
+    assert(isValid() && "not initialized");
+    return MaybeStat->getName();
+  }
+
+  CachedFileSystemEntry(CachedFileSystemEntry &&) = default;
+  CachedFileSystemEntry &operator=(CachedFileSystemEntry &&) = default;
+
+  CachedFileSystemEntry(const CachedFileSystemEntry &) = delete;
+  CachedFileSystemEntry &operator=(const CachedFileSystemEntry &) = delete;
+
+private:
+  llvm::ErrorOr<llvm::vfs::Status> MaybeStat;
+  // Store the contents in a small string to allow a
+  // move from the small string for the minimized contents.
+  // Note: small size of 1 allows us to store an empty string with an implicit
+  // null terminator without any allocations.
+  llvm::SmallString<1> Contents;
+};
+
+/// This class is a shared cache, that caches the 'stat' and 'open' calls to the
+/// underlying real file system.
+///
+/// It is sharded based on the hash of the key to reduce the lock contention for
+/// the worker threads.
+class DependencyScanningFilesystemSharedCache {
+public:
+  struct SharedFileSystemEntry {
+    std::mutex ValueLock;
+    CachedFileSystemEntry Value;
+  };
+
+  DependencyScanningFilesystemSharedCache();
+
+  /// 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.
+  SharedFileSystemEntry &get(StringRef Key);
+
+private:
+  struct CacheShard {
+    std::mutex CacheLock;
+    llvm::StringMap<SharedFileSystemEntry, llvm::BumpPtrAllocator> Cache;
+  };
+  std::unique_ptr<CacheShard[]> CacheShards;
+  unsigned NumShards;
+};
+
+/// A virtual file system optimized for the dependency discovery.
+///
+/// It is primarily designed to work with source files whose contents was was
+/// preprocessed to remove any tokens that are unlikely to affect the dependency
+/// computation.
+///
+/// This is not a thread safe VFS. A single instance is meant to be used only in
+/// one thread. Multiple instances are allowed to service multiple threads
+/// running in parallel.
+class DependencyScanningWorkerFilesystem : public llvm::vfs::ProxyFileSystem {
+public:
+  DependencyScanningWorkerFilesystem(
+      DependencyScanningFilesystemSharedCache &SharedCache,
+      IntrusiveRefCntPtr<llvm::vfs::FileSystem> FS)
+      : ProxyFileSystem(std::move(FS)), SharedCache(SharedCache) {}
+
+  llvm::ErrorOr<llvm::vfs::Status> status(const Twine &Path) override;
+  llvm::ErrorOr<std::unique_ptr<llvm::vfs::File>>
+  openFileForRead(const Twine &Path) override;
+
+  /// The set of files that should not be minimized.
+  llvm::StringSet<> IgnoredFiles;
+
+private:
+  void setCachedEntry(StringRef Filename, const CachedFileSystemEntry *Entry) {
+    bool IsInserted = Cache.try_emplace(Filename, Entry).second;
+    (void)IsInserted;
+    assert(IsInserted && "local cache is updated more than once");
+  }
+
+  const CachedFileSystemEntry *getCachedEntry(StringRef Filename) {
+    auto It = Cache.find(Filename);
+    return It == Cache.end() ? nullptr : It->getValue();
+  }
+
+  DependencyScanningFilesystemSharedCache &SharedCache;
+  /// The local cache is used by the worker thread to cache file system queries
+  /// locally instead of querying the global cache every time.
+  llvm::StringMap<const CachedFileSystemEntry *, llvm::BumpPtrAllocator> Cache;
+};
+
+} // end namespace dependencies
+} // end namespace tooling
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_FILESYSTEM_H
diff --git a/include/clang/Tooling/DependencyScanning/DependencyScanningService.h b/include/clang/Tooling/DependencyScanning/DependencyScanningService.h
new file mode 100644
index 0000000000..0dde0ad35d
--- /dev/null
+++ b/include/clang/Tooling/DependencyScanning/DependencyScanningService.h
@@ -0,0 +1,55 @@
+//===- DependencyScanningService.h - clang-scan-deps service ===-*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_SERVICE_H
+#define LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_SERVICE_H
+
+#include "clang/Tooling/DependencyScanning/DependencyScanningFilesystem.h"
+
+namespace clang {
+namespace tooling {
+namespace dependencies {
+
+/// The mode in which the dependency scanner will operate to find the
+/// dependencies.
+enum class ScanningMode {
+  /// This mode is used to compute the dependencies by running the preprocessor
+  /// over
+  /// the unmodified source files.
+  CanonicalPreprocessing,
+
+  /// This mode is used to compute the dependencies by running the preprocessor
+  /// over
+  /// the source files that have been minimized to contents that might affect
+  /// the dependencies.
+  MinimizedSourcePreprocessing
+};
+
+/// The dependency scanning service contains the shared state that is used by
+/// the invidual dependency scanning workers.
+class DependencyScanningService {
+public:
+  DependencyScanningService(ScanningMode Mode);
+
+  ScanningMode getMode() const { return Mode; }
+
+  DependencyScanningFilesystemSharedCache &getSharedCache() {
+    return SharedCache;
+  }
+
+private:
+  const ScanningMode Mode;
+  /// The global file system cache.
+  DependencyScanningFilesystemSharedCache SharedCache;
+};
+
+} // end namespace dependencies
+} // end namespace tooling
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_SERVICE_H
diff --git a/include/clang/Tooling/DependencyScanning/DependencyScanningWorker.h b/include/clang/Tooling/DependencyScanning/DependencyScanningWorker.h
index 3ea261a30d..79c652ef5a 100644
--- a/include/clang/Tooling/DependencyScanning/DependencyScanningWorker.h
+++ b/include/clang/Tooling/DependencyScanning/DependencyScanningWorker.h
@@ -10,6 +10,7 @@
 #define LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_WORKER_H
 
 #include "clang/Basic/DiagnosticOptions.h"
+#include "clang/Basic/FileManager.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Frontend/PCHContainerOperations.h"
 #include "clang/Tooling/CompilationDatabase.h"
@@ -21,6 +22,9 @@ namespace clang {
 namespace tooling {
 namespace dependencies {
 
+class DependencyScanningService;
+class DependencyScanningWorkerFilesystem;
+
 /// An individual dependency scanning worker that is able to run on its own
 /// thread.
 ///
@@ -29,7 +33,7 @@ namespace dependencies {
 /// using the regular processing run.
 class DependencyScanningWorker {
 public:
-  DependencyScanningWorker();
+  DependencyScanningWorker(DependencyScanningService &Service);
 
   /// Print out the dependency information into a string using the dependency
   /// file format that is specified in the options (-MD is the default) and
@@ -45,10 +49,11 @@ private:
   IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts;
   std::shared_ptr<PCHContainerOperations> PCHContainerOps;
 
+  llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> RealFS;
   /// The file system that is used by each worker when scanning for
   /// dependencies. This filesystem persists accross multiple compiler
   /// invocations.
-  llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> WorkerFS;
+  llvm::IntrusiveRefCntPtr<DependencyScanningWorkerFilesystem> DepFS;
 };
 
 } // end namespace dependencies