[Use] Preserve original uselist order in Use::swap().

[fhahn]

Summary

There is no need to remove and add the swapped values to their
respective use lists. We can just adjust thread the swapped values in
the uselist, preserving the original order.

[fhahn]

Remove unnecessary checks.

[fhahn]

It looks like there's an alternative that also preserves the order and is less complicated: D80116

llvm/include/llvm/IR/Value.h

 class Value {
   // The least-significant bit of the first word of Value *must* be zero:
   //   http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm
   Type *VTy;
   Use *UseList;
 
   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?
 
 protected:
   /// Hold subclass data that can be dropped.
   ///
   /// This member is similar to SubclassData, however it is for holding

llvm/lib/IR/Use.cpp

 #include <new>
 
 namespace llvm {
 
 void Use::swap(Use &RHS) {
   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;
-  }
+  Use **OldPrev = Prev.getPointer();
+  Use *OldNext = Next;
+
+  // Update this
+  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;
 
-  if (OldVal) {
-    RHS.Val = OldVal;
-    RHS.Val->addUse(RHS);
-  } else {
-    RHS.Val = nullptr;
-  }
+  // Update RHS.
+  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 {
   const Use *End = getImpliedUser();
   const UserRef *ref = reinterpret_cast<const UserRef *>(End);
   return ref->getInt() ? ref->getPointer()
                        : reinterpret_cast<User *>(const_cast<Use *>(End));
 }

llvm/test/Transforms/LoopReroll/nonconst_lb.ll

 ; CHECK: for.body.preheader:                               ; preds = %entry
 ; CHECK:   %0 = add i32 %n, -1
 ; CHECK:   %1 = sub i32 %0, %m
 ; CHECK:   %2 = lshr i32 %1, 2
 ; CHECK:   %3 = shl nuw i32 %2, 2
 ; 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
 ; CHECK:   %6 = load i32, i32* %arrayidx, align 4
 ; CHECK:   %mul = shl nsw i32 %6, 2
 ; CHECK:   %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %5
 ; CHECK:   store i32 %mul, i32* %arrayidx2, align 4
 ; CHECK:   %indvar.next = add i32 %indvar, 1