[GVNSink] Fix failing GVNSink tests in the reverse iteration bot

[mgrang]

Summary

The elts of ActivePreds which is defined as a SmallPtrSet are copied into
Blocks using std::copy. This makes the resultant order of Blocks
non-deterministic. We cannot simply sort Blocks as they need to match the
corresponding Values. So a better approach is to define ActivePreds as
SmallSetVector.

This fixes the following failures in http://lab.llvm.org:8011/builders/reverse-iteration:
        LLVM :: Transforms/GVNSink/indirect-call.ll
        LLVM :: Transforms/GVNSink/sink-common-code.ll
        LLVM :: Transforms/GVNSink/struct.ll

[efriedma]

This is right in the sense that it's deterministic, which is definitely an improvement. I'm not sure equality comparisons on ModelledPHI really work the way they're supposed to, even with this patch, but I guess we don't need to fix that here.

Looks fine, but I'll wait for @dberlin to comment.

[mgrang]

@dberlin Could you please review this?

[• dberlin]

This seems reasonable to me,
I'd just add a comment to explain why it's a small set vector (so nobody breaks this future)

llvm/trunk/lib/Transforms/Scalar/GVNSink.cpp

 ///   ...
 ///
 /// It continues until all blocks have been exhausted. Use \c getActiveBlocks()
 /// to
 /// determine which blocks are still going and the order they appear in the
 /// list returned by operator*.
 class LockstepReverseIterator {
   ArrayRef<BasicBlock *> Blocks;
-  SmallPtrSet<BasicBlock *, 4> ActiveBlocks;
+  SmallSetVector<BasicBlock *, 4> ActiveBlocks;
   SmallVector<Instruction *, 4> Insts;
   bool Fail;
 
 public:
   LockstepReverseIterator(ArrayRef<BasicBlock *> Blocks) : Blocks(Blocks) {
     reset();
   }
 
   void reset() {
     Fail = false;
     ActiveBlocks.clear();
     for (BasicBlock *BB : Blocks)
       ActiveBlocks.insert(BB);
     Insts.clear();
     for (BasicBlock *BB : Blocks) {
       if (BB->size() <= 1) {
         // Block wasn't big enough - only contained a terminator.
-        ActiveBlocks.erase(BB);
+        ActiveBlocks.remove(BB);
         continue;
       }
       Insts.push_back(BB->getTerminator()->getPrevNode());
     }
     if (Insts.empty())
       Fail = true;
   }
 
   bool isValid() const { return !Fail; }
   ArrayRef<Instruction *> operator*() const { return Insts; }
-  SmallPtrSet<BasicBlock *, 4> &getActiveBlocks() { return ActiveBlocks; }
 
-  void restrictToBlocks(SmallPtrSetImpl<BasicBlock *> &Blocks) {
+  // Note: This needs to return a SmallSetVector as the elements of
+  // ActiveBlocks will be later copied to Blocks using std::copy. The
+  // resultant order of elements in Blocks needs to be deterministic.
+  // Using SmallPtrSet instead causes non-deterministic order while
+  // copying. And we cannot simply sort Blocks as they need to match the
+  // corresponding Values.
+  SmallSetVector<BasicBlock *, 4> &getActiveBlocks() { return ActiveBlocks; }
+
+  void restrictToBlocks(SmallSetVector<BasicBlock *, 4> &Blocks) {
     for (auto II = Insts.begin(); II != Insts.end();) {
       if (std::find(Blocks.begin(), Blocks.end(), (*II)->getParent()) ==
           Blocks.end()) {
-        ActiveBlocks.erase((*II)->getParent());
+        ActiveBlocks.remove((*II)->getParent());
         II = Insts.erase(II);
       } else {
         ++II;
       }
     }
   }
 
   void operator--() {
     if (Fail)
       return;
     SmallVector<Instruction *, 4> NewInsts;
     for (auto *Inst : Insts) {
       if (Inst == &Inst->getParent()->front())
-        ActiveBlocks.erase(Inst->getParent());
+        ActiveBlocks.remove(Inst->getParent());
       else
         NewInsts.push_back(Inst->getPrevNode());
     }
     if (NewInsts.empty()) {
       Fail = true;
       return;
     }
     Insts = NewInsts;
public:
   ModelledPHI(ArrayRef<Instruction *> Insts, unsigned OpNum, const BArray &B) {
     std::copy(B.begin(), B.end(), std::back_inserter(Blocks));
     for (auto *I : Insts)
       Values.push_back(I->getOperand(OpNum));
   }
 
   /// Restrict the PHI's contents down to only \c NewBlocks.
   /// \c NewBlocks must be a subset of \c this->Blocks.
-  void restrictToBlocks(const SmallPtrSetImpl<BasicBlock *> &NewBlocks) {
+  void restrictToBlocks(const SmallSetVector<BasicBlock *, 4> &NewBlocks) {
     auto BI = Blocks.begin();
     auto VI = Values.begin();
     while (BI != Blocks.end()) {
       assert(VI != Values.end());
       if (std::find(NewBlocks.begin(), NewBlocks.end(), *BI) ==
           NewBlocks.end()) {
         BI = Blocks.erase(BI);
         VI = Values.erase(VI);
Optional<SinkingInstructionCandidate> GVNSink::analyzeInstructionForSinking(
 
   // Now restrict the number of incoming blocks down to only those with
   // VNumToSink.
   auto &ActivePreds = LRI.getActiveBlocks();
   unsigned InitialActivePredSize = ActivePreds.size();
   SmallVector<Instruction *, 4> NewInsts;
   for (auto *I : Insts) {
     if (VN.lookup(I) != VNumToSink)
-      ActivePreds.erase(I->getParent());
+      ActivePreds.remove(I->getParent());
     else
       NewInsts.push_back(I);
   }
   for (auto *I : NewInsts)
     if (isInstructionBlacklisted(I))
       return None;
 
   // If we've restricted the incoming blocks, restrict all needed PHIs also