Index: llvm/include/llvm/Transforms/Scalar/JumpThreading.h =================================================================== --- llvm/include/llvm/Transforms/Scalar/JumpThreading.h +++ llvm/include/llvm/Transforms/Scalar/JumpThreading.h @@ -34,6 +34,7 @@ class BranchInst; class CmpInst; class Constant; +class DominatorTree; class Function; class Instruction; class IntrinsicInst; @@ -77,6 +78,7 @@ TargetLibraryInfo *TLI; LazyValueInfo *LVI; AliasAnalysis *AA; + DominatorTree *DT; std::unique_ptr BFI; std::unique_ptr BPI; bool HasProfileData = false; @@ -107,7 +109,7 @@ // 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 BFI_, std::unique_ptr BPI_); Index: llvm/include/llvm/Transforms/Utils/Local.h =================================================================== --- llvm/include/llvm/Transforms/Utils/Local.h +++ llvm/include/llvm/Transforms/Utils/Local.h @@ -86,7 +86,8 @@ /// 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. @@ -140,7 +141,8 @@ /// /// .. 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 @@ -151,7 +153,8 @@ /// 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 @@ -349,7 +352,8 @@ /// 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 @@ -364,12 +368,13 @@ /// /// \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 /// Index: llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp =================================================================== --- llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -74,6 +74,7 @@ bool runOnFunction(Function &F) override; void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); AU.addRequired(); AU.addPreserved(); } @@ -85,6 +86,7 @@ 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) Index: llvm/lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -131,10 +131,11 @@ bool runOnFunction(Function &F) override; void getAnalysisUsage(AnalysisUsage &AU) const override { - if (PrintLVIAfterJumpThreading) - AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); AU.addRequired(); AU.addRequired(); + AU.addPreserved(); AU.addPreserved(); AU.addRequired(); } @@ -148,6 +149,7 @@ 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) @@ -277,6 +279,9 @@ if (skipFunction(F)) return false; auto TLI = &getAnalysis().getTLI(); + // Get DT analysis before LVI. When LVI is initialized it conditionally adds + // DT if it's available. + auto DT = &getAnalysis().getDomTree(); auto LVI = &getAnalysis().getLVI(); auto AA = &getAnalysis().getAAResults(); std::unique_ptr BFI; @@ -288,12 +293,11 @@ 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().getDomTree(), - dbgs()); + LVI->printLVI(F, *DT, dbgs()); } return Changed; } @@ -301,6 +305,9 @@ PreservedAnalyses JumpThreadingPass::run(Function &F, FunctionAnalysisManager &AM) { auto &TLI = AM.getResult(F); + // Get DT analysis before LVI. When LVI is initialized it conditionally adds + // DT if it's available. + auto &DT = AM.getResult(F); auto &LVI = AM.getResult(F); auto &AA = AM.getResult(F); @@ -313,25 +320,28 @@ 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(); + PA.preserve(); + PA.preserve(); return PA; } bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, AliasAnalysis *AA_, - bool HasProfileData_, + DominatorTree *DT_, bool HasProfileData_, std::unique_ptr BFI_, std::unique_ptr 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 @@ -353,8 +363,7 @@ // 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; @@ -400,7 +409,7 @@ // 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; } } @@ -948,7 +957,7 @@ 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 @@ -1031,18 +1040,27 @@ // successors to branch to. Let GetBestDestForJumpOnUndef decide. if (isa(Condition)) { unsigned BestSucc = GetBestDestForJumpOnUndef(BB); + std::vector 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; } @@ -1053,7 +1071,7 @@ DEBUG(dbgs() << " In block '" << BB->getName() << "' folding terminator: " << *BB->getTerminator() << '\n'); ++NumFolds; - ConstantFoldTerminator(BB, true); + ConstantFoldTerminator(BB, true, nullptr, DT); return true; } @@ -1086,9 +1104,13 @@ 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 @@ -1182,9 +1204,13 @@ Optional 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; @@ -1576,18 +1602,27 @@ if (OnlyDest && OnlyDest != MultipleDestSentinel) { if (PredWithKnownDest == (size_t)std::distance(pred_begin(BB), pred_end(BB))) { + std::vector 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. @@ -1922,7 +1957,6 @@ UsesToRename.push_back(&U); } - // If there are no uses outside the block, we're done with this instruction. if (UsesToRename.empty()) continue; @@ -1951,6 +1985,10 @@ 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. @@ -1977,7 +2015,7 @@ 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. @@ -2147,7 +2185,7 @@ BranchInst *OldPredBranch = dyn_cast(PredBB->getTerminator()); if (!OldPredBranch || !OldPredBranch->isUnconditional()) { - PredBB = SplitEdge(PredBB, BB); + PredBB = SplitEdge(PredBB, BB, DT); OldPredBranch = cast(PredBB->getTerminator()); } @@ -2244,6 +2282,8 @@ // Remove the unconditional branch at the end of the PredBB block. OldPredBranch->eraseFromParent(); + if (BB != PredBB) + DT->deleteEdge(PredBB, BB); ++NumDupes; return true; @@ -2309,6 +2349,7 @@ // 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()); @@ -2316,6 +2357,7 @@ // 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(BI); ++BI) @@ -2393,7 +2435,7 @@ 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); @@ -2485,8 +2527,8 @@ 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(); @@ -2495,17 +2537,28 @@ 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 Index: llvm/lib/Transforms/Utils/Local.cpp =================================================================== --- llvm/lib/Transforms/Utils/Local.cpp +++ llvm/lib/Transforms/Utils/Local.cpp @@ -100,7 +100,8 @@ /// 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); @@ -127,6 +128,8 @@ // 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; } @@ -197,9 +200,17 @@ 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; } @@ -225,19 +236,29 @@ // Insert the new branch. Builder.CreateBr(TheOnlyDest); BasicBlock *BB = SI->getParent(); + BasicBlock *TheOnlyDestCheck = TheOnlyDest; + std::vector 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; @@ -285,17 +306,30 @@ if (BlockAddress *BA = dyn_cast(IBI->getAddress()->stripPointerCasts())) { BasicBlock *TheOnlyDest = BA->getBasicBlock(); + BasicBlock *TheOnlyDestCheck = TheOnlyDest; + std::vector 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); @@ -583,7 +617,8 @@ /// /// .. 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(BB->begin())) return; @@ -606,6 +641,8 @@ // 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 @@ -625,6 +662,23 @@ 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 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()) { @@ -645,16 +699,25 @@ // 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 @@ -861,7 +924,8 @@ /// 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!"); @@ -902,6 +966,22 @@ 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 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(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 @@ -936,16 +1016,27 @@ // 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; } @@ -1427,13 +1518,19 @@ } unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap, - bool PreserveLCSSA) { + bool PreserveLCSSA, DominatorTree *DT) { BasicBlock *BB = I->getParent(); + std::vector 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) { @@ -1453,11 +1550,13 @@ 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 Args(II->arg_begin(), II->arg_end()); SmallVector OpBundles; II->getOperandBundlesAsDefs(OpBundles); @@ -1470,11 +1569,16 @@ 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, @@ -1515,8 +1619,9 @@ } static bool markAliveBlocks(Function &F, - SmallPtrSetImpl &Reachable) { - SmallVector Worklist; + SmallPtrSetImpl &Reachable, + DominatorTree *DT = nullptr) { + SmallVector Worklist; BasicBlock *BB = &F.front(); Worklist.push_back(BB); Reachable.insert(BB); @@ -1535,7 +1640,7 @@ 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; } @@ -1552,7 +1657,8 @@ // still be useful for widening. if (match(II->getArgOperand(0), m_Zero())) if (!isa(II->getNextNode())) { - changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/ false); + changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/false, + false, DT); Changed = true; break; } @@ -1562,7 +1668,7 @@ if (auto *CI = dyn_cast(&I)) { Value *Callee = CI->getCalledValue(); if (isa(Callee) || isa(Callee)) { - changeToUnreachable(CI, /*UseLLVMTrap=*/false); + changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DT); Changed = true; break; } @@ -1572,7 +1678,7 @@ // though. if (!isa(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; @@ -1591,7 +1697,7 @@ if (isa(Ptr) || (isa(Ptr) && SI->getPointerAddressSpace() == 0)) { - changeToUnreachable(SI, true); + changeToUnreachable(SI, true, false, DT); Changed = true; break; } @@ -1603,16 +1709,20 @@ // Turn invokes that call 'nounwind' functions into ordinary calls. Value *Callee = II->getCalledValue(); if (isa(Callee) || isa(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(Terminator)) { @@ -1658,7 +1768,7 @@ } } - Changed |= ConstantFoldTerminator(BB, true); + Changed |= ConstantFoldTerminator(BB, true, nullptr, DT); for (BasicBlock *Successor : successors(BB)) if (Reachable.insert(Successor).second) Worklist.push_back(Successor); @@ -1666,29 +1776,34 @@ return Changed; } -void llvm::removeUnwindEdge(BasicBlock *BB) { +void llvm::removeUnwindEdge(BasicBlock *BB, DominatorTree *DT) { TerminatorInst *TI = BB->getTerminator(); if (auto *II = dyn_cast(TI)) { - changeToCall(II); + changeToCall(II, DT); return; } TerminatorInst *NewTI; BasicBlock *UnwindDest; + bool DeleteEdge = true; if (auto *CRI = dyn_cast(TI)) { NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI); UnwindDest = CRI->getUnwindDest(); } else if (auto *CatchSwitch = dyn_cast(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"); } @@ -1698,15 +1813,19 @@ 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 Reachable; - bool Changed = markAliveBlocks(F, Reachable); + bool Changed = markAliveBlocks(F, Reachable, DT); + std::vector Updates; // If there are unreachable blocks in the CFG... if (Reachable.size() == F.size()) @@ -1715,6 +1834,8 @@ assert(Reachable.size() < F.size()); NumRemoved += F.size()-Reachable.size(); + SmallPtrSet 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) { @@ -1722,13 +1843,35 @@ 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); Index: llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll =================================================================== --- llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll +++ llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll @@ -19,10 +19,13 @@ ; 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: Index: llvm/test/Transforms/JumpThreading/lvi-tristate.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/JumpThreading/lvi-tristate.ll @@ -0,0 +1,51 @@ +; 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 +}