diff --git a/docs/LangRef.html b/docs/LangRef.html
index 36eae71..3f16e38 100644
--- a/docs/LangRef.html
+++ b/docs/LangRef.html
@@ -2061,6 +2061,10 @@
 exclamation point).  For example: "<tt>!{ { } !"test\00", i32 10}</tt>".
 </p>
 
+<p>A metadata node will attempt to track changes to the values it holds. In
+the event that a value is deleted, it will be replaced with a typeless
+"<tt>null</tt>", such as "<tt>{ } !{null, i32 0}</tt>".</p> 
+
 <p>Optimizations may rely on metadata to provide additional information about
 the program that isn't available in the instructions, or that isn't easily
 computable. Similarly, the code generator may expect a certain metadata format
diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h
index 2e48097..0b908e9 100644
--- a/include/llvm/Constants.h
+++ b/include/llvm/Constants.h
@@ -26,7 +26,6 @@
 #include "llvm/OperandTraits.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/APFloat.h"
-#include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/SmallVector.h"
 
 namespace llvm {
@@ -877,55 +876,6 @@
   }
 };
 
-//===----------------------------------------------------------------------===//
-/// MDNode - a tuple of other values.
-/// These contain a list of the Constants that represent the metadata.
-///
-class MDNode : public Constant, public FoldingSetNode {
-  MDNode(const MDNode &);      // DO NOT IMPLEMENT
-protected:
-  explicit MDNode(Constant*const* Vals, unsigned NumVals);
-public:
-  /// get() - Static factory methods - Return objects of the specified value.
-  ///
-  static MDNode *get(Constant*const* Vals, unsigned NumVals);
-
-  // Transparently provide more efficient getOperand methods.
-  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Constant);
-
-  /// getType() specialization - Type is always an empty struct.
-  ///
-  inline const Type *getType() const {
-    return Type::EmptyStructTy;
-  }
-
-  /// isNullValue - Return true if this is the value that would be returned by
-  /// getNullValue.  This always returns false because getNullValue will never
-  /// produce metadata.
-  virtual bool isNullValue() const {
-    return false;
-  }
-
-  /// Profile - calculate a unique identifier for this MDNode to collapse
-  /// duplicates
-  void Profile(FoldingSetNodeID &ID);
-
-  virtual void destroyConstant();
-  virtual void replaceUsesOfWithOnConstant(Value *From, Value *To, Use *U);
-
-  /// Methods for support type inquiry through isa, cast, and dyn_cast:
-  static inline bool classof(const MDNode *) { return true; }
-  static bool classof(const Value *V) {
-    return V->getValueID() == MDNodeVal;
-  }
-};
-
-template <>
-struct OperandTraits<MDNode> : VariadicOperandTraits<> {
-};
-
-DEFINE_TRANSPARENT_CASTED_OPERAND_ACCESSORS(MDNode, Constant)
-
 } // End llvm namespace
 
 #endif
