[WIP!][DomTreeUpdater/Auto[3]] Convert existing passes and utils to use the Auto UpdateStrategy

[NutshellySima]

Summary

This patch is a work-in-process and I don't intend to commit it. If you are automatically subscribed to this patch, please ignore it.

It converts passes (e.g. CorrelatedValuePropagation/RewriteStatepointsForGC/JumpThreading) and various functions which currently uses the Lzay UpdateStrategy in local.cpp and BasicBlockUtils.cpp to use the new Auto UpdateStrategy.

[NutshellySima]

Close this revision along with D50311.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 /// Simplify a switch instruction by removing cases which can never fire. If the
 /// uselessness of a case could be determined locally then constant propagation
 /// would already have figured it out. Instead, walk the predecessors and
 /// statically evaluate cases based on information available on that edge. Cases
 /// that cannot fire no matter what the incoming edge can safely be removed. If
 /// a case fires on every incoming edge then the entire switch can be removed
 /// and replaced with a branch to the case destination.
 static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI, DominatorTree *DT) {
-  DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Auto);
   Value *Cond = SI->getCondition();
   BasicBlock *BB = SI->getParent();
 
   // If the condition was defined in same block as the switch then LazyValueInfo
   // currently won't say anything useful about it, though in theory it could.
   if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
     return false;
 
for (pred_iterator PI = PB; PI != PE; ++PI) {
       // others then there is nothing we can do - give up.
       if (Value != State) {
         State = LazyValueInfo::Unknown;
         break;
       }
     }
 
     if (State == LazyValueInfo::False) {
+
       // This case never fires - remove it.
       BasicBlock *Succ = CI->getCaseSuccessor();
+      if (SuccessorsCount[Succ] == 1)
+        DTU.isAboutToChange(BB);
       Succ->removePredecessor(BB);
       CI = SI->removeCase(CI);
       CE = SI->case_end();
 
       // The condition can be modified by removePredecessor's PHI simplification
       // logic.
       Cond = SI->getCondition();
 

lib/Transforms/Scalar/JumpThreading.cpp

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();
-  DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Auto);
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = F.hasProfileData();
   if (HasProfileData) {
     LoopInfo LI{DominatorTree(F)};
     BPI.reset(new BranchProbabilityInfo(F, LI, TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }

 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);
-  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Auto);
 
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   if (F.hasProfileData()) {
     LoopInfo LI{DominatorTree(F)};
     BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }
if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {
     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, DTU);
-
       // 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
       // call @exit() // need not transfer execution to successor.
if (isa<UndefValue>(Condition)) {
     std::vector<DominatorTree::UpdateType> Updates;
 
     // Fold the branch/switch.
     TerminatorInst *BBTerm = BB->getTerminator();
     Updates.reserve(BBTerm->getNumSuccessors());
     for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
       if (i == BestSucc) continue;
       BasicBlock *Succ = BBTerm->getSuccessor(i);
+      // Notify DTU about the change of BB.
+      DTU->isAboutToChange(BB);
       Succ->removePredecessor(BB, true);
       Updates.push_back({DominatorTree::Delete, BB, Succ});
     }
 
     LLVM_DEBUG(dbgs() << "  In block '" << BB->getName()
                       << "' folding undef terminator: " << *BBTerm << '\n');
     BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
     BBTerm->eraseFromParent();
bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
 
   // All the rest of our checks depend on the condition being an instruction.
   if (!CondInst) {
     // FIXME: Unify this with code below.
     if (ProcessThreadableEdges(Condition, BB, Preference, Terminator))
       return true;
     return false;
   }
