InstrProf: Avoid linear search in a hot loop

Every time we were adding or removing an expression when generating a
coverage mapping we were doing a linear search to try and deduplicate
the list. The indices in the list are important, so we can't just
replace it by a DenseMap entirely, but an auxilliary DenseMap for fast
lookup massively improves the performance issues I was seeing here.

llvm-svn: 218892

1 files changed, 6 insertions, 5 deletions

diff --git a/llvm/lib/ProfileData/CoverageMapping.cpp b/llvm/lib/ProfileData/CoverageMapping.cpp
index afddbc31c2d..df22eb791be 100644
--- a/llvm/lib/ProfileData/CoverageMapping.cpp
+++ b/llvm/lib/ProfileData/CoverageMapping.cpp
@@ -28,12 +28,13 @@ using namespace coverage;
 #define DEBUG_TYPE "coverage-mapping"
 
 Counter CounterExpressionBuilder::get(const CounterExpression &E) {
-  for (unsigned I = 0, S = Expressions.size(); I < S; ++I) {
-    if (Expressions[I] == E)
-      return Counter::getExpression(I);
-  }
+  auto It = ExpressionIndices.find(E);
+  if (It != ExpressionIndices.end())
+    return Counter::getExpression(It->second);
+  unsigned I = Expressions.size();
   Expressions.push_back(E);
-  return Counter::getExpression(Expressions.size() - 1);
+  ExpressionIndices[E] = I;
+  return Counter::getExpression(I);
 }
 
 void CounterExpressionBuilder::extractTerms(