diff --git a/include/llvm/MDNode.h b/include/llvm/MDNode.h
new file mode 100644
index 0000000..50b3104
--- /dev/null
+++ b/include/llvm/MDNode.h
@@ -0,0 +1,130 @@
+//===-- llvm/Metadata.h - Constant class subclass definitions ---*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// @file
+/// This file contains the declarations for the subclasses of Constant, 
+/// which represent the different flavors of constant values that live in LLVM.
+/// Note that Constants are immutable (once created they never change) and are 
+/// fully shared by structural equivalence.  This means that two structurally
+/// equivalent constants will always have the same address.  Constant's are
+/// created on demand as needed and never deleted: thus clients don't have to
+/// worry about the lifetime of the objects.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_MDNODE_H
+#define LLVM_MDNODE_H
+
+#include "llvm/Constant.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/ValueHandle.h"
+
+namespace llvm {
+
+//===----------------------------------------------------------------------===//
+/// MDNode - a tuple of other values.
+/// These contain a list of the Constants that represent the metadata. The
+/// operand list is always empty, query the element list instead.
+///
+/// This class will attempt to keep track of values as they are modified. When
+/// a value is replaced the element will be replaced with it, and when the
+/// value is deleted the element is set to a null pointer. In order to preserve
+/// structural equivalence while the elements mutate, the MDNode may call
+/// replaceAllUsesWith on itself. Because of this, users of MDNode must use a
+/// WeakVH or CallbackVH to hold the node pointer if there is a chance that one
+/// of the elements held by the node may change.
+///
+class MDNode : public Constant, public FoldingSetNode {
+  MDNode(const MDNode &);      // DO NOT IMPLEMENT
+
+  friend class ElementVH;
+  struct ElementVH : public CallbackVH {
+    MDNode *OwningNode;
+
+    ElementVH(Value *V, MDNode *Parent)
+      : CallbackVH(V), OwningNode(Parent) {}
+
+    ~ElementVH() {}
+
+    /// deleted - Set this entry in the MDNode to 'null'. This will reallocate
+    /// the MDNode.
+    virtual void deleted() {
+      OwningNode->replaceElement(this->operator Value*(), 0);
+    }
+
+    /// allUsesReplacedWith - Modify the MDNode by replacing this entry with
+    /// new_value. This will reallocate the MDNode.
+    virtual void allUsesReplacedWith(Value *new_value) {
+      OwningNode->replaceElement(this->operator Value*(), new_value);
+    }
+  };
+
+  void replaceElement(Value *From, Value *To);
+
+  SmallVector<ElementVH, 4> Node;
+  typedef SmallVectorImpl<ElementVH>::iterator elem_iterator;
+protected:
+  explicit MDNode(Value*const* Vals, unsigned NumVals);
+public:
+  typedef SmallVectorImpl<ElementVH>::const_iterator const_elem_iterator;
+
+  /// get() - Static factory methods - Return objects of the specified value.
+  ///
+  static MDNode *get(Value*const* Vals, unsigned NumVals);
+
+  Value *getElement(unsigned i) const {
+    return Node[i];
+  }
+
+  unsigned getNumElements() const {
+    return Node.size();
+  }
+
+  const_elem_iterator elem_begin() const {
+    return Node.begin();
+  }
+
+  const_elem_iterator elem_end() const {
+    return Node.end();
+  }
+
+  /// getType() specialization - Type is always an empty struct.
+  ///
+  inline const Type *getType() const {
+    return Type::EmptyStructTy;
+  }
+
+  /// isNullValue - Return true if this is the value that would be returned by
+  /// getNullValue.  This always returns false because getNullValue will never
+  /// produce metadata.
+  virtual bool isNullValue() const {
+    return false;
+  }
+
+  /// Profile - calculate a unique identifier for this MDNode to collapse
+  /// duplicates
+  void Profile(FoldingSetNodeID &ID) const;
+
+  virtual void destroyConstant();
+  virtual void replaceUsesOfWithOnConstant(Value *From, Value *To, Use *U) {
+    assert(0 && "This should never be called because MDNodes have no ops");
+    abort();
+  }
+
+  /// Methods for support type inquiry through isa, cast, and dyn_cast:
+  static inline bool classof(const MDNode *) { return true; }
+  static bool classof(const Value *V) {
+    return V->getValueID() == MDNodeVal;
+  }
+};
+
+} // end llvm namespace
+
+#endif
diff --git a/lib/AsmParser/LLParser.cpp b/lib/AsmParser/LLParser.cpp
index a2edf05..2124397 100644
--- a/lib/AsmParser/LLParser.cpp
+++ b/lib/AsmParser/LLParser.cpp
@@ -18,6 +18,7 @@
 #include "llvm/DerivedTypes.h"
 #include "llvm/InlineAsm.h"
 #include "llvm/Instructions.h"
+#include "llvm/MDNode.h"
 #include "llvm/Module.h"
 #include "llvm/ValueSymbolTable.h"
 #include "llvm/ADT/SmallPtrSet.h"
@@ -1571,13 +1572,11 @@
     ID.Kind = ValID::t_Constant;
     Lex.Lex();
     if (Lex.getKind() == lltok::lbrace) {
-      // MDNode:
-      //  ::= '!' '{' TypeAndValue (',' TypeAndValue)* '}'
-      SmallVector<Constant*, 16> Elts;
+      SmallVector<Value*, 16> Elts;
       if (ParseMDNodeVector(Elts) ||
           ParseToken(lltok::rbrace, "expected end of metadata node"))
         return true;
-    
+
       ID.ConstantVal = MDNode::get(&Elts[0], Elts.size());
       return false;
     }
