diff --git a/clang/lib/ASTMatchers/ASTMatchFinder.cpp b/clang/lib/ASTMatchers/ASTMatchFinder.cpp --- a/clang/lib/ASTMatchers/ASTMatchFinder.cpp +++ b/clang/lib/ASTMatchers/ASTMatchFinder.cpp @@ -74,6 +74,35 @@ } }; +/// Performance optimization for querying the memoized map without the expensive +/// copy of the \c BoundNodesTreeBuilder and to a lesser extent the \c +/// DynTypedNode. +struct MatchKeyRef { + const DynTypedMatcher::MatcherIDType MatcherID; + const DynTypedNode &Node; + const BoundNodesTreeBuilder &BoundNodes; + const TraversalKind Traversal; + MatchType Type; + + MatchKey toKey() const { + return MatchKey{MatcherID, Node, BoundNodes, Traversal, Type}; + } +}; + +bool operator<(const MatchKey &LHS, const MatchKeyRef &RHS) { + return std::tie(LHS.Traversal, LHS.Type, LHS.MatcherID, LHS.Node, + LHS.BoundNodes) < std::tie(RHS.Traversal, RHS.Type, + RHS.MatcherID, RHS.Node, + RHS.BoundNodes); +} + +bool operator<(const MatchKeyRef &LHS, const MatchKey &RHS) { + return std::tie(LHS.Traversal, LHS.Type, LHS.MatcherID, LHS.Node, + LHS.BoundNodes) < std::tie(RHS.Traversal, RHS.Type, + RHS.MatcherID, RHS.Node, + RHS.BoundNodes); +} + // Used to store the result of a match and possibly bound nodes. struct MemoizedMatchResult { bool ResultOfMatch; @@ -457,14 +486,11 @@ 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; - MemoizationMap::iterator I = ResultCache.find(Key); + MatchKeyRef KeyRef = {Matcher.getID(), Node, *Builder, + Ctx.getParentMapContext().getTraversalKind()}; + + MemoizationMap::iterator I = ResultCache.find(KeyRef); if (I != ResultCache.end()) { *Builder = I->second.Nodes; return I->second.ResultOfMatch; @@ -475,11 +501,10 @@ Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes, MaxDepth, Traversal, Bind); - MemoizedMatchResult &CachedResult = ResultCache[Key]; - CachedResult = std::move(Result); - - *Builder = CachedResult.Nodes; - return CachedResult.ResultOfMatch; + auto Cached = ResultCache.emplace(KeyRef.toKey(), std::move(Result)); + assert(Cached.second && "Emplace should succeed"); + *Builder = Cached.first->second.Nodes; + return Cached.first->second.ResultOfMatch; } // Matches children or descendants of 'Node' with 'BaseMatcher'. @@ -705,16 +730,13 @@ return matchesAncestorOfRecursively(Node, Ctx, Matcher, Builder, MatchMode); - MatchKey Key; - Key.MatcherID = Matcher.getID(); - Key.Node = Node; - Key.BoundNodes = *Builder; - Key.Traversal = Ctx.getParentMapContext().getTraversalKind(); - Key.Type = MatchType::Ancestors; + // Note that we key on the bindings *before* the match. + MatchKeyRef KeyRef = {Matcher.getID(), Node, *Builder, + Ctx.getParentMapContext().getTraversalKind()}; // Note that we cannot use insert and reuse the iterator, as recursive // calls to match might invalidate the result cache iterators. - MemoizationMap::iterator I = ResultCache.find(Key); + MemoizationMap::iterator I = ResultCache.find(KeyRef); if (I != ResultCache.end()) { *Builder = I->second.Nodes; return I->second.ResultOfMatch; @@ -725,11 +747,10 @@ Result.ResultOfMatch = matchesAncestorOfRecursively( Node, Ctx, Matcher, &Result.Nodes, MatchMode); - MemoizedMatchResult &CachedResult = ResultCache[Key]; - CachedResult = std::move(Result); - - *Builder = CachedResult.Nodes; - return CachedResult.ResultOfMatch; + auto Cached = ResultCache.emplace(KeyRef.toKey(), std::move(Result)); + assert(Cached.second && "Emplace should succeed"); + *Builder = Cached.first->second.Nodes; + return Cached.first->second.ResultOfMatch; } bool matchesAncestorOfRecursively(const DynTypedNode &Node, ASTContext &Ctx, @@ -878,7 +899,7 @@ CompatibleAliases; // Maps (matcher, node) -> the match result for memoization. - typedef std::map MemoizationMap; + typedef std::map> MemoizationMap; MemoizationMap ResultCache; };