[WIP!][DomTreeUpdater/Auto[1]] Preserve the DomTree in the SimplifyCFG pass

[NutshellySima]

Summary

Note: This is a work-in-progress patch and I don't intend to commit it. Please ignore it if you are automatically subscribed.

This patch relies on D50302 which provides a utility for complex passes to test whether it is profitable to preserve the DominatorTree.

This patch converts the SimplifyCFG pass into preserving the DominatorTree. Combined with D50303, you can compare the performance difference by looking at the total time used by the whole DominatorTree.

From my experiment, it is not profit to preserve the DomTree in the SimplifyCFG pass, and we can further look into this issue. (Detect whether it is slow because SimplifyCFG loves to rewire a bunch of edges and make DominatorTree spend to much effort on it).

[NutshellySima]

This patch only converts a limited number of tests to demonstrate the implementation of preserving the DT is correct.

[NutshellySima]

Benchmark results: https://reviews.llvm.org/P8097

[NutshellySima]

Close along with D50302.

include/llvm/Transforms/Utils/Local.h

 /// This function is used to do simplification of a CFG.  For example, it
 /// adjusts branches to branches to eliminate the extra hop, it eliminates
 /// unreachable basic blocks, and does other peephole optimization of the CFG.
 /// It returns true if a modification was made, possibly deleting the basic
 /// block that was pointed to. LoopHeaders is an optional input parameter
 /// 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
 /// identical statements.
 bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr);
 
 /// If this basic block is ONLY a setcc and a branch, and if a predecessor
 /// branches to us and one of our successors, fold the setcc into the

lib/Transforms/Scalar/SimplifyCFGPass.cpp

 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #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"
 #include "llvm/Pass.h"
 #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;
 
 #define DEBUG_TYPE "simplifycfg"
 
 static cl::opt<unsigned> UserBonusInstThreshold(
     "bonus-inst-threshold", cl::Hidden, cl::init(1),
     cl::desc("Control the number of bonus instructions (default = 1)"));
static cl::opt<bool> UserSinkCommonInsts(
     "sink-common-insts", cl::Hidden, cl::init(false),
     cl::desc("Sink common instructions (default = false)"));
 
 
 STATISTIC(NumSimpl, "Number of blocks simplified");
 
 /// 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;
 
   // Scan all the blocks in the function, looking for empty return blocks.
   for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
     BasicBlock &BB = *BBI++;
 
for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
 
     // Case when there is no input to the return or when the returned values
     // agree is trivial.  Note that they can't agree if there are phis in the
     // blocks.
     if (Ret->getNumOperands() == 0 ||
         Ret->getOperand(0) ==
           cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
       BB.replaceAllUsesWith(RetBlock);
+      if (DTU)
+        DTU->deleteBB(&BB);
+      else
         BB.eraseFromParent();
       continue;
     }
 
     // If the canonical return block has no PHI node, create one now.
     PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
     if (!RetBlockPHI) {
       Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
       pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
static bool mergeEmptyReturnBlocks(Function &F, DomTreeUpdater *DTU) {
   }
 
   return Changed;
 }
 
 /// 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;
 
   SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
   FindFunctionBackedges(F, Edges);
   SmallPtrSet<BasicBlock *, 16> LoopHeaders;
   for (unsigned i = 0, e = Edges.size(); i != e; ++i)
     LoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
 
   while (LocalChange) {
     LocalChange = false;
 
     // 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;
       }
     }
     Changed |= LocalChange;
   }
   return Changed;
 }
 
 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;
 
   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
   // removeUnreachableBlocks is needed to nuke them, which means we should
   // 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;
 }
 
 // Command-line settings override compile-time settings.
 SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts) {
   Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts) {
   Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
                                 ? UserSinkCommonInsts
                                 : Opts.SinkCommonInsts;
 }
 
 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;
 }
 
 namespace {
 struct CFGSimplifyPass : public FunctionPass {
   static char ID;
   SimplifyCFGOptions Options;
   std::function<bool(const Function &)> PredicateFtor;
struct CFGSimplifyPass : public FunctionPass {
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
       return false;
 
     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>();
   }
 };
 }
 
 char CFGSimplifyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)

