Index: include/llvm/Transforms/Utils/Local.h
===================================================================
--- include/llvm/Transforms/Utils/Local.h
+++ include/llvm/Transforms/Utils/Local.h
@@ -215,7 +215,8 @@
 /// providing the set of loop headers that SimplifyCFG should not eliminate.
 bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
                  const SimplifyCFGOptions &Options = {},
-                 SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr);
+                 SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr,
+                 DomTreeUpdater *DTU = nullptr);
 
 /// This function is used to flatten a CFG. For example, it uses parallel-and
 /// and parallel-or mode to collapse if-conditions and merge if-regions with
Index: lib/Transforms/Scalar/SimplifyCFGPass.cpp
===================================================================
--- lib/Transforms/Scalar/SimplifyCFGPass.cpp
+++ lib/Transforms/Scalar/SimplifyCFGPass.cpp
@@ -28,11 +28,12 @@
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DomTreeUpdater.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
@@ -40,6 +41,7 @@
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include <utility>
 using namespace llvm;
 
@@ -70,7 +72,7 @@
 
 /// If we have more than one empty (other than phi node) return blocks,
 /// merge them together to promote recursive block merging.
-static bool mergeEmptyReturnBlocks(Function &F) {
+static bool mergeEmptyReturnBlocks(Function &F, DomTreeUpdater *DTU) {
   bool Changed = false;
 
   BasicBlock *RetBlock = nullptr;
@@ -114,7 +116,10 @@
         Ret->getOperand(0) ==
           cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
       BB.replaceAllUsesWith(RetBlock);
-      BB.eraseFromParent();
+      if (DTU)
+        DTU->deleteBB(&BB);
+      else
+        BB.eraseFromParent();
       continue;
     }
 
@@ -146,7 +151,8 @@
 /// Call SimplifyCFG on all the blocks in the function,
 /// iterating until no more changes are made.
 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
-                                   const SimplifyCFGOptions &Options) {
+                                   const SimplifyCFGOptions &Options,
+                                   DomTreeUpdater *DTU) {
   bool Changed = false;
   bool LocalChange = true;
 
@@ -161,7 +167,7 @@
 
     // Loop over all of the basic blocks and remove them if they are unneeded.
     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
-      if (simplifyCFG(&*BBIt++, TTI, Options, &LoopHeaders)) {
+      if (simplifyCFG(&*BBIt++, TTI, Options, &LoopHeaders, DTU)) {
         LocalChange = true;
         ++NumSimpl;
       }
@@ -172,10 +178,12 @@
 }
 
 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
-                                const SimplifyCFGOptions &Options) {
-  bool EverChanged = removeUnreachableBlocks(F);
-  EverChanged |= mergeEmptyReturnBlocks(F);
-  EverChanged |= iterativelySimplifyCFG(F, TTI, Options);
+                                const SimplifyCFGOptions &Options,
+                                DominatorTree *DT) {
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Auto);
+  bool EverChanged = removeUnreachableBlocks(F, nullptr, &DTU);
+  EverChanged |= mergeEmptyReturnBlocks(F, &DTU);
+  EverChanged |= iterativelySimplifyCFG(F, TTI, Options, &DTU);
 
   // If neither pass changed anything, we're done.
   if (!EverChanged) return false;
@@ -185,12 +193,12 @@
   // iterate between the two optimizations.  We structure the code like this to
   // avoid rerunning iterativelySimplifyCFG if the second pass of
   // removeUnreachableBlocks doesn't do anything.
-  if (!removeUnreachableBlocks(F))
+  if (!removeUnreachableBlocks(F, nullptr, &DTU))
     return true;
 
   do {
-    EverChanged = iterativelySimplifyCFG(F, TTI, Options);
-    EverChanged |= removeUnreachableBlocks(F);
+    EverChanged = iterativelySimplifyCFG(F, TTI, Options, &DTU);
+    EverChanged |= removeUnreachableBlocks(F, nullptr, &DTU);
   } while (EverChanged);
 
   return true;
