[clang-scan-deps] add skip excluded conditional preprocessor block preprocessing optimization

[arphaman]

Summary

This patch adds an optimization to clang-scan-deps and clang's preprocessor that skips excluded preprocessor blocks by bumping the lexer pointer, and not lexing the tokens until reaching appropriate #else/#endif directive. The skip positions and lexer offsets are computed when the file is minimized, directly from the minimized tokens.

On an 18-core iMacPro with macOS Catalina Beta I got 10-15% speed-up from this optimization when running clang-scan-deps on the compilation database for a recent LLVM and Clang (3511 files).

[Bigcheese]

clang/include/clang/Frontend/CompilerInstance.h

256

This kinda sounds like it can be called multiple times. Is there any way you can use chained pp callbacks?

clang/tools/clang-scan-deps/ClangScanDeps.cpp

171–177

Is there any reason for this to be configurable other than for perf testing?

[arphaman]

Add support for chained PP callbacks in setAdditionalPPCallbacks.

clang/include/clang/Frontend/CompilerInstance.h

256

Good idea, I implemented support for adding multiple ones with chained callbacks.

clang/tools/clang-scan-deps/ClangScanDeps.cpp

171–177

It's just for perf-testing / verification. No other reason.

[Bigcheese]

Looking more into this I'm not sure you need the PPCallbacks. The Preprocessor should just own the PreprocessorSkippedMappings data structure and the dependency scanner can update it live.

[arphaman]

restructure the code to perform skipping directly in the preprocessor

clang/include/clang/Frontend/CompilerInstance.h

 class DiagnosticsEngine;
 class DiagnosticConsumer;
 class ExternalASTSource;
 class FileEntry;
 class FileManager;
 class FrontendAction;
 class InMemoryModuleCache;
 class Module;
+class PPCallbacks;
 class Preprocessor;
 class Sema;
 class SourceManager;
 class TargetInfo;
 
 /// CompilerInstance - Helper class for managing a single instance of the Clang
 /// compiler.
 ///
class CompilerInstance : public ModuleLoader {
   std::unique_ptr<llvm::raw_fd_ostream> NonSeekStream;
 
   /// The list of active output files.
   std::list<OutputFile> OutputFiles;
 
   /// Force an output buffer.
   std::unique_ptr<llvm::raw_pwrite_stream> OutputStream;
 
+  /// Additional PPCallbacks to add to the created preprocessor.
+  std::unique_ptr<PPCallbacks> AdditionalPPCallbacks;
+
   CompilerInstance(const CompilerInstance &) = delete;
   void operator=(const CompilerInstance &) = delete;
 public:
   explicit CompilerInstance(
       std::shared_ptr<PCHContainerOperations> PCHContainerOps =
           std::make_shared<PCHContainerOperations>(),
       InMemoryModuleCache *SharedModuleCache = nullptr);
   ~CompilerInstance() override;
public:
   bool shouldBuildGlobalModuleIndex() const;
 
   /// Set the flag indicating whether we should (re)build the global
   /// module index.
   void setBuildGlobalModuleIndex(bool Build) {
     BuildGlobalModuleIndex = Build;
   }
 
+  /// Set the additional PP callbacks that will be added to the created
+  /// preprocessor.
+  void setAdditionalPPCallbacks(std::unique_ptr<PPCallbacks> PPC);
+
   /// }
   /// @name Forwarding Methods
   /// {
 
   AnalyzerOptionsRef getAnalyzerOpts() {
     return Invocation->getAnalyzerOpts();
   }
 

clang/include/clang/Lex/DependencyDirectivesSourceMinimizer.h

struct Token {
   TokenKind K = pp_none;
 
   /// Offset into the output byte stream of where the directive begins.
   int Offset = -1;
 
   Token(TokenKind K, int Offset) : K(K), Offset(Offset) {}
 };
 
+/// Simplified token range to track the range of a potentially skippable PP
+/// directive.
+struct SkippedRange {
+  /// Offset into the output byte stream of where the skipped directive begins.
+  int Offset;
+
+  /// The number of bytes that can be skipped before the preprocessing must
+  /// resume.
+  int Length;
+};
+
+/// Computes the potential source ranges that can be skipped by the preprocessor
+/// when skipping a directive like #if, #ifdef or #elsif.
+///
+/// \returns false on success, true on error.
+bool computeSkippedRanges(ArrayRef<Token> Input,
+                          llvm::SmallVectorImpl<SkippedRange> &Range);
+
 } // end namespace minimize_source_to_dependency_directives
 
 /// Minimize the input down to the preprocessor directives that might have
 /// an effect on the dependencies for a compilation unit.
 ///
 /// This function deletes all non-preprocessor code, and strips anything that
 /// can't affect what gets included. It canonicalizes whitespace where
 /// convenient to stabilize the output against formatting changes in the input.