lib/Transforms/Utils/SimplifyCFG.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #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"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #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"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"

 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
 #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>
 #include <climits>
 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <map>
struct ValueEqualityComparisonCase {
   bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; }
 };
 
 class SimplifyCFGOpt {
   const TargetTransformInfo &TTI;
   const DataLayout &DL;
   SmallPtrSetImpl<BasicBlock *> *LoopHeaders;
   const SimplifyCFGOptions &Options;
+  DomTreeUpdater *DTU;
 
   Value *isValueEqualityComparison(TerminatorInst *TI);
   BasicBlock *GetValueEqualityComparisonCases(
       TerminatorInst *TI, std::vector<ValueEqualityComparisonCase> &Cases);
   bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
                                                      BasicBlock *Pred,
                                                      IRBuilder<> &Builder);
   bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
                                            IRBuilder<> &Builder);
 
   bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder);
   bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
   bool SimplifySingleResume(ResumeInst *RI);
   bool SimplifyCommonResume(ResumeInst *RI);
   bool SimplifyCleanupReturn(CleanupReturnInst *RI);
   bool SimplifyUnreachable(UnreachableInst *UI);
   bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
   bool SimplifyIndirectBr(IndirectBrInst *IBI);
   bool SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder);
   bool SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder);
 
 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);
 };
 
 } // end anonymous namespace
 
 /// Return true if it is safe to merge these two
 /// terminator instructions together.

 ///   br label %end
 /// end:
 ///   ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ]
 ///
 /// We prefer to split the edge to 'end' so that there is a true/false entry to
 /// 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
   // complex.
   if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse())
     return false;
 
   Value *V = ICI->getOperand(0);
if (SI->getDefaultDest() != BB) {
     assert(VVal && "Should have a unique destination value");
     ICI->setOperand(0, VVal);
 
     if (Value *V = SimplifyInstruction(ICI, {DL, ICI})) {
       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;
   }
 
   // Ok, the block is reachable from the default dest.  If the constant we're
   // comparing exists in one of the other edges, then we can constant fold ICI
   // and zap it.
   if (SI->findCaseValue(Cst) != SI->case_default()) {
     Value *V;
     if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
       V = ConstantInt::getFalse(BB->getContext());
     else
       V = ConstantInt::getTrue(BB->getContext());
 
     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
   // the block.
   BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0);
   PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back());
   if (PHIUse == nullptr || PHIUse != &SuccBlock->front() ||
       isa<PHINode>(++BasicBlock::iterator(PHIUse)))
for (auto *TrivialBB : TrivialUnwindBlocks) {
     // Note there could be multiple edges to the resume block, and we need
     // to remove them all.
     while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
       BB->removePredecessor(TrivialBB, true);
 
     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.
     // Otherwise, it will break the iteration of SimplifyCFG pass. So instead
     // of erasing TrivialBB, we only remove the branch to the common resume
     // block so that we can later erase the resume block since it has no
     // predecessors.
     TrivialBB->getTerminator()->eraseFromParent();
     new UnreachableInst(RI->getContext(), TrivialBB);
   }
 
   // Delete the resume block if all its predecessors have been removed.
-  if (pred_empty(BB))
+  if (pred_empty(BB)) {
+    if (DTU)
+      DTU->deleteBB(BB);
+    else
       BB->eraseFromParent();
+  }
 
   return !TrivialUnwindBlocks.empty();
 }
 
 // Simplify resume that is only used by a single (non-phi) landing pad.
 bool SimplifyCFGOpt::SimplifySingleResume(ResumeInst *RI) {
   BasicBlock *BB = RI->getParent();
   LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI());
   assert(RI->getValue() == LPInst &&
          "Resume must unwind the exception that caused control to here");
 
   // Check that there are no other instructions except for debug intrinsics.
   BasicBlock::iterator I = LPInst->getIterator(), E = RI->getIterator();
   while (++I != E)
     if (!isa<DbgInfoIntrinsic>(I))
       return false;
 
   // 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.