-
   if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) {
     // If we're branching on a conditional, LVI might be able to determine
     // it's value at the branch instruction.  We only handle comparisons
     // against a constant at this time.
     // TODO: This should be extended to handle switches as well.
     BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
     Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1));
     if (CondBr && CondConst) {
       // We should have returned as soon as we turn a conditional branch to
       // unconditional. Because its no longer interesting as far as jump
       // threading is concerned.
       assert(CondBr->isConditional() && "Threading on unconditional terminator");
 
       if (DTU->hasPendingDomTreeUpdates())
         LVI->disableDT();
       else
         LVI->enableDT();
       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;
+        // Notify DTU.
+        DTU->isAboutToChange(BB);
         BasicBlock *ToRemoveSucc = CondBr->getSuccessor(ToRemove);
         ToRemoveSucc->removePredecessor(BB, true);
         BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
         CondBr->eraseFromParent();
         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
bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
 
   return false;
 }
 
 bool JumpThreadingPass::ProcessImpliedCondition(BasicBlock *BB) {
   auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
   if (!BI || !BI->isConditional())
     return false;
-
   Value *Cond = BI->getCondition();
   BasicBlock *CurrentBB = BB;
   BasicBlock *CurrentPred = BB->getSinglePredecessor();
   unsigned Iter = 0;
 
   auto &DL = BB->getModule()->getDataLayout();
 
   while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
     auto *PBI = dyn_cast<BranchInst>(CurrentPred->getTerminator());
     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) {
       BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
       BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
+      DTU->isAboutToChange(BB);
       RemoveSucc->removePredecessor(BB);
       BranchInst::Create(KeepSucc, BI);
       BI->eraseFromParent();
       DTU->deleteEdgeRelaxed(BB, RemoveSucc);
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
-
   return false;
 }
 
 /// Return true if Op is an instruction defined in the given block.
 static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB) {
   if (Instruction *OpInst = dyn_cast<Instruction>(Op))
     if (OpInst->getParent() == BB)
       return true;
bool JumpThreadingPass::ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
   // as a null dest in the PredToDestList).
   SmallPtrSet<BasicBlock*, 16> SeenPreds;
   SmallVector<std::pair<BasicBlock*, BasicBlock*>, 16> PredToDestList;
 
   BasicBlock *OnlyDest = nullptr;
   BasicBlock *MultipleDestSentinel = (BasicBlock*)(intptr_t)~0ULL;
   Constant *OnlyVal = nullptr;
   Constant *MultipleVal = (Constant *)(intptr_t)~0ULL;
-
   unsigned PredWithKnownDest = 0;
   for (const auto &PredValue : PredValues) {
     BasicBlock *Pred = PredValue.second;
     if (!SeenPreds.insert(Pred).second)
       continue;  // Duplicate predecessor entry.
 
     Constant *Val = PredValue.first;
 
bool JumpThreadingPass::ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
   // 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)pred_size(BB)) {
       bool SeenFirstBranchToOnlyDest = false;
       std::vector <DominatorTree::UpdateType> Updates;
       Updates.reserve(BB->getTerminator()->getNumSuccessors() - 1);
+      if (BB->getTerminator()->getNumSuccessors() > 1)
+        DTU->isAboutToChange(BB);
       for (BasicBlock *SuccBB : successors(BB)) {
         if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
           SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
         } else {
           SuccBB->removePredecessor(BB, true); // This is unreachable successor.
           Updates.push_back({DominatorTree::Delete, BB, SuccBB});
         }
       }
 
       // Finally update the terminator.
       TerminatorInst *Term = BB->getTerminator();
       BranchInst::Create(OnlyDest, Term);
       Term->eraseFromParent();
       DTU->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
         // presence of guards and assumes, that have the `Cond` as the use. This
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   BasicBlock *PredBB;
   if (PredBBs.size() == 1)
     PredBB = PredBBs[0];
   else {
     LLVM_DEBUG(dbgs() << "  Factoring out " << PredBBs.size()
                       << " common predecessors.\n");
     PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");
   }
-
   // And finally, do it!
   LLVM_DEBUG(dbgs() << "  Threading edge from '" << PredBB->getName()
                     << "' to '" << SuccBB->getName()
                     << "' with cost: " << JumpThreadCost
                     << ", across block:\n    " << *BB << "\n");
 
   if (DTU->hasPendingDomTreeUpdates())
     LVI->disableDT();
   else
     LVI->enableDT();
   LVI->threadEdge(PredBB, BB, SuccBB);
 
   // We are going to have to map operands from the original BB block to the new
   // copy of the block 'NewBB'.  If there are PHI nodes in BB, evaluate them to
   // account for entry from PredBB.
   DenseMap<Instruction*, Value*> ValueMapping;
 
   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(),
                                          BB->getName()+".thread",
                                          BB->getParent(), BB);
+
   NewBB->moveAfter(PredBB);
 
   // Set the block frequency of NewBB.
   if (HasProfileData) {
     auto NewBBFreq =
         BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
     BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
   }
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   AddPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping);
 
   // Update the terminator of PredBB to jump to NewBB instead of BB.  This
   // eliminates predecessors from BB, which requires 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) {
