Index: lib/Transforms/Scalar/NewGVN.cpp
===================================================================
--- lib/Transforms/Scalar/NewGVN.cpp
+++ lib/Transforms/Scalar/NewGVN.cpp
@@ -1876,10 +1876,43 @@
   for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
     DEBUG(dbgs() << "We believe block " << getBlockName(&BB)
                  << " is unreachable\n");
+    std::vector<BasicBlock *> OldSuccessors(succ_begin(&BB), succ_end(&BB));
+
     deleteInstructionsInBlock(&BB);
+
+    // Update immediate dominator of successors of BB, which have only a single
+    // predecessor after removing all instruction from BB.
+    for (auto *Succ : OldSuccessors) {
+      if (BasicBlock *OnlyPred = Succ->getSinglePredecessor()) {
+        if (DT->getNode(OnlyPred))
+          DT->changeImmediateDominator(Succ, OnlyPred);
+      }
+    }
     Changed = true;
   }
 
+  // Erase unreachable blocks from the dominator tree.
+  for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
+    DomTreeNode *DTN = DT->getNode(&BB);
+    if (!DTN)
+      continue;
+
+    // If BB has a predecessor in the CFG, we have to keep it in the dominator
+    //  tree.
+    if (pred_begin(&BB) != pred_end(&BB))
+      continue;
+
+    SmallVector<DomTreeNode *, 8> Children(DTN->begin(), DTN->end());
+    // Temporarily change the immediate dominator for all nodes immediately
+    // dominated by BB, so we can erase BB from the dominator tree. Those
+    // nodes should be unreachable as well and will be deleted in future
+    // iterations of the outer loop.
+    for (auto *DI : Children)
+      DT->changeImmediateDominator(DI, DT->getRootNode());
+
+    DT->eraseNode(&BB);
+  }
+
   cleanupTables();
   return Changed;
 }
Index: test/Transforms/NewGVN/2007-07-25-NestedLoop.ll
===================================================================
--- test/Transforms/NewGVN/2007-07-25-NestedLoop.ll
+++ test/Transforms/NewGVN/2007-07-25-NestedLoop.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -newgvn | llvm-dis
+; RUN: opt < %s -newgvn -verify-dom-info | llvm-dis
 
 	%struct.TypHeader = type { i32, %struct.TypHeader**, [3 x i8], i8 }
 
Index: test/Transforms/NewGVN/2007-07-30-PredIDom.ll
===================================================================
--- test/Transforms/NewGVN/2007-07-30-PredIDom.ll
+++ test/Transforms/NewGVN/2007-07-30-PredIDom.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -newgvn | llvm-dis
+; RUN: opt < %s -newgvn -verify-dom-info | llvm-dis
 
 	%"struct.Block::$_16" = type { i32 }
 	%struct.Exp = type { %struct.Exp_*, i32, i32, i32, %struct.Exp*, %struct.Exp*, %"struct.Exp::$_10", %"struct.Block::$_16", %"struct.Exp::$_12" }
Index: test/Transforms/NewGVN/cond_br.ll
===================================================================
--- test/Transforms/NewGVN/cond_br.ll
+++ test/Transforms/NewGVN/cond_br.ll
@@ -1,4 +1,4 @@
-; RUN: opt -basicaa -newgvn -S < %s | FileCheck %s
+; RUN: opt -basicaa -newgvn -verify-dom-info -S < %s | FileCheck %s
 @y = external global i32
 @z = external global i32