[JumpThreading] Preserve DT and LVI across the pass.

[brzycki]

Summary

JumpThreading now preserves dominance and lazy value information across the entire pass. The pass manager is also informed of this preservation with the goal of DT and LVI being recalculated fewer times overall during compilation.

This change prepares JumpThreading for enhanced opportunities; particularly those across loop boundaries.

Patch by Brian Rzycki and Sebastian Pop.

This is the second attempt at the patch, the first one can be found at D37528. This also includes the fix from D38383 and a fix to an assert reported by @eli.friedman .

[kuhar]

Have you tried profiling it on some non-trivial module, like sqlite3? I'm wondering where the reported slowdown comes from exactly.

[brzycki]

In D38558#888638, @kuhar wrote:

Have you tried profiling it on some non-trivial module, like sqlite3? I'm wondering where the reported slowdown comes from exactly.

Not yet. I've focused on correctness and bug fixing. I was planning on spending some time tomorrow to analyze compile time deltas. Do you have any recommended tools to help?

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1112

@eli.friedman This is the fix for your assert. In this context BB had a terminator instruction that looked like:

br i8 cmp eq 0, %BB_A, %BB_A

In this corner-case we don't actually remove the edge in the dominance graph because we're converting to:

br %BB_A

And the edge between these two blocks still exists.

[bmakam]

llvm/lib/Transforms/Utils/Local.cpp

692

I am trying to understand why we need to recalculate DT here. Can't we just delete the edge before nuking BB instead of recalculating?

[brzycki]

Rebase patch to tip as of 10/24/2017.

[brzycki]

This code is superceded by D40146.

llvm/lib/Transforms/Utils/Local.cpp

692

Hello @bmakam , unfortunately no. In this corner case we've removed the entry block of the function. This is treated as the root node of the new DT data structure @kuhar implemented. If we continue as you propose the next insertEdge() or deleteEdge() returns an assert about the root node of the DT being invalid.

I had a private e-mail thread discussion with @kuhar and @dberlin last August and we decided on this compromise in this corner-case event.

692

I collected some statistics on this event: of the times we enter MergeBasicBlockIntoOnlyPred() this case is encountered somewhere around 5% of the time:

4.49% of calls remove the entry block for ninja check
913 calls into MergeBasicBlockIntoOnlyPred
41 entry block removals

5.09% of calls remove the entry block for test-suite build
30335 calls into MergeBasicBlockIntoOnlyPred
1545 entry block removals

953

This is the same patch as D38383.

llvm/include/llvm/Transforms/Scalar/JumpThreading.h

 
 namespace llvm {
 
 class BasicBlock;
 class BinaryOperator;
 class BranchInst;
 class CmpInst;
 class Constant;
+class DominatorTree;
 class Function;
 class Instruction;
 class IntrinsicInst;
 class LazyValueInfo;
 class LoadInst;
 class PHINode;
 class TargetLibraryInfo;
 class Value;

 ///   if (X < 3) {
 ///
 /// In this case, the unconditional branch at the end of the first if can be
 /// revectored to the false side of the second if.
 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
   TargetLibraryInfo *TLI;
   LazyValueInfo *LVI;
   AliasAnalysis *AA;
+  DominatorTree *DT;
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = false;
   bool HasGuards = false;
 #ifdef NDEBUG
   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
 #else
   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
struct RecursionSetRemover {
     ~RecursionSetRemover() { TheSet.erase(ThePair); }
   };
 
 public:
   JumpThreadingPass(int T = -1);
 
   // Glue for old PM.
   bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_,
-               AliasAnalysis *AA_, bool HasProfileData_,
+               AliasAnalysis *AA_, DominatorTree *DT_, bool HasProfileData_,
                std::unique_ptr<BlockFrequencyInfo> BFI_,
                std::unique_ptr<BranchProbabilityInfo> BPI_);
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   void releaseMemory() {
     BFI.reset();
     BPI.reset();

llvm/include/llvm/Transforms/Utils/Local.h

 /// If a terminator instruction is predicated on a constant value, convert it
 /// into an unconditional branch to the constant destination.
 /// This is a nontrivial operation because the successors of this basic block
 /// must have their PHI nodes updated.
 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
 /// conditions and indirectbr addresses this might make dead if
 /// DeleteDeadConditions is true.
 bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,
-                            const TargetLibraryInfo *TLI = nullptr);
+                            const TargetLibraryInfo *TLI = nullptr,
+                            DominatorTree *DT = nullptr);
 
 //===----------------------------------------------------------------------===//
 //  Local dead code elimination.
 //
 
 /// Return true if the result produced by the instruction is not used, and the
 /// instruction has no side effects.
 bool isInstructionTriviallyDead(Instruction *I,

 ///
 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
 /// nodes that collapse into identity values.  For example, if we have:
 ///   x = phi(1, 0, 0, 0)
 ///   y = and x, z
 ///
 /// .. and delete the predecessor corresponding to the '1', this will attempt to
 /// recursively fold the 'and' to 0.
-void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred);
+void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
+                                  DominatorTree *DT = nullptr);
 
 /// BB is a block with one predecessor and its predecessor is known to have one
 /// successor (BB!). Eliminate the edge between them, moving the instructions in
 /// the predecessor into BB. This deletes the predecessor block.
 void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr);
 
 /// BB is known to contain an unconditional branch, and contains no instructions
 /// other than PHI nodes, potential debug intrinsics and the branch. If
 /// possible, eliminate BB by rewriting all the predecessors to branch to the
 /// successor block and return true. If we can't transform, return false.
-bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB);
+bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
+                                             DominatorTree *DT = nullptr);
 
 /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try
 /// to be clever about PHI nodes which differ only in the order of the incoming
 /// values, but instcombine orders them so it usually won't matter.
 bool EliminateDuplicatePHINodes(BasicBlock *BB);
 
 /// This function is used to do simplification of a CFG.  For example, it
 /// adjusts branches to branches to eliminate the extra hop, it eliminates

 
 /// Remove all instructions from a basic block other than it's terminator
 /// and any present EH pad instructions.
 unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB);
 
 /// Insert an unreachable instruction before the specified
 /// instruction, making it and the rest of the code in the block dead.
 unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap,
-                             bool PreserveLCSSA = false);
+                             bool PreserveLCSSA = false,
+                             DominatorTree *DT = nullptr);
 
 /// Convert the CallInst to InvokeInst with the specified unwind edge basic
 /// block.  This also splits the basic block where CI is located, because
 /// InvokeInst is a terminator instruction.  Returns the newly split basic
 /// block.
 BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                              BasicBlock *UnwindEdge);
 
 /// Replace 'BB's terminator with one that does not have an unwind successor
 /// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind
 /// successor.
 ///
 /// \param BB  Block whose terminator will be replaced.  Its terminator must
 ///            have an unwind successor.