@@ -3257,14 +3256,23 @@
 //===----------------------------------------------------------------------===//
 
 /// ParseMDNodeVector
-///   ::= TypeAndValue (',' TypeAndValue)*
-bool LLParser::ParseMDNodeVector(SmallVectorImpl<Constant*> &Elts) {
+///   ::= Element (',' Element)*
+/// Element
+///   ::= 'null' | TypeAndValue
+bool LLParser::ParseMDNodeVector(SmallVectorImpl<Value*> &Elts) {
   assert(Lex.getKind() == lltok::lbrace);
   Lex.Lex();
   do {
-    Constant *C;
-    if (ParseGlobalTypeAndValue(C)) return true;
-    Elts.push_back(C);
+    Value *V;
+    if (Lex.getKind() == lltok::kw_null) {
+      Lex.Lex();
+      V = 0;
+    } else {
+      Constant *C;
+      if (ParseGlobalTypeAndValue(C)) return true;
+      V = C;
+    }
+    Elts.push_back(V);
   } while (EatIfPresent(lltok::comma));
 
   return false;
diff --git a/lib/AsmParser/LLParser.h b/lib/AsmParser/LLParser.h
index 44f4c2a..7106689 100644
--- a/lib/AsmParser/LLParser.h
+++ b/lib/AsmParser/LLParser.h
@@ -158,7 +158,7 @@
     bool ParseGlobalValue(const Type *Ty, Constant *&V);
     bool ParseGlobalTypeAndValue(Constant *&V);
     bool ParseGlobalValueVector(SmallVectorImpl<Constant*> &Elts);
-    bool ParseMDNodeVector(SmallVectorImpl<Constant*> &);
+    bool ParseMDNodeVector(SmallVectorImpl<Value*> &);
 
 
     // Function Semantic Analysis.
diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp
index fe20f72..d2b4544 100644
--- a/lib/Bitcode/Reader/BitcodeReader.cpp
+++ b/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -17,6 +17,7 @@
 #include "llvm/DerivedTypes.h"
 #include "llvm/InlineAsm.h"
 #include "llvm/Instructions.h"
+#include "llvm/MDNode.h"
 #include "llvm/Module.h"
 #include "llvm/AutoUpgrade.h"
 #include "llvm/ADT/SmallString.h"
@@ -287,12 +288,10 @@
                                    UserCS->getType()->isPacked());
       } else if (isa<ConstantVector>(UserC)) {
         NewC = ConstantVector::get(&NewOps[0], NewOps.size());
-      } else if (isa<ConstantExpr>(UserC)) {
+      } else {
+        assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr.");
         NewC = cast<ConstantExpr>(UserC)->getWithOperands(&NewOps[0],
                                                           NewOps.size());
-      } else {
-        assert(isa<MDNode>(UserC) && "Must be a metadata node.");
-        NewC = MDNode::get(&NewOps[0], NewOps.size());
       }
       
       UserC->replaceAllUsesWith(NewC);
@@ -300,6 +299,8 @@
       NewOps.clear();
     }
     
+    // Update all ValueHandles, they should be the only users at this point.
+    Placeholder->replaceAllUsesWith(RealVal);
     delete Placeholder;
   }
 }
@@ -1017,10 +1018,13 @@
         return Error("Invalid CST_MDNODE record");
       
       unsigned Size = Record.size();
-      SmallVector<Constant*, 8> Elts;
+      SmallVector<Value*, 8> Elts;
       for (unsigned i = 0; i != Size; i += 2) {
         const Type *Ty = getTypeByID(Record[i], false);
-        Elts.push_back(ValueList.getConstantFwdRef(Record[i+1], Ty));
+        if (Ty != Type::VoidTy)
+          Elts.push_back(ValueList.getConstantFwdRef(Record[i+1], Ty));
+        else
+          Elts.push_back(NULL);
       }
       V = MDNode::get(&Elts[0], Elts.size());
       break;
