njames93 updated this revision to Diff 272433.
njames93 added a comment.
rebase
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D80202/new/
https://reviews.llvm.org/D80202
Files:
clang/lib/ASTMatchers/ASTMatchFinder.cpp
Index: clang/lib/ASTMatchers/ASTMatchFinder.cpp
===================================================================
--- clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ 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<MatchKey, MemoizedMatchResult> MemoizationMap;
+ typedef std::map<MatchKey, MemoizedMatchResult, std::less<>> MemoizationMap;
MemoizationMap ResultCache;
};
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