-void removeUnwindEdge(BasicBlock *BB);
+void removeUnwindEdge(BasicBlock *BB, DominatorTree *DT = nullptr);
 
 /// Remove all blocks that can not be reached from the function's entry.
 ///
 /// Returns true if any basic block was removed.
-bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr);
+bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr,
+                             DominatorTree *DT = nullptr);
 
 /// Combine the metadata of two instructions so that K can replace J
 ///
 /// Metadata not listed as known via KnownIDs is removed
 void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
 
 /// Combine the metadata of two instructions so that K can replace J. This
 /// specifically handles the case of CSE-like transformations.

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

public:
     static char ID;
     CorrelatedValuePropagation(): FunctionPass(ID) {
      initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.addRequired<DominatorTreeWrapperPass>();
       AU.addRequired<LazyValueInfoWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
     }
   };
 }
 
 char CorrelatedValuePropagation::ID = 0;
 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
                 "Value Propagation", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
                 "Value Propagation", false, false)
 
 // Public interface to the Value Propagation pass
 Pass *llvm::createCorrelatedValuePropagationPass() {
   return new CorrelatedValuePropagation();
 }

llvm/lib/Transforms/Scalar/JumpThreading.cpp

public:
 
     JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) {
       initializeJumpThreadingPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
-      if (PrintLVIAfterJumpThreading)
-        AU.addRequired<DominatorTreeWrapperPass>();
+      AU.addPreserved<DominatorTreeWrapperPass>();
       AU.addRequired<AAResultsWrapperPass>();
       AU.addRequired<LazyValueInfoWrapperPass>();
+      AU.addPreserved<LazyValueInfoWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
       AU.addRequired<TargetLibraryInfoWrapperPass>();
     }
 
     void releaseMemory() override { Impl.releaseMemory(); }
   };
 
 } // end anonymous namespace
 
 char JumpThreading::ID = 0;
 
 INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading",
                 "Jump Threading", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(JumpThreading, "jump-threading",
                 "Jump Threading", false, false)
 
 // Public interface to the Jump Threading pass
 FunctionPass *llvm::createJumpThreadingPass(int Threshold) {
static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB) {
   }
 }
 
 /// runOnFunction - Toplevel algorithm.
 bool JumpThreading::runOnFunction(Function &F) {
   if (skipFunction(F))
     return false;
   auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+  // Get DT analysis before LVI. When LVI is initialized it conditionally adds
+  // DT if it's available.
+  auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
   auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = F.getEntryCount().hasValue();
   if (HasProfileData) {
     LoopInfo LI{DominatorTree(F)};
     BPI.reset(new BranchProbabilityInfo(F, LI, TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }
 
-  bool Changed = Impl.runImpl(F, TLI, LVI, AA, HasProfileData, std::move(BFI),
-                              std::move(BPI));
+  bool Changed = Impl.runImpl(F, TLI, LVI, AA, DT, HasProfileData,
+                              std::move(BFI), std::move(BPI));
   if (PrintLVIAfterJumpThreading) {
     dbgs() << "LVI for function '" << F.getName() << "':\n";
-    LVI->printLVI(F, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
-                  dbgs());
+    LVI->printLVI(F, *DT, dbgs());
   }
   return Changed;
 }
 
 PreservedAnalyses JumpThreadingPass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
+  // Get DT analysis before LVI. When LVI is initialized it conditionally adds
+  // DT if it's available.
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &LVI = AM.getResult<LazyValueAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
 
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = F.getEntryCount().hasValue();
   if (HasProfileData) {
     LoopInfo LI{DominatorTree(F)};
     BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }
 
-  bool Changed = runImpl(F, &TLI, &LVI, &AA, HasProfileData, std::move(BFI),
-                         std::move(BPI));
+  bool Changed = runImpl(F, &TLI, &LVI, &AA, &DT, HasProfileData,
+                         std::move(BFI), std::move(BPI));
 
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<GlobalsAA>();
+  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<LazyValueAnalysis>();
   return PA;
 }
 
 bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
                                 LazyValueInfo *LVI_, AliasAnalysis *AA_,
-                                bool HasProfileData_,
+                                DominatorTree *DT_, bool HasProfileData_,
                                 std::unique_ptr<BlockFrequencyInfo> BFI_,
                                 std::unique_ptr<BranchProbabilityInfo> BPI_) {
   DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
   TLI = TLI_;
   LVI = LVI_;
   AA = AA_;
+  DT = DT_;
   BFI.reset();
   BPI.reset();
   // When profile data is available, we need to update edge weights after
   // successful jump threading, which requires both BPI and BFI being available.
   HasProfileData = HasProfileData_;
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   HasGuards = GuardDecl && !GuardDecl->use_empty();
   if (HasProfileData) {
     BPI = std::move(BPI_);
     BFI = std::move(BFI_);
   }
 
   // Remove unreachable blocks from function as they may result in infinite
   // loop. We do threading if we found something profitable. Jump threading a
   // branch can create other opportunities. If these opportunities form a cycle
   // i.e. if any jump threading is undoing previous threading in the path, then
   // we will loop forever. We take care of this issue by not jump threading for
   // back edges. This works for normal cases but not for unreachable blocks as
   // they may have cycle with no back edge.
   bool EverChanged = false;
-  EverChanged |= removeUnreachableBlocks(F, LVI);
-
+  EverChanged |= removeUnreachableBlocks(F, LVI, DT);
   FindLoopHeaders(F);
 
   bool Changed;
   do {
     Changed = false;
     for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
       BasicBlock *BB = &*I;
       // Thread all of the branches we can over this block.
for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
           // If the terminator is the only non-phi instruction, try to nuke it.
           BB->getFirstNonPHIOrDbg()->isTerminator() && !LoopHeaders.count(BB) &&
           !LoopHeaders.count(BI->getSuccessor(0))) {
         // FIXME: It is always conservatively correct to drop the info
         // for a block even if it doesn't get erased.  This isn't totally
         // awesome, but it allows us to use AssertingVH to prevent nasty
         // dangling pointer issues within LazyValueInfo.
         LVI->eraseBlock(BB);
-        if (TryToSimplifyUncondBranchFromEmptyBlock(BB))
+        if (TryToSimplifyUncondBranchFromEmptyBlock(BB, DT))
           Changed = true;
       }
     }
     EverChanged |= Changed;
   } while (Changed);
 
   LoopHeaders.clear();
   return EverChanged;