+  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
   // predecessor that terminates with an invoke instruction will have its invoke
   // instruction converted to a call instruction.  If the cleanup pad being
   // simplified does not continue to the caller, each predecessor will be
   // updated to continue to the unwind destination of the cleanup pad being
   // simplified.
for (BasicBlock::iterator I = BB->begin(),
       PN->moveBefore(InsertPt);
     }
   }
 
   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
     // 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);
     }
   }
 
   // The cleanup pad is now unreachable.  Zap it.
+  if (DTU)
+    DTU->deleteBB(BB);
+  else
     BB->eraseFromParent();
   return true;
 }
 
 // Try to merge two cleanuppads together.
 static bool mergeCleanupPad(CleanupReturnInst *RI) {
   // Skip any cleanuprets which unwind to caller, there is nothing to merge
   // with.
   BasicBlock *UnwindDest = RI->getUnwindDest();
bool SimplifyCFGOpt::SimplifyCleanupReturn(CleanupReturnInst *RI) {
   // have deleted some, but not all, dead blocks.
   // Eventually, this block will be deleted.
   if (isa<UndefValue>(RI->getOperand(0)))
     return false;
 
   if (mergeCleanupPad(RI))
     return true;
 
-  if (removeEmptyCleanup(RI))
+  if (removeEmptyCleanup(RI, DTU))
     return true;
 
   return false;
 }
 
 bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) {
   BasicBlock *BB = RI->getParent();
   if (!BB->getFirstNonPHIOrDbg()->isTerminator())
while (!UncondBranchPreds.empty()) {
       LLVM_DEBUG(dbgs() << "FOLDING: " << *BB
                         << "INTO UNCOND BRANCH PRED: " << *Pred);
       (void)FoldReturnIntoUncondBranch(RI, BB, Pred);
     }
 
     // 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.
+      if (DTU)
+        DTU->deleteBB(BB);
+      else
         BB->eraseFromParent();
+      // FIXME: bug???
       if (LoopHeaders)
         LoopHeaders->erase(BB);
     }
 
     return true;
   }
 
   // Check out all of the conditional branches going to this return
if (auto *BI = dyn_cast<BranchInst>(TI)) {
         }
         BB->removePredecessor(SI->getParent());
         i = SI->removeCase(i);
         e = SI->case_end();
         Changed = true;
       }
     } 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;
       }
 
       for (CatchSwitchInst::handler_iterator I = CSI->handler_begin(),
                                              E = CSI->handler_end();
            I != E; ++I) {
         if (*I == BB) {
           CSI->removeHandler(I);
           --I;
           --E;
           Changed = true;
         }
       }
       if (CSI->getNumHandlers() == 0) {
         BasicBlock *CatchSwitchBB = CSI->getParent();
         if (CSI->hasUnwindDest()) {
           // Redirect preds to the unwind dest
           CatchSwitchBB->replaceAllUsesWith(CSI->getUnwindDest());
         } else {
           // 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);
         CSI->eraseFromParent();
         Changed = true;
       }
     } else if (isa<CleanupReturnInst>(TI)) {
       new UnreachableInst(TI->getContext(), TI);
       TI->eraseFromParent();
       Changed = true;
     }
   }
 
   // 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.