+      DTU->isAboutToChange(PredBB);
       BB->removePredecessor(PredBB, true);
       PredTerm->setSuccessor(i, NewBB);
     }
 
   // Enqueue required DT updates.
   DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
                      {DominatorTree::Insert, PredBB, NewBB},
                      {DominatorTree::Delete, PredBB, BB}});

 }
 
 /// Create a new basic block that will be the predecessor of BB and successor of
 /// all blocks in Preds. When profile data is available, update the frequency of
 /// this new block.
 BasicBlock *JumpThreadingPass::SplitBlockPreds(BasicBlock *BB,
                                                ArrayRef<BasicBlock *> Preds,
                                                const char *Suffix) {
+  for (auto *Pred : Preds)
+    DTU->isAboutToChange(Pred);
+
   SmallVector<BasicBlock *, 2> NewBBs;
 
   // Collect the frequencies of all predecessors of BB, which will be used to
   // update the edge weight of the result of splitting predecessors.
   DenseMap<BasicBlock *, BlockFrequency> FreqMap;
   if (HasProfileData)
     for (auto Pred : Preds)
       FreqMap.insert(std::make_pair(
           Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
 
   // In the case when BB is a LandingPad block we create 2 new predecessors
   // instead of just one.
   if (BB->isLandingPad()) {
+    for (auto *Pred : predecessors(BB))
+      DTU->isAboutToChange(Pred);
     std::string NewName = std::string(Suffix) + ".split-lp";
     SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs);
   } else {
     NewBBs.push_back(SplitBlockPredecessors(BB, Preds, Suffix));
   }
 
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve((2 * Preds.size()) + NewBBs.size());
bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
   // cause us to transform this into an irreducible loop, don't do this.
   // See the comments above FindLoopHeaders for justifications and caveats.
   if (LoopHeaders.count(BB)) {
     LLVM_DEBUG(dbgs() << "  Not duplicating loop header '" << BB->getName()
                       << "' into predecessor block '" << PredBBs[0]->getName()
                       << "' - it might create an irreducible loop!\n");
     return false;
   }
-
   unsigned DuplicationCost =
       getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
   if (DuplicationCost > BBDupThreshold) {
     LLVM_DEBUG(dbgs() << "  Not duplicating BB '" << BB->getName()
                       << "' - Cost is too high: " << DuplicationCost << "\n");
     return false;
   }
 
   // And finally, do it!  Start by factoring the predecessors if needed.
   std::vector<DominatorTree::UpdateType> Updates;
   BasicBlock *PredBB;
   if (PredBBs.size() == 1)
     PredBB = PredBBs[0];
   else {
     LLVM_DEBUG(dbgs() << "  Factoring out " << PredBBs.size()
                       << " common predecessors.\n");
     PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");
   }
+
   Updates.push_back({DominatorTree::Delete, PredBB, BB});
 
   // Okay, we decided to do this!  Clone all the instructions in BB onto the end
   // of PredBB.
   LLVM_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()) {
+    DTU->isAboutToChange(PredBB);
     BasicBlock *OldPredBB = PredBB;
     PredBB = SplitEdge(OldPredBB, BB);
     Updates.push_back({DominatorTree::Insert, OldPredBB, PredBB});
     Updates.push_back({DominatorTree::Insert, PredBB, BB});
     Updates.push_back({DominatorTree::Delete, OldPredBB, BB});
     OldPredBranch = cast<BranchInst>(PredBB->getTerminator());
   }
+  DTU->isAboutToChange(PredBB);
 
   // 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();
   for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
     ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
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();
   DTU->applyUpdates(Updates);
-
   ++NumDupes;
   return true;
 }
 
 /// TryToUnfoldSelect - Look for blocks of the form
 /// bb1:
 ///   %a = select
 ///   br bb2
for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) {
     // Look if one of the incoming values is a select in the corresponding
     // predecessor.
     if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
       continue;
 
     BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator());
     if (!PredTerm || !PredTerm->isUnconditional())
       continue;
-
     // Now check if one of the select values would allow us to constant fold the
     // terminator in BB. We don't do the transform if both sides fold, those
     // cases will be threaded in any case.
     if (DTU->hasPendingDomTreeUpdates())
       LVI->disableDT();
     else
       LVI->enableDT();
     LazyValueInfo::Tristate LHSFolds =
if ((LHSFolds != LazyValueInfo::Unknown ||
       //  |    v
       //  |  NewBB
       //  |    |
       //  |-----
       //  v
       // BB
       BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold",
                                              BB->getParent(), BB);
+      DTU->isAboutToChange(Pred);
       // Move the unconditional branch to NewBB.
       PredTerm->removeFromParent();
       NewBB->getInstList().insert(NewBB->end(), PredTerm);
       // 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.
for (Use &U : PN->uses()) {
           SI = SelectI;
           break;
         }
       }
     }
 
     if (!SI)
       continue;
