diff --git a/clang-tools-extra/clangd/ParsedAST.cpp b/clang-tools-extra/clangd/ParsedAST.cpp --- a/clang-tools-extra/clangd/ParsedAST.cpp +++ b/clang-tools-extra/clangd/ParsedAST.cpp @@ -236,6 +236,58 @@ std::vector MainFileTokens; }; +llvm::Expected +scanMainFileMacros(llvm::StringRef Contents, + const tooling::CompileCommand &Cmd) { + class EmptyFS : public ThreadsafeFS { + private: + llvm::IntrusiveRefCntPtr viewImpl() const override { + return new llvm::vfs::InMemoryFileSystem; + } + }; + EmptyFS FS; + // Build and run Preprocessor over the preamble. + ParseInputs PI; + PI.Contents = Contents.str(); + PI.TFS = &FS; + PI.CompileCommand = Cmd; + IgnoringDiagConsumer IgnoreDiags; + auto CI = buildCompilerInvocation(PI, IgnoreDiags); + if (!CI) + return error("failed to create compiler invocation"); + CI->getDiagnosticOpts().IgnoreWarnings = true; + auto ContentsBuffer = llvm::MemoryBuffer::getMemBuffer(Contents); + // This means we're scanning (though not preprocessing) the preamble section + // twice. However, it's important to precisely follow the preamble bounds used + // elsewhere. + auto Bounds = ComputePreambleBounds(*CI->getLangOpts(), *ContentsBuffer, 0); + auto PreambleContents = + llvm::MemoryBuffer::getMemBufferCopy(Contents.substr(0, Bounds.Size)); + auto Clang = prepareCompilerInstance( + std::move(CI), nullptr, std::move(PreambleContents), + // Provide an empty FS to prevent preprocessor from performing IO. This + // also implies missing resolved paths for includes. + FS.view(llvm::None), IgnoreDiags); + if (Clang->getFrontendOpts().Inputs.empty()) + return error("compiler instance had no inputs"); + // We are only interested in main file includes. + Clang->getPreprocessorOpts().SingleFileParseMode = true; + PreprocessOnlyAction Action; + if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])) + return error("failed BeginSourceFile"); + + MainFileMacros Macros; + Clang->getPreprocessor().addPPCallbacks( + std::make_unique(Clang->getSourceManager(), + Macros)); + + if (llvm::Error Err = Action.Execute()) + return std::move(Err); + Action.EndSourceFile(); + + return Macros; +} + } // namespace llvm::Optional @@ -393,8 +445,17 @@ // Copy over the macros in the preamble region of the main file, and combine // with non-preamble macros below. MainFileMacros Macros; - if (Preamble) + if (Preamble && Preamble->CompileCommand.Filename == Filename) { Macros = Preamble->Macros; + } + else if (Preamble) { + auto EM = scanMainFileMacros(Inputs.Contents, Inputs.CompileCommand); + if (!EM) { + elog("Failed to scan macros of {0}: {1}", Filename, EM.takeError()); + } else { + Macros = std::move(*EM); + } + } Clang->getPreprocessor().addPPCallbacks( std::make_unique(Clang->getSourceManager(), Macros)); diff --git a/clang-tools-extra/clangd/TUScheduler.h b/clang-tools-extra/clangd/TUScheduler.h --- a/clang-tools-extra/clangd/TUScheduler.h +++ b/clang-tools-extra/clangd/TUScheduler.h @@ -310,6 +310,8 @@ /// Responsible for retaining and rebuilding idle ASTs. An implementation is /// an LRU cache. class ASTCache; + /// Store all known preambles + class PreambleStore; // The file being built/processed in the current thread. This is a hack in // order to get the file name into the index implementations. Do not depend on @@ -332,6 +334,7 @@ Semaphore QuickRunBarrier; llvm::StringMap> Files; std::unique_ptr IdleASTs; + std::unique_ptr Preambles; // None when running tasks synchronously and non-None when running tasks // asynchronously. llvm::Optional PreambleTasks; diff --git a/clang-tools-extra/clangd/TUScheduler.cpp b/clang-tools-extra/clangd/TUScheduler.cpp --- a/clang-tools-extra/clangd/TUScheduler.cpp +++ b/clang-tools-extra/clangd/TUScheduler.cpp @@ -94,6 +94,62 @@ namespace { class ASTWorker; + +bool compileCommandsAreSimilar(const tooling::CompileCommand &LHS, + const tooling::CompileCommand &RHS) { + auto LIt = LHS.CommandLine.begin(); + auto RIt = RHS.CommandLine.begin(); + + auto SkipSpecificArg = [](auto It, auto End, const std::string &Filename) { + while (It != End) { + if (*It == "-o" || *It == "-x") { + // Erase -o and its argument + // Erase -x and its argument: it would prevent using header file + // preamble for a source file + It = std::min(It + 2, End); + } else if (*It == "-c" || It->find("-W") == 0 || *It == "-pedantic") { + // We don't care about those flags + It++; + } else if (It->find(Filename) != std::string::npos) { + // The file we're compiling appears in this argument, drop it to make it + // generic + It++; + } else { + break; + } + } + return It; + }; + + // Iterate the command line, skipping arguments that are specific to the + // file being compiled and that would not influence the premable + // compatiblity. Stop when one iterate reach the or when an argument differs + auto LEnd = LHS.CommandLine.end(); + auto REnd = RHS.CommandLine.end(); + while (true) { + LIt = SkipSpecificArg(LIt, LEnd, LHS.Filename); + RIt = SkipSpecificArg(RIt, REnd, RHS.Filename); + + if (LIt == LEnd || RIt == REnd) { + break; + } + + if (*LIt != *RIt) { + break; + } + + LIt++; + RIt++; + } + + // If both iterator get to the end at the same time, the CL are compatible + bool Compatible = LIt == LEnd && RIt == REnd; + if (Compatible) { + vlog("{0} and {1} are compatible", LHS.Filename, RHS.Filename); + } + return Compatible; +} + } // namespace static clang::clangd::Key kFileBeingProcessed; @@ -179,6 +235,59 @@ std::vector LRU; /* GUARDED_BY(Mut) */ }; +class TUScheduler::PreambleStore { +public: + struct Entry { + std::shared_ptr Preamble; + size_t Score; + Path FileName; + + bool operator>(const Entry &Other) const { return Score > Other.Score; } + }; + + auto getAll() { + std::unique_lock Lock(Mut); + return Store; + } + + void push(PathRef FileName, std::shared_ptr Preamble) { + std::unique_lock Lock(Mut); + auto It = llvm::find_if( + Store, [&](const auto &Item) { return Item.FileName == FileName; }); + if (It == Store.end()) { + Store.push_back(Entry{std::move(Preamble), 0, FileName.str()}); + popWorstPreambles(); + } + vlog("Store contains {0} preambles", Store.size()); + } + + void hit(PathRef FileName) { + std::unique_lock Lock(Mut); + auto It = llvm::find_if( + Store, [&](const auto &Item) { return Item.FileName == FileName; }); + if (It == Store.end()) { + return; + } + It->Score++; + } + +private: + void popWorstPreambles() { + constexpr int ClosedPreamblesToKeep = 5; + auto Begin = llvm::partition( + Store, [](const auto &Item) { return Item.Preamble.use_count() > 1; }); + if (std::distance(Begin, Store.end()) <= ClosedPreamblesToKeep) { + return; + } + auto Nth = Begin + ClosedPreamblesToKeep; + std::nth_element(Begin, Nth, Store.end(), std::greater()); + Store.erase(Nth, Store.end()); + } + + std::mutex Mut; + std::vector Store; +}; + namespace { /// Threadsafe manager for updating a TUStatus and emitting it after each /// update. @@ -368,8 +477,10 @@ class ASTWorker { friend class ASTWorkerHandle; ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB, - TUScheduler::ASTCache &LRUCache, Semaphore &Barrier, bool RunSync, - const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks); + TUScheduler::ASTCache &LRUCache, + TUScheduler::PreambleStore &Preambles, Semaphore &Barrier, + bool RunSync, const TUScheduler::Options &Opts, + ParsingCallbacks &Callbacks); public: /// Create a new ASTWorker and return a handle to it. @@ -377,12 +488,11 @@ /// is null, all requests will be processed on the calling thread /// synchronously instead. \p Barrier is acquired when processing each /// request, it is used to limit the number of actively running threads. - static ASTWorkerHandle create(PathRef FileName, - const GlobalCompilationDatabase &CDB, - TUScheduler::ASTCache &IdleASTs, - AsyncTaskRunner *Tasks, Semaphore &Barrier, - const TUScheduler::Options &Opts, - ParsingCallbacks &Callbacks); + static ASTWorkerHandle + create(PathRef FileName, const GlobalCompilationDatabase &CDB, + TUScheduler::ASTCache &IdleASTs, TUScheduler::PreambleStore &Preambles, + AsyncTaskRunner *Tasks, Semaphore &Barrier, + const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks); ~ASTWorker(); void update(ParseInputs Inputs, WantDiagnostics, bool ContentChanged); @@ -394,6 +504,8 @@ std::shared_ptr getPossiblyStalePreamble( std::shared_ptr *ASTSignals = nullptr) const; + std::shared_ptr getBestPreamble( + std::shared_ptr *ASTSignals = nullptr) const; /// Used to inform ASTWorker about a new preamble build by PreambleThread. /// Diagnostics are only published through this callback. This ensures they @@ -460,6 +572,9 @@ /// Should the first task in the queue be skipped instead of run? bool shouldSkipHeadLocked() const; + /// Get all preambles that may be used to accelerate the AST build + std::vector getCompatiblePreambles() const; + struct Request { llvm::unique_function Action; std::string Name; @@ -473,6 +588,7 @@ /// Handles retention of ASTs. TUScheduler::ASTCache &IdleASTs; + TUScheduler::PreambleStore &Preambles; const bool RunSync; /// Time to wait after an update to see whether another update obsoletes it. const DebouncePolicy UpdateDebounce; @@ -574,11 +690,13 @@ ASTWorkerHandle ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB, TUScheduler::ASTCache &IdleASTs, + TUScheduler::PreambleStore &Preambles, AsyncTaskRunner *Tasks, Semaphore &Barrier, const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks) { - std::shared_ptr Worker(new ASTWorker( - FileName, CDB, IdleASTs, Barrier, /*RunSync=*/!Tasks, Opts, Callbacks)); + std::shared_ptr Worker( + new ASTWorker(FileName, CDB, IdleASTs, Preambles, Barrier, + /*RunSync=*/!Tasks, Opts, Callbacks)); if (Tasks) { Tasks->runAsync("ASTWorker:" + llvm::sys::path::filename(FileName), [Worker]() { Worker->run(); }); @@ -590,13 +708,14 @@ } ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB, - TUScheduler::ASTCache &LRUCache, Semaphore &Barrier, + TUScheduler::ASTCache &LRUCache, + TUScheduler::PreambleStore &Preambles, Semaphore &Barrier, bool RunSync, const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks) - : IdleASTs(LRUCache), RunSync(RunSync), UpdateDebounce(Opts.UpdateDebounce), - FileName(FileName), ContextProvider(Opts.ContextProvider), CDB(CDB), - Callbacks(Callbacks), Barrier(Barrier), Done(false), - Status(FileName, Callbacks), + : IdleASTs(LRUCache), Preambles(Preambles), RunSync(RunSync), + UpdateDebounce(Opts.UpdateDebounce), FileName(FileName), + ContextProvider(Opts.ContextProvider), CDB(CDB), Callbacks(Callbacks), + Barrier(Barrier), Done(false), Status(FileName, Callbacks), PreamblePeer(FileName, Callbacks, Opts.StorePreamblesInMemory, RunSync, Status, *this) { // Set a fallback command because compile command can be accessed before @@ -687,14 +806,18 @@ PreamblePeer.update(std::move(Invocation), std::move(Inputs), std::move(CompilerInvocationDiags), WantDiags); + std::unique_lock Lock(Mutex); PreambleCV.wait(Lock, [this] { // Block until we reiceve a preamble request, unless a preamble already // exists, as patching an empty preamble would imply rebuilding it from // scratch. + // It is also acceptable to unblock is we have compatible preambles + // that may be used to accelerate the AST build. // We block here instead of the consumer to prevent any deadlocks. Since // LatestPreamble is only populated by ASTWorker thread. - return LatestPreamble || !PreambleRequests.empty() || Done; + return LatestPreamble || !PreambleRequests.empty() || + !getCompatiblePreambles().empty() || Done; }); return; }; @@ -722,13 +845,13 @@ vlog("ASTWorker rebuilding evicted AST to run {0}: {1} version {2}", Name, FileName, FileInputs.Version); // FIXME: We might need to build a patched ast once preamble thread starts - // running async. Currently getPossiblyStalePreamble below will always + // running async. Currently getBestPreamble below will always // return a compatible preamble as ASTWorker::update blocks. llvm::Optional NewAST; if (Invocation) { NewAST = ParsedAST::build(FileName, FileInputs, std::move(Invocation), CompilerInvocationDiagConsumer.take(), - getPossiblyStalePreamble()); + getBestPreamble()); ++ASTBuildCount; } AST = NewAST ? std::make_unique(std::move(*NewAST)) : nullptr; @@ -808,6 +931,7 @@ else LatestPreamble = std::move(Preamble); } + Preambles.push(FileName, *LatestPreamble); // Notify anyone waiting for a preamble. PreambleCV.notify_all(); // Give up our ownership to old preamble before starting expensive AST @@ -950,6 +1074,51 @@ return LatestPreamble ? *LatestPreamble : nullptr; } +std::vector +ASTWorker::getCompatiblePreambles() const { + auto AllPreamblesEntries = Preambles.getAll(); + auto End = llvm::remove_if(AllPreamblesEntries, [&](const auto &Item) { + return !compileCommandsAreSimilar(FileInputs.CompileCommand, + Item.Preamble->CompileCommand) || + // Using the preamble of a file that include the file we're + // processing will only yield partial results Unless we can tackle + // this issue, just ignore this preamble + Item.Preamble->Includes.includeDepth(Item.FileName).count(FileName); + }); + AllPreamblesEntries.erase(End, AllPreamblesEntries.end()); + return AllPreamblesEntries; +} + +std::shared_ptr ASTWorker::getBestPreamble( + std::shared_ptr *ASTSignals) const { + if (auto Preamble = getPossiblyStalePreamble(ASTSignals)) { + vlog("Best premable is the real one"); + return Preamble; + } + + auto CompatiblePreambles = getCompatiblePreambles(); + vlog("Looking for the best of {0} preambles ...", CompatiblePreambles.size()); + if (CompatiblePreambles.empty()) { + vlog("No compatible preanble"); + return nullptr; + } + + auto Best = CompatiblePreambles.begin(); + auto BestPatch = PreamblePatch::create(FileName, FileInputs, *Best->Preamble); + + for (auto It = Best + 1; It != CompatiblePreambles.end(); ++It) { + auto Patch = PreamblePatch::create(FileName, FileInputs, *It->Preamble); + if (Patch.preambleIncludes().size() > BestPatch.preambleIncludes().size()) { + BestPatch = std::move(Patch); + Best = It; + } + } + + vlog("Using preamble from: {0}", Best->FileName); + Preambles.hit(Best->FileName); + return Best->Preamble; +} + void ASTWorker::waitForFirstPreamble() const { std::unique_lock Lock(Mutex); PreambleCV.wait(Lock, [this] { return LatestPreamble.hasValue() || Done; }); @@ -1297,7 +1466,8 @@ : std::make_unique()), Barrier(Opts.AsyncThreadsCount), QuickRunBarrier(Opts.AsyncThreadsCount), IdleASTs( - std::make_unique(Opts.RetentionPolicy.MaxRetainedASTs)) { + std::make_unique(Opts.RetentionPolicy.MaxRetainedASTs)), + Preambles(std::make_unique()) { // Avoid null checks everywhere. if (!Opts.ContextProvider) { this->Opts.ContextProvider = [](llvm::StringRef) { @@ -1339,7 +1509,7 @@ if (!FD) { // Create a new worker to process the AST-related tasks. ASTWorkerHandle Worker = - ASTWorker::create(File, CDB, *IdleASTs, + ASTWorker::create(File, CDB, *IdleASTs, *Preambles, WorkerThreads ? WorkerThreads.getPointer() : nullptr, Barrier, Opts, *Callbacks); FD = std::unique_ptr( @@ -1426,7 +1596,7 @@ SPAN_ATTACH(Tracer, "file", File); std::shared_ptr Signals; std::shared_ptr Preamble = - It->second->Worker->getPossiblyStalePreamble(&Signals); + It->second->Worker->getBestPreamble(&Signals); WithContext WithProvidedContext(Opts.ContextProvider(File)); Action(InputsAndPreamble{It->second->Contents, It->second->Worker->getCurrentCompileCommand(), @@ -1449,7 +1619,7 @@ Worker->waitForFirstPreamble(); } std::shared_ptr Signals; - Preamble = Worker->getPossiblyStalePreamble(&Signals); + Preamble = Worker->getBestPreamble(&Signals); std::lock_guard BarrierLock(Barrier); WithContext Guard(std::move(Ctx));