1 files changed, 27 insertions, 5 deletions
diff --git a/lib/Transforms/IPO/MergeFunctions.cpp b/lib/Transforms/IPO/MergeFunctions.cpp
index c678db8590..49ebe65fe8 100644
--- a/lib/Transforms/IPO/MergeFunctions.cpp
+++ b/lib/Transforms/IPO/MergeFunctions.cpp
@@ -109,10 +109,23 @@ public:
     Func = NULL;
   }
 
+  bool &getOrInsertCachedComparison(const ComparableFunction &Other,
+                                    bool &inserted) const {
+    typedef DenseMap<Function *, bool>::iterator iterator;
+    std::pair<iterator, bool> p =
+        CompareResultCache.insert(std::make_pair(Other.getFunc(), false));
+    inserted = p.second;
+    return p.first->second;
+  }
+
 private:
   explicit ComparableFunction(unsigned Hash)
     : Func(NULL), Hash(Hash), TD(NULL) {}
 
+  // DenseMap::grow() triggers a recomparison of all keys in the map, which is
+  // wildly expensive. This cache tries to preserve known results.
+  mutable DenseMap<Function *, bool> CompareResultCache;
+
   AssertingVH<Function> Func;
   unsigned Hash;
   TargetData *TD;
@@ -708,10 +721,10 @@ void MergeFunctions::RemoveUsers(Value *V) {
       if (Instruction *I = dyn_cast<Instruction>(U.getUser())) {
         Remove(I->getParent()->getParent());
       } else if (isa<GlobalValue>(U.getUser())) {
-	// do nothing
+        // do nothing
       } else if (Constant *C = dyn_cast<Constant>(U.getUser())) {
-	for (Value::use_iterator CUI = C->use_begin(), CUE = C->use_end();
-	     CUI != CUE; ++CUI)
+        for (Value::use_iterator CUI = C->use_begin(), CUE = C->use_end();
+             CUI != CUE; ++CUI)
           Worklist.push_back(*CUI);
       }
     }
@@ -777,6 +790,15 @@ bool DenseMapInfo<ComparableFunction>::isEqual(const ComparableFunction &LHS,
     return false;
   assert(LHS.getTD() == RHS.getTD() &&
          "Comparing functions for different targets");
-  return FunctionComparator(LHS.getTD(),
-                            LHS.getFunc(), RHS.getFunc()).Compare();
+
+  bool inserted;
+  bool &result1 = LHS.getOrInsertCachedComparison(RHS, inserted);
+  if (!inserted)
+    return result1;
+  bool &result2 = RHS.getOrInsertCachedComparison(LHS, inserted);
+  if (!inserted)
+    return result1 = result2;
+
+  return result1 = result2 = FunctionComparator(LHS.getTD(), LHS.getFunc(),
+                                                RHS.getFunc()).Compare();
 }