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?
diff --git a/llvm/lib/IR/Use.cpp b/llvm/lib/IR/Use.cpp
--- a/llvm/lib/IR/Use.cpp
+++ b/llvm/lib/IR/Use.cpp
@@ -17,24 +17,37 @@
   if (Val == RHS.Val)
     return;
 
-  if (Val)
-    removeFromList();
+  assert(Val && RHS.Val && "Need proper uses");
 
   Value *OldVal = Val;
-  if (RHS.Val) {
-    RHS.removeFromList();
-    Val = RHS.Val;
-    Val->addUse(*this);
-  } else {
-    Val = nullptr;
-  }
-
-  if (OldVal) {
-    RHS.Val = OldVal;
-    RHS.Val->addUse(RHS);
-  } else {
-    RHS.Val = nullptr;
-  }
+  Use **OldPrev = Prev.getPointer();
+  Use *OldNext = Next;
+
+  // Update this
+  Val = RHS.Val;
+  Prev.setPointer(RHS.Prev.getPointer());
+  Next = RHS.Next;
+
+  // Adjust use list pointers to point to this instead of RHS.
+  if (Next)
+    Next->setPrev(&Next);
+  if (Val->UseList == &RHS)
+    Val->UseList = this;
+  else
+    (*Prev.getPointer()) = this;
+
+  // Update RHS.
+  RHS.Val = OldVal;
+  RHS.Prev.setPointer(OldPrev);
+  RHS.Next = OldNext;
+
+  // Adjust use list pointers to point to RHS instead of this.
+  if (RHS.Next)
+    RHS.Next->setPrev(&RHS.Next);
+  if (RHS.Val->UseList == this)
+    RHS.Val->UseList = &RHS;
+  else
+    (*RHS.Prev.getPointer()) = &RHS;
 }
 
 User *Use::getUser() const {
diff --git a/llvm/test/Transforms/LoopReroll/nonconst_lb.ll b/llvm/test/Transforms/LoopReroll/nonconst_lb.ll
--- a/llvm/test/Transforms/LoopReroll/nonconst_lb.ll
+++ b/llvm/test/Transforms/LoopReroll/nonconst_lb.ll
@@ -56,7 +56,7 @@
 ; CHECK:   %4 = add i32 %3, 3
 ; CHECK:   br label %for.body
 
-; CHECK: for.body:                                         ; preds = %for.body, %for.body.preheader
+; CHECK: for.body:                                         ; preds = %for.body.preheader, %for.body
 ; CHECK:   %indvar = phi i32 [ 0, %for.body.preheader ], [ %indvar.next, %for.body ]
 ; CHECK:   %5 = add i32 %m, %indvar
 ; CHECK:   %arrayidx = getelementptr inbounds i32, i32* %B, i32 %5