Use a deterministic order when updating the DominatorTree

[bjope]

Summary

This solved a problem with non-deterministic output from opt due
to not performing dominator tree updates in a deterministic order.
The problem found was the JumpThreading used the DomTreeUpdater via
llvm::MergeBasicBlockIntoOnlyPred. And when preparing the list of
updates to send to DomTreeUpdater::applyUpdates we iterated over
a SmallPtrSet, which does not give a well-defined order.

The added domtree-updates.ll test case is an example that would
result in non-deterministic printouts of the domtree. Semantically
those domtree:s where equivalent, but since passes (at least EarlyCSE)
are iterating over nodes in the dominator tree the order in which
transforms are applied transitively also depend on the order in which
dominator tree updates are performed.

[lebedev.ri]

I think we need to first establish whether this is a bug in DomTree/DomTreeUpdater or the passes that depend on the dom tree node order or here.

[bjope]

In D110292#3017659, @lebedev.ri wrote:

I think we need to first establish whether this is a bug in DomTree/DomTreeUpdater or the passes that depend on the dom tree node order or here.

Sure! Agreed!
When I started off with this patch I thought it was a single place to update (i.e. that it really was a one-location bug). But now it seems like this was more of a design choice since the patch grew so large.

Here are some of my ideas about it (and my motivations for/against are probably pretty vague):

One assumed upside with this patch is that if passes like EarlyCSE need to make an ordering for the nodes to be iterated themselves, then that would be an extra cost (at least potentially) compared to just doing things in a deterministic order from the start.
With that being said, the accumulative cost of doing things like in this patch up-front might end up being higher than doing a single sorting later. And it will also just add a cost even if there are no passes later in the pipeline that depends on the node order. So lots of uncertainty when considering which is best for compile-time.

One downside with this is that if the analysis is invalidated (and recalculated from scratch) then we probably get a different order of the nodes. Still making things a bit shaky when debugging/bisecting/reducing test cases.
With that being said, when debugging and printing the DomTree between passes etc it could be nice if the printout is deterministic. This could of course be solved by doing some kind of sorting before printing, just like we would have to do in EarlyCSE. And the performance of the print-function should not be that important.

(maybe this discussion should move back to the llvm-dev mailthread...)

[foad]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

242

This line looks like a bug fix -- or does it just avoid doing some unnecesssary updates?

[bjope]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

242

This will go away when rebasing. It was pre committed as: https://reviews.llvm.org/rG85a586501bcc5b556d34a566b9d256d56d6fc5ba

[bjope]

Updated code comments.

[bjope]

I'm also showing the alternative approach, making EarlyCSE less depending on what other passes is doing when updating the DomTree, here: https://reviews.llvm.org/D114620

[kuhar]

llvm/include/llvm/Support/GenericDomTree.h

550–552

unordered -> ordered also here?

llvm/lib/CodeGen/IndirectBrExpandPass.cpp

265–267

This pattern appears many time in the patch. I wonder if we could have a helper function that helps with that. Perhaps something like insert_range(InsertTo, NewElements) -> RangeOfInserted:

for (BasicBlock* Inserted : insert_range(UniqueSuccessors, BBs))
  Updates.push_back(...);

llvm/test/Transforms/JumpThreading/domtree-updates.ll

12