if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {
     const TerminatorInst *TI = SinglePred->getTerminator();
     if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&
         SinglePred != BB && !hasAddressTakenAndUsed(BB)) {
       // If SinglePred was a loop header, BB becomes one.
       if (LoopHeaders.erase(SinglePred))
         LoopHeaders.insert(BB);
 
       LVI->eraseBlock(SinglePred);
-      MergeBasicBlockIntoOnlyPred(BB);
+      MergeBasicBlockIntoOnlyPred(BB, DT);
 
       // Now that BB is merged into SinglePred (i.e. SinglePred Code followed by
       // BB code within one basic block `BB`), we need to invalidate the LVI
       // information associated with BB, because the LVI information need not be
       // true for all of BB after the merge. For example,
       // Before the merge, LVI info and code is as follows:
       // SinglePred: <LVI info1 for %p val>
       // %y = use of %p
if (SimpleVal) {
       Condition = SimpleVal;
     }
   }
 
   // If the terminator is branching on an undef, we can pick any of the
   // successors to branch to.  Let GetBestDestForJumpOnUndef decide.
   if (isa<UndefValue>(Condition)) {
     unsigned BestSucc = GetBestDestForJumpOnUndef(BB);
+    std::vector<DominatorTree::UpdateType> Updates;
 
     // Fold the branch/switch.
     TerminatorInst *BBTerm = BB->getTerminator();
     for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
       if (i == BestSucc) continue;
-      BBTerm->getSuccessor(i)->removePredecessor(BB, true);
+      BasicBlock *Succ = BBTerm->getSuccessor(i);
+      Succ->removePredecessor(BB, true);
+      if (Succ == BB)
+        continue;
+      DominatorTree::UpdateType UT = {DominatorTree::Delete, BB, Succ};
+      // Make sure to remove a DT edge exactly once and not an edge to itself.
+      if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+        Updates.push_back(UT);
     }
 
     DEBUG(dbgs() << "  In block '" << BB->getName()
           << "' folding undef terminator: " << *BBTerm << '\n');
     BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
     BBTerm->eraseFromParent();
+    DT->applyUpdates(Updates);
     return true;
   }
 
   // If the terminator of this block is branching on a constant, simplify the
   // terminator to an unconditional branch.  This can occur due to threading in
   // other blocks.
   if (getKnownConstant(Condition, Preference)) {
     DEBUG(dbgs() << "  In block '" << BB->getName()
           << "' folding terminator: " << *BB->getTerminator() << '\n');
     ++NumFolds;
-    ConstantFoldTerminator(BB, true);
+    ConstantFoldTerminator(BB, true, nullptr, DT);
     return true;
   }
 
   Instruction *CondInst = dyn_cast<Instruction>(Condition);
 
   // All the rest of our checks depend on the condition being an instruction.
   if (!CondInst) {
     // FIXME: Unify this with code below.
if (CondBr && CondConst) {
       assert(CondBr->isConditional() && "Threading on unconditional terminator");
 
       LazyValueInfo::Tristate Ret =
         LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
                             CondConst, CondBr);
       if (Ret != LazyValueInfo::Unknown) {
         unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
         unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;
-        CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true);
+        BasicBlock *ToRemoveSucc = CondBr->getSuccessor(ToRemove);
+        BasicBlock *ToKeepSucc = CondBr->getSuccessor(ToKeep);
+        ToRemoveSucc->removePredecessor(BB, true);
         BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
         CondBr->eraseFromParent();
+        if (BB != ToRemoveSucc && ToRemoveSucc != ToKeepSucc)
+          DT->deleteEdge(BB, ToRemoveSucc);
         if (CondCmp->use_empty())
           CondCmp->eraseFromParent();
         // We can safely replace *some* uses of the CondInst if it has
         // exactly one value as returned by LVI. RAUW is incorrect in the
         // presence of guards and assumes, that have the `Cond` as the use. This
         // is because we use the guards/assume to reason about the `Cond` value
         // at the end of block, but RAUW unconditionally replaces all uses
         // including the guards/assumes themselves and the uses before the
if (!PBI || !PBI->isConditional())
       return false;
     if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
       return false;
 
     bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
     Optional<bool> Implication =
         isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
     if (Implication) {
-      BI->getSuccessor(*Implication ? 1 : 0)->removePredecessor(BB);
-      BranchInst::Create(BI->getSuccessor(*Implication ? 0 : 1), BI);
+      BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
+      BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
+      RemoveSucc->removePredecessor(BB);
+      BranchInst::Create(KeepSucc, BI);
       BI->eraseFromParent();
+      if (BB != RemoveSucc && RemoveSucc != KeepSucc)
+        DT->deleteEdge(BB, RemoveSucc);
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 
   return false;
 }
if (PredToDestList.empty())
     return false;
 
   // If all the predecessors go to a single known successor, we want to fold,
   // not thread. By doing so, we do not need to duplicate the current block and
   // also miss potential opportunities in case we dont/cant duplicate.
   if (OnlyDest && OnlyDest != MultipleDestSentinel) {
     if (PredWithKnownDest ==
         (size_t)std::distance(pred_begin(BB), pred_end(BB))) {
+      std::vector<DominatorTree::UpdateType> Updates;
       bool SeenFirstBranchToOnlyDest = false;
       for (BasicBlock *SuccBB : successors(BB)) {
-        if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest)
+        if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
           SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
-        else
+        } else {
           SuccBB->removePredecessor(BB, true); // This is unreachable successor.
+          if (SuccBB != OnlyDest && SuccBB != BB) {
+            DominatorTree::UpdateType UT = {DominatorTree::Delete, BB, SuccBB};
+            // Make sure to remove a DT edge exactly once.
+            if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+              Updates.push_back(UT);
+          }
+        }
       }
 
       // Finally update the terminator.
       TerminatorInst *Term = BB->getTerminator();
       BranchInst::Create(OnlyDest, Term);
       Term->eraseFromParent();
+      DT->applyUpdates(Updates);
 
       // If the condition is now dead due to the removal of the old terminator,
       // erase it.
       if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
         if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
           CondInst->eraseFromParent();
         // We can safely replace *some* uses of the CondInst if it has
         // exactly one value as returned by LVI. RAUW is incorrect in the
for (Use &U : I.uses()) {
       if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
         if (UserPN->getIncomingBlock(U) == BB)
           continue;
       } else if (User->getParent() == BB)
         continue;
 
       UsesToRename.push_back(&U);
     }
-
     // If there are no uses outside the block, we're done with this instruction.
     if (UsesToRename.empty())
       continue;
 
     DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
 
     // We found a use of I outside of BB.  Rename all uses of I that are outside
     // its block to be uses of the appropriate PHI node etc.  See ValuesInBlocks
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   // us to simplify any PHI nodes in BB.
   TerminatorInst *PredTerm = PredBB->getTerminator();
   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
     if (PredTerm->getSuccessor(i) == BB) {
       BB->removePredecessor(PredBB, true);
       PredTerm->setSuccessor(i, NewBB);
     }
 