@@ -218,11 +226,13 @@
 PreservedAnalyses SimplifyCFGPass::run(Function &F,
                                        FunctionAnalysisManager &AM) {
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
+  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
   Options.AC = &AM.getResult<AssumptionAnalysis>(F);
-  if (!simplifyFunctionCFG(F, TTI, Options))
+  if (!simplifyFunctionCFG(F, TTI, Options, DT))
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<GlobalsAA>();
+  PA.preserve<DominatorTreeAnalysis>();
   return PA;
 }
 
@@ -267,12 +277,15 @@
 
     Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
-    return simplifyFunctionCFG(F, TTI, Options);
+    auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+    DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
+    return simplifyFunctionCFG(F, TTI, Options, DT);
   }
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
   }
 };
 }
Index: lib/Transforms/Utils/SimplifyCFG.cpp
===================================================================
--- lib/Transforms/Utils/SimplifyCFG.cpp
+++ lib/Transforms/Utils/SimplifyCFG.cpp
@@ -27,7 +27,6 @@
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
@@ -38,6 +37,8 @@
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/DomTreeUpdater.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"
@@ -66,6 +67,7 @@
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include <algorithm>
 #include <cassert>
@@ -173,6 +175,7 @@
   const DataLayout &DL;
   SmallPtrSetImpl<BasicBlock *> *LoopHeaders;
   const SimplifyCFGOptions &Options;
+  DomTreeUpdater *DTU;
 
   Value *isValueEqualityComparison(TerminatorInst *TI);
   BasicBlock *GetValueEqualityComparisonCases(
@@ -197,8 +200,8 @@
 public:
   SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL,
                  SmallPtrSetImpl<BasicBlock *> *LoopHeaders,
-                 const SimplifyCFGOptions &Opts)
-      : TTI(TTI), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {}
+                 const SimplifyCFGOptions &Opts, DomTreeUpdater *DTU)
+      : TTI(TTI), DL(DL), LoopHeaders(LoopHeaders), Options(Opts), DTU(DTU) {}
 
   bool run(BasicBlock *BB);
 };
@@ -3536,7 +3539,8 @@
 /// the PHI, merging the third icmp into the switch.
 static bool tryToSimplifyUncondBranchWithICmpInIt(
     ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL,
-    const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options) {
+    const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options,
+    DomTreeUpdater *DTU) {
   BasicBlock *BB = ICI->getParent();
 
   // If the block has any PHIs in it or the icmp has multiple uses, it is too
@@ -3571,7 +3575,7 @@
       ICI->eraseFromParent();
     }
     // BB is now empty, so it is likely to simplify away.
-    return simplifyCFG(BB, TTI, Options) | true;
+    return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
   }
 
   // Ok, the block is reachable from the default dest.  If the constant we're
@@ -3587,7 +3591,7 @@
     ICI->replaceAllUsesWith(V);
     ICI->eraseFromParent();
     // BB is now empty, so it is likely to simplify away.
-    return simplifyCFG(BB, TTI, Options) | true;
+    return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
   }
 
   // The use of the icmp has to be in the 'end' block, by the only PHI node in
@@ -3822,7 +3826,7 @@
     for (pred_iterator PI = pred_begin(TrivialBB), PE = pred_end(TrivialBB);
          PI != PE;) {
       BasicBlock *Pred = *PI++;
-      removeUnwindEdge(Pred);
+      removeUnwindEdge(Pred, DTU);
     }
 
     // In each SimplifyCFG run, only the current processed block can be erased.
@@ -3835,8 +3839,12 @@
   }
 
   // Delete the resume block if all its predecessors have been removed.
-  if (pred_empty(BB))
-    BB->eraseFromParent();
+  if (pred_empty(BB)) {
+    if (DTU)
+      DTU->deleteBB(BB);
+    else
+      BB->eraseFromParent();
+  }
 
   return !TrivialUnwindBlocks.empty();
 }