clang/include/clang/Lex/Lexer.h

public:
   /// the current file.
   SourceLocation getSourceLocation() override {
     return getSourceLocation(BufferPtr);
   }
 
   /// Return the current location in the buffer.
   const char *getBufferLocation() const { return BufferPtr; }
 
+  /// Returns the current lexing offset.
+  unsigned getCurrentBufferOffset() {
+    assert(BufferPtr >= BufferStart && "Invalid buffer state");
+    return BufferPtr - BufferStart;
+  }
+
+  /// Skip over \p NumBytes bytes.
+  ///
+  /// If the skip is successful, the next token will be lexed from the new
+  /// offset. The lexer also assumes that we skipped to the start of the line.
+  ///
+  /// \returns true if the skip failed (new offset would have been past the
+  /// end of the buffer), false otherwise.
+  bool skipOver(unsigned NumBytes);
+
   /// Stringify - Convert the specified string into a C string by i) escaping
   /// '\\' and " characters and ii) replacing newline character(s) with "\\n".
   /// If Charify is true, this escapes the ' character instead of ".
   static std::string Stringify(StringRef Str, bool Charify = false);
 
   /// Stringify - Convert the specified string into a C string by i) escaping
   /// '\\' and " characters and ii) replacing newline character(s) with "\\n".
   static void Stringify(SmallVectorImpl<char> &Str);

clang/include/clang/Lex/PPCallbacks.h

public:
   virtual void Else(SourceLocation Loc, SourceLocation IfLoc) {
   }
 
   /// Hook called whenever an \#endif is seen.
   /// \param Loc the source location of the directive.
   /// \param IfLoc the source location of the \#if/\#ifdef/\#ifndef directive.
   virtual void Endif(SourceLocation Loc, SourceLocation IfLoc) {
   }
+
+  /// This skipped range class returns an optional thing.
+  virtual Optional<unsigned> getSkippedRangeForExcludedConditionalBlock(
+      Preprocessor &PP, SourceLocation HashLoc, unsigned CurLexerBufferOffset) {
+    return None;
+  }
 };
 
 /// Simple wrapper class for chaining callbacks.
 class PPChainedCallbacks : public PPCallbacks {
   virtual void anchor();
   std::unique_ptr<PPCallbacks> First, Second;
 
 public:
void Else(SourceLocation Loc, SourceLocation IfLoc) override {
     Second->Else(Loc, IfLoc);
   }
 
   /// Hook called whenever an \#endif is seen.
   void Endif(SourceLocation Loc, SourceLocation IfLoc) override {
     First->Endif(Loc, IfLoc);
     Second->Endif(Loc, IfLoc);
   }
+
+  Optional<unsigned> getSkippedRangeForExcludedConditionalBlock(
+      Preprocessor &PP, SourceLocation HashLoc,
+      unsigned CurLexerBufferOffset) override {
+    if (auto I = First->getSkippedRangeForExcludedConditionalBlock(
+            PP, HashLoc, CurLexerBufferOffset))
+      return I;
+    return Second->getSkippedRangeForExcludedConditionalBlock(
+        PP, HashLoc, CurLexerBufferOffset);
+  }
 };
 
 }  // end namespace clang
 
 #endif

clang/include/clang/Tooling/DependencyScanning/DependencyScanningFilesystem.h

 //===- 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 "clang/Tooling/DependencyScanning/PPRangeSkipping.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 {
public:
   }
 
   /// \returns the name of the file.
   StringRef getName() const {
     assert(isValid() && "not initialized");
     return MaybeStat->getName();
   }
 
+  /// Return the mapping between location -> distance that is used to speed up
+  /// the block skipping in the preprocessor.
+  const SkippedRangeMapping &getPPSkippedRangeMapping() const {
+    return PPSkippedRangeMapping;
+  }
+
   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;
+  SkippedRangeMapping PPSkippedRangeMapping;
 };
 
 /// 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 {

 ///
 /// 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) {}
+      IntrusiveRefCntPtr<llvm::vfs::FileSystem> FS,
+      PreprocessorSkippedMappings &PPSkippedRanges)
+      : ProxyFileSystem(std::move(FS)), SharedCache(SharedCache),
+        PPSkippedRanges(PPSkippedRanges) {}
 
   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;
+  PreprocessorSkippedMappings &PPSkippedRanges;
 };
 
 } // end namespace dependencies
 } // end namespace tooling
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_FILESYSTEM_H

clang/include/clang/Tooling/DependencyScanning/DependencyScanningService.h

enum class ScanningMode {
   /// 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, bool ReuseFileManager = true);
+  DependencyScanningService(ScanningMode Mode, bool ReuseFileManager = true,
+                            bool SkipExcludedPPRanges = true);
 
   ScanningMode getMode() const { return Mode; }
 