+    DTU->isAboutToChange(BB);
     // Expand the select.
     TerminatorInst *Term =
         SplitBlockAndInsertIfThen(SI->getCondition(), SI, false);
     BasicBlock *SplitBB = SI->getParent();
     BasicBlock *NewBB = Term->getParent();
     PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);
     NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
     NewPN->addIncoming(SI->getFalseValue(), BB);
else {
     // False dest is safe if !BranchCond => GuardCond.
     Impl = isImpliedCondition(BranchCond, GuardCond, DL, /* LHSIsTrue */ false);
     if (Impl && *Impl)
       FalseDestIsSafe = true;
   }
 
   if (!TrueDestIsSafe && !FalseDestIsSafe)
     return false;
-
   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;
+  DTU->isAboutToChange(PredGuardedBlock);
+  DTU->isAboutToChange(PredUnguardedBlock);
   // Duplicate all instructions before the guard and the guard itself to the
   // branch where implication is not proved.
   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.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

if (ImmutableCallSite CS = ImmutableCallSite(&I))
       return !callsGCLeafFunction(CS, TLI) && !isStatepoint(CS);
     return false;
   };
 
 
   // Delete any unreachable statepoints so that we don't have unrewritten
   // statepoints surviving this pass.  This makes testing easier and the
   // resulting IR less confusing to human readers.
-  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Auto);
   bool MadeChange = removeUnreachableBlocks(F, nullptr, &DTU);
   // Flush the Dominator Tree.
   DTU.getDomTree();
 
   // Gather all the statepoints which need rewritten.  Be careful to only
   // consider those in reachable code since we need to ask dominance queries
   // when rewriting.  We'll delete the unreachable ones in a moment.
   SmallVector<CallSite, 64> ParsePointNeeded;

lib/Transforms/Utils/BasicBlockUtils.cpp

 
 using namespace llvm;
 
 void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU) {
   assert((pred_begin(BB) == pred_end(BB) ||
          // Can delete self loop.
          BB->getSinglePredecessor() == BB) && "Block is not dead!");
   TerminatorInst *BBTerm = BB->getTerminator();
+  if (DTU)
+    if (BBTerm->getNumSuccessors() > 0)
+      DTU->isAboutToChange(BB);
   std::vector<DominatorTree::UpdateType> Updates;
 
   // Loop through all of our successors and make sure they know that one
   // of their predecessors is going away.
   if (DTU)
     Updates.reserve(BBTerm->getNumSuccessors());
   for (BasicBlock *Succ : BBTerm->successors()) {
     Succ->removePredecessor(BB);

lib/Transforms/Utils/Local.cpp

bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
 
   // Branch - See if we are conditional jumping on constant
   if (auto *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 (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
+      if (DTU)
+        DTU->isAboutToChange(BB);
       // Are we branching on constant?
       // YES.  Change to unconditional branch...
       BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
       BasicBlock *OldDest     = Cond->getZExtValue() ? Dest2 : Dest1;
 
       // 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);
for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
           std::swap(Weights[idx+1], Weights.back());
           Weights.pop_back();
           SI->setMetadata(LLVMContext::MD_prof,
                           MDBuilder(BB->getContext()).
                           createBranchWeights(Weights));
         }
         // Remove this entry.
         BasicBlock *ParentBB = SI->getParent();
+        if (DTU)
+          DTU->isAboutToChange(ParentBB);
         DefaultDest->removePredecessor(ParentBB);
         i = SI->removeCase(i);
         e = SI->case_end();
         if (DTU)
           DTU->deleteEdgeRelaxed(ParentBB, DefaultDest);
         continue;
       }
 
if (TheOnlyDest) {
         Updates.reserve(SI->getNumSuccessors() - 1);
 
       // 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) {
           TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
         } else {
+          if (DTU)
+            DTU->isAboutToChange(BB);
           Succ->removePredecessor(BB);
           if (DTU)
             Updates.push_back({DominatorTree::Delete, BB, Succ});
         }
       }
 
       // Delete the old switch.
       Value *Cond = SI->getCondition();
if (auto *BA =
       Builder.CreateBr(TheOnlyDest);
 
       for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
         if (IBI->getDestination(i) == TheOnlyDest) {
           TheOnlyDest = nullptr;
         } else {
           BasicBlock *ParentBB = IBI->getParent();
           BasicBlock *DestBB = IBI->getDestination(i);
+          if (DTU)
+            DTU->isAboutToChange(ParentBB);
           DestBB->removePredecessor(ParentBB);
           if (DTU)
             Updates.push_back({DominatorTree::Delete, ParentBB, DestBB});
         }
       }
       Value *Address = IBI->getAddress();
       IBI->eraseFromParent();
       if (DeleteDeadConditions)
if (PredBB == &DestBB->getParent()->getEntryBlock())
     ReplaceEntryBB = true;
 
   // DTU updates: Collect all the edges that enter
   // PredBB. These dominator edges will be redirected to DestBB.
   std::vector <DominatorTree::UpdateType> Updates;
 
   if (DTU) {
     Updates.reserve(1 + (2 * pred_size(PredBB)));
+    DTU->isAboutToChange(PredBB);
     Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
     for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) {
+      DTU->isAboutToChange(*I);
       Updates.push_back({DominatorTree::Delete, *I, PredBB});
       // This predecessor of PredBB may already have DestBB as a successor.
       if (llvm::find(successors(*I), DestBB) == succ_end(*I))
         Updates.push_back({DominatorTree::Insert, *I, DestBB});
     }
   }
 
   // Zap anything that took the address of DestBB.  Not doing this will give the