diff --git a/lib/Bitcode/Writer/BitcodeWriter.cpp b/lib/Bitcode/Writer/BitcodeWriter.cpp
index 1937c7e..1ad70df 100644
--- a/lib/Bitcode/Writer/BitcodeWriter.cpp
+++ b/lib/Bitcode/Writer/BitcodeWriter.cpp
@@ -19,6 +19,7 @@
 #include "llvm/DerivedTypes.h"
 #include "llvm/InlineAsm.h"
 #include "llvm/Instructions.h"
+#include "llvm/MDNode.h"
 #include "llvm/Module.h"
 #include "llvm/TypeSymbolTable.h"
 #include "llvm/ValueSymbolTable.h"
@@ -706,9 +707,14 @@
       }
     } else if (const MDNode *N = dyn_cast<MDNode>(C)) {
       Code = bitc::CST_CODE_MDNODE;
-      for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
-        Record.push_back(VE.getTypeID(N->getOperand(i)->getType()));
-        Record.push_back(VE.getValueID(N->getOperand(i)));
+      for (unsigned i = 0, e = N->getNumElements(); i != e; ++i) {
+        if (N->getElement(i)) {
+          Record.push_back(VE.getTypeID(N->getElement(i)->getType()));
+          Record.push_back(VE.getValueID(N->getElement(i)));
+        } else {
+          Record.push_back(VE.getTypeID(Type::VoidTy));
+          Record.push_back(0);
+        }
       }
     } else {
       assert(0 && "Unknown constant!");
diff --git a/lib/Bitcode/Writer/ValueEnumerator.cpp b/lib/Bitcode/Writer/ValueEnumerator.cpp
index 1c12bc4..8002a36 100644
--- a/lib/Bitcode/Writer/ValueEnumerator.cpp
+++ b/lib/Bitcode/Writer/ValueEnumerator.cpp
@@ -14,6 +14,7 @@
 #include "ValueEnumerator.h"
 #include "llvm/Constants.h"
 #include "llvm/DerivedTypes.h"
+#include "llvm/MDNode.h"
 #include "llvm/Module.h"
 #include "llvm/TypeSymbolTable.h"
 #include "llvm/ValueSymbolTable.h"
@@ -203,6 +204,18 @@
       Values.push_back(std::make_pair(V, 1U));
       ValueMap[V] = Values.size();
       return;
+    } else if (const MDNode *N = dyn_cast<MDNode>(C)) {
+      for (MDNode::const_elem_iterator I = N->elem_begin(), E = N->elem_end();
+           I != E; ++I) {
+        if (*I)
+          EnumerateValue(*I);
+        else
+          EnumerateType(Type::VoidTy);
+      }
+
+      Values.push_back(std::make_pair(V, 1U));
+      ValueMap[V] = Values.size();
+      return;
     }
   }
   
@@ -244,6 +257,11 @@
     // them.
     for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i)
       EnumerateOperandType(C->getOperand(i));
+
+    if (const MDNode *N = dyn_cast<MDNode>(V)) {
+      for (unsigned i = 0, e = N->getNumElements(); i != e; ++i)
+        EnumerateOperandType(N->getElement(i));
+    }
   }
 }
 
diff --git a/lib/VMCore/AsmWriter.cpp b/lib/VMCore/AsmWriter.cpp
index 742931e..efcb07d 100644
--- a/lib/VMCore/AsmWriter.cpp
+++ b/lib/VMCore/AsmWriter.cpp
@@ -23,6 +23,7 @@
 #include "llvm/InlineAsm.h"
 #include "llvm/Instruction.h"
 #include "llvm/Instructions.h"
+#include "llvm/MDNode.h"
 #include "llvm/Module.h"
 #include "llvm/ValueSymbolTable.h"
 #include "llvm/TypeSymbolTable.h"