+  DT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
+                    {DominatorTree::Insert, PredBB, NewBB},
+                    {DominatorTree::Delete, PredBB, BB}});
+
   // At this point, the IR is fully up to date and consistent.  Do a quick scan
   // over the new instructions and zap any that are constants or dead.  This
   // frequently happens because of phi translation.
   SimplifyInstructionsInBlock(NewBB, TLI);
 
   // Update the edge weight from BB to SuccBB, which should be less than before.
   UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);
 
BasicBlock *JumpThreadingPass::SplitBlockPreds(BasicBlock *BB,
                                                const char *Suffix) {
   // Collect the frequencies of all predecessors of BB, which will be used to
   // update the edge weight on BB->SuccBB.
   BlockFrequency PredBBFreq(0);
   if (HasProfileData)
     for (auto Pred : Preds)
       PredBBFreq += BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB);
 
-  BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix);
+  BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix, DT);
 
   // Set the block frequency of the newly created PredBB, which is the sum of
   // frequencies of Preds.
   if (HasProfileData)
     BFI->setBlockFreq(PredBB, PredBBFreq.getFrequency());
   return PredBB;
 }
 
DEBUG(dbgs() << "  Duplicating block '" << BB->getName() << "' into end of '"
         << PredBB->getName() << "' to eliminate branch on phi.  Cost: "
         << DuplicationCost << " block is:" << *BB << "\n");
 
   // Unless PredBB ends with an unconditional branch, split the edge so that we
   // can just clone the bits from BB into the end of the new PredBB.
   BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
 
   if (!OldPredBranch || !OldPredBranch->isUnconditional()) {
-    PredBB = SplitEdge(PredBB, BB);
+    PredBB = SplitEdge(PredBB, BB, DT);
     OldPredBranch = cast<BranchInst>(PredBB->getTerminator());
   }
 
   // We are going to have to map operands from the original BB block into the
   // PredBB block.  Evaluate PHI nodes in BB.
   DenseMap<Instruction*, Value*> ValueMapping;
 
   BasicBlock::iterator BI = BB->begin();
bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
   }
 
   // PredBB no longer jumps to BB, remove entries in the PHI node for the edge
   // that we nuked.
   BB->removePredecessor(PredBB, true);
 
   // Remove the unconditional branch at the end of the PredBB block.
   OldPredBranch->eraseFromParent();
+  if (BB != PredBB)
+    DT->deleteEdge(PredBB, BB);
 
   ++NumDupes;
   return true;
 }
 
 /// TryToUnfoldSelect - Look for blocks of the form
 /// bb1:
 ///   %a = select
if ((LHSFolds != LazyValueInfo::Unknown ||
       //  |-----
       //  v
       // BB
       BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold",
                                              BB->getParent(), BB);
       // Move the unconditional branch to NewBB.
       PredTerm->removeFromParent();
       NewBB->getInstList().insert(NewBB->end(), PredTerm);
+      DT->insertEdge(NewBB, BB);
       // Create a conditional branch and update PHI nodes.
       BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
       CondLHS->setIncomingValue(I, SI->getFalseValue());
       CondLHS->addIncoming(SI->getTrueValue(), NewBB);
       // The select is now dead.
       SI->eraseFromParent();
 
+      DT->insertEdge(Pred, NewBB);
       // Update any other PHI nodes in BB.
       for (BasicBlock::iterator BI = BB->begin();
            PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
         if (Phi != CondLHS)
           Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
       return true;
     }
   }
for (Use &U : PN->uses()) {
         }
       }
     }
 
     if (!SI)
       continue;
     // Expand the select.
     TerminatorInst *Term =
-        SplitBlockAndInsertIfThen(SI->getCondition(), SI, false);
+        SplitBlockAndInsertIfThen(SI->getCondition(), SI, false, nullptr, DT);
     PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);
     NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
     NewPN->addIncoming(SI->getFalseValue(), BB);
     SI->replaceAllUsesWith(NewPN);
     SI->eraseFromParent();
     return true;
   }
   return false;
else {
     Impl = isImpliedCondition(BranchCond, GuardCond, DL, /* LHSIsTrue */ false);
     if (Impl && *Impl)
       FalseDestIsSafe = true;
   }
 
   if (!TrueDestIsSafe && !FalseDestIsSafe)
     return false;
 
-  BasicBlock *UnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
-  BasicBlock *GuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
+  BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
+  BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
 
   ValueToValueMapTy UnguardedMapping, GuardedMapping;
   Instruction *AfterGuard = Guard->getNextNode();
   unsigned Cost = getJumpThreadDuplicationCost(BB, AfterGuard, BBDupThreshold);
   if (Cost > BBDupThreshold)
     return false;
   // Duplicate all instructions before the guard and the guard itself to the
   // branch where implication is not proved.
-  GuardedBlock = DuplicateInstructionsInSplitBetween(
-      BB, GuardedBlock, AfterGuard, GuardedMapping);
+  BasicBlock *GuardedBlock = DuplicateInstructionsInSplitBetween(
+      BB, PredGuardedBlock, AfterGuard, GuardedMapping);
   assert(GuardedBlock && "Could not create the guarded block?");
   // Duplicate all instructions before the guard in the unguarded branch.
   // Since we have successfully duplicated the guarded block and this block
   // has fewer instructions, we expect it to succeed.
-  UnguardedBlock = DuplicateInstructionsInSplitBetween(BB, UnguardedBlock,
-                                                       Guard, UnguardedMapping);
+  BasicBlock *UnguardedBlock = DuplicateInstructionsInSplitBetween(
+      BB, PredUnguardedBlock, Guard, UnguardedMapping);
   assert(UnguardedBlock && "Could not create the unguarded block?");
   DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
                << GuardedBlock->getName() << "\n");
+  // DuplicateInstructionsInSplitBetween inserts a new block, BB.split, between
+  // PredBB and BB. We need to perform two inserts and one delete in DT for each
+  // of the above calls.
+  DT->applyUpdates({// Guarded block split.
+                    {DominatorTree::Delete, PredGuardedBlock, BB},
+                    {DominatorTree::Insert, PredGuardedBlock, GuardedBlock},
+                    {DominatorTree::Insert, GuardedBlock, BB},
+                    // Unguarded block split.
+                    {DominatorTree::Delete, PredUnguardedBlock, BB},
+                    {DominatorTree::Insert, PredUnguardedBlock, UnguardedBlock},
+                    {DominatorTree::Insert, UnguardedBlock, BB}});
 
   // Some instructions before the guard may still have uses. For them, we need
   // to create Phi nodes merging their copies in both guarded and unguarded
   // branches. Those instructions that have no uses can be just removed.
   SmallVector<Instruction *, 4> ToRemove;
   for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
     if (!isa<PHINode>(&*BI))
       ToRemove.push_back(&*BI);