@@ -3857,17 +3865,20 @@
   // Turn all invokes that unwind here into calls and delete the basic block.
   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
     BasicBlock *Pred = *PI++;
-    removeUnwindEdge(Pred);
+    removeUnwindEdge(Pred, DTU);
   }
 
   // The landingpad is now unreachable.  Zap it.
-  BB->eraseFromParent();
+  if (DTU)
+    DTU->deleteBB(BB);
+  else
+    BB->eraseFromParent();
   if (LoopHeaders)
     LoopHeaders->erase(BB);
   return true;
 }
 
-static bool removeEmptyCleanup(CleanupReturnInst *RI) {
+static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU) {
   // If this is a trivial cleanup pad that executes no instructions, it can be
   // eliminated.  If the cleanup pad continues to the caller, any predecessor
   // that is an EH pad will be updated to continue to the caller and any
@@ -3991,7 +4002,7 @@
     // The iterator must be updated here because we are removing this pred.
     BasicBlock *PredBB = *PI++;
     if (UnwindDest == nullptr) {
-      removeUnwindEdge(PredBB);
+      removeUnwindEdge(PredBB, DTU);
     } else {
       TerminatorInst *TI = PredBB->getTerminator();
       TI->replaceUsesOfWith(BB, UnwindDest);
@@ -3999,7 +4010,10 @@
   }
 
   // The cleanup pad is now unreachable.  Zap it.
-  BB->eraseFromParent();
+  if (DTU)
+    DTU->deleteBB(BB);
+  else
+    BB->eraseFromParent();
   return true;
 }
 
@@ -4046,7 +4060,7 @@
   if (mergeCleanupPad(RI))
     return true;
 
-  if (removeEmptyCleanup(RI))
+  if (removeEmptyCleanup(RI, DTU))
     return true;
 
   return false;
@@ -4083,7 +4097,11 @@
     // If we eliminated all predecessors of the block, delete the block now.
     if (pred_empty(BB)) {
       // We know there are no successors, so just nuke the block.
-      BB->eraseFromParent();
+      if (DTU)
+        DTU->deleteBB(BB);
+      else
+        BB->eraseFromParent();
+      // FIXME: bug???
       if (LoopHeaders)
         LoopHeaders->erase(BB);
     }
@@ -4199,12 +4217,12 @@
       }
     } else if (auto *II = dyn_cast<InvokeInst>(TI)) {
       if (II->getUnwindDest() == BB) {
-        removeUnwindEdge(TI->getParent());
+        removeUnwindEdge(TI->getParent(), DTU);
         Changed = true;
       }
     } else if (auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
       if (CSI->getUnwindDest() == BB) {
-        removeUnwindEdge(TI->getParent());
+        removeUnwindEdge(TI->getParent(), DTU);
         Changed = true;
         continue;
       }
@@ -4228,7 +4246,7 @@
           // Rewrite all preds to unwind to caller (or from invoke to call).
           SmallVector<BasicBlock *, 8> EHPreds(predecessors(CatchSwitchBB));
           for (BasicBlock *EHPred : EHPreds)
-            removeUnwindEdge(EHPred);
+            removeUnwindEdge(EHPred, DTU);
         }
         // The catchswitch is no longer reachable.
         new UnreachableInst(CSI->getContext(), CSI);
