Index: include/llvm/Support/GenericDomTreeConstruction.h
===================================================================
--- include/llvm/Support/GenericDomTreeConstruction.h
+++ include/llvm/Support/GenericDomTreeConstruction.h
@@ -706,7 +706,7 @@
       // algorithm does not really know or use the set of roots and can make a
       // different (implicit) decision about which nodes within an infinite loop
       // becomes a root.
-      if (DT.isVirtualRoot(TN->getIDom())) {
+      if (TN && !DT.isVirtualRoot(TN->getIDom())) {
         DEBUG(dbgs() << "Root " << BlockNamePrinter(R)
                      << " is not virtual root's child\n"
                      << "The entire tree needs to be rebuilt\n");
@@ -920,21 +920,21 @@
     const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
     const TreeNodePtr NCD = DT.getNode(NCDBlock);
 
-    // To dominates From -- nothing to do.
-    if (ToTN == NCD) return;
+    // If To dominates From -- nothing to do.
+    if (ToTN != NCD) {
+      DT.DFSInfoValid = false;
 
-    DT.DFSInfoValid = false;
-
-    const TreeNodePtr ToIDom = ToTN->getIDom();
-    DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
-                 << BlockNamePrinter(ToIDom) << "\n");
+      const TreeNodePtr ToIDom = ToTN->getIDom();
+      DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
+                   << BlockNamePrinter(ToIDom) << "\n");
 
-    // To remains reachable after deletion.
-    // (Based on the caption under Figure 4. from the second paper.)
-    if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
-      DeleteReachable(DT, BUI, FromTN, ToTN);
-    else
-      DeleteUnreachable(DT, BUI, ToTN);
+      // To remains reachable after deletion.
+      // (Based on the caption under Figure 4. from the second paper.)
+      if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
+        DeleteReachable(DT, BUI, FromTN, ToTN);
+      else
+        DeleteUnreachable(DT, BUI, ToTN);
+    }
 
     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
   }
Index: unittests/IR/DominatorTreeBatchUpdatesTest.cpp
===================================================================
--- unittests/IR/DominatorTreeBatchUpdatesTest.cpp
+++ unittests/IR/DominatorTreeBatchUpdatesTest.cpp
@@ -258,3 +258,87 @@
     EXPECT_TRUE(PDT.verify());
   }
 }
+
+// These are some odd flowgraphs, usually generated from csmith cases,
+// which are difficult on post dom trees.
+TEST(DominatorTreeBatchUpdates, InfiniteLoop) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "2"}, {"2", "3"}, {"3", "6"}, {"3", "5"}, {"4", "5"}, {"5", "2"},
+      {"6", "3"}, {"6", "4"}};
+
+  // SplitBlock on 3 -> 5
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGInsert, {"7", "5"}},  {CFGInsert, {"3", "7"}},
+      {CFGDelete, {"3", "5"}}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  while (B.applyUpdate())
+    ;
+
+  auto DomUpdates = ToDomUpdates(B, Updates);
+  DT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, DeadBlocks) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "3"}, {"3", "4"}, {"3", "5"}, {"5", "6"}, {"6", "7"}, {"6", "9"}, {"4", "14"},
+      {"7", "8"}, {"8", "8"}, {"9", "10"}, {"9", "11"}, {"10", "13"}, {"11", "13"},
+      {"12", "15"}, {"12", "13"}, {"15", "13"}, {"13", "2"}, {"2", "3"}, {"13", "14"}};
+
+  // Remove dead 12 and 13,
+  // plus SplitBlock on 13 -> 14
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGDelete, {"15", "13"}},  {CFGDelete, {"12", "13"}}, {CFGDelete, {"12", "15"}},
+      {CFGInsert, {"N", "14"}},  {CFGInsert, {"13", "N"}}, {CFGDelete, {"13", "14"}}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  while (B.applyUpdate())
+    ;
+
+  auto DomUpdates = ToDomUpdates(B, Updates);
+  DT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, InfiniteLoop2) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "2"}, {"2", "6"}, {"2", "3"}, {"3", "4"},
+      {"4", "5"}, {"4", "6"}, {"5", "4"}, {"6", "2"}};
+
+  // SplitBlock on 4 -> 6
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGInsert, {"N", "6"}},  {CFGInsert, {"4", "N"}}, {CFGDelete, {"4", "6"}}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  while (B.applyUpdate())
+    ;
+
+  auto DomUpdates = ToDomUpdates(B, Updates);
+  DT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(PDT.verify());
+}