llvm/lib/Transforms/Utils/Local.cpp

 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
 /// constant value, convert it into an unconditional branch to the constant
 /// destination.  This is a nontrivial operation because the successors of this
 /// basic block must have their PHI nodes updated.
 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
 /// conditions and indirectbr addresses this might make dead if
 /// DeleteDeadConditions is true.
 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
-                                  const TargetLibraryInfo *TLI) {
+                                  const TargetLibraryInfo *TLI,
+                                  DominatorTree *DT) {
   TerminatorInst *T = BB->getTerminator();
   IRBuilder<> Builder(T);
 
   // Branch - See if we are conditional jumping on constant
   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
     BasicBlock *Dest1 = BI->getSuccessor(0);
     BasicBlock *Dest2 = BI->getSuccessor(1);
if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
 
       // Let the basic block know that we are letting go of it.  Based on this,
       // it will adjust it's PHI nodes.
       OldDest->removePredecessor(BB);
 
       // Replace the conditional branch with an unconditional one.
       Builder.CreateBr(Destination);
       BI->eraseFromParent();
+      if (DT && OldDest != Destination && OldDest != BB)
+        DT->deleteEdge(BB, OldDest);
       return true;
     }
 
     if (Dest2 == Dest1) {       // Conditional branch to same location?
       // This branch matches something like this:
       //     br bool %cond, label %Dest, label %Dest
       // and changes it into:  br label %Dest
 
for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
           // Remove weight for this case.
           std::swap(Weights[idx+1], Weights.back());
           Weights.pop_back();
           SI->setMetadata(LLVMContext::MD_prof,
                           MDBuilder(BB->getContext()).
                           createBranchWeights(Weights));
         }
         // Remove this entry.
-        DefaultDest->removePredecessor(SI->getParent());
+        BasicBlock *ParentBB = SI->getParent();
+        DefaultDest->removePredecessor(ParentBB);
         i = SI->removeCase(i);
         e = SI->case_end();
+        if (DT && DefaultDest != ParentBB) {
+          // DefaultDest may still be a successor of a non-default case.
+          if (none_of(successors(ParentBB), [DefaultDest](BasicBlock *S) {
+                return S == DefaultDest;
+              }))
+            DT->deleteEdge(ParentBB, DefaultDest);
+        }
         continue;
       }
 
       // Otherwise, check to see if the switch only branches to one destination.
       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
       // destinations.
       if (i->getCaseSuccessor() != TheOnlyDest)
         TheOnlyDest = nullptr;
if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
     }
 
     // If we found a single destination that we can fold the switch into, do so
     // now.
     if (TheOnlyDest) {
       // Insert the new branch.
       Builder.CreateBr(TheOnlyDest);
       BasicBlock *BB = SI->getParent();
+      BasicBlock *TheOnlyDestCheck = TheOnlyDest;
+      std::vector<DominatorTree::UpdateType> Updates;
 
       // Remove entries from PHI nodes which we no longer branch to...
       for (BasicBlock *Succ : SI->successors()) {
         // Found case matching a constant operand?
-        if (Succ == TheOnlyDest)
+        if (Succ == TheOnlyDest) {
           TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
-        else
+        } else {
           Succ->removePredecessor(BB);
+          if (DT && Succ != TheOnlyDestCheck && Succ != BB) {
+            DominatorTree::UpdateType UT = {DominatorTree::Delete, BB, Succ};
+            if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+              Updates.push_back(UT);
+          }
+        }
       }
 
       // Delete the old switch.
       Value *Cond = SI->getCondition();
       SI->eraseFromParent();
+      if (DT)
+        DT->applyUpdates(Updates);
       if (DeleteDeadConditions)
         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
       return true;
     }
 
     if (SI->getNumCases() == 1) {
       // Otherwise, we can fold this switch into a conditional branch
       // instruction if it has only one non-default destination.
if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
     return false;
   }
 
   if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {
     // indirectbr blockaddress(@F, @BB) -> br label @BB
     if (BlockAddress *BA =
           dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
       BasicBlock *TheOnlyDest = BA->getBasicBlock();
+      BasicBlock *TheOnlyDestCheck = TheOnlyDest;
+      std::vector<DominatorTree::UpdateType> Updates;
       // Insert the new branch.
       Builder.CreateBr(TheOnlyDest);
 
       for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
-        if (IBI->getDestination(i) == TheOnlyDest)
+        if (IBI->getDestination(i) == TheOnlyDest) {
           TheOnlyDest = nullptr;
-        else
-          IBI->getDestination(i)->removePredecessor(IBI->getParent());
+        } else {
+          BasicBlock *ParentBB = IBI->getParent();
+          BasicBlock *DestBB = IBI->getDestination(i);
+          DestBB->removePredecessor(ParentBB);
+          if (DT && DestBB != TheOnlyDestCheck && DestBB != ParentBB) {
+            DominatorTree::UpdateType UT = {DominatorTree::Delete, ParentBB,
+                                            DestBB};
+            if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+              Updates.push_back(UT);
+          }
+        }
       }
       Value *Address = IBI->getAddress();
       IBI->eraseFromParent();
+      if (DT)
+        DT->applyUpdates(Updates);
       if (DeleteDeadConditions)
         RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);
 
       // If we didn't find our destination in the IBI successor list, then we
       // have undefined behavior.  Replace the unconditional branch with an
       // 'unreachable' instruction.
       if (TheOnlyDest) {
         BB->getTerminator()->eraseFromParent();

 ///
 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
 /// nodes that collapse into identity values.  For example, if we have:
 ///   x = phi(1, 0, 0, 0)
 ///   y = and x, z
 ///
 /// .. and delete the predecessor corresponding to the '1', this will attempt to
 /// recursively fold the and to 0.
-void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) {
+void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
+                                        DominatorTree *DT) {
   // This only adjusts blocks with PHI nodes.
   if (!isa<PHINode>(BB->begin()))
     return;
 
   // Remove the entries for Pred from the PHI nodes in BB, but do not simplify
   // them down.  This will leave us with single entry phi nodes and other phis
   // that can be removed.
   BB->removePredecessor(Pred, true);
 
   WeakTrackingVH PhiIt = &BB->front();
   while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
     PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
     Value *OldPhiIt = PhiIt;
 
     if (!recursivelySimplifyInstruction(PN))
       continue;
 
     // If recursive simplification ended up deleting the next PHI node we would
     // iterate to, then our iterator is invalid, restart scanning from the top
     // of the block.
     if (PhiIt != OldPhiIt) PhiIt = &BB->front();
   }
+  if (DT && BB != Pred)
+    DT->deleteEdge(Pred, BB);
 }
 
 
 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
 /// between them, moving the instructions in the predecessor into DestBB and
 /// deleting the predecessor block.
 ///
 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) {
   // If BB has single-entry PHI nodes, fold them.
   while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
     Value *NewVal = PN->getIncomingValue(0);
     // Replace self referencing PHI with undef, it must be dead.
     if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
     PN->replaceAllUsesWith(NewVal);
     PN->eraseFromParent();
   }
 
   BasicBlock *PredBB = DestBB->getSinglePredecessor();
   assert(PredBB && "Block doesn't have a single predecessor!");
 