+    if (DTU)
+      DTU->deleteBB(BB);
+    else
       BB->eraseFromParent();
     if (LoopHeaders)
       LoopHeaders->erase(BB);
     return true;
   }
 
   return Changed;
 }
 

 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   BasicBlock *BB = SI->getParent();
 
   if (isValueEqualityComparison(SI)) {
     // If we only have one predecessor, and if it is a branch on this value,
     // 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
   // switch expression itself can still be restricted as a result of inlining or
   // CVP. Therefore, only apply this transformation during late stages of the
   // 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;
 }
 
 bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) {
   BasicBlock *BB = IBI->getParent();
   bool Changed = false;
 
if (IBI->getNumDestinations() == 1) {
     // If the indirectbr has one successor, change it to a direct branch.
     BranchInst::Create(IBI->getDestination(0), IBI);
     EraseTerminatorInstAndDCECond(IBI);
     return true;
   }
 
   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;
 }
 
 /// Given an block with only a single landing pad and a unconditional branch
 /// try to find another basic block which this one can be merged with.  This
 /// handles cases where we have multiple invokes with unique landing pads, but
 /// a shared handler.
bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI,
   // Note that if BB has only one predecessor then we do not introduce new
   // backedge, so we can eliminate BB.
   bool NeedCanonicalLoop =
       Options.NeedCanonicalLoop &&
       (LoopHeaders && pred_size(BB) > 1 &&
        (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
   // constant, try to simplify the block.
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))
     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;
     }
 
   // See if we can merge an empty landing pad block with another which is
   // equivalent.
   if (LandingPadInst *LPad = dyn_cast<LandingPadInst>(I)) {
     for (++I; isa<DbgInfoIntrinsic>(I); ++I)
       ;
     if (I->isTerminator() && TryToMergeLandingPad(LPad, BI, BB))
       return true;
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and our successor, fold the comparison into the
   // 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;
 }
 
 static BasicBlock *allPredecessorsComeFromSameSource(BasicBlock *BB) {
   BasicBlock *PredPred = nullptr;
   for (auto *P : predecessors(BB)) {
     BasicBlock *PPred = P->getSinglePredecessor();
     if (!PPred || (PredPred && PredPred != PPred))
bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
 
   // Conditional branch
   if (isValueEqualityComparison(BI)) {
     // If we only have one predecessor, and if it is a branch on this value,
     // see if that predecessor totally determines the outcome of this
     // 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;
     }
   }
 
   // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction.
   if (SimplifyBranchOnICmpChain(BI, Builder, DL))
     return true;
 
   // If this basic block has a single dominating predecessor block and the
if (PBI && PBI->isConditional() &&
       if (Implication) {
         // Turn this into a branch on constant.
         auto *OldCond = BI->getCondition();
         ConstantInt *CI = *Implication
                               ? ConstantInt::getTrue(BB->getContext())
                               : ConstantInt::getFalse(BB->getContext());
         BI->setCondition(CI);
         RecursivelyDeleteTriviallyDeadInstructions(OldCond);
-        return simplifyCFG(BB, TTI, Options) | true;
+        return simplifyCFG(BB, TTI, Options, nullptr, DTU) | true;
       }
     }
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // 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
   // there is any identical code in the "then" and "else" blocks.  If so, we
   // can hoist it up to the branching block.
   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.
       TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator();
       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
     // execute Successor #1 if it branches to Successor #0.
     TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator();
     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
   // through this block if any PHI node entries are constants.
   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)
     if (BasicBlock *PrevBB = allPredecessorsComeFromSameSource(BB))
       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;
 }
 
 /// Check if passing a value to an instruction will cause undefined behavior.
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) {
   Constant *C = dyn_cast<Constant>(V);
   if (!C)
bool SimplifyCFGOpt::run(BasicBlock *BB) {
 
   assert(BB && BB->getParent() && "Block not embedded in function!");
   assert(BB->getTerminator() && "Degenerate basic block encountered!");
 
   // Remove basic blocks that have no predecessors (except the entry block)...
   // 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);
 
   // Check for and remove branches that will always cause undefined behavior.
   Changed |= removeUndefIntroducingPredecessor(BB);
 
   // 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)
     Changed |= SinkCommonCodeFromPredecessors(BB);
 
   IRBuilder<> Builder(BB);
 
   // If there is a trivial two-entry PHI node in this basic block, and we can
if (SimplifyIndirectBr(IBI))
       return true;
   }
 
   return Changed;
 }
 
 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);
 }