   bool canReuseFileManager() const { return ReuseFileManager; }
 
+  bool canSkipExcludedPPRanges() const { return SkipExcludedPPRanges; }
+
   DependencyScanningFilesystemSharedCache &getSharedCache() {
     return SharedCache;
   }
 
 private:
   const ScanningMode Mode;
   const bool ReuseFileManager;
+  /// Set to true to use the preprocessor optimization that skips excluded PP
+  /// ranges by bumping the buffer pointer in the lexer instead of lexing the
+  /// tokens in the range until reaching the corresponding directive.
+  const bool SkipExcludedPPRanges;
   /// The global file system cache.
   DependencyScanningFilesystemSharedCache SharedCache;
 };
 
 } // end namespace dependencies
 } // end namespace tooling
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_SERVICE_H

clang/include/clang/Tooling/DependencyScanning/DependencyScanningWorker.h

 //===- DependencyScanningWorker.h - clang-scan-deps worker ===---*- 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_WORKER_H
 #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"
+#include "clang/Tooling/DependencyScanning/PPRangeSkipping.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem.h"
 #include <string>
 
 namespace clang {
 
 class DependencyOutputOptions;
 
public:
   llvm::Error computeDependencies(const std::string &Input,
                                   StringRef WorkingDirectory,
                                   const CompilationDatabase &CDB,
                                   DependencyConsumer &Consumer);
 
 private:
   IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts;
   std::shared_ptr<PCHContainerOperations> PCHContainerOps;
+  /// The mapping that holds the active 'skip' mappings that are used by a
+  /// particular preprocessor.
+  PreprocessorSkippedMappings PPSkippedRanges;
+  const bool SkipExcludedPPRanges;
 
   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<DependencyScanningWorkerFilesystem> DepFS;
   /// The file manager that is reused accross multiple invocations by this
   /// worker. If null, the file manager will not be reused.
   llvm::IntrusiveRefCntPtr<FileManager> Files;
 };
 
 } // end namespace dependencies
 } // end namespace tooling
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_WORKER_H

clang/include/clang/Tooling/DependencyScanning/PPRangeSkipping.h