+  // Collect all the edges that enter PredBB, discarding edges to itself and
+  // duplicates. These dominator edges will be redirected to DestBB.
+  std::vector<DominatorTree::UpdateType> Updates;
+  if (DT)
+    for (pred_iterator PI = pred_begin(PredBB), E = pred_end(PredBB); PI != E;
+         ++PI) {
+      if (*PI == PredBB)
+        continue;
+      DominatorTree::UpdateType UT = {DominatorTree::Delete, *PI, PredBB};
+      if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end()) {
+        Updates.push_back(UT);
+        // DestBB cannot dominate itself.
+        if (*PI != DestBB)
+          Updates.push_back({DominatorTree::Insert, *PI, DestBB});
+      }
+    }
+
   // Zap anything that took the address of DestBB.  Not doing this will give the
   // address an invalid value.
   if (DestBB->hasAddressTaken()) {
     BlockAddress *BA = BlockAddress::get(DestBB);
     Constant *Replacement =
       ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1);
     BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
                                                      BA->getType()));
     BA->destroyConstant();
   }
 
   // Anything that branched to PredBB now branches to DestBB.
   PredBB->replaceAllUsesWith(DestBB);
 
   // Splice all the instructions from PredBB to DestBB.
   PredBB->getTerminator()->eraseFromParent();
   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
 
   // If the PredBB is the entry block of the function, move DestBB up to
   // become the entry block after we erase PredBB.
-  if (PredBB == &DestBB->getParent()->getEntryBlock())
+  bool ReplacedEntryBB = false;
+  if (PredBB == &DestBB->getParent()->getEntryBlock()) {
     DestBB->moveAfter(PredBB);
+    ReplacedEntryBB = true;
+  }
 
-  if (DT) {
-    BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock();
-    DT->changeImmediateDominator(DestBB, PredBBIDom);
-    DT->eraseNode(PredBB);
+  if (DT && !ReplacedEntryBB) {
+    Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
+    DT->applyUpdates(Updates);
   }
+
   // Nuke BB.
   PredBB->eraseFromParent();
+
+  // The entry block was removed and there is no external interface for the
+  // dominator tree to be notified of this change. In this corner-case we
+  // recalculate the entire tree.
+  if (DT && ReplacedEntryBB)
+    DT->recalculate(*(DestBB->getParent()));
 }
 
 /// CanMergeValues - Return true if we can choose one of these values to use
 /// in place of the other. Note that we will always choose the non-undef
 /// value to keep.
 static bool CanMergeValues(Value *First, Value *Second) {
   return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
 }
static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
   replaceUndefValuesInPhi(PN, IncomingValues);
 }
 
 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
 /// unconditional branch, and contains no instructions other than PHI nodes,
 /// potential side-effect free intrinsics and the branch.  If possible,
 /// eliminate BB by rewriting all the predecessors to branch to the successor
 /// block and return true.  If we can't transform, return false.
-bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) {
+bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
+                                                   DominatorTree *DT) {
   assert(BB != &BB->getParent()->getEntryBlock() &&
          "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
 
   // We can't eliminate infinite loops.
   BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
   if (BB == Succ) return false;
 
   // Check to see if merging these blocks would cause conflicts for any of the
while (isa<PHINode>(*BBI)) {
         }
       }
       ++BBI;
     }
   }
 
   DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
 
+  // Collect all the edges that enter BB, discarding edges to itself and
+  // duplicates. These dominator edges will be redirected to Succ.
+  std::vector<DominatorTree::UpdateType> Updates;
+  if (DT)
+    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+      if (*PI == BB)
+        continue;
+      DominatorTree::UpdateType UT = {DominatorTree::Delete, *PI, BB};
+      if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end()) {
+        Updates.push_back(UT);
+        // Succ cannot dominate itself.
+        if (*PI != Succ)
+          Updates.push_back({DominatorTree::Insert, *PI, Succ});
+      }
+    }
+
   if (isa<PHINode>(Succ->begin())) {
     // If there is more than one pred of succ, and there are PHI nodes in
     // the successor, then we need to add incoming edges for the PHI nodes
     //
     const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
 
     // Loop over all of the PHI nodes in the successor of BB.
     for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
       PN->eraseFromParent();
     }
   }
 
   // If the unconditional branch we replaced contains llvm.loop metadata, we
   // add the metadata to the branch instructions in the predecessors.
   unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop");
   Instruction *TI = BB->getTerminator();
-  if (TI)
+  if (TI) {
     if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
       for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
         BasicBlock *Pred = *PI;
         Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
       }
+    // Replace the terminator instruction with unreachable to ensure the CFG is
+    // consistent. This is necessary for dominance to be correctly calculated.
+    new UnreachableInst(BB->getContext(), TI);
+    TI->eraseFromParent();
+  }
 
   // Everything that jumped to BB now goes to Succ.
   BB->replaceAllUsesWith(Succ);
   if (!Succ->hasName()) Succ->takeName(BB);
+
+  if (DT) {
+    Updates.push_back({DominatorTree::Delete, BB, Succ});
+    DT->applyUpdates(Updates);
+  }
+
   BB->eraseFromParent();              // Delete the old basic block.
   return true;
 }
 
 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
 /// nodes in this block. This doesn't try to be clever about PHI nodes
 /// which differ only in the order of the incoming values, but instcombine
 /// orders them so it usually won't matter.
while (EndInst != &BB->front()) {
     if (!isa<DbgInfoIntrinsic>(Inst))
       ++NumDeadInst;
     Inst->eraseFromParent();
   }
   return NumDeadInst;
 }
 
 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
-                                   bool PreserveLCSSA) {
+                                   bool PreserveLCSSA, DominatorTree *DT) {
   BasicBlock *BB = I->getParent();
+  std::vector<DominatorTree::UpdateType> Updates;
   // Loop over all of the successors, removing BB's entry from any PHI
   // nodes.
-  for (BasicBlock *Successor : successors(BB))
+  for (BasicBlock *Successor : successors(BB)) {
     Successor->removePredecessor(BB, PreserveLCSSA);
-
+    if (DT && BB != Successor) {
+      DominatorTree::UpdateType UT = {DominatorTree::Delete, BB, Successor};
+      if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+        Updates.push_back(UT);
+    }
+  }
   // Insert a call to llvm.trap right before this.  This turns the undefined
   // behavior into a hard fail instead of falling through into random code.
   if (UseLLVMTrap) {
     Function *TrapFn =
       Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
     CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
     CallTrap->setDebugLoc(I->getDebugLoc());
   }
   new UnreachableInst(I->getContext(), I);
 
   // All instructions after this are dead.
   unsigned NumInstrsRemoved = 0;
   BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
   while (BBI != BBE) {
     if (!BBI->use_empty())
       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
     BB->getInstList().erase(BBI++);
     ++NumInstrsRemoved;
   }
+  if (DT)
+    DT->applyUpdates(Updates);
   return NumInstrsRemoved;
 }
 
 /// changeToCall - Convert the specified invoke into a normal call.
