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

llvm-svn: 222688

1 files changed, 67 insertions, 10 deletions

diff --git a/clang/lib/ASTMatchers/ASTMatchFinder.cpp b/clang/lib/ASTMatchers/ASTMatchFinder.cpp
index 27c02bbd2c9..fa7968a805c 100644
--- a/clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ b/clang/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 <deque>
@@ -523,7 +524,7 @@ private:
   ///
   /// Used by \c matchDispatch() below.
   template <typename T, typename MC>
-  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<unsigned short> &
+  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<llvm::TimeRecord> 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<ast_type_traits::ASTNodeKind, std::vector<unsigned short>>
+      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);
 }