[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Sam McCall via Phabricator via cfe-commits]

sammccall added inline comments.



Comment at: clang/lib/ASTMatchers/ASTMatchFinder.cpp:902
   // Maps (matcher, node) -> the match result for memoization.
-  typedef std::map MemoizationMap;
+  typedef std::map> MemoizationMap;
   MemoizationMap ResultCache;

klimek wrote:
> Ok, if this actually matters, we should also not use a std::map here, but a 
> llvm::DenseMap (or do we rely on iteration invalidation semantics here?).
Belated +1. 5% seems like this performance *does* matter, so DenseMap::find_as 
should be yet faster.
It looks like BoundNodesTreeBuilder would need a DenseMapInfo, but all the 
other members are hashable already.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80202/new/

https://reviews.llvm.org/D80202



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Nathan James via Phabricator via cfe-commits]

njames93 updated this revision to Diff 272470.
njames93 added a comment.

Fix checks failing


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 
+  const BoundNodesTreeBuilder 
+  const TraversalKind Traversal;
+  MatchType Type;
+
+  MatchKey toKey() const {
+return MatchKey{MatcherID, Node, BoundNodes, Traversal, Type};
+  }
+};
+
+bool operator<(const MatchKey , const MatchKeyRef ) {
+  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 , const MatchKey ) {
+  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,12 @@
   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(),
+  MatchType::Descendants};
+
+MemoizationMap::iterator I = ResultCache.find(KeyRef);
 if (I != ResultCache.end()) {
   *Builder = I->second.Nodes;
   return I->second.ResultOfMatch;
@@ -475,11 +502,10 @@
 Result.ResultOfMatch = matchesRecursively(Node, Matcher, ,
   MaxDepth, Traversal, Bind);
 
-MemoizedMatchResult  = 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 +731,14 @@
   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(),
+  MatchType::Ancestors};
 
 // 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 +749,10 @@
 Result.ResultOfMatch = matchesAncestorOfRecursively(
 Node, Ctx, Matcher, , MatchMode);
 
-MemoizedMatchResult  = 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 , ASTContext ,
@@ -878,7 +901,7 @@
   CompatibleAliases;
 
   // Maps (matcher, node) -> the match result for memoization.
-  typedef std::map MemoizationMap;
+  typedef std::map> MemoizationMap;
   

[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Manuel Klimek via Phabricator via cfe-commits]

klimek added a reviewer: sammccall.
klimek added a comment.

+Sam for additional sanity checking.




Comment at: clang/lib/ASTMatchers/ASTMatchFinder.cpp:902
   // Maps (matcher, node) -> the match result for memoization.
-  typedef std::map MemoizationMap;
+  typedef std::map> MemoizationMap;
   MemoizationMap ResultCache;

Ok, if this actually matters, we should also not use a std::map here, but a 
llvm::DenseMap (or do we rely on iteration invalidation semantics here?).


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80202/new/

https://reviews.llvm.org/D80202



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Nathan James via Phabricator via cfe-commits]

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 
+  const BoundNodesTreeBuilder 
+  const TraversalKind Traversal;
+  MatchType Type;
+
+  MatchKey toKey() const {
+return MatchKey{MatcherID, Node, BoundNodes, Traversal, Type};
+  }
+};
+
+bool operator<(const MatchKey , const MatchKeyRef ) {
+  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 , const MatchKey ) {
+  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, ,
   MaxDepth, Traversal, Bind);
 
-MemoizedMatchResult  = 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, , MatchMode);
 
-MemoizedMatchResult  = 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 , ASTContext ,
@@ -878,7 +899,7 @@
   CompatibleAliases;
 
   // Maps (matcher, node) -> the match result for memoization.
-  typedef std::map MemoizationMap;
+  typedef std::map> MemoizationMap;
   MemoizationMap ResultCache;
 };
 
___
cfe-commits mailing list

[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Nathan James via Phabricator via cfe-commits]

njames93 added a comment.

I decided to do some more stringent benchmarking, just focusing on the 
matching, not the boilerplate of running clang-tidy.

  
=BeforePatch===
  Matcher Timings:   116.0756 user  29.1397 system  145.2154 process  145.2168 
