Index: lib/Analysis/LazyValueInfo.cpp
===================================================================
--- lib/Analysis/LazyValueInfo.cpp
+++ lib/Analysis/LazyValueInfo.cpp
@@ -366,6 +366,9 @@
   /// A callback value handle updates the cache when values are erased.
   class LazyValueInfoCache;
   struct LVIValueHandle final : public CallbackVH {
+    // Needs to access getValPtr(), which is protected.
+    friend struct DenseMapInfo<LVIValueHandle>;
+
     LazyValueInfoCache *Parent;
 
     LVIValueHandle(Value *V, LazyValueInfoCache *P)
@@ -376,7 +379,31 @@
       deleted();
     }
   };
-}
+} // end anonymous namespace
+
+template <> struct DenseMapInfo<LVIValueHandle> {
+  static inline LVIValueHandle getEmptyKey() {
+    return LVIValueHandle(DenseMapInfo<Value *>::getEmptyKey(), nullptr);
+  }
+  static inline LVIValueHandle getTombstoneKey() {
+    return LVIValueHandle(DenseMapInfo<Value *>::getTombstoneKey(), nullptr);
+  }
+  static unsigned getHashValue(const LVIValueHandle &Val) {
+    // No need to consider Val.Parent, as all elements in the hashtable have the
+    // same parent.
+    return getHashValue(Val.getValPtr());
+  }
+  static bool isEqual(const LVIValueHandle &LHS, const LVIValueHandle &RHS) {
+    return LHS == RHS;
+  }
+
+  static unsigned getHashValue(const Value *Val) {
+    return DenseMapInfo<Value *>::getHashValue(Val);
+  }
+  static bool isEqual(const Value *LHS, const LVIValueHandle &RHS) {
+    return LHS == RHS.getValPtr();
+  }
+};
 
 namespace {
   /// This is the cache kept by LazyValueInfo which
@@ -392,7 +419,7 @@
 
     /// This is all of the cached information for all values,
     /// mapped from Value* to key information.
-    std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
+    DenseMap<LVIValueHandle, ValueCacheEntryTy> ValueCache;
 
     /// This tracks, on a per-block basis, the set of values that are
     /// over-defined at the end of that block.
@@ -438,7 +465,7 @@
       if (Result.isOverdefined())
         OverDefinedCache[BB].insert(Val);
       else
-        lookup(Val)[BB] = Result;
+        ValueCache[LVIValueHandle(Val, this)][BB] = Result;
     }
 
     LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
@@ -466,10 +493,6 @@
 
     void solve();
 
-    ValueCacheEntryTy &lookup(Value *V) {
-      return ValueCache[LVIValueHandle(V, this)];
-    }
-
     bool isOverdefined(Value *V, BasicBlock *BB) const {
       auto ODI = OverDefinedCache.find(BB);
 
@@ -483,8 +506,7 @@
       if (isOverdefined(V, BB))
         return true;
 
-      LVIValueHandle ValHandle(V, this);
-      auto I = ValueCache.find(ValHandle);
+      auto I = ValueCache.find_as(V);
       if (I == ValueCache.end())
         return false;
 
@@ -495,7 +517,13 @@
       if (isOverdefined(V, BB))
         return LVILatticeVal::getOverdefined();
 
-      return lookup(V)[BB];
+      auto I = ValueCache.find_as(V);
+      if (I == ValueCache.end())
+        return LVILatticeVal();
+      auto BBI = I->second.find(BB);
+      if (BBI == I->second.end())
+        return LVILatticeVal();
+      return BBI->second;
     }
     
   public: