Index: lib/Transforms/Scalar/CorrelatedValuePropagation.cpp =================================================================== --- lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -309,7 +309,7 @@ /// 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(); @@ -361,8 +361,11 @@ } 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(); Index: lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- lib/Transforms/Scalar/JumpThreading.cpp +++ lib/Transforms/Scalar/JumpThreading.cpp @@ -286,7 +286,7 @@ auto DT = &getAnalysis().getDomTree(); auto LVI = &getAnalysis().getLVI(); auto AA = &getAnalysis().getAAResults(); - DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy); + DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Auto); std::unique_ptr BFI; std::unique_ptr BPI; bool HasProfileData = F.hasProfileData(); @@ -313,7 +313,7 @@ auto &DT = AM.getResult(F); auto &LVI = AM.getResult(F); auto &AA = AM.getResult(F); - DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Auto); std::unique_ptr BFI; std::unique_ptr BPI; @@ -996,7 +996,6 @@ 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 @@ -1084,6 +1083,8 @@ 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}); } @@ -1117,7 +1118,6 @@ return true; return false; } - if (CmpInst *CondCmp = dyn_cast(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 @@ -1141,6 +1141,8 @@ 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); @@ -1220,7 +1222,6 @@ auto *BI = dyn_cast(BB->getTerminator()); if (!BI || !BI->isConditional()) return false; - Value *Cond = BI->getCondition(); BasicBlock *CurrentBB = BB; BasicBlock *CurrentPred = BB->getSinglePredecessor(); @@ -1241,6 +1242,7 @@ 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(); @@ -1250,7 +1252,6 @@ CurrentBB = CurrentPred; CurrentPred = CurrentBB->getSinglePredecessor(); } - return false; } @@ -1597,7 +1598,6 @@ 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; @@ -1658,6 +1658,8 @@ bool SeenFirstBranchToOnlyDest = false; std::vector 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. @@ -1672,7 +1674,6 @@ 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(Cond)) { @@ -1942,7 +1943,6 @@ << " common predecessors.\n"); PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm"); } - // And finally, do it! LLVM_DEBUG(dbgs() << " Threading edge from '" << PredBB->getName() << "' to '" << SuccBB->getName() @@ -1963,6 +1963,7 @@ BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+".thread", BB->getParent(), BB); + NewBB->moveAfter(PredBB); // Set the block frequency of NewBB. @@ -2008,6 +2009,7 @@ 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); } @@ -2075,6 +2077,9 @@ BasicBlock *JumpThreadingPass::SplitBlockPreds(BasicBlock *BB, ArrayRef Preds, const char *Suffix) { + for (auto *Pred : Preds) + DTU->isAboutToChange(Pred); + SmallVector NewBBs; // Collect the frequencies of all predecessors of BB, which will be used to @@ -2088,6 +2093,8 @@ // 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 { @@ -2244,7 +2251,6 @@ << "' - it might create an irreducible loop!\n"); return false; } - unsigned DuplicationCost = getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold); if (DuplicationCost > BBDupThreshold) { @@ -2263,6 +2269,7 @@ << " 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 @@ -2277,6 +2284,7 @@ BranchInst *OldPredBranch = dyn_cast(PredBB->getTerminator()); if (!OldPredBranch || !OldPredBranch->isUnconditional()) { + DTU->isAboutToChange(PredBB); BasicBlock *OldPredBB = PredBB; PredBB = SplitEdge(OldPredBB, BB); Updates.push_back({DominatorTree::Insert, OldPredBB, PredBB}); @@ -2284,6 +2292,7 @@ Updates.push_back({DominatorTree::Delete, OldPredBB, BB}); OldPredBranch = cast(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. @@ -2383,7 +2392,6 @@ // Remove the unconditional branch at the end of the PredBB block. OldPredBranch->eraseFromParent(); DTU->applyUpdates(Updates); - ++NumDupes; return true; } @@ -2421,7 +2429,6 @@ BranchInst *PredTerm = dyn_cast(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. @@ -2449,6 +2456,7 @@ // 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); @@ -2536,6 +2544,7 @@ if (!SI) continue; + DTU->isAboutToChange(BB); // Expand the select. TerminatorInst *Term = SplitBlockAndInsertIfThen(SI->getCondition(), SI, false); @@ -2643,7 +2652,6 @@ if (!TrueDestIsSafe && !FalseDestIsSafe) return false; - BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest; BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest; @@ -2652,6 +2660,8 @@ 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( Index: lib/Transforms/Scalar/RewriteStatepointsForGC.cpp =================================================================== --- lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -2535,7 +2535,7 @@ // 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(); Index: lib/Transforms/Utils/BasicBlockUtils.cpp =================================================================== --- lib/Transforms/Utils/BasicBlockUtils.cpp +++ lib/Transforms/Utils/BasicBlockUtils.cpp @@ -52,6 +52,9 @@ // 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 Updates; // Loop through all of our successors and make sure they know that one Index: lib/Transforms/Utils/Local.cpp =================================================================== --- lib/Transforms/Utils/Local.cpp +++ lib/Transforms/Utils/Local.cpp @@ -114,6 +114,8 @@ BasicBlock *Dest2 = BI->getSuccessor(1); if (auto *Cond = dyn_cast(BI->getCondition())) { + if (DTU) + DTU->isAboutToChange(BB); // Are we branching on constant? // YES. Change to unconditional branch... BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; @@ -199,6 +201,8 @@ } // Remove this entry. BasicBlock *ParentBB = SI->getParent(); + if (DTU) + DTU->isAboutToChange(ParentBB); DefaultDest->removePredecessor(ParentBB); i = SI->removeCase(i); e = SI->case_end(); @@ -239,6 +243,8 @@ 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}); @@ -310,6 +316,8 @@ } 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}); @@ -683,8 +691,10 @@ 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)) @@ -989,9 +999,11 @@ std::vector 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)) @@ -1918,6 +1930,8 @@ 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}); @@ -1966,6 +1980,8 @@ // 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) @@ -2112,6 +2128,8 @@ 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) @@ -2231,6 +2249,8 @@ if (Reachable.count(BB)) continue; for (BasicBlock *Successor : successors(BB)) { + if (DTU) + DTU->isAboutToChange(BB); if (Reachable.count(Successor)) Successor->removePredecessor(BB); if (DTU)