From 0a51ec29c91f4e3df7b831f6bbc7e933d138dbf6 Mon Sep 17 00:00:00 2001 From: Daniel Jasper Date: Sat, 30 Sep 2017 11:57:19 +0000 Subject: [PATCH] Revert r314435: "[JumpThreading] Preserve DT and LVI across the pass" Causes a segfault on a builtbot (and in our internal bootstrapping of Clang). See Eli's response on the commit thread. llvm-svn: 314589 --- .../include/llvm/Transforms/Scalar/JumpThreading.h | 4 +- llvm/include/llvm/Transforms/Utils/Local.h | 17 +- .../Scalar/CorrelatedValuePropagation.cpp | 2 - llvm/lib/Transforms/Scalar/JumpThreading.cpp | 109 +++-------- llvm/lib/Transforms/Utils/Local.cpp | 207 ++++----------------- .../LazyValueAnalysis/lvi-after-jumpthreading.ll | 3 - 6 files changed, 72 insertions(+), 270 deletions(-) diff --git a/llvm/include/llvm/Transforms/Scalar/JumpThreading.h b/llvm/include/llvm/Transforms/Scalar/JumpThreading.h index 4308e71..a946671 100644 --- a/llvm/include/llvm/Transforms/Scalar/JumpThreading.h +++ b/llvm/include/llvm/Transforms/Scalar/JumpThreading.h @@ -34,7 +34,6 @@ class BinaryOperator; class BranchInst; class CmpInst; class Constant; -class DominatorTree; class Function; class Instruction; class IntrinsicInst; @@ -78,7 +77,6 @@ class JumpThreadingPass : public PassInfoMixin { TargetLibraryInfo *TLI; LazyValueInfo *LVI; AliasAnalysis *AA; - DominatorTree *DT; std::unique_ptr BFI; std::unique_ptr BPI; bool HasProfileData = false; @@ -109,7 +107,7 @@ public: // Glue for old PM. bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, - AliasAnalysis *AA_, DominatorTree *DT_, bool HasProfileData_, + AliasAnalysis *AA_, bool HasProfileData_, std::unique_ptr BFI_, std::unique_ptr BPI_); diff --git a/llvm/include/llvm/Transforms/Utils/Local.h b/llvm/include/llvm/Transforms/Utils/Local.h index 4144a84..b445bbd 100644 --- a/llvm/include/llvm/Transforms/Utils/Local.h +++ b/llvm/include/llvm/Transforms/Utils/Local.h @@ -79,8 +79,7 @@ struct SimplifyCFGOptions { /// conditions and indirectbr addresses this might make dead if /// DeleteDeadConditions is true. bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, - const TargetLibraryInfo *TLI = nullptr, - DominatorTree *DT = nullptr); + const TargetLibraryInfo *TLI = nullptr); //===----------------------------------------------------------------------===// // Local dead code elimination. @@ -134,8 +133,7 @@ bool SimplifyInstructionsInBlock(BasicBlock *BB, /// /// .. and delete the predecessor corresponding to the '1', this will attempt to /// recursively fold the 'and' to 0. -void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, - DominatorTree *DT = nullptr); +void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred); /// 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 @@ -146,8 +144,7 @@ void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr); /// 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, - DominatorTree *DT = nullptr); +bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); /// 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 @@ -345,8 +342,7 @@ 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, - DominatorTree *DT = nullptr); + bool PreserveLCSSA = false); /// Convert the CallInst to InvokeInst with the specified unwind edge basic /// block. This also splits the basic block where CI is located, because @@ -361,13 +357,12 @@ BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI, /// /// \param BB Block whose terminator will be replaced. Its terminator must /// have an unwind successor. -void removeUnwindEdge(BasicBlock *BB, DominatorTree *DT = nullptr); +void removeUnwindEdge(BasicBlock *BB); /// 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, - DominatorTree *DT = nullptr); +bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr); /// Combine the metadata of two instructions so that K can replace J /// diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp index 99ba50a..2815778 100644 --- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -55,7 +55,6 @@ namespace { bool runOnFunction(Function &F) override; void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); AU.addRequired(); AU.addPreserved(); } @@ -65,7 +64,6 @@ namespace { 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) diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp index 5d94eb2..33afc20 100644 --- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -131,11 +131,10 @@ namespace { bool runOnFunction(Function &F) override; void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); - AU.addPreserved(); + if (PrintLVIAfterJumpThreading) + AU.addRequired(); AU.addRequired(); AU.addRequired(); - AU.addPreserved(); AU.addPreserved(); AU.addRequired(); } @@ -149,7 +148,6 @@ 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) @@ -279,9 +277,6 @@ bool JumpThreading::runOnFunction(Function &F) { 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; @@ -293,11 +288,12 @@ bool JumpThreading::runOnFunction(Function &F) { BFI.reset(new BlockFrequencyInfo(F, *BPI, LI)); } - bool Changed = Impl.runImpl(F, TLI, LVI, AA, DT, HasProfileData, - std::move(BFI), std::move(BPI)); + bool Changed = Impl.runImpl(F, TLI, LVI, AA, HasProfileData, std::move(BFI), + std::move(BPI)); if (PrintLVIAfterJumpThreading) { dbgs() << "LVI for function '" << F.getName() << "':\n"; - LVI->printLVI(F, *DT, dbgs()); + LVI->printLVI(F, getAnalysis().getDomTree(), + dbgs()); } return Changed; } @@ -305,9 +301,6 @@ bool JumpThreading::runOnFunction(Function &F) { 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); @@ -320,28 +313,25 @@ PreservedAnalyses JumpThreadingPass::run(Function &F, BFI.reset(new BlockFrequencyInfo(F, *BPI, LI)); } - bool Changed = runImpl(F, &TLI, &LVI, &AA, &DT, HasProfileData, - std::move(BFI), std::move(BPI)); + bool Changed = runImpl(F, &TLI, &LVI, &AA, 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_, - DominatorTree *DT_, bool HasProfileData_, + 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 @@ -363,7 +353,8 @@ bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_, // 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, DT); + EverChanged |= removeUnreachableBlocks(F, LVI); + FindLoopHeaders(F); bool Changed; @@ -409,7 +400,7 @@ bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_, // awesome, but it allows us to use AssertingVH to prevent nasty // dangling pointer issues within LazyValueInfo. LVI->eraseBlock(BB); - if (TryToSimplifyUncondBranchFromEmptyBlock(BB, DT)) + if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) Changed = true; } } @@ -957,7 +948,7 @@ bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) { LoopHeaders.insert(BB); LVI->eraseBlock(SinglePred); - MergeBasicBlockIntoOnlyPred(BB, DT); + MergeBasicBlockIntoOnlyPred(BB); // 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 @@ -1040,27 +1031,18 @@ bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) { // 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; - 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); + BBTerm->getSuccessor(i)->removePredecessor(BB, true); } DEBUG(dbgs() << " In block '" << BB->getName() << "' folding undef terminator: " << *BBTerm << '\n'); BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm); BBTerm->eraseFromParent(); - DT->applyUpdates(Updates); return true; } @@ -1071,7 +1053,7 @@ bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) { DEBUG(dbgs() << " In block '" << BB->getName() << "' folding terminator: " << *BB->getTerminator() << '\n'); ++NumFolds; - ConstantFoldTerminator(BB, true, nullptr, DT); + ConstantFoldTerminator(BB, true); return true; } @@ -1104,12 +1086,9 @@ bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) { if (Ret != LazyValueInfo::Unknown) { unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0; unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1; - BasicBlock *ToRemoveSucc = CondBr->getSuccessor(ToRemove); - ToRemoveSucc->removePredecessor(BB, true); + CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true); BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr); CondBr->eraseFromParent(); - if (BB != ToRemoveSucc) - DT->deleteEdge(BB, ToRemoveSucc); if (CondCmp->use_empty()) CondCmp->eraseFromParent(); // We can safely replace *some* uses of the CondInst if it has @@ -1203,12 +1182,9 @@ bool JumpThreadingPass::ProcessImpliedCondition(BasicBlock *BB) { Optional Implication = isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue); if (Implication) { - BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0); - RemoveSucc->removePredecessor(BB); + BI->getSuccessor(*Implication ? 1 : 0)->removePredecessor(BB); BranchInst::Create(BI->getSuccessor(*Implication ? 0 : 1), BI); BI->eraseFromParent(); - if (BB != RemoveSucc) - DT->deleteEdge(BB, RemoveSucc); return true; } CurrentBB = CurrentPred; @@ -1600,27 +1576,18 @@ bool JumpThreadingPass::ProcessThreadableEdges(Value *Cond, BasicBlock *BB, 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. @@ -1955,6 +1922,7 @@ bool JumpThreadingPass::ThreadEdge(BasicBlock *BB, UsesToRename.push_back(&U); } + // If there are no uses outside the block, we're done with this instruction. if (UsesToRename.empty()) continue; @@ -1983,10 +1951,6 @@ bool JumpThreadingPass::ThreadEdge(BasicBlock *BB, 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. @@ -2013,7 +1977,7 @@ BasicBlock *JumpThreadingPass::SplitBlockPreds(BasicBlock *BB, for (auto Pred : Preds) PredBBFreq += BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB); - BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix, DT); + BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix); // Set the block frequency of the newly created PredBB, which is the sum of // frequencies of Preds. @@ -2183,7 +2147,7 @@ bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred( BranchInst *OldPredBranch = dyn_cast(PredBB->getTerminator()); if (!OldPredBranch || !OldPredBranch->isUnconditional()) { - PredBB = SplitEdge(PredBB, BB, DT); + PredBB = SplitEdge(PredBB, BB); OldPredBranch = cast(PredBB->getTerminator()); } @@ -2280,8 +2244,6 @@ bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred( // Remove the unconditional branch at the end of the PredBB block. OldPredBranch->eraseFromParent(); - if (BB != PredBB) - DT->deleteEdge(PredBB, BB); ++NumDupes; return true; @@ -2347,7 +2309,6 @@ bool JumpThreadingPass::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *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()); @@ -2355,7 +2316,6 @@ bool JumpThreadingPass::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) { // 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) @@ -2433,7 +2393,7 @@ bool JumpThreadingPass::TryToUnfoldSelectInCurrBB(BasicBlock *BB) { continue; // Expand the select. TerminatorInst *Term = - SplitBlockAndInsertIfThen(SI->getCondition(), SI, false, nullptr, DT); + SplitBlockAndInsertIfThen(SI->getCondition(), SI, false); PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI); NewPN->addIncoming(SI->getTrueValue(), Term->getParent()); NewPN->addIncoming(SI->getFalseValue(), BB); @@ -2525,8 +2485,8 @@ bool JumpThreadingPass::ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, if (!TrueDestIsSafe && !FalseDestIsSafe) return false; - BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest; - BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest; + BasicBlock *UnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest; + BasicBlock *GuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest; ValueToValueMapTy UnguardedMapping, GuardedMapping; Instruction *AfterGuard = Guard->getNextNode(); @@ -2535,28 +2495,17 @@ bool JumpThreadingPass::ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, return false; // 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); + GuardedBlock = DuplicateInstructionsInSplitBetween( + BB, GuardedBlock, 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. - BasicBlock *UnguardedBlock = DuplicateInstructionsInSplitBetween( - BB, PredUnguardedBlock, Guard, UnguardedMapping); + UnguardedBlock = DuplicateInstructionsInSplitBetween(BB, UnguardedBlock, + 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 diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp index 8b580f5..21412dc 100644 --- a/llvm/lib/Transforms/Utils/Local.cpp +++ b/llvm/lib/Transforms/Utils/Local.cpp @@ -68,8 +68,7 @@ STATISTIC(NumRemoved, "Number of unreachable basic blocks removed"); /// conditions and indirectbr addresses this might make dead if /// DeleteDeadConditions is true. bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, - const TargetLibraryInfo *TLI, - DominatorTree *DT) { + const TargetLibraryInfo *TLI) { TerminatorInst *T = BB->getTerminator(); IRBuilder<> Builder(T); @@ -96,8 +95,6 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, // 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; } @@ -168,17 +165,9 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, createBranchWeights(Weights)); } // Remove this entry. - BasicBlock *ParentBB = SI->getParent(); - DefaultDest->removePredecessor(ParentBB); + DefaultDest->removePredecessor(SI->getParent()); 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; } @@ -204,29 +193,19 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, // 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 && !Updates.empty()) - DT->applyUpdates(Updates); if (DeleteDeadConditions) RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); return true; @@ -274,30 +253,17 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, 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 { - 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); - } - } + else + IBI->getDestination(i)->removePredecessor(IBI->getParent()); } Value *Address = IBI->getAddress(); IBI->eraseFromParent(); - if (DT && !Updates.empty()) - DT->applyUpdates(Updates); if (DeleteDeadConditions) RecursivelyDeleteTriviallyDeadInstructions(Address, TLI); @@ -587,8 +553,7 @@ bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, /// /// .. 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, - DominatorTree *DT) { +void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) { // This only adjusts blocks with PHI nodes. if (!isa(BB->begin())) return; @@ -611,8 +576,6 @@ void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, // of the block. if (PhiIt != OldPhiIt) PhiIt = &BB->front(); } - if (DT && BB != Pred) - DT->deleteEdge(Pred, BB); } @@ -634,23 +597,6 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { 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()) { @@ -671,25 +617,16 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { // If the PredBB is the entry block of the function, move DestBB up to // become the entry block after we erase PredBB. - bool ReplacedEntryBB = false; - if (PredBB == &DestBB->getParent()->getEntryBlock()) { + if (PredBB == &DestBB->getParent()->getEntryBlock()) DestBB->moveAfter(PredBB); - ReplacedEntryBB = true; - } - if (DT && !ReplacedEntryBB) { - Updates.push_back({DominatorTree::Delete, PredBB, DestBB}); - DT->applyUpdates(Updates); + if (DT) { + BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); + DT->changeImmediateDominator(DestBB, PredBBIDom); + DT->eraseNode(PredBB); } - // 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 @@ -897,8 +834,7 @@ static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, /// 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, - DominatorTree *DT) { +bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { assert(BB != &BB->getParent()->getEntryBlock() && "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); @@ -939,20 +875,6 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 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); - 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 @@ -987,27 +909,16 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, // 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; } @@ -1488,19 +1399,13 @@ unsigned llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) { } unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap, - bool PreserveLCSSA, DominatorTree *DT) { + bool PreserveLCSSA) { 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) { @@ -1520,13 +1425,11 @@ unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap, BB->getInstList().erase(BBI++); ++NumInstrsRemoved; } - if (DT && !Updates.empty()) - DT->applyUpdates(Updates); return NumInstrsRemoved; } /// changeToCall - Convert the specified invoke into a normal call. -static void changeToCall(InvokeInst *II, DominatorTree *DT = nullptr) { +static void changeToCall(InvokeInst *II) { SmallVector Args(II->arg_begin(), II->arg_end()); SmallVector OpBundles; II->getOperandBundlesAsDefs(OpBundles); @@ -1539,16 +1442,11 @@ static void changeToCall(InvokeInst *II, DominatorTree *DT = nullptr) { II->replaceAllUsesWith(NewCall); // Follow the call by a branch to the normal destination. - BasicBlock *NormalDestBB = II->getNormalDest(); - BranchInst::Create(NormalDestBB, II); + BranchInst::Create(II->getNormalDest(), II); // Update PHI nodes in the unwind destination - BasicBlock *BB = II->getParent(); - BasicBlock *UnwindDestBB = II->getUnwindDest(); - UnwindDestBB->removePredecessor(BB); + II->getUnwindDest()->removePredecessor(II->getParent()); II->eraseFromParent(); - if (DT && BB != UnwindDestBB && NormalDestBB != UnwindDestBB) - DT->deleteEdge(BB, UnwindDestBB); } BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, @@ -1589,8 +1487,7 @@ BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, } static bool markAliveBlocks(Function &F, - SmallPtrSetImpl &Reachable, - DominatorTree *DT = nullptr) { + SmallPtrSetImpl &Reachable) { SmallVector Worklist; BasicBlock *BB = &F.front(); @@ -1611,7 +1508,7 @@ static bool markAliveBlocks(Function &F, 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, false, DT); + changeToUnreachable(II, false); Changed = true; break; } @@ -1628,8 +1525,7 @@ static bool markAliveBlocks(Function &F, // still be useful for widening. if (match(II->getArgOperand(0), m_Zero())) if (!isa(II->getNextNode())) { - changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/false, - false, DT); + changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/ false); Changed = true; break; } @@ -1639,7 +1535,7 @@ static bool markAliveBlocks(Function &F, if (auto *CI = dyn_cast(&I)) { Value *Callee = CI->getCalledValue(); if (isa(Callee) || isa(Callee)) { - changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DT); + changeToUnreachable(CI, /*UseLLVMTrap=*/false); Changed = true; break; } @@ -1649,7 +1545,7 @@ static bool markAliveBlocks(Function &F, // though. if (!isa(CI->getNextNode())) { // Don't insert a call to llvm.trap right before the unreachable. - changeToUnreachable(CI->getNextNode(), false, false, DT); + changeToUnreachable(CI->getNextNode(), false); Changed = true; } break; @@ -1668,7 +1564,7 @@ static bool markAliveBlocks(Function &F, if (isa(Ptr) || (isa(Ptr) && SI->getPointerAddressSpace() == 0)) { - changeToUnreachable(SI, true, false, DT); + changeToUnreachable(SI, true); Changed = true; break; } @@ -1680,19 +1576,16 @@ static bool markAliveBlocks(Function &F, // Turn invokes that call 'nounwind' functions into ordinary calls. Value *Callee = II->getCalledValue(); if (isa(Callee) || isa(Callee)) { - changeToUnreachable(II, true, false, DT); + changeToUnreachable(II, true); Changed = true; } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { if (II->use_empty() && II->onlyReadsMemory()) { // jump to the normal destination branch. - BasicBlock *UnwindDestBB = II->getUnwindDest(); BranchInst::Create(II->getNormalDest(), II); - UnwindDestBB->removePredecessor(II->getParent()); + II->getUnwindDest()->removePredecessor(II->getParent()); II->eraseFromParent(); - if (DT && BB != UnwindDestBB) - DT->deleteEdge(BB, UnwindDestBB); } else - changeToCall(II, DT); + changeToCall(II); Changed = true; } } else if (auto *CatchSwitch = dyn_cast(Terminator)) { @@ -1735,7 +1628,7 @@ static bool markAliveBlocks(Function &F, } } - Changed |= ConstantFoldTerminator(BB, true, nullptr, DT); + Changed |= ConstantFoldTerminator(BB, true); for (BasicBlock *Successor : successors(BB)) if (Reachable.insert(Successor).second) Worklist.push_back(Successor); @@ -1743,11 +1636,11 @@ static bool markAliveBlocks(Function &F, return Changed; } -void llvm::removeUnwindEdge(BasicBlock *BB, DominatorTree *DT) { +void llvm::removeUnwindEdge(BasicBlock *BB) { TerminatorInst *TI = BB->getTerminator(); if (auto *II = dyn_cast(TI)) { - changeToCall(II, DT); + changeToCall(II); return; } @@ -1775,19 +1668,15 @@ void llvm::removeUnwindEdge(BasicBlock *BB, DominatorTree *DT) { UnwindDest->removePredecessor(BB); TI->replaceAllUsesWith(NewTI); TI->eraseFromParent(); - if (DT && BB != UnwindDest) - 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, - DominatorTree *DT) { +bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) { SmallPtrSet Reachable; - bool Changed = markAliveBlocks(F, Reachable, DT); - std::vector Updates; + bool Changed = markAliveBlocks(F, Reachable); // If there are unreachable blocks in the CFG... if (Reachable.size() == F.size()) @@ -1796,8 +1685,6 @@ bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI, 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) { @@ -1805,35 +1692,13 @@ bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI, 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 && !Updates.empty()) - DT->applyUpdates(Updates); - for (Function::iterator I = ++F.begin(); I != F.end();) if (!Reachable.count(&*I)) I = F.getBasicBlockList().erase(I); diff --git a/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll b/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll index 27cd226..41bb8c9 100644 --- a/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll +++ b/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll @@ -19,13 +19,10 @@ entry: ; 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: -- 2.7.4