-static void changeToCall(InvokeInst *II) {
+static void changeToCall(InvokeInst *II, DominatorTree *DT = nullptr) {
   SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end());
   SmallVector<OperandBundleDef, 1> OpBundles;
   II->getOperandBundlesAsDefs(OpBundles);
   CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,
                                        "", II);
   NewCall->takeName(II);
   NewCall->setCallingConv(II->getCallingConv());
   NewCall->setAttributes(II->getAttributes());
   NewCall->setDebugLoc(II->getDebugLoc());
   II->replaceAllUsesWith(NewCall);
 
   // Follow the call by a branch to the normal destination.
-  BranchInst::Create(II->getNormalDest(), II);
+  BasicBlock *NormalDestBB = II->getNormalDest();
+  BranchInst::Create(NormalDestBB, II);
 
   // Update PHI nodes in the unwind destination
-  II->getUnwindDest()->removePredecessor(II->getParent());
+  BasicBlock *BB = II->getParent();
+  BasicBlock *UnwindDestBB = II->getUnwindDest();
+  UnwindDestBB->removePredecessor(BB);
   II->eraseFromParent();
+  if (DT && BB != UnwindDestBB && NormalDestBB != UnwindDestBB)
+    DT->deleteEdge(BB, UnwindDestBB);
 }
 
 BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                                    BasicBlock *UnwindEdge) {
   BasicBlock *BB = CI->getParent();
 
   // Convert this function call into an invoke instruction.  First, split the
   // basic block.
BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
   CI->replaceAllUsesWith(II);
 
   // Delete the original call
   Split->getInstList().pop_front();
   return Split;
 }
 
 static bool markAliveBlocks(Function &F,
-                            SmallPtrSetImpl<BasicBlock*> &Reachable) {
+                            SmallPtrSetImpl<BasicBlock *> &Reachable,
+                            DominatorTree *DT = nullptr) {
 
   SmallVector<BasicBlock*, 128> Worklist;
   BasicBlock *BB = &F.front();
   Worklist.push_back(BB);
   Reachable.insert(BB);
   bool Changed = false;
   do {
     BB = Worklist.pop_back_val();
 
     // Do a quick scan of the basic block, turning any obviously unreachable
     // instructions into LLVM unreachable insts.  The instruction combining pass
     // canonicalizes unreachable insts into stores to null or undef.
     for (Instruction &I : *BB) {
       // Assumptions that are known to be false are equivalent to unreachable.
       // Also, if the condition is undefined, then we make the choice most
       // beneficial to the optimizer, and choose that to also be unreachable.
       if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
         if (II->getIntrinsicID() == Intrinsic::assume) {
           if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
             // Don't insert a call to llvm.trap right before the unreachable.
-            changeToUnreachable(II, false);
+            changeToUnreachable(II, false, false, DT);
             Changed = true;
             break;
           }
         }
 
         if (II->getIntrinsicID() == Intrinsic::experimental_guard) {
           // A call to the guard intrinsic bails out of the current compilation
           // unit if the predicate passed to it is false.  If the predicate is a
           // constant false, then we know the guard will bail out of the current
           // compile unconditionally, so all code following it is dead.
           //
           // Note: unlike in llvm.assume, it is not "obviously profitable" for
           // guards to treat `undef` as `false` since a guard on `undef` can
           // still be useful for widening.
           if (match(II->getArgOperand(0), m_Zero()))
             if (!isa<UnreachableInst>(II->getNextNode())) {
-              changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/ false);
+              changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/false,
+                                  false, DT);
               Changed = true;
               break;
             }
         }
       }
 
       if (auto *CI = dyn_cast<CallInst>(&I)) {
         Value *Callee = CI->getCalledValue();
         if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
-          changeToUnreachable(CI, /*UseLLVMTrap=*/false);
+          changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DT);
           Changed = true;
           break;
         }
         if (CI->doesNotReturn()) {
           // If we found a call to a no-return function, insert an unreachable
           // instruction after it.  Make sure there isn't *already* one there
           // though.
           if (!isa<UnreachableInst>(CI->getNextNode())) {
             // Don't insert a call to llvm.trap right before the unreachable.
-            changeToUnreachable(CI->getNextNode(), false);
+            changeToUnreachable(CI->getNextNode(), false, false, DT);
             Changed = true;
           }
           break;
         }
       }
 
       // Store to undef and store to null are undefined and used to signal that
       // they should be changed to unreachable by passes that can't modify the
       // CFG.
       if (auto *SI = dyn_cast<StoreInst>(&I)) {
         // Don't touch volatile stores.
         if (SI->isVolatile()) continue;
 
         Value *Ptr = SI->getOperand(1);
 
         if (isa<UndefValue>(Ptr) ||
             (isa<ConstantPointerNull>(Ptr) &&
              SI->getPointerAddressSpace() == 0)) {
-          changeToUnreachable(SI, true);
+          changeToUnreachable(SI, true, false, DT);
           Changed = true;
           break;
         }
       }
     }
 
     TerminatorInst *Terminator = BB->getTerminator();
     if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
       // Turn invokes that call 'nounwind' functions into ordinary calls.
       Value *Callee = II->getCalledValue();
       if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
-        changeToUnreachable(II, true);
+        changeToUnreachable(II, true, false, DT);
         Changed = true;
       } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
         if (II->use_empty() && II->onlyReadsMemory()) {
           // jump to the normal destination branch.
-          BranchInst::Create(II->getNormalDest(), II);
-          II->getUnwindDest()->removePredecessor(II->getParent());
+          BasicBlock *NormalDestBB = II->getNormalDest();
+          BasicBlock *UnwindDestBB = II->getUnwindDest();
+          BranchInst::Create(NormalDestBB, II);
+          UnwindDestBB->removePredecessor(II->getParent());
           II->eraseFromParent();
+          if (DT && BB != UnwindDestBB && NormalDestBB != UnwindDestBB)
+            DT->deleteEdge(BB, UnwindDestBB);
         } else
-          changeToCall(II);
+          changeToCall(II, DT);
         Changed = true;
       }
     } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
       // Remove catchpads which cannot be reached.
       struct CatchPadDenseMapInfo {
         static CatchPadInst *getEmptyKey() {
           return DenseMapInfo<CatchPadInst *>::getEmptyKey();
         }
if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
           CatchSwitch->removeHandler(I);
           --I;
           --E;
           Changed = true;
         }
       }
     }
 