if (!Succ->getSinglePredecessor()) {
     }
   }
 
   LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
 
   std::vector<DominatorTree::UpdateType> Updates;
   if (DTU) {
     Updates.reserve(1 + (2 * pred_size(BB)));
+    DTU->isAboutToChange(BB);
     Updates.push_back({DominatorTree::Delete, BB, Succ});
     // All predecessors of BB will be moved to Succ.
     for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
+      DTU->isAboutToChange(*I);
       Updates.push_back({DominatorTree::Delete, *I, BB});
       // This predecessor of BB may already have Succ as a successor.
       if (llvm::find(successors(*I), Succ) == succ_end(*I))
         Updates.push_back({DominatorTree::Insert, *I, Succ});
     }
   }
 
   if (isa<PHINode>(Succ->begin())) {
unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
   BasicBlock *BB = I->getParent();
   std::vector <DominatorTree::UpdateType> Updates;
 
   // Loop over all of the successors, removing BB's entry from any PHI
   // nodes.
   if (DTU)
     Updates.reserve(BB->getTerminator()->getNumSuccessors());
   for (BasicBlock *Successor : successors(BB)) {
+    if (DTU)
+      DTU->isAboutToChange(BB);
     Successor->removePredecessor(BB, PreserveLCSSA);
     if (DTU)
       Updates.push_back({DominatorTree::Delete, BB, Successor});
   }
   // 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 =
static void changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr) {
 
   // Follow the call by a branch to the normal destination.
   BasicBlock *NormalDestBB = II->getNormalDest();
   BranchInst::Create(NormalDestBB, II);
 
   // Update PHI nodes in the unwind destination
   BasicBlock *BB = II->getParent();
   BasicBlock *UnwindDestBB = II->getUnwindDest();
+  if (DTU)
+    DTU->isAboutToChange(BB);
   UnwindDestBB->removePredecessor(BB);
   II->eraseFromParent();
   if (DTU)
     DTU->deleteEdgeRelaxed(BB, UnwindDestBB);
 }
 
 BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                                    BasicBlock *UnwindEdge) {
if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
         changeToUnreachable(II, true, false, DTU);
         Changed = true;
       } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
         if (II->use_empty() && II->onlyReadsMemory()) {
           // jump to the normal destination branch.
           BasicBlock *NormalDestBB = II->getNormalDest();
           BasicBlock *UnwindDestBB = II->getUnwindDest();
           BranchInst::Create(NormalDestBB, II);
+          if (DTU)
+            DTU->isAboutToChange(BB);
           UnwindDestBB->removePredecessor(II->getParent());
           II->eraseFromParent();
           if (DTU)
             DTU->deleteEdgeRelaxed(BB, UnwindDestBB);
         } else
           changeToCall(II, DTU);
         Changed = true;
       }
bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
   // Loop over all of the basic blocks that are not reachable, dropping all of
   // their internal references. Update DTU and LVI if available.
   std::vector <DominatorTree::UpdateType> Updates;
   for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
     auto *BB = &*I;
     if (Reachable.count(BB))
       continue;
     for (BasicBlock *Successor : successors(BB)) {
+      if (DTU)
+        DTU->isAboutToChange(BB);
       if (Reachable.count(Successor))
         Successor->removePredecessor(BB);
       if (DTU)
         Updates.push_back({DominatorTree::Delete, BB, Successor});
     }
     if (LVI)
       LVI->eraseBlock(BB);
     BB->dropAllReferences();