wall
  Matcher Timings:   117.7205 user  29.2475 system  146.9681 process  146.9158 
wall
  Matcher Timings:   116.8313 user  29.5170 system  146.3483 process  146.2655 
wall
  Matcher Timings:   117.9491 user  29.0969 system  147.0459 process  146.9678 
wall
  Matcher Timings:   117.6309 user  29.1864 system  146.8173 process  146.7687 
wall
  
  user:117.2+-0.753
  system:  29.24+-0.166
  process: 146.5+-0.760

  
==AfterPatch===
  Matcher Timings:   110.5497 user  28.3316 system  138.8813 process  138.7960 
wall
  Matcher Timings:   112.5151 user  28.8616 system  141.3767 process  141.3003 
wall
  Matcher Timings:   116.1578 user  28.9472 system  145.1049 process  145.0785 
wall
  Matcher Timings:   107.1089 user  27.2752 system  134.3841 process  134.3459 
wall
  Matcher Timings:   105.9242 user  27.0338 system  132.9580 process  132.9010 
wall
  
  user:110.4+-4.159
  system:  28.09+-0.890
  process: 138.6+-4.979

This is showing ~5% improvement when running every clang-tidy check on a 
translation unit (Specifically 
`clang-tools-extra/clang-tidy/modernize/LoopConvertCheck.cpp`)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80202/new/

https://reviews.llvm.org/D80202



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Nathan James via Phabricator via cfe-commits]

njames93 added a comment.

Running most of the clang tidy checks on the clang-tidy folder yields these 
results

  
=BeforePatch===
  
  RUN1:
  4045.17user 83.93system 11:28.80elapsed 599%CPU (0avgtext+0avgdata 
534024maxresident)k
  0inputs+0outputs (0major+27584683minor)pagefaults 0swaps
  
  RUN2:
  4078.06user 84.99system 11:35.99elapsed 598%CPU (0avgtext+0avgdata 
506912maxresident)k
  55312inputs+0outputs (663major+27661947minor)pagefaults 0swaps
  
  RUN3:
  4040.77user 86.02system 11:28.85elapsed 599%CPU (0avgtext+0avgdata 
547096maxresident)k
  0inputs+0outputs (0major+27698937minor)pagefaults 0swaps



  
==AfterPatch===
  
  RUN1: 
  4025.33user 83.32system 11:27.00elapsed 598%CPU (0avgtext+0avgdata 
530568maxresident)k
  0inputs+0outputs (0major+27689512minor)pagefaults 0swaps
  
  RUN2:
  4056.93user 83.36system 11:32.31elapsed 598%CPU (0avgtext+0avgdata 
529120maxresident)k
  3752inputs+0outputs (19major+27794845minor)pagefaults 0swaps
  
  RUN3:
  4029.05user 85.45system 11:26.31elapsed 599%CPU (0avgtext+0avgdata 
533508maxresident)k
  0inputs+0outputs (0major+27730918minor)pagefaults 0swaps

Shows a consistent improvement but there tests are very noisy and dont focus on 
just the matching, they also include all the other boilderplate when running 
clang-tidy over a database. not to mention a small sample size


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80202/new/

https://reviews.llvm.org/D80202



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Manuel Klimek via Phabricator via cfe-commits]

klimek added a comment.

In D80202#2046321 , @njames93 wrote:

> In D80202#2046266 , @klimek wrote:
>
> > Given the extra complexity I'd like to see that it matters - bound nodes 
> > tend to be small.
>
>
> I put that in the description, but this is where i need help. whats the best 
> way to benchmark the matchers? 
>  Also, do you know how it was benchmarked when `MaxMemoizationEntries` was 
> decided upon?
>  There was also comments about some making some micro benchmarks but I don't 
> think that was acted upon.


I do remember benchmarking it when I wrote it, but that was 10 years ago :)
I mainly did benchmarks on large ASTs, trying various matchers.
Today we can benchmark for example whether running clang-tidy on all of LLVM 
makes a difference.
Micro-BMs would be nice to add, but are somewhat hard to get right.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80202/new/

