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<MatchKey, MemoizedMatchResult> MemoizationMap;
+  typedef std::map<MatchKey, MemoizedMatchResult, std::less<>> MemoizationMap;
   MemoizationMap ResultCache;
 };