@@ -4245,7 +4263,10 @@
   // If this block is now dead, remove it.
   if (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) {
     // We know there are no successors, so just nuke the block.
-    BB->eraseFromParent();
+    if (DTU)
+      DTU->deleteBB(BB);
+    else
+      BB->eraseFromParent();
     if (LoopHeaders)
       LoopHeaders->erase(BB);
     return true;
@@ -5583,33 +5604,33 @@
     // see if that predecessor totally determines the outcome of this switch.
     if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
       if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
     Value *Cond = SI->getCondition();
     if (SelectInst *Select = dyn_cast<SelectInst>(Cond))
       if (SimplifySwitchOnSelect(SI, Select))
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
     // If the block only contains the switch, see if we can fold the block
     // away into any preds.
     if (SI == &*BB->instructionsWithoutDebug().begin())
       if (FoldValueComparisonIntoPredecessors(SI, Builder))
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
   }
 
   // Try to transform the switch into an icmp and a branch.
   if (TurnSwitchRangeIntoICmp(SI, Builder))
-    return simplifyCFG(BB, TTI, Options) | true;
+    return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
   // Remove unreachable cases.
   if (eliminateDeadSwitchCases(SI, Options.AC, DL))
-    return simplifyCFG(BB, TTI, Options) | true;
+    return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
   if (switchToSelect(SI, Builder, DL, TTI))
-    return simplifyCFG(BB, TTI, Options) | true;
+    return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
   if (Options.ForwardSwitchCondToPhi && ForwardSwitchConditionToPHI(SI))
-    return simplifyCFG(BB, TTI, Options) | true;
+    return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
   // The conversion from switch to lookup tables results in difficult-to-analyze
   // code and makes pruning branches much harder. This is a problem if the
@@ -5618,10 +5639,10 @@
   // optimisation pipeline.
   if (Options.ConvertSwitchToLookupTable &&
       SwitchToLookupTable(SI, Builder, DL, TTI))
-    return simplifyCFG(BB, TTI, Options) | true;
+    return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
   if (ReduceSwitchRange(SI, Builder, DL, TTI))
-    return simplifyCFG(BB, TTI, Options) | true;
+    return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
   return false;
 }
@@ -5659,7 +5680,7 @@
 
   if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
     if (SimplifyIndirectBrOnSelect(IBI, SI))
-      return simplifyCFG(BB, TTI, Options) | true;
+      return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
   }
   return Changed;
 }
@@ -5759,7 +5780,7 @@
        (LoopHeaders->count(BB) || LoopHeaders->count(Succ)));
   BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator();
   if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() &&
-      !NeedCanonicalLoop && TryToSimplifyUncondBranchFromEmptyBlock(BB))
+      !NeedCanonicalLoop && TryToSimplifyUncondBranchFromEmptyBlock(BB, DTU))
     return true;
 
   // If the only instruction in the block is a seteq/setne comparison against a
@@ -5768,8 +5789,8 @@
     if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) {
       for (++I; isa<DbgInfoIntrinsic>(I); ++I)
         ;
-      if (I->isTerminator() &&
-          tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI, Options))
+      if (I->isTerminator() && tryToSimplifyUncondBranchWithICmpInIt(
+                                   ICI, Builder, DL, TTI, Options, DTU))
         return true;
     }
 
@@ -5787,7 +5808,7 @@
   // predecessor and use logical operations to update the incoming value
   // for PHI nodes in common successor.
   if (FoldBranchToCommonDest(BI, Options.BonusInstThreshold))
-    return simplifyCFG(BB, TTI, Options) | true;
+    return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
   return false;
 }
 
@@ -5815,18 +5836,18 @@
     // switch.
     if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
       if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
     // This block must be empty, except for the setcond inst, if it exists.
     // Ignore dbg intrinsics.
     auto I = BB->instructionsWithoutDebug().begin();
     if (&*I == BI) {
       if (FoldValueComparisonIntoPredecessors(BI, Builder))
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
     } else if (&*I == cast<Instruction>(BI->getCondition())) {
       ++I;
       if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
     }
   }
 
@@ -5853,7 +5874,7 @@
                               : ConstantInt::getFalse(BB->getContext());
         BI->setCondition(CI);
         RecursivelyDeleteTriviallyDeadInstructions(OldCond);
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
       }
     }
   }
