Index: llvm/include/llvm/IR/DeferredDominance.h =================================================================== --- /dev/null +++ llvm/include/llvm/IR/DeferredDominance.h @@ -0,0 +1,108 @@ +//===- DeferredDominance.h - Deferred Dominator/Post-Dominators -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the DeferredDominance class, which provides deferred +// updates to Dominators (and optionally Post-Dominators). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_IR_DEFERREDDOMINANCE_H +#define LLVM_IR_DEFERREDDOMINANCE_H + +#include "llvm/ADT/SmallSet.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" + +namespace llvm { + +class DeferredDominance { +public: + DeferredDominance(DominatorTree *DT_) : DT(DT_) {} + + void applyUpdates(ArrayRef Updates) { + for (auto U : Updates) + applyUpdate(U); + } + + void insertEdge(BasicBlock *From, BasicBlock *To) { + applyUpdate({DominatorTree::Insert, From, To}); + } + + void deleteEdge(BasicBlock *From, BasicBlock *To) { + applyUpdate({DominatorTree::Delete, From, To}); + } + + void deleteBB(BasicBlock *DelBB) { + assert(DelBB && "Invalid push_back of nullptr DelBB."); + assert(pred_empty(DelBB) && "DelBB has one or more predecessors."); + // DelBB is unreachable and all values need to be dead. + while (!DelBB->empty()) { + Instruction &I = DelBB->back(); + // Replace used instructions with an arbitrary value (undef). + if (!I.use_empty()) + I.replaceAllUsesWith(llvm::UndefValue::get(I.getType())); + DelBB->getInstList().pop_back(); + } + new UnreachableInst(DelBB->getContext(), DelBB); + PendDelBB.insert(DelBB); + } + + bool pendingDelBB(BasicBlock *DelBB) { + if (PendDelBB.empty()) + return false; + return PendDelBB.count(DelBB) != 0; + } + + DominatorTree *flush() { + // Updates to DT must happen before blocks are deleted below. Otherwise the + // DT traversal will encounter badref blocks and assert. + if (!PendDom.empty()) { + DT->applyUpdates(PendDom); + PendDom.clear(); + } + flushDelBB(); + return DT; + } + + void recalculate(Function &F) { + // flushDelBB must be flushed before the recalculation. The state of the CFG + // must be consistent before the DT traversal algorithm determines the + // actual DT. + if (flushDelBB() || !PendDom.empty()) { + DT->recalculate(F); + PendDom.clear(); + } + } + + void dump(); + +private: + DominatorTree *DT; + std::vector PendDom; + SmallPtrSet PendDelBB; + + void applyUpdate(DominatorTree::UpdateType UT) { + assert(UT.getFrom() != UT.getTo() && "Cannot dominate self."); + PendDom.push_back(UT); + } + + bool flushDelBB() { + if (PendDelBB.empty()) + return false; + for (auto *BB : PendDelBB) + BB->eraseFromParent(); + PendDelBB.clear(); + return true; + } +}; + +} // end namespace llvm + +#endif // LLVM_IR_DEFERREDDOMINANCE_H Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -1206,7 +1206,6 @@ Result.reserve(Operations.size()); for (auto &Op : Operations) { const int NumInsertions = Op.second; - assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!"); if (NumInsertions == 0) continue; const UpdateKind UK = NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete; 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 DeferredDominance; class Function; class Instruction; class IntrinsicInst; @@ -77,6 +78,7 @@ TargetLibraryInfo *TLI; LazyValueInfo *LVI; AliasAnalysis *AA; + DeferredDominance *DDT; std::unique_ptr BFI; std::unique_ptr BPI; bool HasProfileData = false; @@ -107,8 +109,8 @@ // Glue for old PM. bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, - AliasAnalysis *AA_, bool HasProfileData_, - std::unique_ptr BFI_, + AliasAnalysis *AA_, DeferredDominance *DDT_, + bool HasProfileData_, std::unique_ptr BFI_, std::unique_ptr BPI_); PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); Index: llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h =================================================================== --- llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -25,6 +25,7 @@ namespace llvm { +class DeferredDominance; class DominatorTree; class Function; class Instruction; @@ -36,7 +37,7 @@ class Value; /// Delete the specified block, which must have no predecessors. -void DeleteDeadBlock(BasicBlock *BB); +void DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT = nullptr); /// We know that BB has one predecessor. If there are any single-entry PHI nodes /// in it, fold them away. This handles the case when all entries to the PHI Index: llvm/include/llvm/Transforms/Utils/Local.h =================================================================== --- llvm/include/llvm/Transforms/Utils/Local.h +++ llvm/include/llvm/Transforms/Utils/Local.h @@ -24,6 +24,7 @@ #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" +#include "llvm/IR/DeferredDominance.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/Operator.h" @@ -109,7 +110,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, + DeferredDominance *DDT = nullptr); //===----------------------------------------------------------------------===// // Local dead code elimination. @@ -163,18 +165,21 @@ /// /// .. 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, + DeferredDominance *DDT = nullptr); /// BB is a block with one predecessor and its predecessor is known to have one /// successor (BB!). Eliminate the edge between them, moving the instructions in /// the predecessor into BB. This deletes the predecessor block. -void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr); +void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr, + DeferredDominance *DDT = nullptr); /// BB is known to contain an unconditional branch, and contains no instructions /// other than PHI nodes, potential debug intrinsics and the branch. If /// possible, eliminate BB by rewriting all the predecessors to branch to the /// successor block and return true. If we can't transform, return false. -bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); +bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, + DeferredDominance *DDT = 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 @@ -372,7 +377,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, + DeferredDominance *DDT = nullptr); /// Convert the CallInst to InvokeInst with the specified unwind edge basic /// block. This also splits the basic block where CI is located, because @@ -387,12 +393,13 @@ /// /// \param BB Block whose terminator will be replaced. Its terminator must /// have an unwind successor. -void removeUnwindEdge(BasicBlock *BB); +void removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT = 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, + DeferredDominance *DDT = nullptr); /// Combine the metadata of two instructions so that K can replace J /// Index: llvm/lib/IR/Dominators.cpp =================================================================== --- llvm/lib/IR/Dominators.cpp +++ llvm/lib/IR/Dominators.cpp @@ -18,6 +18,7 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/IR/CFG.h" +#include "llvm/IR/DeferredDominance.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/PassManager.h" #include "llvm/Support/CommandLine.h" @@ -388,3 +389,45 @@ DT.print(OS); } +void DeferredDominance::dump() { + raw_ostream &OS = llvm::outs(); + OS << "PendDom:\n"; + int I = 0; + for (auto U : PendDom) { + OS << " " << I << " : "; + if (U.getKind() == DominatorTree::Insert) + OS << "Insert, "; + else + OS << "Delete, "; + BasicBlock *From = U.getFrom(); + if (From) { + auto S = From->getName(); + if (!From->hasName()) + S = "(no name)"; + OS << S << "(" << From << "), "; + } else { + OS << "(badref), "; + } + BasicBlock *To = U.getTo(); + if (To) { + auto S = To->getName(); + if (!To->hasName()) + S = "(no_name)"; + OS << S << "(" << To << ")\n"; + } else { + OS << "(badref)\n"; + } + ++I; + } + OS << "PendDelBB:\n"; + I = 0; + for (auto BB : PendDelBB) { + OS << " " << I << " : "; + if (BB->hasName()) + OS << BB->getName() << "("; + else + OS << "(no_name)("; + OS << BB << ")\n"; + ++I; + } +} Index: llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp =================================================================== --- llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -77,6 +77,7 @@ bool runOnFunction(Function &F) override; void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); AU.addRequired(); AU.addPreserved(); } @@ -88,6 +89,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 @@ -37,6 +37,7 @@ #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" +#include "llvm/IR/DeferredDominance.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstrTypes.h" @@ -131,10 +132,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 +150,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) @@ -278,8 +281,12 @@ 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(); + DeferredDominance *DDT = new DeferredDominance(DT); std::unique_ptr BFI; std::unique_ptr BPI; bool HasProfileData = F.getEntryCount().hasValue(); @@ -289,12 +296,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, DDT, 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; } @@ -302,8 +308,12 @@ 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); + DeferredDominance *DDT = new DeferredDominance(&DT); std::unique_ptr BFI; std::unique_ptr BPI; @@ -314,25 +324,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, DDT, 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_, + DeferredDominance *DDT_, 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_; + DDT = DDT_; BFI.reset(); BPI.reset(); // When profile data is available, we need to update edge weights after @@ -354,8 +367,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, DDT); FindLoopHeaders(F); bool Changed; @@ -369,6 +381,10 @@ ++I; + // Don't thread branches over a block that's slated for deletion. + if (DDT->pendingDelBB(BB)) + continue; + // If the block is trivially dead, zap it. This eliminates the successor // edges which simplifies the CFG. if (pred_empty(BB) && @@ -377,7 +393,7 @@ << "' with terminator: " << *BB->getTerminator() << '\n'); LoopHeaders.erase(BB); LVI->eraseBlock(BB); - DeleteDeadBlock(BB); + DeleteDeadBlock(BB, DDT); Changed = true; continue; } @@ -401,7 +417,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, DDT)) Changed = true; } } @@ -409,6 +425,7 @@ } while (Changed); LoopHeaders.clear(); + DDT->flush(); return EverChanged; } @@ -932,8 +949,8 @@ bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) { // If the block is trivially dead, just return and let the caller nuke it. // This simplifies other transformations. - if (pred_empty(BB) && - BB != &BB->getParent()->getEntryBlock()) + if (DDT->pendingDelBB(BB) || + (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock())) return false; // If this block has a single predecessor, and if that pred has a single @@ -949,7 +966,7 @@ LoopHeaders.insert(BB); LVI->eraseBlock(SinglePred); - MergeBasicBlockIntoOnlyPred(BB); + MergeBasicBlockIntoOnlyPred(BB, nullptr, DDT); // 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 @@ -1037,7 +1054,10 @@ 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) + DDT->deleteEdge(BB, Succ); } DEBUG(dbgs() << " In block '" << BB->getName() @@ -1054,7 +1074,7 @@ DEBUG(dbgs() << " In block '" << BB->getName() << "' folding terminator: " << *BB->getTerminator() << '\n'); ++NumFolds; - ConstantFoldTerminator(BB, true); + ConstantFoldTerminator(BB, true, nullptr, DDT); return true; } @@ -1087,9 +1107,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) + DDT->deleteEdge(BB, ToRemoveSucc); if (CondCmp->use_empty()) CondCmp->eraseFromParent(); // We can safely replace *some* uses of the CondInst if it has @@ -1183,9 +1207,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) + DDT->deleteEdge(BB, RemoveSucc); return true; } CurrentBB = CurrentPred; @@ -1579,10 +1607,13 @@ (size_t)std::distance(pred_begin(BB), pred_end(BB))) { 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) + DDT->deleteEdge(BB, SuccBB); + } } // Finally update the terminator. @@ -1923,7 +1954,6 @@ UsesToRename.push_back(&U); } - // If there are no uses outside the block, we're done with this instruction. if (UsesToRename.empty()) continue; @@ -1952,6 +1982,10 @@ PredTerm->setSuccessor(i, NewBB); } + DDT->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. @@ -1980,6 +2014,13 @@ BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix); + DDT->insertEdge(PredBB, BB); + for (auto Pred : Preds) { + if (Pred != BB) + DDT->deleteEdge(Pred, BB); + DDT->insertEdge(Pred, PredBB); + } + // Set the block frequency of the newly created PredBB, which is the sum of // frequencies of Preds. if (HasProfileData) @@ -2148,7 +2189,11 @@ BranchInst *OldPredBranch = dyn_cast(PredBB->getTerminator()); if (!OldPredBranch || !OldPredBranch->isUnconditional()) { - PredBB = SplitEdge(PredBB, BB); + BasicBlock *OldPredBB = PredBB; + PredBB = SplitEdge(OldPredBB, BB); + DDT->applyUpdates({{DominatorTree::Insert, OldPredBB, PredBB}, + {DominatorTree::Insert, PredBB, BB}, + {DominatorTree::Delete, OldPredBB, BB}}); OldPredBranch = cast(PredBB->getTerminator()); } @@ -2245,6 +2290,8 @@ // Remove the unconditional branch at the end of the PredBB block. OldPredBranch->eraseFromParent(); + if (BB != PredBB) + DDT->deleteEdge(PredBB, BB); ++NumDupes; return true; @@ -2310,6 +2357,7 @@ // Move the unconditional branch to NewBB. PredTerm->removeFromParent(); NewBB->getInstList().insert(NewBB->end(), PredTerm); + DDT->insertEdge(NewBB, BB); // Create a conditional branch and update PHI nodes. BranchInst::Create(NewBB, BB, SI->getCondition(), Pred); CondLHS->setIncomingValue(I, SI->getFalseValue()); @@ -2317,6 +2365,7 @@ // The select is now dead. SI->eraseFromParent(); + DDT->insertEdge(Pred, NewBB); // Update any other PHI nodes in BB. for (BasicBlock::iterator BI = BB->begin(); PHINode *Phi = dyn_cast(BI); ++BI) @@ -2394,12 +2443,28 @@ continue; // Expand the select. TerminatorInst *Term = - SplitBlockAndInsertIfThen(SI->getCondition(), SI, false); + SplitBlockAndInsertIfThen(SI->getCondition(), SI, false, nullptr); + 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); SI->replaceAllUsesWith(NewPN); SI->eraseFromParent(); + // From the point of view of the DDT, both NewBB and SplitBB are newly + // created blocks. We first need to handle the edges caused by inserting an + // if..then block. + DDT->applyUpdates({{DominatorTree::Insert, BB, SplitBB}, + {DominatorTree::Insert, BB, NewBB}, + {DominatorTree::Insert, NewBB, SplitBB}}); + // The successors of BB are now the successors of SplitBB. We need to remove + // them as successors of BB and attach them as successors of SplitBB. + for (auto *Succ : successors(SplitBB)) { + if (Succ != BB) + DDT->deleteEdge(BB, Succ); + if (Succ != SplitBB) + DDT->insertEdge(SplitBB, Succ); + } return true; } return false; @@ -2486,8 +2551,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(); @@ -2496,18 +2561,29 @@ 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. + DDT->applyUpdates( + {// Guarded block split. + {DominatorTree::Delete, PredGuardedBlock, BB}, + {DominatorTree::Insert, PredGuardedBlock, GuardedBlock}, + {DominatorTree::Insert, GuardedBlock, BB}, + // Unguarded block split. + {DominatorTree::Delete, PredUnguardedBlock, BB}, + {DominatorTree::Insert, PredUnguardedBlock, UnguardedBlock}, + {DominatorTree::Insert, UnguardedBlock, BB}}); // Some instructions before the guard may still have uses. For them, we need // to create Phi nodes merging their copies in both guarded and unguarded // branches. Those instructions that have no uses can be just removed. Index: llvm/lib/Transforms/Utils/BasicBlockUtils.cpp =================================================================== --- llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -45,7 +45,7 @@ using namespace llvm; -void llvm::DeleteDeadBlock(BasicBlock *BB) { +void llvm::DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT) { assert((pred_begin(BB) == pred_end(BB) || // Can delete self loop. BB->getSinglePredecessor() == BB) && "Block is not dead!"); @@ -53,8 +53,11 @@ // Loop through all of our successors and make sure they know that one // of their predecessors is going away. - for (BasicBlock *Succ : BBTerm->successors()) + for (BasicBlock *Succ : BBTerm->successors()) { + if (DDT && BB != Succ) + DDT->deleteEdge(BB, Succ); Succ->removePredecessor(BB); + } // Zap all the instructions in the block. while (!BB->empty()) { @@ -69,8 +72,10 @@ BB->getInstList().pop_back(); } - // Zap the block! - BB->eraseFromParent(); + if (DDT) + DDT->deleteBB(BB); // Deferred deletion of BB. + else + BB->eraseFromParent(); // Zap the block! } void llvm::FoldSingleEntryPHINodes(BasicBlock *BB, 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, + DeferredDominance *DDT) { 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 (DDT && OldDest != Destination && OldDest != BB) + DDT->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 (DDT && DefaultDest != ParentBB) { + // DefaultDest may still be a successor of a non-default case. + if (none_of(successors(ParentBB), [DefaultDest](BasicBlock *S) { + return S == DefaultDest; + })) + DDT->deleteEdge(ParentBB, DefaultDest); + } continue; } @@ -225,14 +236,18 @@ // Insert the new branch. Builder.CreateBr(TheOnlyDest); BasicBlock *BB = SI->getParent(); + BasicBlock *TheOnlyDestCheck = TheOnlyDest; // 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 (DDT && Succ != TheOnlyDestCheck && Succ != BB) + DDT->deleteEdge(BB, Succ); + } } // Delete the old switch. @@ -285,14 +300,20 @@ if (BlockAddress *BA = dyn_cast(IBI->getAddress()->stripPointerCasts())) { BasicBlock *TheOnlyDest = BA->getBasicBlock(); + BasicBlock *TheOnlyDestCheck = TheOnlyDest; // 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 (DDT && DestBB != TheOnlyDestCheck && DestBB != ParentBB) + DDT->deleteEdge(ParentBB, DestBB); + } } Value *Address = IBI->getAddress(); IBI->eraseFromParent(); @@ -583,7 +604,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, + DeferredDominance *DDT) { // This only adjusts blocks with PHI nodes. if (!isa(BB->begin())) return; @@ -606,13 +628,18 @@ // of the block. if (PhiIt != OldPhiIt) PhiIt = &BB->front(); } + if (DDT && BB != Pred) + DDT->deleteEdge(Pred, BB); } /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its /// predecessor is known to have one successor (DestBB!). Eliminate the edge /// between them, moving the instructions in the predecessor into DestBB and /// deleting the predecessor block. -void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { +void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT, + DeferredDominance *DDT) { + assert(!(DT && DDT) && "Cannot call with both DT and DDT."); + // If BB has single-entry PHI nodes, fold them. while (PHINode *PN = dyn_cast(DestBB->begin())) { Value *NewVal = PN->getIncomingValue(0); @@ -625,6 +652,25 @@ BasicBlock *PredBB = DestBB->getSinglePredecessor(); assert(PredBB && "Block doesn't have a single predecessor!"); + bool ReplaceEntryBB = false; + if (PredBB == &DestBB->getParent()->getEntryBlock()) + ReplaceEntryBB = true; + + // Deferred DT update: Collect all the edges that enter PredBB, discarding + // edges to itself and duplicates. These dominator edges will be redirected to + // DestBB. + if (!ReplaceEntryBB && DDT) { + for (pred_iterator PI = pred_begin(PredBB), E = pred_end(PredBB); PI != E; + ++PI) { + if (*PI == PredBB) + continue; + DDT->deleteEdge(*PI, PredBB); + if (*PI != DestBB) + DDT->insertEdge(*PI, DestBB); // DestBB cannot dominate itself. + } + DDT->deleteEdge(PredBB, DestBB); + } + // Zap anything that took the address of DestBB. Not doing this will give the // address an invalid value. if (DestBB->hasAddressTaken()) { @@ -645,7 +691,7 @@ // 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()) + if (ReplaceEntryBB) DestBB->moveAfter(PredBB); if (DT) { @@ -657,8 +703,17 @@ DT->eraseNode(PredBB); } } - // Nuke BB. - PredBB->eraseFromParent(); + + if (DDT) + DDT->deleteBB(PredBB); // Deferred deletion of BB. + else + PredBB->eraseFromParent(); // Nuke BB. + + // 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 (ReplaceEntryBB && DDT) + DDT->recalculate(*(DestBB->getParent())); } /// CanMergeValues - Return true if we can choose one of these values to use @@ -865,7 +920,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, + DeferredDominance *DDT) { assert(BB != &BB->getParent()->getEntryBlock() && "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); @@ -906,6 +962,19 @@ 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. + if (DDT) { + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + if (*PI == BB) + continue; + DDT->deleteEdge(*PI, BB); + if (*PI != Succ) + DDT->insertEdge(*PI, Succ); // Succ cannot dominate itself. + } + DDT->deleteEdge(BB, 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 @@ -940,17 +1009,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); - BB->eraseFromParent(); // Delete the old basic block. + + if (DDT) + DDT->deleteBB(BB); // Deferred deletion of the old basic block. + else + BB->eraseFromParent(); // Delete the old basic block. + return true; } @@ -1450,13 +1529,15 @@ } unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap, - bool PreserveLCSSA) { + bool PreserveLCSSA, DeferredDominance *DDT) { BasicBlock *BB = I->getParent(); // 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 (DDT && BB != Successor) + DDT->deleteEdge(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) { @@ -1480,7 +1561,7 @@ } /// changeToCall - Convert the specified invoke into a normal call. -static void changeToCall(InvokeInst *II) { +static void changeToCall(InvokeInst *II, DeferredDominance *DDT = nullptr) { SmallVector Args(II->arg_begin(), II->arg_end()); SmallVector OpBundles; II->getOperandBundlesAsDefs(OpBundles); @@ -1493,11 +1574,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 (DDT && BB != UnwindDestBB && NormalDestBB != UnwindDestBB) + DDT->deleteEdge(BB, UnwindDestBB); } BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, @@ -1538,8 +1624,9 @@ } static bool markAliveBlocks(Function &F, - SmallPtrSetImpl &Reachable) { - SmallVector Worklist; + SmallPtrSetImpl &Reachable, + DeferredDominance *DDT = nullptr) { + SmallVector Worklist; BasicBlock *BB = &F.front(); Worklist.push_back(BB); Reachable.insert(BB); @@ -1558,7 +1645,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, DDT); Changed = true; break; } @@ -1575,7 +1662,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, DDT); Changed = true; break; } @@ -1585,7 +1673,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, DDT); Changed = true; break; } @@ -1595,7 +1683,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, DDT); Changed = true; } break; @@ -1614,7 +1702,7 @@ if (isa(Ptr) || (isa(Ptr) && SI->getPointerAddressSpace() == 0)) { - changeToUnreachable(SI, true); + changeToUnreachable(SI, true, false, DDT); Changed = true; break; } @@ -1626,16 +1714,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, DDT); 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 (DDT && BB != UnwindDestBB && NormalDestBB != UnwindDestBB) + DDT->deleteEdge(BB, UnwindDestBB); } else - changeToCall(II); + changeToCall(II, DDT); Changed = true; } } else if (auto *CatchSwitch = dyn_cast(Terminator)) { @@ -1681,7 +1773,7 @@ } } - Changed |= ConstantFoldTerminator(BB, true); + Changed |= ConstantFoldTerminator(BB, true, nullptr, DDT); for (BasicBlock *Successor : successors(BB)) if (Reachable.insert(Successor).second) Worklist.push_back(Successor); @@ -1689,29 +1781,34 @@ return Changed; } -void llvm::removeUnwindEdge(BasicBlock *BB) { +void llvm::removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT) { TerminatorInst *TI = BB->getTerminator(); if (auto *II = dyn_cast(TI)) { - changeToCall(II); + changeToCall(II, DDT); 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"); } @@ -1721,15 +1818,18 @@ UnwindDest->removePredecessor(BB); TI->replaceAllUsesWith(NewTI); TI->eraseFromParent(); + if (DDT && BB != UnwindDest && DeleteEdge) + DDT->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, + DeferredDominance *DDT) { SmallPtrSet Reachable; - bool Changed = markAliveBlocks(F, Reachable); + bool Changed = markAliveBlocks(F, Reachable, DDT); // If there are unreachable blocks in the CFG... if (Reachable.size() == F.size()) @@ -1739,25 +1839,33 @@ NumRemoved += F.size()-Reachable.size(); // Loop over all of the basic blocks that are not reachable, dropping all of - // their internal references... - for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { - if (Reachable.count(&*BB)) + // their internal references. Update DDT and LVI if available. + 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)) + for (BasicBlock *Successor : successors(BB)) { if (Reachable.count(Successor)) - Successor->removePredecessor(&*BB); + Successor->removePredecessor(BB); + if (DDT && BB != Successor) + DDT->deleteEdge(BB, Successor); + } if (LVI) - LVI->eraseBlock(&*BB); + LVI->eraseBlock(BB); BB->dropAllReferences(); } - for (Function::iterator I = ++F.begin(); I != F.end();) - if (!Reachable.count(&*I)) + for (Function::iterator I = ++F.begin(); I != F.end(); ++I) { + auto *BB = &*I; + if (Reachable.count(BB)) + continue; + if (DDT) { + DDT->deleteBB(BB); // deferred deletion of BB. + } else { I = F.getBasicBlockList().erase(I); - else - ++I; - + --I; // We deleted a block and need to "freeze" incrementing. + } + } return true; } 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/ddt-crash.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/JumpThreading/ddt-crash.ll @@ -0,0 +1,37 @@ +; RUN: opt < %s -jump-threading -disable-output + +declare i32 @ham() + +define void @zot() { +bb: ; entry + %tmp = load i32, i32* undef + %tmp1 = icmp eq i32 %tmp, 0 + br i1 %tmp1, label %bb15, label %bb2 + +bb2: ; preds = %bb + %tmp3 = tail call i32 @ham() + switch i32 %tmp3, label %bb8 [ + i32 0, label %bb9 + i32 1, label %bb11 + i32 2, label %bb11 + i32 3, label %bb15 + ] + +bb8: ; preds = %bb2 + br label %bb11 + +bb9: ; preds = %bb2 + %tmp10 = tail call i32 @ham() + br label %bb11 + +bb11: ; preds = %bb9, %bb8, %bb2, %bb2 + %tmp12 = phi i32 [ 0, %bb9 ], [ 1, %bb8 ], [ 2, %bb2 ], [ 2, %bb2 ] + %tmp13 = icmp eq i32 %tmp12, 0 + br i1 %tmp13, label %bb15, label %bb14 + +bb14: ; preds = %bb11 + ret void + +bb15: ; preds = %bb11, %bb2, %bb + ret void +} 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 +}