@@ -945,10 +946,16 @@
 
   if (const MDNode *N = dyn_cast<MDNode>(CV)) {
     Out << "!{";
-    for (MDNode::const_op_iterator I = N->op_begin(), E = N->op_end(); I != E;){
-      TypePrinter.print((*I)->getType(), Out);
-      Out << ' ';
-      WriteAsOperandInternal(Out, *I, TypePrinter, Machine);
+    for (MDNode::const_elem_iterator I = N->elem_begin(), E = N->elem_end();
+         I != E;) {
+      if (!*I) {
+        Out << "null";
+      } else {
+        TypePrinter.print((*I)->getType(), Out);
+        Out << ' ';
+        WriteAsOperandInternal(Out, *I, TypePrinter, Machine);
+      }
+
       if (++I != E)
         Out << ", ";
     }
diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp
index 2afaa6c..b38474d 100644
--- a/lib/VMCore/Constants.cpp
+++ b/lib/VMCore/Constants.cpp
@@ -16,6 +16,7 @@
 #include "llvm/DerivedTypes.h"
 #include "llvm/GlobalValue.h"
 #include "llvm/Instructions.h"
+#include "llvm/MDNode.h"
 #include "llvm/Module.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/StringExtras.h"
@@ -1687,18 +1688,18 @@
 
 static ManagedStatic<FoldingSet<MDNode> > MDNodeSet;
 
-MDNode::MDNode(Constant*const* Vals, unsigned NumVals)
-  : Constant(Type::EmptyStructTy, MDNodeVal,
-             OperandTraits<MDNode>::op_end(this) - NumVals, NumVals) {
-  std::copy(Vals, Vals + NumVals, OperandList);
+MDNode::MDNode(Value*const* Vals, unsigned NumVals)
+  : Constant(Type::EmptyStructTy, MDNodeVal, 0, 0) {
+  for (unsigned i = 0; i != NumVals; ++i)
+    Node.push_back(ElementVH(Vals[i], this));
 }
 
-void MDNode::Profile(FoldingSetNodeID &ID) {
-  for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
+void MDNode::Profile(FoldingSetNodeID &ID) const {
+  for (const_elem_iterator I = elem_begin(), E = elem_end(); I != E; ++I)
     ID.AddPointer(*I);
 }
 
-MDNode *MDNode::get(Constant*const* Vals, unsigned NumVals) {
+MDNode *MDNode::get(Value*const* Vals, unsigned NumVals) {
   FoldingSetNodeID ID;
   for (unsigned i = 0; i != NumVals; ++i)
     ID.AddPointer(Vals[i]);
@@ -1708,12 +1709,13 @@
     return N;
 
   // InsertPoint will have been set by the FindNodeOrInsertPos call.
-  MDNode *N = new(NumVals) MDNode(Vals, NumVals);
+  MDNode *N = new(0) MDNode(Vals, NumVals);
   MDNodeSet->InsertNode(N, InsertPoint);
   return N;
 }
 
 void MDNode::destroyConstant() {
+  MDNodeSet->RemoveNode(this);
   destroyConstantImpl();
 }
 
@@ -2801,23 +2803,19 @@
   destroyConstant();
 }
 
-void MDNode::replaceUsesOfWithOnConstant(Value *From, Value *To, Use *U) {
-  assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
-  
-  SmallVector<Constant*, 8> Values;
-  Values.reserve(getNumOperands());  // Build replacement array...
-  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
-    Constant *Val = getOperand(i);
-    if (Val == From) Val = cast<Constant>(To);
+void MDNode::replaceElement(Value *From, Value *To) {
+  SmallVector<Value*, 4> Values;
+  Values.reserve(getNumElements());  // Build replacement array...
+  for (unsigned i = 0, e = getNumElements(); i != e; ++i) {
+    Value *Val = getElement(i);
+    if (Val == From) Val = To;
     Values.push_back(Val);
   }
-  
-  Constant *Replacement = MDNode::get(&Values[0], Values.size());
+
+  MDNode *Replacement = MDNode::get(&Values[0], Values.size());
   assert(Replacement != this && "I didn't contain From!");
-  
-  // Everyone using this now uses the replacement.
+
   uncheckedReplaceAllUsesWith(Replacement);
-  
-  // Delete the old constant!
+
   destroyConstant();
 }
diff --git a/test/Feature/embeddedmetadata.ll b/test/Feature/embeddedmetadata.ll
index 6f16e6a..c143398 100644
--- a/test/Feature/embeddedmetadata.ll
+++ b/test/Feature/embeddedmetadata.ll
@@ -2,7 +2,7 @@
 
 declare i8 @llvm.something({ } %a)
 
-@llvm.foo = internal constant { } !{i17 123, { } !"foobar"}
+@llvm.foo = internal constant { } !{i17 123, null, { } !"foobar"}
 
 define void @foo() {
   %x = call i8 @llvm.something({ } !{{ } !"f\00oa", i42 123})
diff --git a/unittests/VMCore/MetadataTest.cpp b/unittests/VMCore/MetadataTest.cpp
index 6cf8bc7..c4b845e 100644
--- a/unittests/VMCore/MetadataTest.cpp
+++ b/unittests/VMCore/MetadataTest.cpp
@@ -9,6 +9,10 @@
 
 #include "gtest/gtest.h"
 #include "llvm/Constants.h"
+#include "llvm/Instructions.h"
+#include "llvm/MDNode.h"
+#include "llvm/Type.h"
+#include "llvm/Support/ValueHandle.h"
 #include <sstream>
 
 using namespace llvm;
@@ -59,7 +63,7 @@
 }
 
 // Test the two constructors, and containing other Constants.
-TEST(MDNodeTest, Everything) {
+TEST(MDNodeTest, Simple) {
   char x[3] = { 'a', 'b', 'c' };
   char y[3] = { '1', '2', '3' };
 
@@ -67,25 +71,25 @@
   MDString *s2 = MDString::get(&y[0], &y[3]);
   ConstantInt *CI = ConstantInt::get(APInt(8, 0));
 
-  std::vector<Constant *> V;
+  std::vector<Value *> V;
   V.push_back(s1);
   V.push_back(CI);
   V.push_back(s2);
 
   MDNode *n1 = MDNode::get(&V[0], 3);
-  Constant *const c1 = n1;
+  Value *const c1 = n1;
   MDNode *n2 = MDNode::get(&c1, 1);
   MDNode *n3 = MDNode::get(&V[0], 3);
   EXPECT_NE(n1, n2);
   EXPECT_EQ(n1, n3);
 
-  EXPECT_EQ(3u, n1->getNumOperands());
-  EXPECT_EQ(s1, n1->getOperand(0));
-  EXPECT_EQ(CI, n1->getOperand(1));
-  EXPECT_EQ(s2, n1->getOperand(2));
+  EXPECT_EQ(3u, n1->getNumElements());
+  EXPECT_EQ(s1, n1->getElement(0));
+  EXPECT_EQ(CI, n1->getElement(1));
+  EXPECT_EQ(s2, n1->getElement(2));
 
-  EXPECT_EQ(1u, n2->getNumOperands());
-  EXPECT_EQ(n1, n2->getOperand(0));
+  EXPECT_EQ(1u, n2->getNumElements());
+  EXPECT_EQ(n1, n2->getElement(0));
 
   std::ostringstream oss1, oss2;
   n1->print(oss1);
@@ -94,4 +98,40 @@
   EXPECT_STREQ("{ } !{{ } !{{ } !\"abc\", i8 0, { } !\"123\"}}",
                oss2.str().c_str());
 }
+
+TEST(MDNodeTest, RAUW) {
+  Constant *C = ConstantInt::get(Type::Int32Ty, 1);
+  Instruction *I = new BitCastInst(C, Type::Int32Ty);
+
+  Value *const V1 = I;
+  MDNode *n1 = MDNode::get(&V1, 1);
+  WeakVH wn1 = n1;
+
+  Value *const V2 = C;
+  MDNode *n2 = MDNode::get(&V2, 1);
+  WeakVH wn2 = n2;
+
+  EXPECT_NE(wn1, wn2);
+
+  I->replaceAllUsesWith(C);
+
+  EXPECT_EQ(wn1, wn2);
+}
+
+TEST(MDNodeTest, Delete) {
+  Constant *C = ConstantInt::get(Type::Int32Ty, 1);
+  Instruction *I = new BitCastInst(C, Type::Int32Ty);
+
+  Value *const V = I;
+  MDNode *n = MDNode::get(&V, 1);
+  WeakVH wvh = n;
+
+  EXPECT_EQ(n, wvh);
+
+  delete I;
+
+  std::ostringstream oss;
+  wvh->print(oss);
+  EXPECT_STREQ("{ } !{null}", oss.str().c_str());
+}
 }