@@ -5862,7 +5883,7 @@
   // branches to us and one of our successors, fold the comparison into the
   // predecessor and use logical operations to pick the right destination.
   if (FoldBranchToCommonDest(BI, Options.BonusInstThreshold))
-    return simplifyCFG(BB, TTI, Options) | true;
+    return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
   // We have a conditional branch to two blocks that are only reachable
   // from BI.  We know that the condbr dominates the two blocks, so see if
@@ -5871,7 +5892,7 @@
   if (BI->getSuccessor(0)->getSinglePredecessor()) {
     if (BI->getSuccessor(1)->getSinglePredecessor()) {
       if (HoistThenElseCodeToIf(BI, TTI))
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
     } else {
       // If Successor #1 has multiple preds, we may be able to conditionally
       // execute Successor #0 if it branches to Successor #1.
@@ -5879,7 +5900,7 @@
       if (Succ0TI->getNumSuccessors() == 1 &&
           Succ0TI->getSuccessor(0) == BI->getSuccessor(1))
         if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), TTI))
-          return simplifyCFG(BB, TTI, Options) | true;
+          return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
     }
   } else if (BI->getSuccessor(1)->getSinglePredecessor()) {
     // If Successor #0 has multiple preds, we may be able to conditionally
@@ -5888,7 +5909,7 @@
     if (Succ1TI->getNumSuccessors() == 1 &&
         Succ1TI->getSuccessor(0) == BI->getSuccessor(0))
       if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), TTI))
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
   }
 
   // If this is a branch on a phi node in the current block, thread control
@@ -5896,14 +5917,14 @@
   if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition()))
     if (PN->getParent() == BI->getParent())
       if (FoldCondBranchOnPHI(BI, DL, Options.AC))
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
   // Scan predecessor blocks for conditional branches.
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
     if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
       if (PBI != BI && PBI->isConditional())
         if (SimplifyCondBranchToCondBranch(PBI, BI, DL))
-          return simplifyCFG(BB, TTI, Options) | true;
+          return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
   // Look for diamond patterns.
   if (MergeCondStores)
@@ -5911,7 +5932,7 @@
       if (BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
         if (PBI != BI && PBI->isConditional())
           if (mergeConditionalStores(PBI, BI, DL))
-            return simplifyCFG(BB, TTI, Options) | true;
+            return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
 
   return false;
 }
@@ -6004,14 +6025,16 @@
   // or that just have themself as a predecessor.  These are unreachable.
   if ((pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) ||
       BB->getSinglePredecessor() == BB) {
+    if (DTU && DTU->isBBPendingDeletion(BB))
+      return false;
     LLVM_DEBUG(dbgs() << "Removing BB: \n" << *BB);
-    DeleteDeadBlock(BB);
+    DeleteDeadBlock(BB, DTU);
     return true;
   }
 
   // Check to see if we can constant propagate this terminator instruction
   // away...
-  Changed |= ConstantFoldTerminator(BB, true);
+  Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU);
 
   // Check for and eliminate duplicate PHI nodes in this block.
   Changed |= EliminateDuplicatePHINodes(BB);
@@ -6022,7 +6045,7 @@
   // Merge basic blocks into their predecessor if there is only one distinct
   // pred, and if there is only one distinct successor of the predecessor, and
   // if there are no PHI nodes.
-  if (MergeBlockIntoPredecessor(BB))
+  if (MergeBlockIntoPredecessor(BB, DTU))
     return true;
 
   if (SinkCommon && Options.SinkCommonInsts)
@@ -6070,8 +6093,9 @@
 
 bool llvm::simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
                        const SimplifyCFGOptions &Options,
-                       SmallPtrSetImpl<BasicBlock *> *LoopHeaders) {
+                       SmallPtrSetImpl<BasicBlock *> *LoopHeaders,
+                       DomTreeUpdater *DTU) {
   return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), LoopHeaders,
-                        Options)
+                        Options, DTU)
       .run(BB);
 }
