Filter the toplevel matchers by kind.

[sbenza]

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%

[klimek]

include/clang/AST/ASTTypeTraits.h

393–395 ↗

(On Diff #16506)

Is all that whitespace intentional?

include/clang/ASTMatchers/ASTMatchersInternal.h

292–295 ↗

(On Diff #16506)

Either \c both false and true, or none :)

309–311 ↗

(On Diff #16506)

I'd spend the extra 6 characters and call it matchesWithoutKindCheck.

lib/ASTMatchers/ASTMatchersInternal.cpp

187–191 ↗

(On Diff #16506)

Shouldn't every matcher already do that?

[sbenza]

Minor fixes

include/clang/AST/ASTTypeTraits.h

393–395 ↗

(On Diff #16506)

Not really. Fixed.

include/clang/ASTMatchers/ASTMatchersInternal.h

292–295 ↗

(On Diff #16506)

\c ALL the keywords!

309–311 ↗

(On Diff #16506)

What about SkipKindCheck ?

lib/ASTMatchers/ASTMatchersInternal.cpp

187–191 ↗

(On Diff #16506)

Do what? Delete the bindings?
This is where it happens, right?
The MatcherInterface implementations don't delete anything.

I pretty much copied matches() and modified it. That stayed the same.

[klimek]

LG (as the only question I have is basically unrelated to this patch), but I'd still like to get to the bottom of the question...

lib/ASTMatchers/ASTMatchersInternal.cpp

187–191 ↗

(On Diff #16506)

Hm, curious - does that actually make a difference in any test if we remove it (both here and in matches)?

[sbenza]

lib/ASTMatchers/ASTMatchersInternal.cpp

187–191 ↗

(On Diff #16506)

Removing this doesn't affect the tests.
The callers should already be ignoring the contents Builder if matches() return false.
This is here as a protection in case some caller doesn't ignore it.

[sbenza]

Closed by commit rL222688 (authored by @sbenza).

cfe/trunk/include/clang/AST/ASTTypeTraits.h

 
 #include "clang/AST/ASTFwd.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/NestedNameSpecifier.h"
 #include "clang/AST/Stmt.h"
 #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 {
 
 class raw_ostream;
 
 }
 
public:
   static ASTNodeKind getMostDerivedType(ASTNodeKind Kind1, ASTNodeKind Kind2);
 
   /// \brief Return the most derived common ancestor between Kind1 and Kind2.
   ///
   /// Return ASTNodeKind() if they are not related.
   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.
   ///
   /// Includes all possible base and derived kinds.
   enum NodeKindId {
     NKI_None,
     NKI_CXXCtorInitializer,
     NKI_TemplateArgument,
template <typename T, typename EnablerT> struct DynTypedNode::BaseConverter {
   static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
     return NULL;
   }
 };
 
 } // end namespace ast_type_traits
 } // end namespace clang
 
+namespace llvm {
+
+template <>
+struct DenseMapInfo<clang::ast_type_traits::ASTNodeKind>
+    : clang::ast_type_traits::ASTNodeKind::DenseMapInfo {};
+
+}  // end namespace llvm
+
 #endif

cfe/trunk/include/clang/ASTMatchers/ASTMatchFinder.h

public:
   /// The provided closure is called after parsing is done, before the AST is
   /// traversed. Useful for benchmarking.
   /// Each call to FindAll(...) will call the closure once.
   void registerTestCallbackAfterParsing(ParsingDoneTestCallback *ParsingDone);
 
   /// \brief For each \c Matcher<> a \c MatchCallback that will be called
   /// when it matches.
   struct MatchersByType {
-    std::vector<std::pair<DeclarationMatcher, MatchCallback *>> Decl;
+    std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *>>
+        DeclOrStmt;
     std::vector<std::pair<TypeMatcher, MatchCallback *>> Type;
-    std::vector<std::pair<StatementMatcher, MatchCallback *>> Stmt;
     std::vector<std::pair<NestedNameSpecifierMatcher, MatchCallback *>>
         NestedNameSpecifier;
     std::vector<std::pair<NestedNameSpecifierLocMatcher, MatchCallback *>>
         NestedNameSpecifierLoc;
     std::vector<std::pair<TypeLocMatcher, MatchCallback *>> TypeLoc;
     /// \brief All the callbacks in one container to simplify iteration.
     std::vector<MatchCallback *> AllCallbacks;
   };

cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h

public:
 
   /// \brief Get a "true" matcher for \p NodeKind.
   ///
   /// It only checks that the node is of the right kind.
   static DynTypedMatcher trueMatcher(ast_type_traits::ASTNodeKind NodeKind);
 
   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;
 
   /// \brief Returns true if the matcher matches the given \c DynNode.
   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<>.
   llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const;
 
   /// \brief Returns a unique \p ID for the matcher.
   ///
   /// Casting a Matcher<T> to Matcher<U> creates a matcher that has the

cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp

 //  AST node. The matcher can recurse via the ASTMatchFinder interface.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #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>
 #include <memory>
 #include <set>
 
 namespace clang {
 namespace ast_matchers {
private:
   private:
     llvm::TimeRecord *Bucket;
   };
 
   /// \brief Runs all the \p Matchers on \p Node.
   ///
   /// 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) {
       if (EnableCheckProfiling)
         Timer.setBucket(&TimeByBucket[MP.second->getID()]);
       BoundNodesTreeBuilder Builder;
       if (MP.first.matches(Node, this, &Builder)) {
         MatchVisitor Visitor(ActiveASTContext, MP.second);
         Builder.visitMatches(&Visitor);
       }
     }
   }
 
+  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. */ }
   /// @}
 
   // Returns whether an ancestor of \p Node matches \p Matcher.
   //
   // The order of matching ((which can lead to different nodes being bound in
   // case there are multiple matches) is breadth first search.
private:
   }
 
   /// \brief Bucket to record map.
   ///
   /// Used to get the appropriate bucket for each matcher.
   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;
 
   // Maps a canonical type to its TypedefDecls.
   llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
 
   // Maps (matcher, node) -> the match result for memoization.
   typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;

 
 MatchFinder::MatchFinder(MatchFinderOptions Options)
     : Options(std::move(Options)), ParsingDone(nullptr) {}
 
 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);
 }
 
 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
                              MatchCallback *Action) {
   Matchers.Type.push_back(std::make_pair(NodeMatch, Action));
   Matchers.AllCallbacks.push_back(Action);
 }
 
 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);
 }
 
 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
                              MatchCallback *Action) {
   Matchers.NestedNameSpecifier.push_back(std::make_pair(NodeMatch, Action));
   Matchers.AllCallbacks.push_back(Action);
 }

cfe/trunk/lib/ASTMatchers/ASTMatchersInternal.cpp

return DynTypedMatcher(SupportedKind, SupportedKind,
                          new VariadicMatcher(Func, std::move(InnerMatchers)));
 }
 
 DynTypedMatcher DynTypedMatcher::trueMatcher(
     ast_type_traits::ASTNodeKind NodeKind) {
   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;
   Copy.SupportedKind = Kind;
   Copy.RestrictKind =
       ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
   return Copy;
 }
 
 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
                               ASTMatchFinder *Finder,
                               BoundNodesTreeBuilder *Builder) const {
   if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
       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;
 }
 
+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> DynTypedMatcher::tryBind(StringRef ID) const {
   if (!AllowBind) return llvm::None;
   auto Result = *this;
   Result.Implementation = new IdDynMatcher(ID, Result.Implementation);
   return Result;
 }
 
 bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {