[clangd] Skip function bodies inside processed files while indexing

[ilya-biryukov]

Summary

This significantly improves performance of background indexing.

We do not collect references and declarations inside the processed
files, so this does not affect the final indexing results.

The idea is borrowed from libclang, which has a similar optimization in
its indexing functionality.

Measurements show a nice decrease in indexing time, up to ~40% for
building the whole index. These are not proper benchmarks, so one should
not rely on these results too much.

1. Rebuilding the whole index for LLVM:
   • Before. Total time: 14m58s. ./bin/clangd -pch-storage=memory < ./clangd.input 23917.67s user 515.86s system 2718% cpu 14:58.68 total
   • After. Total time: 8m41s. ./bin/clangd -pch-storage=memory < ./clangd.input 13627.29s user 288.10s system 2672% cpu 8:40.67 total

2. Rebuilding index after removing shards matching '*clangd*' (case-insensitively):
   • Before. Total time: 30s. ./bin/clangd -pch-storage=memory < ./clangd.input 130.94s user 6.82s system 452% cpu 30.423 total
   • After. Total time: 26s. ./bin/clangd -pch-storage=memory < ./clangd.input 80.51s user 5.40s system 333% cpu 25.777 total

[kadircet]

This looks great, thanks!

clang-tools-extra/clangd/index/SymbolCollector.cpp

734

we already have shouldIndexFile as an anonymous function inside this file, which performs a similar operation with a cache (since FileFilter performs symlink resolution and a disk read).

Could you make that one a member instead and use it?

[ilya-biryukov]

• Expose the existing helper instead of introducing a new one

[ilya-biryukov]

clang-tools-extra/clangd/index/SymbolCollector.cpp

734

Thanks, did not notice it on the first go. Done.

[kadircet]

clang-tools-extra/clangd/index/IndexAction.cpp

194

nit: can you make these non-doxygen(just two slashes)?

[ilya-biryukov]

• Change / to

clang-tools-extra/clangd/index/IndexAction.cpp

 //===--- IndexAction.cpp -----------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "IndexAction.h"
 #include "Headers.h"
 #include "Logger.h"
 #include "index/Relation.h"
 #include "index/SymbolOrigin.h"
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
 #include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/MultiplexConsumer.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/STLExtras.h"
+#include <functional>
+#include <memory>
 #include <utility>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 llvm::Optional<std::string> toURI(const FileEntry *File) {
   if (!File)

 #endif
   }
 
 private:
   const SourceManager &SM;
   IncludeGraph &IG;
 };
 
