https://github.com/higher-performance updated https://github.com/llvm/llvm-project/pull/87824
>From 78f18445804fdb1cdf7810f56d3ae3c6e55f8da7 Mon Sep 17 00:00:00 2001 From: higher-performance <113926381+higher-performa...@users.noreply.github.com> Date: Fri, 5 Apr 2024 15:36:05 -0400 Subject: [PATCH] Fix quadratic slowdown in AST matcher parent map generation Avoids the need to linearly re-scan all seen parent nodes to check for duplicates, which previously caused a slowdown for ancestry checks in Clang AST matchers. Fixes https://github.com/llvm/llvm-project/issues/86881. --- clang/docs/ReleaseNotes.rst | 3 +++ clang/lib/AST/ParentMapContext.cpp | 25 ++++++++++++++++++++++--- 2 files changed, 25 insertions(+), 3 deletions(-) diff --git a/clang/docs/ReleaseNotes.rst b/clang/docs/ReleaseNotes.rst index 28e8ddb3c41c3e..cd9e0b54d55fde 100644 --- a/clang/docs/ReleaseNotes.rst +++ b/clang/docs/ReleaseNotes.rst @@ -622,6 +622,9 @@ Fixed Point Support in Clang AST Matchers ------------ +- Fixes a long-standing performance issue in parent map generation for + ancestry-based matchers such as ``hasParent`` and ``hasAncestor``, making + them significantly faster. - ``isInStdNamespace`` now supports Decl declared with ``extern "C++"``. - Add ``isExplicitObjectMemberFunction``. - Fixed ``forEachArgumentWithParam`` and ``forEachArgumentWithParamType`` to diff --git a/clang/lib/AST/ParentMapContext.cpp b/clang/lib/AST/ParentMapContext.cpp index 21cfd5b1de6e9d..9723c0cfa83bbe 100644 --- a/clang/lib/AST/ParentMapContext.cpp +++ b/clang/lib/AST/ParentMapContext.cpp @@ -61,7 +61,26 @@ class ParentMapContext::ParentMap { template <typename, typename...> friend struct ::MatchParents; /// Contains parents of a node. - using ParentVector = llvm::SmallVector<DynTypedNode, 2>; + class ParentVector { + public: + ParentVector() = default; + explicit ParentVector(size_t N, const DynTypedNode &Value) { + Items.reserve(N); + for (; N > 0; --N) + push_back(Value); + } + bool contains(const DynTypedNode &Value) { + return Seen.contains(Value); + } + void push_back(const DynTypedNode &Value) { + if (!Value.getMemoizationData() || Seen.insert(Value).second) + Items.push_back(Value); + } + llvm::ArrayRef<DynTypedNode> view() const { return Items; } + private: + llvm::SmallVector<DynTypedNode, 2> Items; + llvm::SmallDenseSet<DynTypedNode, 2> Seen; + }; /// Maps from a node to its parents. This is used for nodes that have /// pointer identity only, which are more common and we can save space by @@ -99,7 +118,7 @@ class ParentMapContext::ParentMap { return llvm::ArrayRef<DynTypedNode>(); } if (const auto *V = I->second.template dyn_cast<ParentVector *>()) { - return llvm::ArrayRef(*V); + return V->view(); } return getSingleDynTypedNodeFromParentMap(I->second); } @@ -252,7 +271,7 @@ class ParentMapContext::ParentMap { const auto *S = It->second.dyn_cast<const Stmt *>(); if (!S) { if (auto *Vec = It->second.dyn_cast<ParentVector *>()) - return llvm::ArrayRef(*Vec); + return Vec->view(); return getSingleDynTypedNodeFromParentMap(It->second); } const auto *P = dyn_cast<Expr>(S); _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
