Index: include/llvm/IR/ValueHandle.h
===================================================================
--- include/llvm/IR/ValueHandle.h
+++ include/llvm/IR/ValueHandle.h
@@ -197,13 +197,12 @@
     ValueHandleBase::operator=(GetAsValue(P));
   }
 #else
-  ValueTy *ThePtr;
-  ValueTy *getValPtr() const { return ThePtr; }
-  void setValPtr(ValueTy *P) { ThePtr = P; }
+  Value *ThePtr;
+  ValueTy *getValPtr() const { return static_cast<ValueTy *>(ThePtr); }
+  void setValPtr(ValueTy *P) { ThePtr = GetAsValue(P); }
 #endif
 
-  // Convert a ValueTy*, which may be const, to the type the base
-  // class expects.
+  // Convert a ValueTy*, which may be const, to the raw Value*.
   static Value *GetAsValue(Value *V) { return V; }
   static Value *GetAsValue(const Value *V) { return const_cast<Value*>(V); }
 
@@ -214,7 +213,7 @@
   AssertingVH(const AssertingVH &RHS) : ValueHandleBase(Assert, RHS) {}
 #else
   AssertingVH() : ThePtr(nullptr) {}
-  AssertingVH(ValueTy *P) : ThePtr(P) {}
+  AssertingVH(ValueTy *P) : ThePtr(GetAsValue(P)) {}
 #endif
 
   operator ValueTy*() const {
@@ -239,10 +238,26 @@
 struct DenseMapInfo<AssertingVH<T> > {
   typedef DenseMapInfo<T*> PointerInfo;
   static inline AssertingVH<T> getEmptyKey() {
-    return AssertingVH<T>(PointerInfo::getEmptyKey());
+    AssertingVH<T> Res;
+    Value *V = const_cast<Value *>(
+        reinterpret_cast<const Value *>(PointerInfo::getEmptyKey()));
+#ifndef NDEBUG
+    Res.ValueHandleBase::operator=(V);
+#else
+    Res.ThePtr = V;
+#endif
+    return Res;
   }
-  static inline T* getTombstoneKey() {
-    return AssertingVH<T>(PointerInfo::getTombstoneKey());
+  static inline AssertingVH<T> getTombstoneKey() {
+    AssertingVH<T> Res;
+    Value *V = const_cast<Value *>(
+        reinterpret_cast<const Value *>(PointerInfo::getTombstoneKey()));
+#ifndef NDEBUG
+    Res.ValueHandleBase::operator=(V);
+#else
+    Res.ThePtr = V;
+#endif
+    return Res;
   }
   static unsigned getHashValue(const AssertingVH<T> &Val) {
     return PointerInfo::getHashValue(Val);
Index: include/llvm/IR/ValueMap.h
===================================================================
--- include/llvm/IR/ValueMap.h
+++ include/llvm/IR/ValueMap.h
@@ -224,6 +224,9 @@
       : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))),
         Map(Map) {}
 
+  // Private constructor used to create empty/tombstone DenseMap keys.
+  ValueMapCallbackVH(Value *V) : CallbackVH(V), Map(nullptr) {}
+
 public:
   KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); }
 
@@ -269,10 +272,12 @@
   typedef DenseMapInfo<KeyT> PointerInfo;
 
   static inline VH getEmptyKey() {
-    return VH(PointerInfo::getEmptyKey(), nullptr);
+    return VH(const_cast<Value *>(
+        reinterpret_cast<const Value *>(PointerInfo::getEmptyKey())));
   }
   static inline VH getTombstoneKey() {
-    return VH(PointerInfo::getTombstoneKey(), nullptr);
+    return VH(const_cast<Value *>(
+        reinterpret_cast<const Value *>(PointerInfo::getTombstoneKey())));
   }
   static unsigned getHashValue(const VH &Val) {
     return PointerInfo::getHashValue(Val.Unwrap());