Index: include/llvm/Support/GenericDomTreeConstruction.h
===================================================================
--- include/llvm/Support/GenericDomTreeConstruction.h
+++ include/llvm/Support/GenericDomTreeConstruction.h
@@ -620,18 +620,17 @@
   // Helper struct used during edge insertions.
   struct InsertionInfo {
     using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
-    struct DecreasingLevel {
+    struct Compare {
       bool operator()(const BucketElementTy &First,
                       const BucketElementTy &Second) const {
-        return First.first > Second.first;
+        return First.first < Second.first;
       }
     };
 
     std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
-        DecreasingLevel>
-        Bucket;  // Queue of tree nodes sorted by level in descending order.
-    SmallDenseSet<TreeNodePtr, 8> Affected;
-    SmallDenseMap<TreeNodePtr, unsigned, 8> Visited;
+                        Compare>
+        Bucket; // Queue of tree nodes sorted by level in descending order.
+    SmallDenseSet<TreeNodePtr, 8> Visited;
     SmallVector<TreeNodePtr, 8> AffectedQueue;
     SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
   };
@@ -744,13 +743,14 @@
 
     // Identify and collect affected nodes.
     InsertionInfo II;
+    SmallVector<TreeNodePtr, 8> Stack;
     LLVM_DEBUG(dbgs() << "Marking " << BlockNamePrinter(To)
                       << " as affected\n");
-    II.Affected.insert(To);
     const unsigned ToLevel = To->getLevel();
     LLVM_DEBUG(dbgs() << "Putting " << BlockNamePrinter(To)
                       << " into a Bucket\n");
     II.Bucket.push({ToLevel, To});
+    II.Visited.insert(To);
 
     while (!II.Bucket.empty()) {
       const TreeNodePtr CurrentNode = II.Bucket.top().second;
@@ -759,11 +759,10 @@
       LLVM_DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
                         << BlockNamePrinter(CurrentNode) << "\n");
 
-      II.Visited.insert({CurrentNode, CurrentLevel});
       II.AffectedQueue.push_back(CurrentNode);
 
       // Discover and collect affected successors of the current node.
-      VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II);
+      VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, Stack, NCD, II);
     }
 
     // Finish by updating immediate dominators and levels.
@@ -772,23 +771,20 @@
 
   // Visits an affected node and collect its affected successors.
   static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
-                             const TreeNodePtr TN, const unsigned RootLevel,
+                             TreeNodePtr TN, const unsigned RootLevel,
+                             SmallVectorImpl<TreeNodePtr> &Stack,
                              const TreeNodePtr NCD, InsertionInfo &II) {
     const unsigned NCDLevel = NCD->getLevel();
     LLVM_DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << ",  RootLevel "
                       << RootLevel << "\n");
 
-    SmallVector<TreeNodePtr, 8> Stack = {TN};
     assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
 
-    SmallPtrSet<TreeNodePtr, 8> Processed;
-
-    do {
-      TreeNodePtr Next = Stack.pop_back_val();
-      LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n");
+    while (1) {
+      LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(TN) << "\n");
 
       for (const NodePtr Succ :
-           ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) {
+           ChildrenGetter<IsPostDom>::Get(TN->getBlock(), BUI)) {
         const TreeNodePtr SuccTN = DT.getNode(Succ);
         assert(SuccTN && "Unreachable successor found at reachable insertion");
         const unsigned SuccLevel = SuccTN->getLevel();
@@ -796,41 +792,25 @@
         LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
                           << ", level = " << SuccLevel << "\n");
 
-        // Do not process the same node multiple times.
-        if (Processed.count(Next) > 0)
+        if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second)
           continue;
 
-        // Succ dominated by subtree From -- not affected.
-        // (Based on the lemma 2.5 from the second paper.)
         if (SuccLevel > RootLevel) {
-          LLVM_DEBUG(dbgs() << "\t\tDominated by subtree From\n");
-          if (II.Visited.count(SuccTN) != 0) {
-            LLVM_DEBUG(dbgs() << "\t\t\talready visited at level "
-                              << II.Visited[SuccTN] << "\n\t\t\tcurrent level "
-                              << RootLevel << ")\n");
-
-            // A node can be necessary to visit again if we see it again at
-            // a lower level than before.
-            if (II.Visited[SuccTN] >= RootLevel)
-              continue;
-          }
-
           LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
                             << BlockNamePrinter(Succ) << "\n");
-          II.Visited.insert({SuccTN, RootLevel});
           II.VisitedNotAffectedQueue.push_back(SuccTN);
           Stack.push_back(SuccTN);
-        } else if ((SuccLevel > NCDLevel + 1) &&
-            II.Affected.count(SuccTN) == 0) {
+        } else {
           LLVM_DEBUG(dbgs() << "\t\tMarking affected and adding "
                             << BlockNamePrinter(Succ) << " to a Bucket\n");
-          II.Affected.insert(SuccTN);
           II.Bucket.push({SuccLevel, SuccTN});
         }
       }
 
-      Processed.insert(Next);
-    } while (!Stack.empty());
+      if (Stack.empty())
+        break;
+      TN = Stack.pop_back_val();
+    }
   }
 
   // Updates immediate dominators and levels after insertion.