Index: test/Transforms/SimplifyCFG/2002-05-21-PHIElimination.ll
===================================================================
--- test/Transforms/SimplifyCFG/2002-05-21-PHIElimination.ll
+++ test/Transforms/SimplifyCFG/2002-05-21-PHIElimination.ll
@@ -4,7 +4,7 @@
 ;
 ; Which is not valid SSA
 ;
-; RUN: opt < %s -simplifycfg | llvm-dis
+; RUN: opt < %s -simplifycfg -verify-dom-info | llvm-dis
 
 define void @test() {
 ; <label>:0
Index: test/Transforms/SimplifyCFG/2002-09-24-PHIAssertion.ll
===================================================================
--- test/Transforms/SimplifyCFG/2002-09-24-PHIAssertion.ll
+++ test/Transforms/SimplifyCFG/2002-09-24-PHIAssertion.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg
+; RUN: opt < %s -simplifycfg -verify-dom-info
 
 define i32 @test(i32 %A, i32 %B, i1 %cond) {
 J:
Index: test/Transforms/SimplifyCFG/2003-03-07-DominateProblem.ll
===================================================================
--- test/Transforms/SimplifyCFG/2003-03-07-DominateProblem.ll
+++ test/Transforms/SimplifyCFG/2003-03-07-DominateProblem.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 
 define void @test(i32* %ldo, i1 %c, i1 %d) {
 bb9:
Index: test/Transforms/SimplifyCFG/2003-08-05-InvokeCrash.ll
===================================================================
--- test/Transforms/SimplifyCFG/2003-08-05-InvokeCrash.ll
+++ test/Transforms/SimplifyCFG/2003-08-05-InvokeCrash.ll
@@ -1,6 +1,6 @@
 ; Do not remove the invoke!
 ;
-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 
 define i32 @test() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
 	%A = invoke i32 @test( )
Index: test/Transforms/SimplifyCFG/2003-08-17-BranchFold.ll
===================================================================
--- test/Transforms/SimplifyCFG/2003-08-17-BranchFold.ll
+++ test/Transforms/SimplifyCFG/2003-08-17-BranchFold.ll
@@ -1,7 +1,7 @@
 ; This test checks to make sure that 'br X, Dest, Dest' is folded into 
 ; 'br Dest'
 
-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 
 declare void @noop()
 
Index: test/Transforms/SimplifyCFG/2003-08-17-BranchFoldOrdering.ll
===================================================================
--- test/Transforms/SimplifyCFG/2003-08-17-BranchFoldOrdering.ll
+++ test/Transforms/SimplifyCFG/2003-08-17-BranchFoldOrdering.ll
@@ -3,7 +3,7 @@
 ; due to the fact that the SimplifyCFG function does not use 
 ; the ConstantFoldTerminator function.
 
-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 
 ; CHECK-NOT: br i1 %c2
 
Index: test/Transforms/SimplifyCFG/2003-08-17-FoldSwitch-dbg.ll
===================================================================
--- test/Transforms/SimplifyCFG/2003-08-17-FoldSwitch-dbg.ll
+++ test/Transforms/SimplifyCFG/2003-08-17-FoldSwitch-dbg.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 
 ; CHECK-NOT: switch
         %llvm.dbg.anchor.type = type { i32, i32 }
Index: test/Transforms/SimplifyCFG/2003-08-17-FoldSwitch.ll
===================================================================
--- test/Transforms/SimplifyCFG/2003-08-17-FoldSwitch.ll
+++ test/Transforms/SimplifyCFG/2003-08-17-FoldSwitch.ll
@@ -1,5 +1,5 @@
 ; NOTE: Assertions have been autogenerated by update_test_checks.py
-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 
 ; Test normal folding
 define i32 @test1() {
Index: test/Transforms/SimplifyCFG/2004-12-10-SimplifyCFGCrash.ll
===================================================================
--- test/Transforms/SimplifyCFG/2004-12-10-SimplifyCFGCrash.ll
+++ test/Transforms/SimplifyCFG/2004-12-10-SimplifyCFGCrash.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 
 define void @symhash_add() {
 entry:
Index: test/Transforms/SimplifyCFG/2005-06-16-PHICrash.ll
===================================================================
--- test/Transforms/SimplifyCFG/2005-06-16-PHICrash.ll
+++ test/Transforms/SimplifyCFG/2005-06-16-PHICrash.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 ; PR584
 @g_38098584 = external global i32		; <i32*> [#uses=1]
 @g_60187400 = external global i32		; <i32*> [#uses=1]
Index: test/Transforms/SimplifyCFG/2005-08-01-PHIUpdateFail.ll
===================================================================
--- test/Transforms/SimplifyCFG/2005-08-01-PHIUpdateFail.ll
+++ test/Transforms/SimplifyCFG/2005-08-01-PHIUpdateFail.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 ; END.
 
 define void @main() {
Index: test/Transforms/SimplifyCFG/2005-10-02-InvokeSimplify.ll
===================================================================
--- test/Transforms/SimplifyCFG/2005-10-02-InvokeSimplify.ll
+++ test/Transforms/SimplifyCFG/2005-10-02-InvokeSimplify.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 
 define i1 @foo() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
 	%X = invoke i1 @foo( )
Index: test/Transforms/SimplifyCFG/2005-12-03-IncorrectPHIFold.ll
===================================================================
--- test/Transforms/SimplifyCFG/2005-12-03-IncorrectPHIFold.ll
+++ test/Transforms/SimplifyCFG/2005-12-03-IncorrectPHIFold.ll
@@ -1,6 +1,6 @@
 ; Make sure this doesn't turn into an infinite loop
 
-; RUN: opt < %s -simplifycfg -constprop -simplifycfg | llvm-dis | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -constprop -simplifycfg | llvm-dis | FileCheck %s
 
 %struct.anon = type { i32, i32, i32, i32, [1024 x i8] }
 @_zero_ = external global %struct.anon*		; <%struct.anon**> [#uses=2]
Index: test/Transforms/SimplifyCFG/2006-02-17-InfiniteUnroll.ll
===================================================================
--- test/Transforms/SimplifyCFG/2006-02-17-InfiniteUnroll.ll
+++ test/Transforms/SimplifyCFG/2006-02-17-InfiniteUnroll.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 
 define void @polnel_() {
 entry:
Index: test/Transforms/SimplifyCFG/2006-06-12-InfLoop.ll
===================================================================
--- test/Transforms/SimplifyCFG/2006-06-12-InfLoop.ll
+++ test/Transforms/SimplifyCFG/2006-06-12-InfLoop.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 ; END.
 
 define void @main(i32 %c) {
Index: test/Transforms/SimplifyCFG/2006-08-03-Crash.ll
===================================================================
--- test/Transforms/SimplifyCFG/2006-08-03-Crash.ll
+++ test/Transforms/SimplifyCFG/2006-08-03-Crash.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -gvn -simplifycfg -disable-output
+; RUN: opt < %s -gvn -simplifycfg -verify-dom-info -disable-output
 ; PR867
 
 target datalayout = "E-p:32:32"
Index: test/Transforms/SimplifyCFG/2006-10-19-UncondDiv.ll
===================================================================
--- test/Transforms/SimplifyCFG/2006-10-19-UncondDiv.ll
+++ test/Transforms/SimplifyCFG/2006-10-19-UncondDiv.ll
@@ -1,5 +1,5 @@
 ; PR957
-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 
 ; CHECK-NOT: select
 
Index: test/Transforms/SimplifyCFG/2006-12-08-Ptr-ICmp-Branch.ll
===================================================================
--- test/Transforms/SimplifyCFG/2006-12-08-Ptr-ICmp-Branch.ll
+++ test/Transforms/SimplifyCFG/2006-12-08-Ptr-ICmp-Branch.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg | llvm-dis
+; RUN: opt < %s -simplifycfg -verify-dom-info | llvm-dis
 ; END.
 
 ; ModuleID = '2006-12-08-Ptr-ICmp-Branch.ll'
Index: test/Transforms/SimplifyCFG/2007-11-22-InvokeNoUnwind.ll
===================================================================
--- test/Transforms/SimplifyCFG/2007-11-22-InvokeNoUnwind.ll
+++ test/Transforms/SimplifyCFG/2007-11-22-InvokeNoUnwind.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 
 ; CHECK-NOT: invoke
 
Index: test/Transforms/SimplifyCFG/2007-12-21-Crash.ll
===================================================================
--- test/Transforms/SimplifyCFG/2007-12-21-Crash.ll
+++ test/Transforms/SimplifyCFG/2007-12-21-Crash.ll
@@ -1,4 +1,4 @@
-;RUN: opt < %s -simplifycfg -disable-output
+;RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
 
 define i32 @bork() nounwind  {
Index: test/Transforms/SimplifyCFG/2008-01-02-hoist-fp-add.ll
===================================================================
--- test/Transforms/SimplifyCFG/2008-01-02-hoist-fp-add.ll
+++ test/Transforms/SimplifyCFG/2008-01-02-hoist-fp-add.ll
@@ -1,5 +1,5 @@
 ; The phi should not be eliminated in this case, because the divide op could trap.
-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
 target triple = "i686-apple-darwin8"
Index: test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll
===================================================================
--- test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll
+++ test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -S > %t
+; RUN: opt < %s -simplifycfg -verify-dom-info -S > %t
 ; RUN: not grep "^BB.tomerge" %t
 ; RUN: grep "^BB.nomerge" %t | count 4
 
Index: test/Transforms/SimplifyCFG/2008-07-13-InfLoopMiscompile.ll
===================================================================
--- test/Transforms/SimplifyCFG/2008-07-13-InfLoopMiscompile.ll
+++ test/Transforms/SimplifyCFG/2008-07-13-InfLoopMiscompile.ll
@@ -1,5 +1,5 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 ; PR2540
 ; Outval should end up with a select from 0/2, not all constants.
 
Index: test/Transforms/SimplifyCFG/2008-09-08-MultiplePred.ll
===================================================================
--- test/Transforms/SimplifyCFG/2008-09-08-MultiplePred.ll
+++ test/Transforms/SimplifyCFG/2008-09-08-MultiplePred.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 ; PR 2777
 @g_103 = common global i32 0		; <i32*> [#uses=1]
 
Index: test/Transforms/SimplifyCFG/DeadSetCC.ll
===================================================================
--- test/Transforms/SimplifyCFG/DeadSetCC.ll
+++ test/Transforms/SimplifyCFG/DeadSetCC.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -simplifycfg -S | \
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | \
 ; RUN:   not grep "icmp eq"
 
 ; Check that simplifycfg deletes a dead 'seteq' instruction when it
Index: test/Transforms/SimplifyCFG/EmptyBlockMerge.ll
===================================================================
--- test/Transforms/SimplifyCFG/EmptyBlockMerge.ll
+++ test/Transforms/SimplifyCFG/EmptyBlockMerge.ll
@@ -1,6 +1,6 @@
 ; Basic block #2 should not be merged into BB #3!
 ;
-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 
 declare void @foo()
 
Index: test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll
===================================================================
--- test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll
+++ test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll
@@ -1,6 +1,6 @@
 ; Test merging of blocks with phi nodes.
 ;
-; RUN: opt < %s -simplifycfg -S > %t
+; RUN: opt < %s -simplifycfg -verify-dom-info -S > %t
 ; RUN: not grep N: %t
 ; RUN: not grep X: %t
 ; RUN: not grep 'switch i32[^U]+%U' %t