test/Transforms/SimplifyCFG/2002-05-21-PHIElimination.ll

 ; CFG Simplification is making a loop dead, then changing the add into:
 ;
 ;   %V1 = add int %V1, 1
 ;
 ; 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
   br i1 true, label %end, label %Loop
 Loop:   ; preds = %Loop, %0
   %V = phi i32 [ 0, %0 ], [ %V1, %Loop ]    ; <i32> [#uses=1]
   %V1 = add i32 %V, 1   ; <i32> [#uses=1]
   br label %Loop
 end:    ; preds = %0
   ret void
 }
 

test/Transforms/SimplifyCFG/2002-09-24-PHIAssertion.ll

-; RUN: opt < %s -simplifycfg
+; RUN: opt < %s -simplifycfg -verify-dom-info
 
 define i32 @test(i32 %A, i32 %B, i1 %cond) {
 J:
   %C = add i32 %A, 12   ; <i32> [#uses=3]
   br i1 %cond, label %L, label %L
 L:    ; preds = %J, %J
   %Q = phi i32 [ %C, %J ], [ %C, %J ]    ; <i32> [#uses=1]
   %D = add i32 %C, %B   ; <i32> [#uses=1]
   %E = add i32 %Q, %D   ; <i32> [#uses=1]
   ret i32 %E
 }
 

test/Transforms/SimplifyCFG/2003-03-07-DominateProblem.ll

-; 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:
   br i1 %c, label %bb11, label %bb10
 bb10:   ; preds = %bb9
   br label %bb11
 bb11:   ; preds = %bb10, %bb9
   %reg330 = phi i32* [ null, %bb10 ], [ %ldo, %bb9 ]    ; <i32*> [#uses=1]
   br label %bb20
 bb20:   ; preds = %bb20, %bb11
   store i32* %reg330, i32** null
   br i1 %d, label %bb20, label %done
 done:   ; preds = %bb20
   ret void
 }
 

test/Transforms/SimplifyCFG/2003-08-05-InvokeCrash.ll

 ; 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( )
       to label %Ret unwind label %Ret2    ; <i32> [#uses=1]
 Ret:    ; preds = %0
   ret i32 %A
 Ret2:   ; preds = %0
         %val = landingpad { i8*, i32 }
                  catch i8* null
   ret i32 undef
 }
 
 declare i32 @__gxx_personality_v0(...)

test/Transforms/SimplifyCFG/2003-08-17-BranchFold.ll

 ; 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()
 
 ; CHECK-NOT: br i1 %c2
 define i32 @test(i1 %c1, i1 %c2) {
   call void @noop( )
   br i1 %c1, label %A, label %Y
 A:    ; preds = %0

test/Transforms/SimplifyCFG/2003-08-17-BranchFoldOrdering.ll

 ; This test checks to make sure that 'br X, Dest, Dest' is folded into 
 ; 'br Dest'.  This can only happen after the 'Z' block is eliminated.  This is
 ; 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
 
 declare void @noop()
 
 define i32 @test(i1 %c1, i1 %c2) {
   call void @noop( )
   br i1 %c1, label %A, label %Y

test/Transforms/SimplifyCFG/2003-08-17-FoldSwitch-dbg.ll

-; 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 }
         %llvm.dbg.compile_unit.type = type { i32, { }*, i32, i8*, i8*, i8*, i1, i1, i8* }
 
 @llvm.dbg.compile_units = linkonce constant %llvm.dbg.anchor.type { i32 458752, i32 17 }, section "llvm.metadata"
 
 @.str = internal constant [4 x i8] c"a.c\00", section "llvm.metadata"    ; <[4 x i8]*> [#uses=1]

test/Transforms/SimplifyCFG/2003-08-17-FoldSwitch.ll

 ; 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() {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  TheDest:
 ; CHECK-NEXT:    ret i32 1234
 ;
   switch i32 5, label %Default [

test/Transforms/SimplifyCFG/2004-12-10-SimplifyCFGCrash.ll

-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 
 define void @symhash_add() {
 entry:
   br i1 undef, label %then.0, label %UnifiedReturnBlock
 then.0:   ; preds = %entry
   br i1 undef, label %loopentry.2, label %loopentry.1.preheader
 loopentry.1.preheader:    ; preds = %then.0
   br label %loopentry.1.outer

test/Transforms/SimplifyCFG/2005-06-16-PHICrash.ll

-; 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]
 @g_59182229 = external global i32   ; <i32*> [#uses=2]
 
 define i32 @_Z13func_26556482h(i8 %l_88173906) {
 entry:
   %tmp.1 = bitcast i8 %l_88173906 to i8   ; <i8> [#uses=2]

test/Transforms/SimplifyCFG/2005-08-01-PHIUpdateFail.ll

-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 ; END.
 
 define void @main() {
 entry:
   %tmp.14.i19 = icmp eq i32 0, 2    ; <i1> [#uses=1]
   br i1 %tmp.14.i19, label %endif.1.i20, label %read_min.exit
 endif.1.i20:    ; preds = %entry
   %tmp.9.i.i = icmp eq i8* null, null    ; <i1> [#uses=1]

test/Transforms/SimplifyCFG/2005-10-02-InvokeSimplify.ll

-; 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( )
       to label %N unwind label %F   ; <i1> [#uses=1]
 F:    ; preds = %0
         %val = landingpad { i8*, i32 }
                  catch i8* null
   ret i1 false

test/Transforms/SimplifyCFG/2005-12-03-IncorrectPHIFold.ll

 ; 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]
 @_one_ = external global %struct.anon*    ; <%struct.anon**> [#uses=4]
 @str = internal constant [4 x i8] c"%d\0A\00"    ; <[4 x i8]*> [#uses=0]
 
 declare i32 @bc_compare(%struct.anon*, %struct.anon*)
 

test/Transforms/SimplifyCFG/2006-02-17-InfiniteUnroll.ll

-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 
 define void @polnel_() {
 entry:
   %tmp595 = icmp slt i32 0, 0    ; <i1> [#uses=4]
   br i1 %tmp595, label %bb148.critedge, label %cond_true40
 bb36:   ; preds = %bb43
   br i1 %tmp595, label %bb43, label %cond_true40
 cond_true40:    ; preds = %bb46, %cond_true40, %bb36, %entry

test/Transforms/SimplifyCFG/2006-06-12-InfLoop.ll

-; RUN: opt < %s -simplifycfg -disable-output
+; RUN: opt < %s -simplifycfg -verify-dom-info -disable-output
 ; END.
 
 define void @main(i32 %c) {
 entry:
   %tmp.9 = icmp eq i32 %c, 2    ; <i1> [#uses=1]
   br i1 %tmp.9, label %endif.0, label %then.0
 then.0:   ; preds = %entry
   ret void

test/Transforms/SimplifyCFG/2006-08-03-Crash.ll

-; RUN: opt < %s -gvn -simplifycfg -disable-output
+; RUN: opt < %s -gvn -simplifycfg -verify-dom-info -disable-output
 ; PR867
 
 target datalayout = "E-p:32:32"
 target triple = "powerpc-apple-darwin8"
   %struct.CUMULATIVE_ARGS = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32 }
   %struct.eh_status = type opaque
   %struct.emit_status = type { i32, i32, %struct.rtx_def*, %struct.rtx_def*, %struct.sequence_stack*, i32, %struct.location_t, i32, i8*, %struct.rtx_def** }
   %struct.expr_status = type { i32, i32, i32, %struct.rtx_def*, %struct.rtx_def*, %struct.rtx_def* }

test/Transforms/SimplifyCFG/2006-10-19-UncondDiv.ll

 ; PR957
-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 
 ; CHECK-NOT: select
 
 @G = extern_weak global i32
 
 define i32 @test(i32 %tmp) {
 cond_false179:
   %tmp181 = icmp eq i32 %tmp, 0    ; <i1> [#uses=1]

test/Transforms/SimplifyCFG/2006-12-08-Ptr-ICmp-Branch.ll

-; RUN: opt < %s -simplifycfg | llvm-dis
+; RUN: opt < %s -simplifycfg -verify-dom-info | llvm-dis
 ; END.
 
 ; ModuleID = '2006-12-08-Ptr-ICmp-Branch.ll'
 target datalayout = "e-p:32:32"
 target triple = "i686-pc-linux-gnu"
   %struct.FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct.FILE*, i32, i32, i32, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i32, i32, [40 x i8] }
   %struct._IO_FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct.FILE*, i32, i32, i32, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i32, i32, [40 x i8] }
   %struct._IO_marker = type { %struct._IO_marker*, %struct.FILE*, i32 }

test/Transforms/SimplifyCFG/2007-11-22-InvokeNoUnwind.ll

-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -verify-dom-info -S | FileCheck %s
 
 ; CHECK-NOT: invoke
 
 declare i32 @func(i8*) nounwind
 
 define i32 @test() personality i32 (...)* @__gxx_personality_v0 {
   invoke i32 @func( i8* null )
       to label %Cont unwind label %Other    ; <i32>:1 [#uses=0]

test/Transforms/SimplifyCFG/2007-12-21-Crash.ll

-;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  {
 entry:
   br label %bb5.outer
 
 bb5.outer.loopexit:   ; preds = %bb5
   br label %bb5.outer

test/Transforms/SimplifyCFG/2008-01-02-hoist-fp-add.ll

 ; 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"
 @G = weak global i32 0, align 8    ; <i32*> [#uses=2]
 
 define void @test(i32 %X, i32 %Y, i32 %Z) {
 entry:
   %"alloca point" = bitcast i32 0 to i32    ; <i32> [#uses=0]

test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll

-; 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
 
 ; ModuleID = '<stdin>' 
 declare i1 @foo()
 
 declare i1 @bar(i32)
 

test/Transforms/SimplifyCFG/2008-07-13-InfLoopMiscompile.ll

 ; 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.
 
 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:32:32"
 target triple = "i386-pc-linux-gnu"
 @g_37 = common global i32 0   ; <i32*> [#uses=1]
 @.str = internal constant [4 x i8] c"%d\0A\00"    ; <[4 x i8]*> [#uses=1]
 

test/Transforms/SimplifyCFG/2008-09-08-MultiplePred.ll

-; 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]
 
 define i32 @func_127(i32 %p_129) nounwind {
 entry:
   load i32, i32* @g_103, align 4    ; <i32>:0 [#uses=1]
   icmp eq i32 %0, 0   ; <i1>:1 [#uses=2]
   br i1 %1, label %bb6.preheader, label %entry.return_crit_edge

test/Transforms/SimplifyCFG/DeadSetCC.ll

-; 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
 ; folds a conditional branch into a switch instruction.
 
 declare void @foo()
 
 declare void @bar()

test/Transforms/SimplifyCFG/EmptyBlockMerge.ll

 ; 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()
 
 define void @cprop_test12(i32* %data) {
 bb0:
   %reg108 = load i32, i32* %data    ; <i32> [#uses=2]
   %cond218 = icmp ne i32 %reg108, 5    ; <i1> [#uses=1]
   br i1 %cond218, label %bb3, label %bb2

test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll

 ; 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
 ; RUN: not grep "^BB.tomerge" %t
 ; RUN: grep "^BB.nomerge" %t | count 4
 ;
 
 ; ModuleID = '<stdin>'