[ASTMatcher] Fix a performance regression: memorize the child match.

[hokein]

Summary

D80025 introduced a performance regression: in some cases, it makes
clang-tidy readability-container-size-empty ~80x slower (running on an internal
huge TU, before that patch 12s vs after 950s).

after this patch, we go back to 12s.

[klimek]

In what situation are we calling child matchers repeatedly with the same matcher on the same node?

[klimek]

clang/lib/ASTMatchers/ASTMatchFinder.cpp

467–468

Here and below: s/memorize/memoize/

[hokein]

Address comments.

[hokein]

In D82771#2120214, @klimek wrote:

In what situation are we calling child matchers repeatedly with the same matcher on the same node?

I guess a pattern like https://github.com/llvm/llvm-project/blob/master/clang-tools-extra/clang-tidy/readability/ContainerSizeEmptyCheck.cpp#L29-L40?

[klimek]

In D82771#2121924, @hokein wrote:

In D82771#2120214, @klimek wrote:

In what situation are we calling child matchers repeatedly with the same matcher on the same node?

I guess a pattern like https://github.com/llvm/llvm-project/blob/master/clang-tools-extra/clang-tidy/readability/ContainerSizeEmptyCheck.cpp#L29-L40?

Ah, so this is when we go hasDeclaration.

I'm wondering whether what we really want to memoize are matchers that go across the AST, like hasType, hasDeclaration, etc, where we can expect a linear number of nodes hitting that matcher.

hasChild specifically seems weird to memoize when we don't memoize other has matchers.

[sammccall]

(I can't quite follow the original reason for disabling memoization in the non-recursive case, so this seems reasonable but going to leave that to Manuel who knew the argument)

clang/lib/ASTMatchers/ASTMatchFinder.cpp

468

This line looks a lot like a cache-poisoning bug, until realizing that MaxDepth is never actually used as an integer, it's a boolean - 1 means non-recursive and 0 means recursive. (Note that the recursive call passes MaxDepth, not MaxDepth-1).
I guess we should just fix the type, actually bounding the depth doesn't seem likely to be done anytime soon.

468

er, 1 means non-recursive and anything else means recursive...

[klimek]

LG

clang/lib/ASTMatchers/ASTMatchFinder.cpp

468

That sounds like a historical reason - feel free to change :) (I don't even remember how that came to be).

clang/lib/ASTMatchers/ASTMatchFinder.cpp

 //
 // FIXME: Do some performance optimization in general and
 // revisit this number; also, put up micro-benchmarks that we can
 // optimize this on.
 static const unsigned MaxMemoizationEntries = 10000;
 
 enum class MatchType {
   Ancestors,
-  Descendants
+
+  Descendants,
+  Child,
 };
 
 // We use memoization to avoid running the same matcher on the same
 // AST node twice.  This struct is the key for looking up match
 // result.  It consists of an ID of the MatcherInterface (for
 // identifying the matcher), a pointer to the AST node and the
 // bound nodes before the matcher was executed.
 //
public:
   bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
 
   // Matches children or descendants of 'Node' with 'BaseMatcher'.
   bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,
                                   const DynTypedMatcher &Matcher,
                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
                                   TraversalKind Traversal, BindKind Bind) {
     // For AST-nodes that don't have an identity, we can't memoize.
-    // When doing a single-level match, we don't need to memoize
-    if (!Node.getMemoizationData() || !Builder->isComparable() || MaxDepth == 1)
+    if (!Node.getMemoizationData() || !Builder->isComparable())
       return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
                                 Bind);
 
     MatchKey Key;
     Key.MatcherID = Matcher.getID();
     Key.Node = Node;
     // Note that we key on the bindings *before* the match.
     Key.BoundNodes = *Builder;
     Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
-    Key.Type = MatchType::Descendants;
+    // Memoize result even doing a single-level match, it might be expensive.
+    Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;
     MemoizationMap::iterator I = ResultCache.find(Key);
     if (I != ResultCache.end()) {
       *Builder = I->second.Nodes;
       return I->second.ResultOfMatch;
     }
 
     MemoizedMatchResult Result;
     Result.Nodes = *Builder;
private:
   // allow simple memoization on the ancestors. Thus, we only memoize as long
   // as there is a single parent.
   bool memoizedMatchesAncestorOfRecursively(const DynTypedNode &Node,
                                             ASTContext &Ctx,
                                             const DynTypedMatcher &Matcher,
                                             BoundNodesTreeBuilder *Builder,
                                             AncestorMatchMode MatchMode) {
     // For AST-nodes that don't have an identity, we can't memoize.
-    // When doing a single-level match, we don't need to memoize
-    if (!Builder->isComparable() || MatchMode == AncestorMatchMode::AMM_ParentOnly)
+    // When doing a single-level match, we don't need to memoize because
+    // ParentMap (in ASTContext) already memoizes the result.
+    if (!Builder->isComparable() ||
+        MatchMode == AncestorMatchMode::AMM_ParentOnly)
       return matchesAncestorOfRecursively(Node, Ctx, Matcher, Builder,
                                           MatchMode);
 
     MatchKey Key;
     Key.MatcherID = Matcher.getID();
     Key.Node = Node;
     Key.BoundNodes = *Builder;
     Key.Traversal = Ctx.getParentMapContext().getTraversalKind();