[PHINode] Preserve use-list order when removing incoming values.

[fhahn]

Summary

Currently we remove/add all ops we copy from their use lists. We can
just swap the op to remove with the last op, which preserves the
use-lists and needs fewer copies.

But it changes the order of the PHI operands. With this change, 14 unit
tests fail. If that's no concern, I'll go ahead and update them.
Otherwise we could also do the copy with preserving the use-list order I
think.

My motivation for this change is to fix a case where we end up with
a non-deterministic use-list order after simplifycfg, which I think is
caused by this trashing of the use-lists.

[fhahn]

Add move assignment operator that preserves the uselist order and use
std::move instead of std::copy. This preserves the original order of operands instead
of swapping them, which is slightly better IMO as swapping would mean that the order
of the remaining operands is dependent on the order in which we remove incoming values.

[fhahn]

ping

[fhahn]

ping

[fhahn]

ping

[fhahn]

ping

[efriedma]

My motivation for this change is to fix a case where we end up with a non-deterministic use-list order after simplifycfg, which I think is caused by this trashing of the use-lists.

I don't see how this could be a problem. Sure, mixing up the order is sort of confusing, but it should get mixed up in a deterministic way.

llvm/include/llvm/IR/Value.h

739

Is this "if" actually necessary? Use::removeFromList just unconditionally dereferences Prev.

llvm/lib/IR/Instructions.cpp

129

Even if this patch fixes the use/def list thrashing, swap would still be faster.

[fhahn]

In D64884#1661810, @efriedma wrote:

My motivation for this change is to fix a case where we end up with a non-deterministic use-list order after simplifycfg, which I think is caused by this trashing of the use-lists.

I don't see how this could be a problem. Sure, mixing up the order is sort of confusing, but it should get mixed up in a deterministic way.

I think I came across this for a codegen non-determinism case fixed by rL365970.

The issue there was that removing blocks in non-deterministic order caused non-deterministic codegen later on, because depending on the deletion order, the use lists order of some PHIs were different. With this fix, we would not have to enforce an order on block deletions, at least not because of the use-list issue.

llvm/lib/IR/Instructions.cpp

129

Yep, I also fixed a similar use-list issue when wapping, so we could swap here as well (D64886).

But that would make the order of incoming values dependent on the deletion order, I think, defeating the original motivation of the patch.

llvm/include/llvm/IR/Use.h

public:
   /// For an instruction operand, for example, this will return the
   /// instruction.
   User *getUser() const LLVM_READONLY;
 
   inline void set(Value *Val);
 
   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; }
 
   Use *getNext() const { return Next; }
 
   /// Return the operand # of this use in its User.
   unsigned getOperandNo() const;

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
Value *Use::operator=(Value *RHS) {
   return RHS;
 }
 
 const Use &Use::operator=(const Use &RHS) {
   set(RHS.Val);
   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.
     return;
 
   // Note: this function completely ignores Prev pointers until the end when
   // they're fixed en masse.
 

llvm/lib/IR/Instructions.cpp

 }
 
 // removeIncomingValue - Remove an incoming value.  This is useful if a
 // predecessor basic block is deleted.
 Value *PHINode::removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty) {
   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);
   setNumHungOffUseOperands(getNumOperands() - 1);
 
   // If the PHI node is dead, because it has zero entries, nuke it now.
   if (getNumOperands() == 0 && DeletePHIIfEmpty) {
     // If anyone is using this PHI, make them use a dummy value instead...