nit: I -> We or `it was possible to see varrying'

[lebedev.ri]

llvm/lib/CodeGen/IndirectBrExpandPass.cpp

265–267

I tried doing that in D99444, but reviewers weren't convinced and i lacked motivation to follow-up.

[kuhar]

I think it would be good to send the DomTree documentation changes separately as they are a clear improvement regardless of whether this patch goes in or not.

llvm/lib/CodeGen/IndirectBrExpandPass.cpp

265–267

Then I think it's fine as is, and we could clean it up separately.

[nikic]

LGTM

[bjope]

llvm/lib/CodeGen/IndirectBrExpandPass.cpp

265–267

Ok, great. Thanks for all the feedback.

llvm/include/llvm/Support/GenericDomTree.h

#endif
   ///  - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
   ///    sense to insert the same edge twice.
   ///
   /// What's more, the functions assumes that it's safe to ask every node in the
   /// CFG about its children and inverse children. This implies that deletions
   /// of CFG edges must not delete the CFG nodes before calling this function.
   ///
   /// The applyUpdates function can reorder the updates and remove redundant
-  /// ones internally. The batch updater is also able to detect sequences of
-  /// zero and exactly one update -- it's optimized to do less work in these
-  /// cases.
+  /// ones internally (as long as it is done in a deterministic fashion). The
+  /// batch updater is also able to detect sequences of zero and exactly one
+  /// update -- it's optimized to do less work in these cases.
   ///
   /// Note that for postdominators it automatically takes care of applying
   /// updates on reverse edges internally (so there's no need to swap the
   /// From and To pointers when constructing DominatorTree::UpdateType).
   /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
   /// with the same template parameter T.
   ///
-  /// \param Updates An unordered sequence of updates to perform. The current
-  /// CFG and the reverse of these updates provides the pre-view of the CFG.
+  /// \param Updates An ordered sequence of updates to perform. The current CFG
+  /// and the reverse of these updates provides the pre-view of the CFG.
   ///
   void applyUpdates(ArrayRef<UpdateType> Updates) {
     GraphDiff<NodePtr, IsPostDominator> PreViewCFG(
         Updates, /*ReverseApplyUpdates=*/true);
     DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, nullptr);
   }
 
-  /// \param Updates An unordered sequence of updates to perform. The current
-  /// CFG and the reverse of these updates provides the pre-view of the CFG.
-  /// \param PostViewUpdates An unordered sequence of update to perform in order
+  /// \param Updates An ordered sequence of updates to perform. The current CFG
+  /// and the reverse of these updates provides the pre-view of the CFG.
+  /// \param PostViewUpdates An ordered sequence of update to perform in order
   /// to obtain a post-view of the CFG. The DT will be updated assuming the
   /// obtained PostViewCFG is the desired end state.
   void applyUpdates(ArrayRef<UpdateType> Updates,
                     ArrayRef<UpdateType> PostViewUpdates) {
     if (Updates.empty()) {
       GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);
       DomTreeBuilder::ApplyUpdates(*this, PostViewCFG, &PostViewCFG);
     } else {

llvm/lib/CodeGen/IndirectBrExpandPass.cpp

bool IndirectBrExpandPass::runOnFunction(Function &F) {
 
   // Add a case for each block.
   for (int i : llvm::seq<int>(1, BBs.size()))
     SI->addCase(ConstantInt::get(CommonITy, i + 1), BBs[i]);
 
   if (DTU) {
     // If there were multiple indirectbr's, they may have common successors,
     // but in the dominator tree, we only track unique edges.
-    SmallPtrSet<BasicBlock *, 8> UniqueSuccessors(BBs.begin(), BBs.end());
-    Updates.reserve(Updates.size() + UniqueSuccessors.size());
-    for (BasicBlock *BB : UniqueSuccessors)
+    SmallPtrSet<BasicBlock *, 8> UniqueSuccessors;
+    Updates.reserve(Updates.size() + BBs.size());
+    for (BasicBlock *BB : BBs) {
+      if (UniqueSuccessors.insert(BB).second)
         Updates.push_back({DominatorTree::Insert, SwitchBB, BB});
+    }
     DTU->applyUpdates(Updates);
   }
 
   return true;
 }

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

for (PHINode &PN : BB->phis())
         IncomingValues.push_back(PN.getIncomingValue(0));
     FoldSingleEntryPHINodes(BB, MemDep);
   }
 
   // DTU update: Collect all the edges that exit BB.
   // These dominator edges will be redirected from Pred.
   std::vector<DominatorTree::UpdateType> Updates;
   if (DTU) {
-    SmallPtrSet<BasicBlock *, 2> SuccsOfBB(succ_begin(BB), succ_end(BB));
+    // To avoid processing the same predecessor more than once.
+    SmallPtrSet<BasicBlock *, 8> SeenSuccs;
     SmallPtrSet<BasicBlock *, 2> SuccsOfPredBB(succ_begin(PredBB),
                                                succ_end(PredBB));
-    Updates.reserve(Updates.size() + 2 * SuccsOfBB.size() + 1);
+    Updates.reserve(Updates.size() + 2 * succ_size(BB) + 1);
     // Add insert edges first. Experimentally, for the particular case of two
     // blocks that can be merged, with a single successor and single predecessor
     // respectively, it is beneficial to have all insert updates first. Deleting
     // edges first may lead to unreachable blocks, followed by inserting edges
     // making the blocks reachable again. Such DT updates lead to high compile
     // times. We add inserts before deletes here to reduce compile time.
-    for (BasicBlock *SuccOfBB : SuccsOfBB)
+    for (BasicBlock *SuccOfBB : successors(BB))
       // This successor of BB may already be a PredBB's successor.
       if (!SuccsOfPredBB.contains(SuccOfBB))
+        if (SeenSuccs.insert(SuccOfBB).second)
           Updates.push_back({DominatorTree::Insert, PredBB, SuccOfBB});
-    for (BasicBlock *SuccOfBB : SuccsOfBB)
+    SeenSuccs.clear();
+    for (BasicBlock *SuccOfBB : successors(BB))
+      if (SeenSuccs.insert(SuccOfBB).second)
         Updates.push_back({DominatorTree::Delete, BB, SuccOfBB});
     Updates.push_back({DominatorTree::Delete, PredBB, BB});
   }
 
   Instruction *PTI = PredBB->getTerminator();
   Instruction *STI = BB->getTerminator();
   Instruction *Start = &*BB->begin();
   // If there's nothing to move, mark the starting instruction as the last
   // instruction in the block. Terminator instruction is handled separately.
static BasicBlock *SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt,
   // LCSSA as well, because we force the split point to be after any PHI nodes.
   if (LI)
     if (Loop *L = LI->getLoopFor(Old))
       L->addBasicBlockToLoop(New, *LI);
 
   if (DTU) {
     SmallVector<DominatorTree::UpdateType, 8> Updates;
     // Old dominates New. New node dominates all other nodes dominated by Old.
-    SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfOld(succ_begin(New),
-                                                       succ_end(New));
+    SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfOld;
     Updates.push_back({DominatorTree::Insert, Old, New});
-    Updates.reserve(Updates.size() + 2 * UniqueSuccessorsOfOld.size());
-    for (BasicBlock *UniqueSuccessorOfOld : UniqueSuccessorsOfOld) {
-      Updates.push_back({DominatorTree::Insert, New, UniqueSuccessorOfOld});
-      Updates.push_back({DominatorTree::Delete, Old, UniqueSuccessorOfOld});
+    Updates.reserve(Updates.size() + 2 * succ_size(New));
+    for (BasicBlock *SuccessorOfOld : successors(New))
+      if (UniqueSuccessorsOfOld.insert(SuccessorOfOld).second) {
+        Updates.push_back({DominatorTree::Insert, New, SuccessorOfOld});
+        Updates.push_back({DominatorTree::Delete, Old, SuccessorOfOld});
       }
 
     DTU->applyUpdates(Updates);
   } else if (DT)
     // Old dominates New. New node dominates all other nodes dominated by Old.
     if (DomTreeNode *OldNode = DT->getNode(Old)) {
       std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
 
       DomTreeNode *NewNode = DT->addNewBlock(New, Old);
BasicBlock *llvm::splitBlockBefore(BasicBlock *Old, Instruction *SplitPt,
   if (LI)
     if (Loop *L = LI->getLoopFor(Old))
       L->addBasicBlockToLoop(New, *LI);
 
   if (DTU) {
     SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
     // New dominates Old. The predecessor nodes of the Old node dominate
     // New node.
-    SmallPtrSet<BasicBlock *, 8> UniquePredecessorsOfOld(pred_begin(New),
-                                                         pred_end(New));
+    SmallPtrSet<BasicBlock *, 8> UniquePredecessorsOfOld;
     DTUpdates.push_back({DominatorTree::Insert, New, Old});
-    DTUpdates.reserve(DTUpdates.size() + 2 * UniquePredecessorsOfOld.size());
-    for (BasicBlock *UniquePredecessorOfOld : UniquePredecessorsOfOld) {
-      DTUpdates.push_back({DominatorTree::Insert, UniquePredecessorOfOld, New});
-      DTUpdates.push_back({DominatorTree::Delete, UniquePredecessorOfOld, Old});
+    DTUpdates.reserve(DTUpdates.size() + 2 * pred_size(New));
+    for (BasicBlock *PredecessorOfOld : predecessors(New))
+      if (UniquePredecessorsOfOld.insert(PredecessorOfOld).second) {
+        DTUpdates.push_back({DominatorTree::Insert, PredecessorOfOld, New});
+        DTUpdates.push_back({DominatorTree::Delete, PredecessorOfOld, Old});
       }
 
     DTU->applyUpdates(DTUpdates);
 
     // Move MemoryAccesses still tracked in Old, but part of New now.
     // Update accesses in successor blocks accordingly.
     if (MSSAU) {
       MSSAU->applyUpdates(DTUpdates, DTU->getDomTree());
       if (VerifyMemorySSA)
if (DTU) {
     if (NewBB->isEntryBlock() && DTU->hasDomTree()) {
       // The entry block was removed and there is no external interface for
       // the dominator tree to be notified of this change. In this corner-case
       // we recalculate the entire tree.
       DTU->recalculate(*NewBB->getParent());
     } else {
       // Split block expects NewBB to have a non-empty set of predecessors.
       SmallVector<DominatorTree::UpdateType, 8> Updates;
-      SmallPtrSet<BasicBlock *, 8> UniquePreds(Preds.begin(), Preds.end());
+      SmallPtrSet<BasicBlock *, 8> UniquePreds;
       Updates.push_back({DominatorTree::Insert, NewBB, OldBB});
-      Updates.reserve(Updates.size() + 2 * UniquePreds.size());
-      for (auto *UniquePred : UniquePreds) {
-        Updates.push_back({DominatorTree::Insert, UniquePred, NewBB});
-        Updates.push_back({DominatorTree::Delete, UniquePred, OldBB});
+      Updates.reserve(Updates.size() + 2 * Preds.size());
+      for (auto *Pred : Preds)
+        if (UniquePreds.insert(Pred).second) {
+          Updates.push_back({DominatorTree::Insert, Pred, NewBB});
+          Updates.push_back({DominatorTree::Delete, Pred, OldBB});
         }
       DTU->applyUpdates(Updates);
     }
   } else if (DT) {
     if (OldBB == DT->getRootNode()->getBlock()) {
       assert(NewBB->isEntryBlock());
       DT->setNewRoot(NewBB);
     } else {
       // Split block expects NewBB to have a non-empty set of predecessors.

 SplitBlockAndInsertIfThenImpl(Value *Cond, Instruction *SplitBefore,
                               bool Unreachable, MDNode *BranchWeights,
                               DomTreeUpdater *DTU, DominatorTree *DT,
                               LoopInfo *LI, BasicBlock *ThenBlock) {
   SmallVector<DominatorTree::UpdateType, 8> Updates;
   BasicBlock *Head = SplitBefore->getParent();
   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
   if (DTU) {
-    SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfHead(succ_begin(Tail),
-                                                        succ_end(Tail));
+    SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfHead;
     Updates.push_back({DominatorTree::Insert, Head, Tail});
-    Updates.reserve(Updates.size() + 2 * UniqueSuccessorsOfHead.size());
-    for (BasicBlock *UniqueSuccessorOfHead : UniqueSuccessorsOfHead) {
-      Updates.push_back({DominatorTree::Insert, Tail, UniqueSuccessorOfHead});
-      Updates.push_back({DominatorTree::Delete, Head, UniqueSuccessorOfHead});
+    Updates.reserve(Updates.size() + 2 * succ_size(Tail));
+    for (BasicBlock *SuccessorOfHead : successors(Tail))
+      if (UniqueSuccessorsOfHead.insert(SuccessorOfHead).second) {
+        Updates.push_back({DominatorTree::Insert, Tail, SuccessorOfHead});
+        Updates.push_back({DominatorTree::Delete, Head, SuccessorOfHead});
       }
   }
   Instruction *HeadOldTerm = Head->getTerminator();
   LLVMContext &C = Head->getContext();
   Instruction *CheckTerm;
   bool CreateThenBlock = (ThenBlock == nullptr);
   if (CreateThenBlock) {
     ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
     if (Unreachable)

llvm/lib/Transforms/Utils/Local.cpp

void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
 
   bool ReplaceEntryBB = PredBB->isEntryBlock();
 
   // DTU updates: Collect all the edges that enter
   // PredBB. These dominator edges will be redirected to DestBB.
   SmallVector<DominatorTree::UpdateType, 32> Updates;
 
   if (DTU) {
-    SmallPtrSet<BasicBlock *, 2> PredsOfPredBB(pred_begin(PredBB),
-                                               pred_end(PredBB));
-    Updates.reserve(Updates.size() + 2 * PredsOfPredBB.size() + 1);
-    for (BasicBlock *PredOfPredBB : PredsOfPredBB)
+    // To avoid processing the same predecessor more than once.
+    SmallPtrSet<BasicBlock *, 2> SeenPreds;
+    Updates.reserve(Updates.size() + 2 * pred_size(PredBB) + 1);
+    for (BasicBlock *PredOfPredBB : predecessors(PredBB))
       // This predecessor of PredBB may already have DestBB as a successor.
       if (PredOfPredBB != PredBB)
+        if (SeenPreds.insert(PredOfPredBB).second)
           Updates.push_back({DominatorTree::Insert, PredOfPredBB, DestBB});
-    for (BasicBlock *PredOfPredBB : PredsOfPredBB)
+    SeenPreds.clear();
+    for (BasicBlock *PredOfPredBB : predecessors(PredBB))
+      if (SeenPreds.insert(PredOfPredBB).second)
         Updates.push_back({DominatorTree::Delete, PredOfPredBB, PredBB});
     Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
   }
 
   // Zap anything that took the address of DestBB.  Not doing this will give the
   // address an invalid value.
   if (DestBB->hasAddressTaken()) {
     BlockAddress *BA = BlockAddress::get(DestBB);
     Constant *Replacement =
if (auto *CBI = dyn_cast<CallBrInst>(PredBB->getTerminator())) {
           return false;
     }
   }
 
   LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
 
   SmallVector<DominatorTree::UpdateType, 32> Updates;
   if (DTU) {
+    // To avoid processing the same predecessor more than once.
+    SmallPtrSet<BasicBlock *, 8> SeenPreds;
     // All predecessors of BB will be moved to Succ.
-    SmallPtrSet<BasicBlock *, 8> PredsOfBB(pred_begin(BB), pred_end(BB));
     SmallPtrSet<BasicBlock *, 8> PredsOfSucc(pred_begin(Succ), pred_end(Succ));
-    Updates.reserve(Updates.size() + 2 * PredsOfBB.size() + 1);
-    for (auto *PredOfBB : PredsOfBB)
+    Updates.reserve(Updates.size() + 2 * pred_size(BB) + 1);
+    for (auto *PredOfBB : predecessors(BB))
       // This predecessor of BB may already have Succ as a successor.
       if (!PredsOfSucc.contains(PredOfBB))
+        if (SeenPreds.insert(PredOfBB).second)
           Updates.push_back({DominatorTree::Insert, PredOfBB, Succ});
-    for (auto *PredOfBB : PredsOfBB)
+    SeenPreds.clear();
+    for (auto *PredOfBB : predecessors(BB))
+      if (SeenPreds.insert(PredOfBB).second)
         Updates.push_back({DominatorTree::Delete, PredOfBB, BB});
     Updates.push_back({DominatorTree::Delete, BB, Succ});
   }
 
   if (isa<PHINode>(Succ->begin())) {
     // If there is more than one pred of succ, and there are PHI nodes in
     // the successor, then we need to add incoming edges for the PHI nodes
     //
     const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(Instruction *OldTerm,
   auto *BB = OldTerm->getParent();
   // Remove any superfluous successor edges from the CFG.
   // First, figure out which successors to preserve.
   // If TrueBB and FalseBB are equal, only try to preserve one copy of that
   // successor.
   BasicBlock *KeepEdge1 = TrueBB;
   BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr;
 
-  SmallPtrSet<BasicBlock *, 2> RemovedSuccessors;
+  SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
 
   // Then remove the rest.
   for (BasicBlock *Succ : successors(OldTerm)) {
     // Make sure only to keep exactly one copy of each edge.
     if (Succ == KeepEdge1)
       KeepEdge1 = nullptr;
     else if (Succ == KeepEdge2)
       KeepEdge2 = nullptr;
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU,
   // the limited range of the condition based on how many significant (non-sign)
   // bits are in the condition value.
   unsigned ExtraSignBits = ComputeNumSignBits(Cond, DL, 0, AC, SI) - 1;
   unsigned MaxSignificantBitsInCond = Bits - ExtraSignBits;
 
   // Gather dead cases.
   SmallVector<ConstantInt *, 8> DeadCases;
   SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
+  SmallVector<BasicBlock *, 8> UniqueSuccessors;
   for (auto &Case : SI->cases()) {
     auto *Successor = Case.getCaseSuccessor();
-    if (DTU)
+    if (DTU) {
+      if (!NumPerSuccessorCases.count(Successor))
+        UniqueSuccessors.push_back(Successor);
       ++NumPerSuccessorCases[Successor];
+    }
     const APInt &CaseVal = Case.getCaseValue()->getValue();
     if (Known.Zero.intersects(CaseVal) || !Known.One.isSubsetOf(CaseVal) ||
         (CaseVal.getMinSignedBits() > MaxSignificantBitsInCond)) {
       DeadCases.push_back(Case.getCaseValue());
       if (DTU)
         --NumPerSuccessorCases[Successor];
       LLVM_DEBUG(dbgs() << "SimplifyCFG: switch case " << CaseVal
                         << " is dead.\n");
assert(CaseI != SI->case_default() &&
            "Case was not found. Probably mistake in DeadCases forming.");
     // Prune unused values from PHI nodes.
     CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
     SIW.removeCase(CaseI);
   }
 
   if (DTU) {
     std::vector<DominatorTree::UpdateType> Updates;
-    for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases)
-      if (I.second == 0)
-        Updates.push_back({DominatorTree::Delete, SI->getParent(), I.first});
+    for (auto *Successor : UniqueSuccessors)
+      if (NumPerSuccessorCases[Successor] == 0)
+        Updates.push_back({DominatorTree::Delete, SI->getParent(), Successor});
     DTU->applyUpdates(Updates);
   }
 
   return true;
 }
 
 /// If BB would be eligible for simplification by
 /// TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated
static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
   // Remove the switch.
   SmallPtrSet<BasicBlock *, 8> RemovedSuccessors;
   for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
     BasicBlock *Succ = SI->getSuccessor(i);
 
     if (Succ == SI->getDefaultDest())
       continue;
     Succ->removePredecessor(BB);
-    RemovedSuccessors.insert(Succ);
+    if (DTU && RemovedSuccessors.insert(Succ).second)
+      Updates.push_back({DominatorTree::Delete, BB, Succ});
   }
   SI->eraseFromParent();
 
-  if (DTU) {
-    for (BasicBlock *RemovedSuccessor : RemovedSuccessors)
-      Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
+  if (DTU)
     DTU->applyUpdates(Updates);
-  }
 
   ++NumLookupTables;
   if (NeedMask)
     ++NumLookupTablesHoles;
   return true;
 }
 
 static bool isSwitchDense(ArrayRef<int64_t> Values) {

 }
 
 bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
   BasicBlock *BB = IBI->getParent();
   bool Changed = false;
 
   // Eliminate redundant destinations.
   SmallPtrSet<Value *, 8> Succs;
-  SmallPtrSet<BasicBlock *, 8> RemovedSuccs;
+  SmallSetVector<BasicBlock *, 8> RemovedSuccs;
   for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
     BasicBlock *Dest = IBI->getDestination(i);
     if (!Dest->hasAddressTaken() || !Succs.insert(Dest).second) {
       if (!Dest->hasAddressTaken())
         RemovedSuccs.insert(Dest);
       Dest->removePredecessor(BB);
       IBI->removeDestination(i);
       --i;
for (BasicBlock *OtherPred : predecessors(Succ)) {
     BranchInst *BI2 = dyn_cast<BranchInst>(I);
     if (!BI2 || !BI2->isIdenticalTo(BI))
       continue;
 
     std::vector<DominatorTree::UpdateType> Updates;
 
     // We've found an identical block.  Update our predecessors to take that
     // path instead and make ourselves dead.
-    SmallPtrSet<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB));
-    for (BasicBlock *Pred : Preds) {
+    SmallSetVector<BasicBlock *, 16> UniquePreds(pred_begin(BB), pred_end(BB));
+    for (BasicBlock *Pred : UniquePreds) {
       InvokeInst *II = cast<InvokeInst>(Pred->getTerminator());
       assert(II->getNormalDest() != BB && II->getUnwindDest() == BB &&
              "unexpected successor");
       II->setUnwindDest(OtherPred);
       if (DTU) {
         Updates.push_back({DominatorTree::Insert, Pred, OtherPred});
         Updates.push_back({DominatorTree::Delete, Pred, BB});
       }
     }
 
     // The debug info in OtherPred doesn't cover the merged control flow that
     // used to go through BB.  We need to delete it or update it.
     for (Instruction &Inst : llvm::make_early_inc_range(*OtherPred))
       if (isa<DbgInfoIntrinsic>(Inst))
         Inst.eraseFromParent();
 
-    SmallPtrSet<BasicBlock *, 16> Succs(succ_begin(BB), succ_end(BB));
-    for (BasicBlock *Succ : Succs) {
+    SmallSetVector<BasicBlock *, 16> UniqueSuccs(succ_begin(BB), succ_end(BB));
+    for (BasicBlock *Succ : UniqueSuccs) {
       Succ->removePredecessor(BB);
       if (DTU)
         Updates.push_back({DominatorTree::Delete, BB, Succ});
     }
 
     IRBuilder<> Builder(BI);
     Builder.CreateUnreachable();
     BI->eraseFromParent();

llvm/test/Transforms/JumpThreading/domtree-updates.ll

+; RUN: opt < %s -disable-output -passes='jump-threading,print<domtree>' 2>&1 | FileCheck %s
+
+; REQUIRES: asserts
+
+; The idea behind this test case is to verify that the dominator tree is
+; updated in a deterministic way. Optimizations, at least EarlyCSE, are
+; iterating the vectors that hold child nodes in the DominatorTree. Thus, the
+; end result might differ depending on the order in which nodes are inserted
+; in the dominator tree. Unfortunately this test case is quite large, but it
+; happened to trigger a non-determinism quite often when being executed
+; multipe times (it was possible to see varying results when running the test
+; less that 10 times in a row).
+; The actual problem was tracked down to llvm::MergeBasicBlockIntoOnlyPred, so
+; the important property of the test is probably that it triggers a call to
+; that function, and that the PredsOfPredBB set that is used to populate
+; Updates for the DomTreeUpdater is populated with more than one entry.
+
+; CHECK:      Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries.
+; CHECK-NEXT:   [1] %entry {4294967295,4294967295} [0]
+; CHECK-NEXT:     [2] %for.cond1 {4294967295,4294967295} [1]
+; CHECK-NEXT:       [3] %for.inc19 {4294967295,4294967295} [2]
+; CHECK-NEXT:       [3] %if.then {4294967295,4294967295} [2]
+; CHECK-NEXT:         [4] %for.cond5.preheader {4294967295,4294967295} [3]
+; CHECK-NEXT:           [5] %cleanup {4294967295,4294967295} [4]
+; CHECK-NEXT:             [6] %cleanup16 {4294967295,4294967295} [5]
+; CHECK-NEXT:               [7] %unreachable {4294967295,4294967295} [6]
+; CHECK-NEXT:               [7] %for.end21 {4294967295,4294967295} [6]
+; CHECK-NEXT:           [5] %for.body7 {4294967295,4294967295} [4]
+; CHECK-NEXT:             [6] %for.inc {4294967295,4294967295} [5]
+; CHECK-NEXT:           [5] %return {4294967295,4294967295} [4]
+; CHECK-NEXT:       [3] %cleanup16.thread {4294967295,4294967295} [2]
+; CHECK-NEXT:     [2] %infinite.loop {4294967295,4294967295} [1]
+; CHECK-NEXT: Roots: %entry
+
+
+@a = dso_local local_unnamed_addr global i16 0, align 1
+
+; Function Attrs: nounwind
+define dso_local i16 @g(i16 %a0, i16 %a1, i16 %a2, i16 %a3) local_unnamed_addr {
+entry:
+  %tobool.not = icmp eq i16 %a0, 0
+  br i1 %tobool.not, label %for.cond1, label %infinite.loop
+
+infinite.loop:                                    ; preds = %infinite.loop, %entry
+  br label %infinite.loop
+
+for.cond1:                                        ; preds = %for.inc19, %entry
+  %retval.0 = phi i16 [ %retval.3, %for.inc19 ], [ undef, %entry ]
+  %i.0 = phi i16 [ %i.3, %for.inc19 ], [ undef, %entry ]
+  %tobool2.not = icmp eq i16 %a1, 0
+  br i1 %tobool2.not, label %if.end15, label %if.then
+
+if.then:                                          ; preds = %for.cond1
+  %tobool3.not = icmp eq i16 %a2, 0
+  br i1 %tobool3.not, label %if.end15, label %for.cond5.preheader
+
+for.cond5.preheader:                              ; preds = %if.then
+  %tobool8.not = icmp eq i16 %a3, 0
+  %tobool6.not31 = icmp eq i16 %i.0, 0
+  br i1 %tobool6.not31, label %for.end10, label %for.body7
+
+for.body7:                                        ; preds = %for.inc, %for.cond5.preheader
+  %i.132 = phi i16 [ %inc, %for.inc ], [ %i.0, %for.cond5.preheader ]
+  br i1 %tobool8.not, label %for.inc, label %cleanup
+
+for.inc:                                          ; preds = %for.body7
+  %inc = add i16 %i.132, 1
+  %tobool6.not = icmp eq i16 %inc, 0
+  br i1 %tobool6.not, label %for.end10, label %for.body7
+
+for.end10:                                        ; preds = %for.inc, %for.cond5.preheader
+  %i.1.lcssa = phi i16 [ %i.0, %for.cond5.preheader ], [ 0, %for.inc ]
+  %.26 = select i1 %tobool8.not, i32 0, i32 4
+  br label %cleanup
+
+cleanup:                                          ; preds = %for.end10, %for.body7
+  %i.128 = phi i16 [ %i.1.lcssa, %for.end10 ], [ %i.0, %for.body7 ]
+  %retval.1 = phi i16 [ %retval.0, %for.end10 ], [ 1, %for.body7 ]
+  %cond = phi i1 [ %tobool8.not, %for.end10 ], [ false, %for.body7 ]
+  %cleanup.dest.slot.0 = phi i32 [ %.26, %for.end10 ], [ 1, %for.body7 ]
+  br i1 %cond, label %if.end15, label %cleanup16
+
+if.end15:                                         ; preds = %cleanup, %if.then, %for.cond1
+  %retval.2 = phi i16 [ %retval.1, %cleanup ], [ %retval.0, %if.then ], [ %retval.0, %for.cond1 ]
+  %i.2 = phi i16 [ %i.128, %cleanup ], [ %i.0, %if.then ], [ %i.0, %for.cond1 ]
+  store i16 0, i16* @a, align 1
+  br label %cleanup16
+
+cleanup16:                                        ; preds = %if.end15, %cleanup
+  %retval.3 = phi i16 [ %retval.2, %if.end15 ], [ %retval.1, %cleanup ]
+  %i.3 = phi i16 [ %i.2, %if.end15 ], [ %i.128, %cleanup ]
+  %cleanup.dest.slot.1 = phi i32 [ 0, %if.end15 ], [ %cleanup.dest.slot.0, %cleanup ]
+  switch i32 %cleanup.dest.slot.1, label %unreachable [
+    i32 0, label %for.inc19
+    i32 1, label %return
+    i32 4, label %for.end21
+  ]
+
+for.inc19:                                        ; preds = %cleanup16
+  br label %for.cond1
+
+for.end21:                                        ; preds = %cleanup16
+  br label %return
+
+return:                                           ; preds = %for.end21, %cleanup16
+  %retval.4 = phi i16 [ 17, %for.end21 ], [ %retval.3, %cleanup16 ]
+  ret i16 %retval.4
+
+unreachable:                                      ; preds = %cleanup16
+  unreachable
+}