https://reviews.llvm.org/D80202



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Nathan James via Phabricator via cfe-commits]

njames93 added a comment.

In D80202#2046266 , @klimek wrote:

> Given the extra complexity I'd like to see that it matters - bound nodes tend 
> to be small.


I put that in the description, but this is where i need help. whats the best 
way to benchmark the matchers? 
Also, do you know how it was benchmarked when `MaxMemoizationEntries` was 
decided upon?
There was also comments about some making some micro benchmarks but I don't 
think that was acted upon.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80202/new/

https://reviews.llvm.org/D80202



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Manuel Klimek via Phabricator via cfe-commits]

klimek added a comment.

Given the extra complexity I'd like to see that it matters - bound nodes tend 
to be small.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80202/new/

https://reviews.llvm.org/D80202



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Noel Grandin via Phabricator via cfe-commits]

grandinj added inline comments.



Comment at: clang/lib/ASTMatchers/ASTMatchFinder.cpp:78
+  const BoundNodesTreeBuilder 
+  const TraversalKind Traversal;
+

note that making fields const tends to disable various move optimisations, so 
better to mark the whole struct const in code that uses it


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80202/new/

https://reviews.llvm.org/D80202



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D80202: [ASTMatchers] Performance optimization for memoization

[Nathan James via Phabricator via cfe-commits]

njames93 created this revision.
njames93 added a reviewer: klimek.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.

A simple optimization to avoid unnecessary copies of BoundNodesTreeBuilders 
when querying the cache for memoized matchers.
This hasn't been benchmarked as I'm unsure how the memoized matchers were first 
benchmarked so it shouldn't be merged unless there is a performance improvement.


Repository:
  rG LLVM Github Monorepo

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
@@ -68,6 +68,30 @@
   }
 };
 
+/// 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 
+  const BoundNodesTreeBuilder 
+  const TraversalKind Traversal;
+
+  MatchKey toKey() const {
+return MatchKey{MatcherID, Node, BoundNodes, Traversal};
+  }
+};
+
+bool operator<(const MatchKey , const MatchKeyRef ) {
+  return std::tie(LHS.Traversal, LHS.MatcherID, LHS.Node, LHS.BoundNodes) <
+ std::tie(RHS.Traversal, RHS.MatcherID, RHS.Node, RHS.BoundNodes);
+}
+
+bool operator<(const MatchKeyRef , const MatchKey ) {
+  return std::tie(LHS.Traversal, LHS.MatcherID, LHS.Node, LHS.BoundNodes) <
+ std::tie(RHS.Traversal, RHS.MatcherID, RHS.Node, RHS.BoundNodes);
+}
+
 // Used to store the result of a match and possibly bound nodes.
 struct MemoizedMatchResult {
   bool ResultOfMatch;
@@ -450,14 +474,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();
+MatchKeyRef KeyRef = {Matcher.getID(), Node, *Builder,
+  Ctx.getParentMapContext().getTraversalKind()};
 
-MemoizationMap::iterator I = ResultCache.find(Key);
+MemoizationMap::iterator I = ResultCache.find(KeyRef);
 if (I != ResultCache.end()) {
   *Builder = I->second.Nodes;
   return I->second.ResultOfMatch;
@@ -468,11 +489,10 @@
 Result.ResultOfMatch = matchesRecursively(Node, Matcher, ,
   MaxDepth, Traversal, Bind);
 
-MemoizedMatchResult  = 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'.
@@ -697,15 +717,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();
+// 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;
@@ -716,11 +734,10 @@
 Result.ResultOfMatch = matchesAncestorOfRecursively(
 Node, Ctx, Matcher, , MatchMode);
 
-MemoizedMatchResult  = 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 , ASTContext ,
@@ -869,7 +886,7 @@
   CompatibleAliases;
 
   // Maps (matcher, node) -> the match result for memoization.
-  typedef std::map MemoizationMap;
+  typedef std::map> MemoizationMap;
   MemoizationMap ResultCache;
 };
 
___
cfe-commits mailing list
cfe-commits@lists.llvm.org