From d76512681efca0eb7ad04b4b4f9d3a5b16dbd2b1 Mon Sep 17 00:00:00 2001
From: Justin Bogner <mail@justinbogner.com>
Date: Thu, 2 Oct 2014 17:14:18 +0000
Subject: [PATCH] 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.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@218892 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ProfileData/CoverageMapping.h | 40 +++++++++++++++++++---
 lib/ProfileData/CoverageMapping.cpp        | 11 +++---
 2 files changed, 41 insertions(+), 10 deletions(-)

diff --git a/include/llvm/ProfileData/CoverageMapping.h b/include/llvm/ProfileData/CoverageMapping.h
index 8f73217c4d4..c1f478459b9 100644
--- a/include/llvm/ProfileData/CoverageMapping.h
+++ b/include/llvm/ProfileData/CoverageMapping.h
@@ -16,6 +16,8 @@
 #define LLVM_PROFILEDATA_COVERAGEMAPPING_H_
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Hashing.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/raw_ostream.h"
 #include <system_error>
@@ -91,10 +93,6 @@ struct CounterExpression {
 
   CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
       : Kind(Kind), LHS(LHS), RHS(RHS) {}
-
-  bool operator==(const CounterExpression &Other) const {
-    return Kind == Other.Kind && LHS == Other.LHS && RHS == Other.RHS;
-  }
 };
 
 /// \brief A Counter expression builder is used to construct the
@@ -102,7 +100,9 @@ struct CounterExpression {
 /// and simplifies algebraic expressions.
 class CounterExpressionBuilder {
   /// \brief A list of all the counter expressions
-  llvm::SmallVector<CounterExpression, 16> Expressions;
+  std::vector<CounterExpression> Expressions;
+  /// \brief A lookup table for the index of a given expression.
+  llvm::DenseMap<CounterExpression, unsigned> ExpressionIndices;
 
   /// \brief Return the counter which corresponds to the given expression.
   ///
@@ -370,6 +370,36 @@ public:
 };
 
 } // end namespace coverage
+
+/// \brief Provide DenseMapInfo for CounterExpression
+template<> struct DenseMapInfo<coverage::CounterExpression> {
+  static inline coverage::CounterExpression getEmptyKey() {
+    using namespace coverage;
+    return CounterExpression(CounterExpression::ExprKind::Subtract,
+                             Counter::getCounter(~0U),
+                             Counter::getCounter(~0U));
+  }
+
+  static inline coverage::CounterExpression getTombstoneKey() {
+    using namespace coverage;
+    return CounterExpression(CounterExpression::ExprKind::Add,
+                             Counter::getCounter(~0U),
+                             Counter::getCounter(~0U));
+  }
+
+  static unsigned getHashValue(const coverage::CounterExpression &V) {
+    return static_cast<unsigned>(
+        hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
+                     V.RHS.getKind(), V.RHS.getCounterID()));
+  }
+
+  static bool isEqual(const coverage::CounterExpression &LHS,
+                      const coverage::CounterExpression &RHS) {
+    return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
+  }
+};
+
+
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_
diff --git a/lib/ProfileData/CoverageMapping.cpp b/lib/ProfileData/CoverageMapping.cpp
index afddbc31c2d..df22eb791be 100644
--- a/lib/ProfileData/CoverageMapping.cpp
+++ b/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(
-- 
2.34.1