diff --git a/llvm/include/llvm/IR/Use.h b/llvm/include/llvm/IR/Use.h
--- a/llvm/include/llvm/IR/Use.h
+++ b/llvm/include/llvm/IR/Use.h
@@ -116,6 +116,7 @@
 
   inline Value *operator=(Value *RHS);
   inline const Use &operator=(const Use &RHS);
+  inline const Use &operator=(Use &&RHS);
 
   Value *operator->() { return Val; }
   const Value *operator->() const { return Val; }
diff --git a/llvm/include/llvm/IR/Value.h b/llvm/include/llvm/IR/Value.h
--- a/llvm/include/llvm/IR/Value.h
+++ b/llvm/include/llvm/IR/Value.h
@@ -77,6 +77,7 @@
 
   friend class ValueAsMetadata; // Allow access to IsUsedByMD.
   friend class ValueHandleBase;
+  friend class Use;
 
   const unsigned char SubclassID;   // Subclass identifier (for isa/dyn_cast)
   unsigned char HasValueHandle : 1; // Has a ValueHandle pointing to this?
@@ -723,6 +724,28 @@
   return *this;
 }
 
+const Use &Use::operator=(Use &&RHS) {
+  if (Val)
+    removeFromList();
+
+  if (RHS.Val) {
+    Val = RHS.Val;
+    Next = RHS.Next;
+    Prev.setPointer(RHS.Prev.getPointer());
+
+    // Replace pointers to RHS with pointers to this in RHS's uselist.
+    if (RHS.Next)
+      RHS.Next->setPrev(&Next);
+    if (Val->UseList == &RHS)
+      Val->UseList = this;
+    else
+      (*Prev.getPointer()) = this;
+  }
+
+  RHS.Val = nullptr;
+  return *this;
+}
+
 template <class Compare> void Value::sortUseList(Compare Cmp) {
   if (!UseList || !UseList->Next)
     // No need to sort 0 or 1 uses.
diff --git a/llvm/lib/IR/Instructions.cpp b/llvm/lib/IR/Instructions.cpp
--- a/llvm/lib/IR/Instructions.cpp
+++ b/llvm/lib/IR/Instructions.cpp
@@ -123,12 +123,8 @@
   Value *Removed = getIncomingValue(Idx);
 
   // Move everything after this operand down.
-  //
-  // FIXME: we could just swap with the end of the list, then erase.  However,
-  // clients might not expect this to happen.  The code as it is thrashes the
-  // use/def lists, which is kinda lame.
-  std::copy(op_begin() + Idx + 1, op_end(), op_begin() + Idx);
-  std::copy(block_begin() + Idx + 1, block_end(), block_begin() + Idx);
+  std::move(op_begin() + Idx + 1, op_end(), op_begin() + Idx);
+  std::move(block_begin() + Idx + 1, block_end(), block_begin() + Idx);
 
   // Nuke the last value.
   Op<-1>().set(nullptr);