From 6d49f699dca8743f419850cc120ca0b7c9c45f32 Mon Sep 17 00:00:00 2001 From: Samuel Benzaquen Date: Mon, 24 Nov 2014 21:21:09 +0000 Subject: [PATCH] Filter the toplevel matchers by kind. Summary: Filter the toplevel matchers by kind. Decl and Stmt matchers are tied to a specific node kind and trying to match incompatible nodes is a waste. Precalculate a filtered list of matchers that have a chance of matching the node and ignore the rest. Speeds up our clang-tidy benchmark by ~10% Reviewers: klimek Subscribers: klimek, cfe-commits Differential Revision: http://reviews.llvm.org/D6361 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@222688 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/AST/ASTTypeTraits.h | 24 ++++++ include/clang/ASTMatchers/ASTMatchFinder.h | 4 +- .../clang/ASTMatchers/ASTMatchersInternal.h | 13 ++++ lib/ASTMatchers/ASTMatchFinder.cpp | 77 ++++++++++++++++--- lib/ASTMatchers/ASTMatchersInternal.cpp | 19 +++++ 5 files changed, 125 insertions(+), 12 deletions(-) diff --git a/include/clang/AST/ASTTypeTraits.h b/include/clang/AST/ASTTypeTraits.h index efeac563db..4fe9a3f87f 100644 --- a/include/clang/AST/ASTTypeTraits.h +++ b/include/clang/AST/ASTTypeTraits.h @@ -23,6 +23,7 @@ #include "clang/AST/TemplateBase.h" #include "clang/AST/TypeLoc.h" #include "clang/Basic/LLVM.h" +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/Support/AlignOf.h" namespace llvm { @@ -90,6 +91,21 @@ public: static ASTNodeKind getMostDerivedCommonAncestor(ASTNodeKind Kind1, ASTNodeKind Kind2); + /// \brief Hooks for using ASTNodeKind as a key in a DenseMap. + struct DenseMapInfo { + // ASTNodeKind() is a good empty key because it is represented as a 0. + static inline ASTNodeKind getEmptyKey() { return ASTNodeKind(); } + // NKI_NumberOfKinds is not a valid value, so it is good for a + // tombstone key. + static inline ASTNodeKind getTombstoneKey() { + return ASTNodeKind(NKI_NumberOfKinds); + } + static unsigned getHashValue(const ASTNodeKind &Val) { return Val.KindId; } + static bool isEqual(const ASTNodeKind &LHS, const ASTNodeKind &RHS) { + return LHS.KindId == RHS.KindId; + } + }; + private: /// \brief Kind ids. /// @@ -375,4 +391,12 @@ template struct DynTypedNode::BaseConverter { } // end namespace ast_type_traits } // end namespace clang +namespace llvm { + +template <> +struct DenseMapInfo + : clang::ast_type_traits::ASTNodeKind::DenseMapInfo {}; + +} // end namespace llvm + #endif diff --git a/include/clang/ASTMatchers/ASTMatchFinder.h b/include/clang/ASTMatchers/ASTMatchFinder.h index e5fc44c050..ce2674e442 100644 --- a/include/clang/ASTMatchers/ASTMatchFinder.h +++ b/include/clang/ASTMatchers/ASTMatchFinder.h @@ -199,9 +199,9 @@ public: /// \brief For each \c Matcher<> a \c MatchCallback that will be called /// when it matches. struct MatchersByType { - std::vector> Decl; + std::vector> + DeclOrStmt; std::vector> Type; - std::vector> Stmt; std::vector> NestedNameSpecifier; std::vector> diff --git a/include/clang/ASTMatchers/ASTMatchersInternal.h b/include/clang/ASTMatchers/ASTMatchersInternal.h index 1b8040cf44..3aecf4b0e4 100644 --- a/include/clang/ASTMatchers/ASTMatchersInternal.h +++ b/include/clang/ASTMatchers/ASTMatchersInternal.h @@ -289,6 +289,11 @@ public: void setAllowBind(bool AB) { AllowBind = AB; } + /// \brief Check whether this matcher could ever match a node of kind \p Kind. + /// \return \c false if this matcher will never match such a node. Otherwise, + /// return \c true. + bool canMatchNodesOfKind(ast_type_traits::ASTNodeKind Kind) const; + /// \brief Return a matcher that points to the same implementation, but /// restricts the node types for \p Kind. DynTypedMatcher dynCastTo(const ast_type_traits::ASTNodeKind Kind) const; @@ -297,6 +302,14 @@ public: bool matches(const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const; + /// \brief Same as matches(), but skips the kind check. + /// + /// It is faster, but the caller must ensure the node is valid for the + /// kind of this matcher. + bool matchesNoKindCheck(const ast_type_traits::DynTypedNode &DynNode, + ASTMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const; + /// \brief Bind the specified \p ID to the matcher. /// \return A new matcher with the \p ID bound to it if this matcher supports /// binding. Otherwise, returns an empty \c Optional<>. diff --git a/lib/ASTMatchers/ASTMatchFinder.cpp b/lib/ASTMatchers/ASTMatchFinder.cpp index 27c02bbd2c..fa7968a805 100644 --- a/lib/ASTMatchers/ASTMatchFinder.cpp +++ b/lib/ASTMatchers/ASTMatchFinder.cpp @@ -20,6 +20,7 @@ #include "clang/AST/ASTConsumer.h" #include "clang/AST/ASTContext.h" #include "clang/AST/RecursiveASTVisitor.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/StringMap.h" #include "llvm/Support/Timer.h" #include @@ -523,7 +524,7 @@ private: /// /// Used by \c matchDispatch() below. template - void matchImpl(const T &Node, const MC &Matchers) { + void matchWithoutFilter(const T &Node, const MC &Matchers) { const bool EnableCheckProfiling = Options.CheckProfiling.hasValue(); TimeBucketRegion Timer; for (const auto &MP : Matchers) { @@ -537,22 +538,66 @@ private: } } + void matchWithFilter(const ast_type_traits::DynTypedNode &DynNode) { + auto Kind = DynNode.getNodeKind(); + auto it = MatcherFiltersMap.find(Kind); + const auto &Filter = + it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind); + + if (Filter.empty()) + return; + + const bool EnableCheckProfiling = Options.CheckProfiling.hasValue(); + TimeBucketRegion Timer; + auto &Matchers = this->Matchers->DeclOrStmt; + for (unsigned short I : Filter) { + auto &MP = Matchers[I]; + if (EnableCheckProfiling) + Timer.setBucket(&TimeByBucket[MP.second->getID()]); + BoundNodesTreeBuilder Builder; + if (MP.first.matchesNoKindCheck(DynNode, this, &Builder)) { + MatchVisitor Visitor(ActiveASTContext, MP.second); + Builder.visitMatches(&Visitor); + } + } + } + + const std::vector & + getFilterForKind(ast_type_traits::ASTNodeKind Kind) { + auto &Filter = MatcherFiltersMap[Kind]; + auto &Matchers = this->Matchers->DeclOrStmt; + assert((Matchers.size() < USHRT_MAX) && "Too many matchers."); + for (unsigned I = 0, E = Matchers.size(); I != E; ++I) { + if (Matchers[I].first.canMatchNodesOfKind(Kind)) { + Filter.push_back(I); + } + } + return Filter; + } + /// @{ /// \brief Overloads to pair the different node types to their matchers. - void matchDispatch(const Decl *Node) { matchImpl(*Node, Matchers->Decl); } - void matchDispatch(const Stmt *Node) { matchImpl(*Node, Matchers->Stmt); } + void matchDispatch(const Decl *Node) { + return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node)); + } + void matchDispatch(const Stmt *Node) { + return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node)); + } + void matchDispatch(const Type *Node) { - matchImpl(QualType(Node, 0), Matchers->Type); + matchWithoutFilter(QualType(Node, 0), Matchers->Type); } void matchDispatch(const TypeLoc *Node) { - matchImpl(*Node, Matchers->TypeLoc); + matchWithoutFilter(*Node, Matchers->TypeLoc); + } + void matchDispatch(const QualType *Node) { + matchWithoutFilter(*Node, Matchers->Type); } - void matchDispatch(const QualType *Node) { matchImpl(*Node, Matchers->Type); } void matchDispatch(const NestedNameSpecifier *Node) { - matchImpl(*Node, Matchers->NestedNameSpecifier); + matchWithoutFilter(*Node, Matchers->NestedNameSpecifier); } void matchDispatch(const NestedNameSpecifierLoc *Node) { - matchImpl(*Node, Matchers->NestedNameSpecifierLoc); + matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc); } void matchDispatch(const void *) { /* Do nothing. */ } /// @} @@ -685,6 +730,18 @@ private: llvm::StringMap TimeByBucket; const MatchFinder::MatchersByType *Matchers; + + /// \brief Filtered list of matcher indices for each matcher kind. + /// + /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node + /// kind (and derived kinds) so it is a waste to try every matcher on every + /// node. + /// We precalculate a list of matchers that pass the toplevel restrict check. + /// This also allows us to skip the restrict check at matching time. See + /// use \c matchesNoKindCheck() above. + llvm::DenseMap> + MatcherFiltersMap; + const MatchFinder::MatchFinderOptions &Options; ASTContext *ActiveASTContext; @@ -855,7 +912,7 @@ MatchFinder::~MatchFinder() {} void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch, MatchCallback *Action) { - Matchers.Decl.push_back(std::make_pair(NodeMatch, Action)); + Matchers.DeclOrStmt.push_back(std::make_pair(NodeMatch, Action)); Matchers.AllCallbacks.push_back(Action); } @@ -867,7 +924,7 @@ void MatchFinder::addMatcher(const TypeMatcher &NodeMatch, void MatchFinder::addMatcher(const StatementMatcher &NodeMatch, MatchCallback *Action) { - Matchers.Stmt.push_back(std::make_pair(NodeMatch, Action)); + Matchers.DeclOrStmt.push_back(std::make_pair(NodeMatch, Action)); Matchers.AllCallbacks.push_back(Action); } diff --git a/lib/ASTMatchers/ASTMatchersInternal.cpp b/lib/ASTMatchers/ASTMatchersInternal.cpp index c7d98b8a3a..ca58d330d8 100644 --- a/lib/ASTMatchers/ASTMatchersInternal.cpp +++ b/lib/ASTMatchers/ASTMatchersInternal.cpp @@ -149,6 +149,11 @@ DynTypedMatcher DynTypedMatcher::trueMatcher( return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance); } +bool DynTypedMatcher::canMatchNodesOfKind( + ast_type_traits::ASTNodeKind Kind) const { + return RestrictKind.isBaseOf(Kind); +} + DynTypedMatcher DynTypedMatcher::dynCastTo( const ast_type_traits::ASTNodeKind Kind) const { auto Copy = *this; @@ -172,6 +177,20 @@ bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode, return false; } +bool DynTypedMatcher::matchesNoKindCheck( + const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const { + assert(RestrictKind.isBaseOf(DynNode.getNodeKind())); + if (Implementation->dynMatches(DynNode, Finder, Builder)) { + return true; + } + // Delete all bindings when a matcher does not match. + // This prevents unexpected exposure of bound nodes in unmatches + // branches of the match tree. + Builder->removeBindings([](const BoundNodesMap &) { return true; }); + return false; +} + llvm::Optional DynTypedMatcher::tryBind(StringRef ID) const { if (!AllowBind) return llvm::None; auto Result = *this; -- 2.40.0