+//===- PPRangeSkipping.h - PP Callbacks to skip inactive range --*- 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_PP_RANGE_SKIPPING_H
+#define LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_PP_RANGE_SKIPPING_H
+
+#include "clang/Basic/LLVM.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Lex/PPCallbacks.h"
+#include "llvm/ADT/DenseMap.h"
+#include <string>
+
+namespace clang {
+namespace tooling {
+namespace dependencies {
+
+/// A mapping from an offset into a buffer to the number of bytes that can be
+/// skipped by the preprocessor when skipping over inactive preprocessor ranges.
+using SkippedRangeMapping = llvm::DenseMap<unsigned, unsigned>;
+
+/// Contains the currently active skipped range mappings for a particular
+/// preprocessor instance.
+class PreprocessorSkippedMappings {
+public:
+  /// Clears the buffer -> skipped range mappings.
+  void reset() { MappingForBuffer.clear(); }
+
+  /// Inserts a new mapping that maps from the specified memory buffer to the
+  /// specified skipped range mappings.
+  void setSkippedRanges(const llvm::MemoryBuffer *Buf,
+                        const SkippedRangeMapping *Mapping) {
+    MappingForBuffer[Buf] = Mapping;
+  }
+
+  /// Returns the skipped range mappings for the given buffer or null if none
+  /// exist.
+  const SkippedRangeMapping *
+  getSkippedRanges(const llvm::MemoryBuffer *Buf) const {
+    auto It = MappingForBuffer.find(Buf);
+    if (It != MappingForBuffer.end())
+      return It->getSecond();
+    return nullptr;
+  }
+
+private:
+  llvm::DenseMap<const llvm::MemoryBuffer *, const SkippedRangeMapping *>
+      MappingForBuffer;
+};
+
+/// A PP callbacks instance that implements fast PP skipping.
+class PPRangeSkippingCallbacks final : public PPCallbacks {
+public:
+  PPRangeSkippingCallbacks(PreprocessorSkippedMappings &BufferMappings)
+      : BufferMappings(BufferMappings) {}
+
+  Optional<unsigned> getSkippedRangeForExcludedConditionalBlock(
+      Preprocessor &PP, SourceLocation HashLoc,
+      unsigned CurLexerBufferOffset) override;
+
+  void FileChanged(SourceLocation Loc, FileChangeReason Reason,
+                   SrcMgr::CharacteristicKind FileType,
+                   FileID PrevFID) override;
+
+private:
+  PreprocessorSkippedMappings &BufferMappings;
+  struct FileInfo {
+    SourceLocation Loc;
+    FileID File;
+    const SkippedRangeMapping *PPSkippedRanges = nullptr;
+
+    FileInfo(SourceLocation Loc) : Loc(Loc) {}
+
+    bool isValid() const { return File.isValid(); }
+  };
+  llvm::SmallVector<FileInfo, 8> FileStack;
+};
+
+} // end namespace dependencies
+} // end namespace tooling
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_DEPENDENCY_SCANNING_PP_RANGE_SKIPPING_H

clang/lib/Frontend/CompilerInstance.cpp

CompilerInstance::~CompilerInstance() {
   assert(OutputFiles.empty() && "Still output files in flight?");
 }
 
 void CompilerInstance::setInvocation(
     std::shared_ptr<CompilerInvocation> Value) {
   Invocation = std::move(Value);
 }
 
+void CompilerInstance::setAdditionalPPCallbacks(
+    std::unique_ptr<PPCallbacks> PPC) {
+  if (AdditionalPPCallbacks)
+    AdditionalPPCallbacks = std::make_unique<PPChainedCallbacks>(
+        std::move(AdditionalPPCallbacks), std::move(PPC));
+  else
+    AdditionalPPCallbacks = std::move(PPC);
+}
+
 bool CompilerInstance::shouldBuildGlobalModuleIndex() const {
   return (BuildGlobalModuleIndex ||
           (ModuleManager && ModuleManager->isGlobalIndexUnavailable() &&
            getFrontendOpts().GenerateGlobalModuleIndex)) &&
          !ModuleBuildFailed;
 }
 
 void CompilerInstance::setDiagnostics(DiagnosticsEngine *Value) {
AttachHeaderIncludeGen(*PP, DepOpts,
                            /*ShowDepth=*/false);
   }
 
   if (DepOpts.ShowIncludesDest != ShowIncludesDestination::None) {
     AttachHeaderIncludeGen(*PP, DepOpts,
                            /*ShowAllHeaders=*/true, /*OutputPath=*/"",
                            /*ShowDepth=*/true, /*MSStyle=*/true);
   }
+
+  if (AdditionalPPCallbacks)
+    PP->addPPCallbacks(std::move(AdditionalPPCallbacks));
 }
 
 std::string CompilerInstance::getSpecificModuleCachePath() {
   // Set up the module path, including the hash for the
   // module-creation options.
   SmallString<256> SpecificModuleCache(getHeaderSearchOpts().ModuleCachePath);
   if (!SpecificModuleCache.empty() && !getHeaderSearchOpts().DisableModuleHash)
     llvm::sys::path::append(SpecificModuleCache,

clang/lib/Lex/DependencyDirectivesSourceMinimizer.cpp

bool Minimizer::minimize() {
 
   // Null-terminate the output. This way the memory buffer that's passed to
   // Clang will not have to worry about the terminating '\0'.
   Out.push_back(0);
   Out.pop_back();
   return Error;
 }
 
+bool clang::minimize_source_to_dependency_directives::computeSkippedRanges(
+    ArrayRef<Token> Input, llvm::SmallVectorImpl<SkippedRange> &Range) {
+  struct Directive {
+    enum DirectiveKind {
+      If,  // if/ifdef/ifndef
+      Else // elif,else
+    };
+    int Offset;
+    DirectiveKind Kind;
+  };
+  llvm::SmallVector<Directive, 32> Offsets;
+  for (const Token &T : Input) {
+    switch (T.K) {
+    case pp_if:
+    case pp_ifdef:
+    case pp_ifndef:
+      Offsets.push_back({T.Offset, Directive::If});
+      break;
+
+    case pp_elif:
+    case pp_else: {
+      if (Offsets.empty())
+        return true;
+      int PreviousOffset = Offsets.back().Offset;
+      Range.push_back({PreviousOffset, T.Offset - PreviousOffset});
+      Offsets.push_back({T.Offset, Directive::Else});
+      break;
+    }
+
+    case pp_endif: {
+      if (Offsets.empty())
+        return true;
+      int PreviousOffset = Offsets.back().Offset;
+      Range.push_back({PreviousOffset, T.Offset - PreviousOffset});
+      do {
+        Directive::DirectiveKind Kind = Offsets.pop_back_val().Kind;
+        if (Kind == Directive::If)
+          break;
+      } while (!Offsets.empty());
+      break;
+    }
+    default:
+      break;
+    }
+  }
+  return false;
+}
+
 bool clang::minimizeSourceToDependencyDirectives(
     StringRef Input, SmallVectorImpl<char> &Output,
     SmallVectorImpl<Token> &Tokens, DiagnosticsEngine *Diags,
     SourceLocation InputSourceLoc) {
   Output.clear();
   Tokens.clear();
   return Minimizer(Output, Tokens, Input, Diags, InputSourceLoc).minimize();
 }

clang/lib/Lex/Lexer.cpp

Lexer *Lexer::Create_PragmaLexer(SourceLocation SpellingLoc,
   // return an EOD token.
   L->ParsingPreprocessorDirective = true;
 
   // This lexer really is for _Pragma.
   L->Is_PragmaLexer = true;
   return L;
 }
 
+bool Lexer::skipOver(unsigned NumBytes) {
+  IsAtPhysicalStartOfLine = true;
+  IsAtStartOfLine = true;
+  if ((BufferPtr + NumBytes) > BufferEnd)
+    return true;
+  BufferPtr += NumBytes;
+  return false;
+}
+
 template <typename T> static void StringifyImpl(T &Str, char Quote) {
   typename T::size_type i = 0, e = Str.size();
   while (i < e) {
     if (Str[i] == '\\' || Str[i] == Quote) {
       Str.insert(Str.begin() + i, '\\');
       i += 2;
       ++e;
     } else if (Str[i] == '\n' || Str[i] == '\r') {

clang/lib/Lex/PPDirectives.cpp

void Preprocessor::SkipExcludedConditionalBlock(SourceLocation HashTokenLoc,
   else
     CurPPLexer->pushConditionalLevel(IfTokenLoc, /*isSkipping*/ false,
                                      FoundNonSkipPortion, FoundElse);
 
   // Enter raw mode to disable identifier lookup (and thus macro expansion),
   // disabling warnings, etc.
   CurPPLexer->LexingRawMode = true;
   Token Tok;
+  if (Callbacks && HashTokenLoc.isFileID()) {
+    if (auto SkipLength = Callbacks->getSkippedRangeForExcludedConditionalBlock(
+            *this, HashTokenLoc, CurLexer->getCurrentBufferOffset())) {
+      // Skip to the next '#endif' / '#else' / '#elif'.
+      CurLexer->skipOver(*SkipLength);
+    }
+  }
   while (true) {
     CurLexer->Lex(Tok);
 
     if (Tok.is(tok::code_completion)) {
       if (CodeComplete)
         CodeComplete->CodeCompleteInConditionalExclusion();
       setCodeCompletionReached();
       continue;

clang/lib/Tooling/DependencyScanning/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Core
   Support
   )
 
 add_clang_library(clangDependencyScanning
   DependencyScanningFilesystem.cpp
   DependencyScanningService.cpp
   DependencyScanningWorker.cpp
+  PPRangeSkipping.cpp
 
   DEPENDS
   ClangDriverOptions
 
   LINK_LIBS
   clangAST
   clangBasic
   clangDriver
   clangFrontend
   clangFrontendTool
   clangLex
   clangParse
   clangSerialization
   clangTooling
 )

clang/lib/Tooling/DependencyScanning/DependencyScanningFilesystem.cpp

CachedFileSystemEntry CachedFileSystemEntry::createFileEntry(
   // 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();
+
+  // Compute the skipped PP ranges that speedup skipping over inactive
+  // preprocessor blocks.
+  llvm::SmallVector<minimize_source_to_dependency_directives::SkippedRange, 32>
+      SkippedRanges;
+  minimize_source_to_dependency_directives::computeSkippedRanges(Tokens,
+                                                                 SkippedRanges);
+  SkippedRangeMapping Mapping;
+  for (const auto &Range : SkippedRanges) {
+    if (Range.Length < 16) {
+      // Ignore small ranges as non-profitable.
+      // FIXME: This is a heuristic, its worth investigating the tradeoffs
+      // when it should be applied.
+      continue;
+    }
+    Mapping[Range.Offset] = Range.Length;
+  }
+  Result.PPSkippedRangeMapping = std::move(Mapping);
+
   return Result;
 }
 
 CachedFileSystemEntry
 CachedFileSystemEntry::createDirectoryEntry(llvm::vfs::Status &&Stat) {
   assert(Stat.isDirectory() && "not a directory!");
   auto Result = CachedFileSystemEntry();
   Result.MaybeStat = std::move(Stat);
public:
   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) {
+createFile(const CachedFileSystemEntry *Entry,
+           PreprocessorSkippedMappings &PPSkippedRanges) {
   llvm::ErrorOr<StringRef> Contents = Entry->getContents();
   if (!Contents)
     return Contents.getError();
-  return std::make_unique<MinimizedVFSFile>(
+  auto Result = std::make_unique<MinimizedVFSFile>(
       llvm::MemoryBuffer::getMemBuffer(*Contents, Entry->getName(),
                                        /*RequiresNullTerminator=*/false),
       *Entry->getStatus());
+  if (!Entry->getPPSkippedRangeMapping().empty())
+    PPSkippedRanges.setSkippedRanges(Result->getBufferPtr(),
+                                     &Entry->getPPSkippedRangeMapping());
+  return Result;
 }
 
 } // 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);
+    return createFile(Entry, PPSkippedRanges);
 
   // 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);
+  return createFile(Result, PPSkippedRanges);
 }

clang/lib/Tooling/DependencyScanning/DependencyScanningService.cpp

 //===- 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,
-                                                     bool ReuseFileManager)
-    : Mode(Mode), ReuseFileManager(ReuseFileManager) {}
+                                                     bool ReuseFileManager,
+                                                     bool SkipExcludedPPRanges)
+    : Mode(Mode), ReuseFileManager(ReuseFileManager),
+      SkipExcludedPPRanges(SkipExcludedPPRanges) {}

clang/lib/Tooling/DependencyScanning/DependencyScanningWorker.cpp

 };
 
 /// A clang tool that runs the preprocessor in a mode that's optimized for
 /// dependency scanning for the given compiler invocation.
 class DependencyScanningAction : public tooling::ToolAction {
 public:
   DependencyScanningAction(
       StringRef WorkingDirectory, DependencyConsumer &Consumer,
-      llvm::IntrusiveRefCntPtr<DependencyScanningWorkerFilesystem> DepFS)
+      llvm::IntrusiveRefCntPtr<DependencyScanningWorkerFilesystem> DepFS,
+      PreprocessorSkippedMappings *PPSkippedRanges)
       : WorkingDirectory(WorkingDirectory), Consumer(Consumer),
-        DepFS(std::move(DepFS)) {}
+        DepFS(std::move(DepFS)), PPSkippedRanges(PPSkippedRanges) {}
 
   bool runInvocation(std::shared_ptr<CompilerInvocation> Invocation,
                      FileManager *FileMgr,
                      std::shared_ptr<PCHContainerOperations> PCHContainerOps,
                      DiagnosticConsumer *DiagConsumer) override {
     // Create a compiler instance to handle the actual work.
     CompilerInstance Compiler(std::move(PCHContainerOps));
     Compiler.setInvocation(std::move(Invocation));
if (DepFS) {
       FileMgr->setVirtualFileSystem(createVFSFromCompilerInvocation(
           CI, Compiler.getDiagnostics(), DepFS));
     }
 
     FileMgr->getFileSystemOpts().WorkingDir = WorkingDirectory;
     Compiler.setFileManager(FileMgr);
     Compiler.createSourceManager(*FileMgr);
 
+    // Set the PP Callbacks which should speed up excluded conditional block
+    // skipping in the preprocessor.
+    if (PPSkippedRanges) {
+      PPSkippedRanges->reset();
+      Compiler.setAdditionalPPCallbacks(
+          std::make_unique<PPRangeSkippingCallbacks>(*PPSkippedRanges));
+    }
+
     // Create the dependency collector that will collect the produced
     // dependencies.
     //
     // This also moves the existing dependency output options from the
     // invocation to the collector. The options in the invocation are reset,
     // which ensures that the compiler won't create new dependency collectors,
     // and thus won't write out the extra '.d' files to disk.
     auto Opts = std::make_unique<DependencyOutputOptions>(
if (!DepFS)
       FileMgr->clearStatCache();
     return Result;
   }
 
 private:
   StringRef WorkingDirectory;
   DependencyConsumer &Consumer;
   llvm::IntrusiveRefCntPtr<DependencyScanningWorkerFilesystem> DepFS;
+  PreprocessorSkippedMappings *PPSkippedRanges;
 };
 
 } // end anonymous namespace
 
 DependencyScanningWorker::DependencyScanningWorker(
-    DependencyScanningService &Service) {
+    DependencyScanningService &Service)
+    : SkipExcludedPPRanges(Service.canSkipExcludedPPRanges()) {
   DiagOpts = new DiagnosticOptions();
   PCHContainerOps = std::make_shared<PCHContainerOperations>();
   RealFS = new ProxyFileSystemWithoutChdir(llvm::vfs::getRealFileSystem());
   if (Service.getMode() == ScanningMode::MinimizedSourcePreprocessing)
     DepFS = new DependencyScanningWorkerFilesystem(Service.getSharedCache(),
-                                                   RealFS);
+                                                   RealFS, PPSkippedRanges);
   if (Service.canReuseFileManager())
     Files = new FileManager(FileSystemOptions(), RealFS);
 }
 
 static llvm::Error runWithDiags(
     DiagnosticOptions *DiagOpts,
     llvm::function_ref<bool(DiagnosticConsumer &DC)> BodyShouldSucceed) {
   // Capture the emitted diagnostics and report them to the client
return runWithDiags(DiagOpts.get(), [&](DiagnosticConsumer &DC) {
     /// 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, Files);
     Tool.clearArgumentsAdjusters();
     Tool.setRestoreWorkingDir(false);
     Tool.setPrintErrorMessage(false);
     Tool.setDiagnosticConsumer(&DC);
-    DependencyScanningAction Action(WorkingDirectory, Consumer, DepFS);
+    DependencyScanningAction Action(WorkingDirectory, Consumer, DepFS,
+                                    SkipExcludedPPRanges ? &PPSkippedRanges
+                                                         : nullptr);
     return !Tool.run(&Action);
   });
 }

clang/lib/Tooling/DependencyScanning/PPRangeSkipping.cpp

+//===- PPRangeSkipping.cpp - PP Callbacks to skip inactive range ----------===//
+//
+// 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/PPRangeSkipping.h"
+#include "clang/Lex/Preprocessor.h"
+
+using namespace clang;
+using namespace tooling;
+using namespace dependencies;
+
+Optional<unsigned>
+PPRangeSkippingCallbacks::getSkippedRangeForExcludedConditionalBlock(
+    Preprocessor &PP, SourceLocation HashLoc, unsigned CurLexerBufferOffset) {
+  if (FileStack.empty())
+    return None;
+  const SourceManager &SM = PP.getSourceManager();
+
+  // Retrieve the information about the file we're currently lexing.
+  auto &Info = FileStack.back();
+  if (!Info.isValid()) {
+    std::pair<FileID, unsigned> F = SM.getDecomposedLoc(Info.Loc);
+    Info.File = F.first;
+    const auto *Buf = SM.getBuffer(F.first);
+    if (const auto *PPSkippedRanges = BufferMappings.getSkippedRanges(Buf)) {
+      Info.PPSkippedRanges = PPSkippedRanges;
+    }
+  }
+
+  if (!Info.PPSkippedRanges)
+    return None;
+
+  auto HashFileOffset = SM.getDecomposedLoc(HashLoc);
+  if (HashFileOffset.first != Info.File)
+    return None;
+  // Check if the offset of '#' is mapped in the skipped ranges.
+  auto It = Info.PPSkippedRanges->find(HashFileOffset.second);
+  if (It == Info.PPSkippedRanges->end()) {
+    return None;
+  }
+  unsigned BytesToSkip = It->getSecond();
+  assert(CurLexerBufferOffset >= HashFileOffset.second &&
+         "lexer is before the hash?");
+  // Take into account the fact that the lexer has already advanced, so the
+  // number of bytes to skip must be adjusted.
+  unsigned LengthDiff = CurLexerBufferOffset - HashFileOffset.second;
+  assert(BytesToSkip >= LengthDiff && "lexer is after the skipped range?");
+  return BytesToSkip - LengthDiff;
+}
+
+void PPRangeSkippingCallbacks::FileChanged(SourceLocation Loc,
+                                           FileChangeReason Reason,
+                                           SrcMgr::CharacteristicKind FileType,
+                                           FileID PrevFID) {
+  switch (Reason) {
+  case EnterFile:
+    if (Loc.isValid())
+      FileStack.push_back(Loc);
+    break;
+  case ExitFile:
+    if (!FileStack.empty())
+      FileStack.pop_back();
+    break;
+  default:
+    break;
+  }
+}

clang/test/ClangScanDeps/regular_cdb.cpp

 // RUN: rm -rf %t.dir
 // RUN: rm -rf %t.cdb
 // RUN: mkdir -p %t.dir
 // RUN: cp %s %t.dir/regular_cdb.cpp
 // RUN: cp %s %t.dir/regular_cdb2.cpp
 // RUN: mkdir %t.dir/Inputs
 // RUN: cp %S/Inputs/header.h %t.dir/Inputs/header.h
 // RUN: cp %S/Inputs/header2.h %t.dir/Inputs/header2.h
 // RUN: sed -e "s|DIR|%/t.dir|g" %S/Inputs/regular_cdb.json > %t.cdb
 //
 // RUN: clang-scan-deps -compilation-database %t.cdb -j 1 -mode preprocess-minimized-sources | \
 // RUN:   FileCheck --check-prefixes=CHECK1,CHECK2,CHECK2NO %s
 // RUN: clang-scan-deps -compilation-database %t.cdb -j 1 -mode preprocess | \
 // RUN:   FileCheck --check-prefixes=CHECK1,CHECK2,CHECK2NO %s
+// RUN: clang-scan-deps -compilation-database %t.cdb -j 1 -mode preprocess-minimized-sources \
+// RUN:   -skip-excluded-pp-ranges=0 | FileCheck --check-prefixes=CHECK1,CHECK2,CHECK2NO %s
 //
 // Make sure we didn't produce any dependency files!
 // RUN: not cat %t.dir/regular_cdb.d
 // RUN: not cat %t.dir/regular_cdb2.d
 //
 // The output order is non-deterministic when using more than one thread,
 // so check the output using two runs. Note that the 'NOT' check is not used
 // as it might fail if the results for `regular_cdb.cpp` are reported before

clang/tools/clang-scan-deps/ClangScanDeps.cpp

CompilationDB("compilation-database",
                   llvm::cl::desc("Compilation database"), llvm::cl::Required,
                   llvm::cl::cat(DependencyScannerCategory));
 
 llvm::cl::opt<bool> ReuseFileManager(
     "reuse-filemanager",
     llvm::cl::desc("Reuse the file manager and its cache between invocations."),
     llvm::cl::init(true), llvm::cl::cat(DependencyScannerCategory));
 
+llvm::cl::opt<bool> SkipExcludedPPRanges(
+    "skip-excluded-pp-ranges",
+    llvm::cl::desc(
+        "Use the preprocessor optimization that skips excluded conditionals by "
+        "bumping the buffer pointer in the lexer instead of lexing the tokens  "
+        "until reaching the end directive."),
+    llvm::cl::init(true), llvm::cl::cat(DependencyScannerCategory));
+
 } // end anonymous namespace
 
 int main(int argc, const char **argv) {
   llvm::InitLLVM X(argc, argv);
   llvm::cl::HideUnrelatedOptions(DependencyScannerCategory);
   if (!llvm::cl::ParseCommandLineOptions(argc, argv))
     return 1;
 
AdjustingCompilations->appendArgumentsAdjuster(
         AdjustedArgs.push_back("-Wno-error");
         return AdjustedArgs;
       });
 
   SharedStream Errs(llvm::errs());
   // Print out the dependency results to STDOUT by default.
   SharedStream DependencyOS(llvm::outs());
 
-  DependencyScanningService Service(ScanMode, ReuseFileManager);
+  DependencyScanningService Service(ScanMode, ReuseFileManager,
+                                    SkipExcludedPPRanges);
 #if LLVM_ENABLE_THREADS
   unsigned NumWorkers =
       NumThreads == 0 ? llvm::hardware_concurrency() : NumThreads;
 #else
   unsigned NumWorkers = 1;
 #endif
   std::vector<std::unique_ptr<DependencyScanningTool>> WorkerTools;
   for (unsigned I = 0; I < NumWorkers; ++I)

clang/unittests/Lex/DependencyDirectivesSourceMinimizerTest.cpp

EXPECT_STREQ("#include \"textual-header.h\"\nexport module m;\n"
                "import f(:sefse);\nimport f(->a = 3);\n", Out.data());
   ASSERT_EQ(Tokens.size(), 12u);
   EXPECT_EQ(Tokens[0].K,
             minimize_source_to_dependency_directives::pp_include);
   EXPECT_EQ(Tokens[2].K,
             minimize_source_to_dependency_directives::cxx_module_decl);
 }
 