-    Changed |= ConstantFoldTerminator(BB, true);
+    Changed |= ConstantFoldTerminator(BB, true, nullptr, DT);
     for (BasicBlock *Successor : successors(BB))
       if (Reachable.insert(Successor).second)
         Worklist.push_back(Successor);
   } while (!Worklist.empty());
   return Changed;
 }
 
-void llvm::removeUnwindEdge(BasicBlock *BB) {
+void llvm::removeUnwindEdge(BasicBlock *BB, DominatorTree *DT) {
   TerminatorInst *TI = BB->getTerminator();
 
   if (auto *II = dyn_cast<InvokeInst>(TI)) {
-    changeToCall(II);
+    changeToCall(II, DT);
     return;
   }
 
   TerminatorInst *NewTI;
   BasicBlock *UnwindDest;
+  bool DeleteEdge = true;
 
   if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
     NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
     UnwindDest = CRI->getUnwindDest();
   } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
+    UnwindDest = CatchSwitch->getUnwindDest();
     auto *NewCatchSwitch = CatchSwitchInst::Create(
         CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
         CatchSwitch->getName(), CatchSwitch);
-    for (BasicBlock *PadBB : CatchSwitch->handlers())
+    for (BasicBlock *PadBB : CatchSwitch->handlers()) {
       NewCatchSwitch->addHandler(PadBB);
-
+      // Don't delete the DT edge if the Unwind successor is also a handler
+      // successor in the new CatchSwitch.
+      if (PadBB == UnwindDest)
+        DeleteEdge = false;
+    }
     NewTI = NewCatchSwitch;
-    UnwindDest = CatchSwitch->getUnwindDest();
   } else {
     llvm_unreachable("Could not find unwind successor");
   }
 
   NewTI->takeName(TI);
   NewTI->setDebugLoc(TI->getDebugLoc());
   UnwindDest->removePredecessor(BB);
   TI->replaceAllUsesWith(NewTI);
   TI->eraseFromParent();
+  if (DT && BB != UnwindDest && DeleteEdge)
+    DT->deleteEdge(BB, UnwindDest);
 }
 
 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
 /// if they are in a dead cycle.  Return true if a change was made, false
 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
 /// after modifying the CFG.
-bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) {
+bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
+                                   DominatorTree *DT) {
   SmallPtrSet<BasicBlock*, 16> Reachable;
-  bool Changed = markAliveBlocks(F, Reachable);
+  bool Changed = markAliveBlocks(F, Reachable, DT);
+  std::vector<DominatorTree::UpdateType> Updates;
 
   // If there are unreachable blocks in the CFG...
   if (Reachable.size() == F.size())
     return Changed;
 
   assert(Reachable.size() < F.size());
   NumRemoved += F.size()-Reachable.size();
 
+  SmallPtrSet<TerminatorInst *, 4> TIRemoved;
+
   // Loop over all of the basic blocks that are not reachable, dropping all of
   // their internal references...
   for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
     if (Reachable.count(&*BB))
       continue;
 
     for (BasicBlock *Successor : successors(&*BB))
-      if (Reachable.count(Successor))
+      if (Reachable.count(Successor)) {
         Successor->removePredecessor(&*BB);
+        if (DT && &*BB != Successor) {
+          DominatorTree::UpdateType UT = {DominatorTree::Delete, &*BB,
+                                          Successor};
+          if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+            Updates.push_back(UT);
+        }
+      }
+
     if (LVI)
       LVI->eraseBlock(&*BB);
+
+    TerminatorInst *TI = BB->getTerminator();
+    TIRemoved.insert(TI);
+    new UnreachableInst(BB->getContext(), TI);
+
     BB->dropAllReferences();
   }
 
+  // Remove all the terminator instructions after dropping all references. This
+  // keeps the state of the CFG consistent and prevents asserts from circular
+  // use counts in groups of unreachable basic blocks.
+  for (TerminatorInst *TI : TIRemoved)
+    TI->eraseFromParent();
+
+  if (DT)
+    DT->applyUpdates(Updates);
+
   for (Function::iterator I = ++F.begin(); I != F.end();)
     if (!Reachable.count(&*I))
       I = F.getBasicBlockList().erase(I);
     else
       ++I;
 
   return true;
 }

llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll

 ; CHECK-NEXT:    ; LatticeVal for: 'i32 %a' is: overdefined
 ; CHECK-NEXT:    ; LatticeVal for: 'i32 %length' is: overdefined
   br label %loop
 
 ; CHECK-LABEL: backedge:
 ; CHECK-NEXT:     ; LatticeVal for: 'i32 %a' is: overdefined
 ; CHECK-NEXT:     ; LatticeVal for: 'i32 %length' is: overdefined
 ; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, 400>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<399, 400>
 ; CHECK-NEXT:  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 ; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, 401>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%exit' is: constantrange<400, 401>
 ; CHECK-NEXT:  %iv.next = add nsw i32 %iv, 1
 ; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%backedge' is: overdefined
+; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%exit' is: constantrange<0, -1>
 ; CHECK-NEXT:  %cont = icmp slt i32 %iv.next, 400
 ; CHECK-NOT: loop
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   %cnd = icmp sge i32 %iv, 0
   br i1 %cnd, label %backedge, label %exit
 
 backedge:

llvm/test/Transforms/JumpThreading/lvi-tristate.ll

+; RUN: opt -jump-threading -simplifycfg -S < %s | FileCheck %s
+; CHECK-NOT: BB2:
+; CHECK-NOT: BB3:
+; CHECK-NOT: BB4:
+; CHECK-NOT: BB6:
+; CHECK-NOT: BB7:
+; CHECK: entry:
+; CHECK: BB0:
+; CHECK: BB1:
+; CHECK: BB5:
+; CHECK: exit:
+
+declare void @foo() local_unnamed_addr
+
+define fastcc void @test() unnamed_addr {
+entry:
+  %0 = and i32 undef, 1073741823
+  %1 = icmp eq i32 %0, 2
+  br i1 %1, label %BB7, label %BB0
+
+BB0:
+  %2 = icmp eq i32 %0, 3
+  br i1 %2, label %exit, label %BB1
+
+BB1:
+  %3 = icmp eq i32 %0, 5
+  br i1 %3, label %BB2, label %BB3
+
+BB2:
+  tail call void @foo()
+  br label %BB3
+
+BB3:
+  br i1 %2, label %exit, label %BB4
+
+BB4:
+  %4 = icmp eq i32 %0, 4
+  br i1 %4, label %exit, label %BB5
+
+BB5:
+  br i1 %4, label %BB6, label %exit
+
+BB6:
+  br label %exit
+
+BB7:
+  br label %BB0
+
+exit:
+  ret void
+}