38#define DEBUG_TYPE "loop-simplifycfg"
44 "Number of terminators folded to unconditional branches");
46 "Number of loop blocks deleted");
48 "Number of loop exiting edges deleted");
55 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
56 if (BI->isUnconditional())
58 if (BI->getSuccessor(0) == BI->getSuccessor(1))
63 return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
66 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
67 auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
70 for (
auto Case : SI->cases())
71 if (Case.getCaseValue() == CI)
72 return Case.getCaseSuccessor();
73 return SI->getDefaultDest();
81 Loop *LastLoop =
nullptr) {
83 "First loop is supposed to be inside of last loop!");
85 for (
Loop *Current = FirstLoop; Current != LastLoop;
87 Current->removeBlockFromLoop(BB);
94 Loop *Innermost =
nullptr;
97 while (BBL && !BBL->
contains(L.getHeader()))
112class ConstantTerminatorFoldingImpl {
124 bool HasIrreducibleCFG =
false;
133 bool DeleteCurrentLoop =
false;
155 dbgs() <<
"Constant terminator folding for loop " <<
L <<
"\n";
156 dbgs() <<
"After terminator constant-folding, the loop will";
157 if (!DeleteCurrentLoop)
159 dbgs() <<
" be destroyed\n";
160 auto PrintOutVector = [&](
const char *Message,
162 dbgs() << Message <<
"\n";
164 dbgs() <<
"\t" << BB->getName() <<
"\n";
166 auto PrintOutSet = [&](
const char *Message,
168 dbgs() << Message <<
"\n";
170 dbgs() <<
"\t" << BB->getName() <<
"\n";
172 PrintOutVector(
"Blocks in which we can constant-fold terminator:",
174 PrintOutSet(
"Live blocks from the original loop:", LiveLoopBlocks);
175 PrintOutVector(
"Dead blocks from the original loop:", DeadLoopBlocks);
176 PrintOutSet(
"Live exit blocks:", LiveExitBlocks);
177 PrintOutVector(
"Dead exit blocks:", DeadExitBlocks);
178 if (!DeleteCurrentLoop)
179 PrintOutSet(
"The following blocks will still be part of the loop:",
180 BlocksInLoopAfterFolding);
188 unsigned Current = 0;
195 if (
L.contains(Succ) && !LI.
isLoopHeader(Succ) && RPO[BB] > RPO[Succ])
217 if (hasIrreducibleCFG(DFS)) {
218 HasIrreducibleCFG =
true;
223 LiveLoopBlocks.
insert(
L.getHeader());
228 if (!LiveLoopBlocks.
count(BB)) {
239 bool TakeFoldCandidate = TheOnlySucc && LI.
getLoopFor(BB) == &
L;
240 if (TakeFoldCandidate)
245 if (!TakeFoldCandidate || TheOnlySucc == Succ) {
246 if (
L.contains(Succ))
247 LiveLoopBlocks.
insert(Succ);
249 LiveExitBlocks.
insert(Succ);
255 assert(
L.getNumBlocks() == LiveLoopBlocks.
size() + DeadLoopBlocks.
size() &&
256 "Malformed block sets?");
262 L.getExitBlocks(ExitBlocks);
264 for (
auto *ExitBlock : ExitBlocks)
265 if (!LiveExitBlocks.
count(ExitBlock) &&
266 UniqueDeadExits.
insert(ExitBlock).second &&
268 [
this](
BasicBlock *Pred) {
return L.contains(Pred); }))
281 DeleteCurrentLoop = !IsEdgeLive(
L.getLoopLatch(),
L.getHeader());
285 if (DeleteCurrentLoop)
290 BlocksInLoopAfterFolding.
insert(
L.getLoopLatch());
297 return BlocksInLoopAfterFolding.
count(Succ) && IsEdgeLive(BB, Succ);
302 if (BlockIsInLoop(BB))
303 BlocksInLoopAfterFolding.
insert(BB);
307 "Header not in loop?");
308 assert(BlocksInLoopAfterFolding.
size() <= LiveLoopBlocks.
size() &&
309 "All blocks that stay in loop should be live!");
347 void handleDeadExits() {
349 if (DeadExitBlocks.
empty())
363 unsigned DummyIdx = 1;
368 for (
auto &PN : BB->
phis())
371 if (
auto *LandingPad = dyn_cast<LandingPadInst>(BB->
getFirstNonPHI()))
377 I->eraseFromParent();
380 assert(DummyIdx != 0 &&
"Too many dead exits!");
382 DTUpdates.
push_back({DominatorTree::Insert, Preheader, BB});
383 ++NumLoopExitsDeleted;
386 assert(
L.getLoopPreheader() == NewPreheader &&
"Malformed CFG?");
396 if (StillReachable != OuterLoop) {
399 for (
auto *BB :
L.blocks())
401 OuterLoop->removeChildLoop(&L);
410 Loop *FixLCSSALoop = OuterLoop;
413 assert(FixLCSSALoop &&
"Should be a loop!");
436 void deleteDeadLoopBlocks() {
439 DeadLoopBlocks.
end());
449 for (
auto *BB : DeadLoopBlocks)
453 if (!
DL->isOutermost()) {
454 for (
auto *PL =
DL->getParentLoop(); PL; PL =
PL->getParentLoop())
455 for (
auto *BB :
DL->getBlocks())
456 PL->removeBlockFromLoop(BB);
457 DL->getParentLoop()->removeChildLoop(
DL);
463 for (
auto *BB : DeadLoopBlocks) {
465 "Header of the current loop cannot be dead!");
474 for (
auto *BB : DeadLoopBlocks)
477 NumLoopBlocksDeleted += DeadLoopBlocks.size();
482 void foldTerminators() {
486 assert(TheOnlySucc &&
"Should have one live successor!");
489 <<
" with an unconditional branch to the block "
490 << TheOnlySucc->
getName() <<
"\n");
494 unsigned TheOnlySuccDuplicates = 0;
496 if (Succ != TheOnlySucc) {
497 DeadSuccessors.
insert(Succ);
500 bool PreserveLCSSAPhi = !
L.contains(Succ);
505 ++TheOnlySuccDuplicates;
507 assert(TheOnlySuccDuplicates > 0 &&
"Should be!");
511 bool PreserveLCSSAPhi = !
L.contains(TheOnlySucc);
512 for (
unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
514 if (MSSAU && TheOnlySuccDuplicates > 1)
521 Term->eraseFromParent();
523 for (
auto *DeadSucc : DeadSuccessors)
524 DTUpdates.
push_back({DominatorTree::Delete, BB, DeadSucc});
526 ++NumTerminatorsFolded;
534 :
L(
L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&
L),
537 assert(
L.getLoopLatch() &&
"Should be single latch!");
545 LLVM_DEBUG(
dbgs() <<
"In function " << Header->getParent()->getName()
548 if (HasIrreducibleCFG) {
549 LLVM_DEBUG(
dbgs() <<
"Loops with irreducible CFG are not supported!\n");
554 if (FoldCandidates.empty()) {
556 dbgs() <<
"No constant terminator folding candidates found in loop "
557 << Header->getName() <<
"\n");
562 if (DeleteCurrentLoop) {
565 <<
"Give up constant terminator folding in loop " << Header->getName()
566 <<
": we don't currently support deletion of the current loop.\n");
572 if (BlocksInLoopAfterFolding.
size() + DeadLoopBlocks.size() !=
575 dbgs() <<
"Give up constant terminator folding in loop "
576 << Header->getName() <<
": we don't currently"
577 " support blocks that are not dead, but will stop "
578 "being a part of the loop after constant-folding.\n");
585 if (!DeadExitBlocks.empty() && !
L.isLCSSAForm(DT,
false)) {
586 assert(
L.isLCSSAForm(DT,
true) &&
587 "LCSSA broken not by tokens?");
588 LLVM_DEBUG(
dbgs() <<
"Give up constant terminator folding in loop "
590 <<
": tokens uses potentially break LCSSA form.\n");
599 <<
" terminators in loop " << Header->getName() <<
"\n");
601 if (!DeadLoopBlocks.empty())
608 if (!DeadLoopBlocks.empty()) {
610 <<
" dead blocks in loop " << Header->getName() <<
"\n");
611 deleteDeadLoopBlocks();
623#if defined(EXPENSIVE_CHECKS)
624 assert(DT.
verify(DominatorTree::VerificationLevel::Full) &&
625 "DT broken after transform!");
627 assert(DT.
verify(DominatorTree::VerificationLevel::Fast) &&
628 "DT broken after transform!");
637 bool foldingBreaksCurrentLoop()
const {
638 return DeleteCurrentLoop;
648 bool &IsLoopDeleted) {
654 if (!L.getLoopLatch())
657 ConstantTerminatorFoldingImpl
BranchFolder(L, LI, DT, SE, MSSAU);
659 IsLoopDeleted = Changed &&
BranchFolder.foldingBreaksCurrentLoop();
666 bool Changed =
false;
700 bool &IsLoopDeleted) {
701 bool Changed =
false;
721 std::optional<MemorySSAUpdater> MSSAU;
724 bool DeleteCurrentLoop =
false;
729 if (DeleteCurrentLoop)
739class LoopSimplifyCFGLegacyPass :
public LoopPass {
750 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
751 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
752 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
753 auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
754 std::optional<MemorySSAUpdater> MSSAU;
758 MSSAU->getMemorySSA()->verifyMemorySSA();
759 bool DeleteCurrentLoop =
false;
760 bool Changed =
simplifyLoopCFG(*L, DT, LI, SE, MSSAU ? &*MSSAU :
nullptr,
762 if (DeleteCurrentLoop)
775char LoopSimplifyCFGLegacyPass::ID = 0;
777 "Simplify loop CFG",
false,
false)
784 return new LoopSimplifyCFGLegacyPass();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
BlockVerifier::State From
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
DenseMap< Block *, BlockRelaxAux > Blocks
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
static BasicBlock * getOnlyLiveSuccessor(BasicBlock *BB)
If BB is a switch or a conditional branch, but only one of its successors can be reached from this bl...
static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU, bool &IsLoopDeleted)
Turn branches and switches with known constant conditions into unconditional branches.
static Loop * getInnermostLoopFor(SmallPtrSetImpl< BasicBlock * > &BBs, Loop &L, LoopInfo &LI)
Find innermost loop that contains at least one block from BBs and contains the header of loop L.
static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution &SE)
static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU, bool &IsLoopDeleted)
static cl::opt< bool > EnableTermFolding("enable-loop-simplifycfg-term-folding", cl::init(true))
static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop, Loop *LastLoop=nullptr)
Removes BB from all loops from [FirstLoop, LastLoop) in parent chain.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM Basic Block Representation.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Conditional or Unconditional Branch instruction.
This is the shared class of boolean and integer constants.
Legacy pass manager pass to access dependence information.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
void markLoopAsDeleted(Loop &L)
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Store the result of a depth first search within basic blocks contained by a single loop.
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
bool isComplete() const
Return true if postorder numbers are assigned to all loop blocks.
POIterator beginPostorder() const
Iterate over the cached postorder blocks.
POIterator endPostorder() const
void perform(const LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
RPOIterator endRPO() const
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
bool isLoopHeader(const BlockT *BB) const
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Represents a single loop in the control flow graph.
An analysis that produces MemorySSA for a function.
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
void removeDuplicatePhiEdgesBetween(const BasicBlock *From, const BasicBlock *To)
Update the MemoryPhi in To to have a single incoming edge from From, following a CFG change that repl...
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
Legacy analysis pass which computes MemorySSA.
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
The main scalar evolution driver.
void forgetTopmostLoop(const Loop *L)
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
StringRef getName() const
Return a constant reference to the value's name.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
auto successors(const MachineBasicBlock *BB)
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
void initializeLoopSimplifyCFGLegacyPassPass(PassRegistry &)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
bool VerifyMemorySSA
Enables verification of MemorySSA.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
Pass * createLoopSimplifyCFGPass()
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
auto predecessors(const MachineBasicBlock *BB)
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...