+TEST(MinimizeSourceToDependencyDirectivesTest, SkippedPPRangesBasic) {
+  SmallString<128> Out;
+  SmallVector<Token, 32> Toks;
+  StringRef Source = "#ifndef GUARD\n"
+                     "#define GUARD\n"
+                     "void foo();\n"
+                     "#endif\n";
+  ASSERT_FALSE(minimizeSourceToDependencyDirectives(Source, Out, Toks));
+  SmallVector<SkippedRange, 4> Ranges;
+  ASSERT_FALSE(computeSkippedRanges(Toks, Ranges));
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges[0].Offset, 0);
+  EXPECT_EQ(Ranges[0].Length, (int)Out.find("#endif"));
+}
+
+TEST(MinimizeSourceToDependencyDirectivesTest, SkippedPPRangesNested) {
+  SmallString<128> Out;
+  SmallVector<Token, 32> Toks;
+  StringRef Source = "#ifndef GUARD\n"
+                     "#define GUARD\n"
+                     "#if FOO\n"
+                     "#include hello\n"
+                     "#elif BAR\n"
+                     "#include bye\n"
+                     "#endif\n"
+                     "#else\n"
+                     "#include nothing\n"
+                     "#endif\n";
+  ASSERT_FALSE(minimizeSourceToDependencyDirectives(Source, Out, Toks));
+  SmallVector<SkippedRange, 4> Ranges;
+  ASSERT_FALSE(computeSkippedRanges(Toks, Ranges));
+  EXPECT_EQ(Ranges.size(), 4u);
+  EXPECT_EQ(Ranges[0].Offset, (int)Out.find("#if FOO"));
+  EXPECT_EQ(Ranges[0].Offset + Ranges[0].Length, (int)Out.find("#elif"));
+  EXPECT_EQ(Ranges[1].Offset, (int)Out.find("#elif BAR"));
+  EXPECT_EQ(Ranges[1].Offset + Ranges[1].Length, (int)Out.find("#endif"));
+  EXPECT_EQ(Ranges[2].Offset, 0);
+  EXPECT_EQ(Ranges[2].Length, (int)Out.find("#else"));
+  EXPECT_EQ(Ranges[3].Offset, (int)Out.find("#else"));
+  EXPECT_EQ(Ranges[3].Offset + Ranges[3].Length, (int)Out.rfind("#endif"));
+}
+
 } // end anonymous namespace