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();
 }