+/// Returns an ASTConsumer that wraps \p Inner and additionally instructs the
+/// parser to skip bodies of functions in the files that should not be
+/// processed.
+static std::unique_ptr<ASTConsumer>
+skipProcessedFunctions(std::unique_ptr<ASTConsumer> Inner,
+                       std::function<bool(FileID)> ShouldIndexFile) {
+  class SkipProcessedFunctions : public ASTConsumer {
+  public:
+    SkipProcessedFunctions(std::function<bool(FileID)> FileFilter)
+        : ShouldIndexFile(std::move(FileFilter)), Context(nullptr) {
+      assert(this->ShouldIndexFile);
+    }
+
+    void Initialize(ASTContext &Context) override { this->Context = &Context; }
+    bool shouldSkipFunctionBody(Decl *D) override {
+      assert(Context && "Initialize() was never called.");
+      auto &SM = Context->getSourceManager();
+      auto FID = SM.getFileID(SM.getExpansionLoc(D->getLocation()));
+      if (!FID.isValid())
+        return false;
+      return !ShouldIndexFile(FID);
+    }
+
+  private:
+    std::function<bool(FileID)> ShouldIndexFile;
+    const ASTContext *Context;
+  };
+  std::vector<std::unique_ptr<ASTConsumer>> Consumers;
+  Consumers.push_back(
+      std::make_unique<SkipProcessedFunctions>(ShouldIndexFile));
+  Consumers.push_back(std::move(Inner));
+  return std::make_unique<MultiplexConsumer>(std::move(Consumers));
+}
+
 // Wraps the index action and reports index data after each translation unit.
 class IndexAction : public WrapperFrontendAction {
 public:
   IndexAction(std::shared_ptr<SymbolCollector> C,
               std::unique_ptr<CanonicalIncludes> Includes,
               const index::IndexingOptions &Opts,
               std::function<void(SymbolSlab)> SymbolsCallback,
               std::function<void(RefSlab)> RefsCallback,
               std::function<void(RelationSlab)> RelationsCallback,
               std::function<void(IncludeGraph)> IncludeGraphCallback)
       : WrapperFrontendAction(index::createIndexingAction(C, Opts, nullptr)),
         SymbolsCallback(SymbolsCallback), RefsCallback(RefsCallback),
         RelationsCallback(RelationsCallback),
         IncludeGraphCallback(IncludeGraphCallback), Collector(C),
         Includes(std::move(Includes)),
         PragmaHandler(collectIWYUHeaderMaps(this->Includes.get())) {}
 
   std::unique_ptr<ASTConsumer>
   CreateASTConsumer(CompilerInstance &CI, llvm::StringRef InFile) override {
     CI.getPreprocessor().addCommentHandler(PragmaHandler.get());
     addSystemHeadersMapping(Includes.get(), CI.getLangOpts());
     if (IncludeGraphCallback != nullptr)
       CI.getPreprocessor().addPPCallbacks(
           std::make_unique<IncludeGraphCollector>(CI.getSourceManager(), IG));
-    return WrapperFrontendAction::CreateASTConsumer(CI, InFile);
+    return skipProcessedFunctions(
+        WrapperFrontendAction::CreateASTConsumer(CI, InFile),
+        [this](FileID FID) { return Collector->shouldIndexFile(FID); });
   }
 
   bool BeginInvocation(CompilerInstance &CI) override {
     // We want all comments, not just the doxygen ones.
     CI.getLangOpts().CommentOpts.ParseAllComments = true;
     // Index the whole file even if there are warnings and -Werror is set.
     // Avoids some analyses too. Set in two places as we're late to the party.
     CI.getDiagnosticOpts().IgnoreWarnings = true;
     CI.getDiagnostics().setIgnoreAllWarnings(true);
+    // Instruct the parser to ask our ASTConsumer if it should skip function
+    // bodies. The ASTConsumer will take care of skipping only functions inside
+    // the files that we have already processed.
+    CI.getFrontendOpts().SkipFunctionBodies = true;
 
     return WrapperFrontendAction::BeginInvocation(CI);
   }
 
   void EndSourceFileAction() override {
     WrapperFrontendAction::EndSourceFileAction();
 
     SymbolsCallback(Collector->takeSymbols());

clang-tools-extra/clangd/index/SymbolCollector.h

public:
   bool handleMacroOccurence(const IdentifierInfo *Name, const MacroInfo *MI,
                             index::SymbolRoleSet Roles,
                             SourceLocation Loc) override;
 
   SymbolSlab takeSymbols() { return std::move(Symbols).build(); }
   RefSlab takeRefs() { return std::move(Refs).build(); }
   RelationSlab takeRelations() { return std::move(Relations).build(); }
 
+  /// Returns true if we are interested in references and declarations from \p
+  /// FID. If this function return false, bodies of functions inside those files
+  /// will be skipped to decrease indexing time.
+  bool shouldIndexFile(FileID FID);
+
   void finish() override;
 
 private:
   const Symbol *addDeclaration(const NamedDecl &, SymbolID,
                                bool IsMainFileSymbol);
   void addDefinition(const NamedDecl &, const Symbol &DeclSymbol);
   void processRelations(const NamedDecl &ND, const SymbolID &ID,
                         ArrayRef<index::SymbolRelation> Relations);

clang-tools-extra/clangd/index/SymbolCollector.cpp

auto CreatePosition = [&SM](SourceLocation Loc) {
     return Pos;
   };
 
   auto TokenLength = clang::Lexer::MeasureTokenLength(TokLoc, SM, LangOpts);
   return {CreatePosition(TokLoc),
           CreatePosition(TokLoc.getLocWithOffset(TokenLength))};
 }
 
-bool shouldIndexFile(const SourceManager &SM, FileID FID,
-                     const SymbolCollector::Options &Opts,
-                     llvm::DenseMap<FileID, bool> *FilesToIndexCache) {
-  if (!Opts.FileFilter)
-    return true;
-  auto I = FilesToIndexCache->try_emplace(FID);
-  if (I.second)
-    I.first->second = Opts.FileFilter(SM, FID);
-  return I.first->second;
-}
-
 // Return the symbol location of the token at \p TokLoc.
 llvm::Optional<SymbolLocation>
 getTokenLocation(SourceLocation TokLoc, const SourceManager &SM,
                  const SymbolCollector::Options &Opts,
                  const clang::LangOptions &LangOpts,
                  std::string &FileURIStorage) {
   auto Path = SM.getFilename(TokLoc);
   if (Path.empty())
bool SymbolCollector::handleMacroOccurence(const IdentifierInfo *Name,
   S.Name = Name->getName();
   if (!IsMainFileSymbol) {
     S.Flags |= Symbol::IndexedForCodeCompletion;
     S.Flags |= Symbol::VisibleOutsideFile;
   }
   S.SymInfo = index::getSymbolInfoForMacro(*MI);
   std::string FileURI;
   // FIXME: use the result to filter out symbols.
-  shouldIndexFile(SM, SM.getFileID(Loc), Opts, &FilesToIndexCache);
+  shouldIndexFile(SM.getFileID(Loc));
   if (auto DeclLoc =
           getTokenLocation(DefLoc, SM, Opts, PP->getLangOpts(), FileURI))
     S.CanonicalDeclaration = *DeclLoc;
 
   CodeCompletionResult SymbolCompletion(Name);
   const auto *CCS = SymbolCompletion.CreateCodeCompletionStringForMacro(
       *PP, *CompletionAllocator, *CompletionTUInfo);
   std::string Signature;
void SymbolCollector::finish() {
   };
   // Populate Refs slab from DeclRefs.
   if (auto MainFileURI = GetURI(SM.getMainFileID())) {
     for (const auto &It : DeclRefs) {
       if (auto ID = getSymbolID(It.first)) {
         for (const auto &LocAndRole : It.second) {
           auto FileID = SM.getFileID(LocAndRole.first);
           // FIXME: use the result to filter out references.
-          shouldIndexFile(SM, FileID, Opts, &FilesToIndexCache);
+          shouldIndexFile(FileID);
           if (auto FileURI = GetURI(FileID)) {
             auto Range =
                 getTokenRange(LocAndRole.first, SM, ASTCtx->getLangOpts());
             Ref R;
             R.Location.Start = Range.first;
             R.Location.End = Range.second;
             R.Location.FileURI = FileURI->c_str();
             R.Kind = toRefKind(LocAndRole.second);
if (isImplementationDetail(&ND))
     S.Flags |= Symbol::ImplementationDetail;
   if (!IsMainFileOnly)
     S.Flags |= Symbol::VisibleOutsideFile;
   S.SymInfo = index::getSymbolInfo(&ND);
   std::string FileURI;
   auto Loc = spellingLocIfSpelled(findName(&ND), SM);
   assert(Loc.isValid() && "Invalid source location for NamedDecl");
   // FIXME: use the result to filter out symbols.
-  shouldIndexFile(SM, SM.getFileID(Loc), Opts, &FilesToIndexCache);
+  shouldIndexFile(SM.getFileID(Loc));
   if (auto DeclLoc =
           getTokenLocation(Loc, SM, Opts, ASTCtx->getLangOpts(), FileURI))
     S.CanonicalDeclaration = *DeclLoc;
 
   S.Origin = Opts.Origin;
   if (ND.getAvailability() == AR_Deprecated)
     S.Flags |= Symbol::Deprecated;
 
void SymbolCollector::addDefinition(const NamedDecl &ND,
   // If we saw some forward declaration, we end up copying the symbol.
   // This is not ideal, but avoids duplicating the "is this a definition" check
   // in clang::index. We should only see one definition.
   Symbol S = DeclSym;
   std::string FileURI;
   const auto &SM = ND.getASTContext().getSourceManager();
   auto Loc = spellingLocIfSpelled(findName(&ND), SM);
   // FIXME: use the result to filter out symbols.
-  shouldIndexFile(SM, SM.getFileID(Loc), Opts, &FilesToIndexCache);
+  shouldIndexFile(SM.getFileID(Loc));
   if (auto DefLoc =
           getTokenLocation(Loc, SM, Opts, ASTCtx->getLangOpts(), FileURI))
     S.Definition = *DefLoc;
   Symbols.insert(S);
 }
 
 /// Gets a canonical include (URI of the header or <header> or "header") for
 /// header of \p FID (which should usually be the *expansion* file).
bool SymbolCollector::isDontIncludeMeHeader(llvm::StringRef Content) {
   for (unsigned I = 0; I < 100 && !Content.empty(); ++I) {
     std::tie(Line, Content) = Content.split('\n');
     if (isIf(Line) && isErrorAboutInclude(Content.split('\n').first))
       return true;
   }
   return false;
 }
 
+bool SymbolCollector::shouldIndexFile(FileID FID) {
+  if (!Opts.FileFilter)
+    return true;
+  auto I = FilesToIndexCache.try_emplace(FID);
+  if (I.second)
+    I.first->second = Opts.FileFilter(ASTCtx->getSourceManager(), FID);
+  return I.first->second;
+}
+
 } // namespace clangd
 } // namespace clang