Go to the documentation of this file.
37 #define DEBUG_TYPE "loop-simplifycfg"
43 "Number of terminators folded to unconditional branches");
45 "Number of loop blocks deleted");
47 "Number of loop exiting edges deleted");
54 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
55 if (BI->isUnconditional())
57 if (BI->getSuccessor(0) == BI->getSuccessor(1))
58 return BI->getSuccessor(0);
62 return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
66 auto *CI = dyn_cast<ConstantInt>(
SI->getCondition());
69 for (
auto Case :
SI->cases())
70 if (Case.getCaseValue() == CI)
71 return Case.getCaseSuccessor();
72 return SI->getDefaultDest();
80 Loop *LastLoop =
nullptr) {
82 "First loop is supposed to be inside of last loop!");
84 for (
Loop *Current = FirstLoop; Current != LastLoop;
86 Current->removeBlockFromLoop(
BB);
93 Loop *Innermost =
nullptr;
111 class ConstantTerminatorFoldingImpl {
123 bool HasIrreducibleCFG =
false;
132 bool DeleteCurrentLoop =
false;
154 dbgs() <<
"Constant terminator folding for loop " << L <<
"\n";
155 dbgs() <<
"After terminator constant-folding, the loop will";
156 if (!DeleteCurrentLoop)
158 dbgs() <<
" be destroyed\n";
159 auto PrintOutVector = [&](
const char *Message,
161 dbgs() << Message <<
"\n";
163 dbgs() <<
"\t" <<
BB->getName() <<
"\n";
165 auto PrintOutSet = [&](
const char *Message,
167 dbgs() << Message <<
"\n";
169 dbgs() <<
"\t" <<
BB->getName() <<
"\n";
171 PrintOutVector(
"Blocks in which we can constant-fold terminator:",
173 PrintOutSet(
"Live blocks from the original loop:", LiveLoopBlocks);
174 PrintOutVector(
"Dead blocks from the original loop:", DeadLoopBlocks);
175 PrintOutSet(
"Live exit blocks:", LiveExitBlocks);
176 PrintOutVector(
"Dead exit blocks:", DeadExitBlocks);
177 if (!DeleteCurrentLoop)
178 PrintOutSet(
"The following blocks will still be part of the loop:",
179 BlocksInLoopAfterFolding);
187 unsigned Current = 0;
216 if (hasIrreducibleCFG(DFS)) {
217 HasIrreducibleCFG =
true;
227 if (!LiveLoopBlocks.
count(
BB)) {
228 DeadLoopBlocks.push_back(
BB);
238 bool TakeFoldCandidate = TheOnlySucc && LI.
getLoopFor(
BB) == &L;
239 if (TakeFoldCandidate)
240 FoldCandidates.push_back(
BB);
244 if (!TakeFoldCandidate || TheOnlySucc == Succ) {
246 LiveLoopBlocks.
insert(Succ);
248 LiveExitBlocks.
insert(Succ);
255 "Malformed block sets?");
263 for (
auto *ExitBlock : ExitBlocks)
264 if (!LiveExitBlocks.
count(ExitBlock) &&
265 UniqueDeadExits.
insert(ExitBlock).second &&
268 DeadExitBlocks.push_back(ExitBlock);
276 return !TheOnlySucc || TheOnlySucc == To || LI.
getLoopFor(
From) != &L;
284 if (DeleteCurrentLoop)
296 return BlocksInLoopAfterFolding.
count(Succ) && IsEdgeLive(
BB, Succ);
301 if (BlockIsInLoop(
BB))
302 BlocksInLoopAfterFolding.
insert(
BB);
306 "Header not in loop?");
307 assert(BlocksInLoopAfterFolding.
size() <= LiveLoopBlocks.
size() &&
308 "All blocks that stay in loop should be live!");
346 void handleDeadExits() {
348 if (DeadExitBlocks.empty())
362 unsigned DummyIdx = 1;
367 for (
auto &PN :
BB->phis())
368 DeadInstructions.push_back(&PN);
370 if (
auto *LandingPad = dyn_cast<LandingPadInst>(
BB->getFirstNonPHI()))
375 I->eraseFromParent();
378 assert(DummyIdx != 0 &&
"Too many dead exits!");
381 ++NumLoopExitsDeleted;
394 if (StillReachable != OuterLoop) {
399 OuterLoop->removeChildLoop(&L);
408 Loop *FixLCSSALoop = OuterLoop;
411 assert(FixLCSSALoop &&
"Should be a loop!");
433 void deleteDeadLoopBlocks() {
436 DeadLoopBlocks.end());
446 for (
auto *
BB : DeadLoopBlocks)
450 if (!
DL->isOutermost()) {
451 for (
auto *
PL =
DL->getParentLoop();
PL;
PL =
PL->getParentLoop())
452 for (
auto *
BB :
DL->getBlocks())
453 PL->removeBlockFromLoop(
BB);
454 DL->getParentLoop()->removeChildLoop(
DL);
460 for (
auto *
BB : DeadLoopBlocks) {
462 "Header of the current loop cannot be dead!");
471 for (
auto *
BB : DeadLoopBlocks)
474 NumLoopBlocksDeleted += DeadLoopBlocks.size();
479 void foldTerminators() {
483 assert(TheOnlySucc &&
"Should have one live successor!");
486 <<
" with an unconditional branch to the block "
487 << TheOnlySucc->
getName() <<
"\n");
491 unsigned TheOnlySuccDuplicates = 0;
493 if (Succ != TheOnlySucc) {
494 DeadSuccessors.
insert(Succ);
497 bool PreserveLCSSAPhi = !L.
contains(Succ);
502 ++TheOnlySuccDuplicates;
504 assert(TheOnlySuccDuplicates > 0 &&
"Should be!");
508 bool PreserveLCSSAPhi = !L.
contains(TheOnlySucc);
509 for (
unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
511 if (MSSAU && TheOnlySuccDuplicates > 1)
518 Term->eraseFromParent();
520 for (
auto *DeadSucc : DeadSuccessors)
523 ++NumTerminatorsFolded;
531 : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),
545 if (HasIrreducibleCFG) {
546 LLVM_DEBUG(
dbgs() <<
"Loops with irreducible CFG are not supported!\n");
551 if (FoldCandidates.empty()) {
553 dbgs() <<
"No constant terminator folding candidates found in loop "
559 if (DeleteCurrentLoop) {
562 <<
"Give up constant terminator folding in loop " << Header->
getName()
563 <<
": we don't currently support deletion of the current loop.\n");
569 if (BlocksInLoopAfterFolding.
size() + DeadLoopBlocks.size() !=
572 dbgs() <<
"Give up constant terminator folding in loop "
573 << Header->
getName() <<
": we don't currently"
574 " support blocks that are not dead, but will stop "
575 "being a part of the loop after constant-folding.\n");
584 <<
" terminators in loop " << Header->
getName() <<
"\n");
590 if (!DeadLoopBlocks.empty()) {
592 <<
" dead blocks in loop " << Header->
getName() <<
"\n");
593 deleteDeadLoopBlocks();
605 #if defined(EXPENSIVE_CHECKS)
607 "DT broken after transform!");
610 "DT broken after transform!");
619 bool foldingBreaksCurrentLoop()
const {
620 return DeleteCurrentLoop;
630 bool &IsLoopDeleted) {
639 ConstantTerminatorFoldingImpl
BranchFolder(L, LI, DT, SE, MSSAU);
641 IsLoopDeleted = Changed &&
BranchFolder.foldingBreaksCurrentLoop();
647 bool Changed =
false;
653 for (
auto &Block : Blocks) {
656 BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
678 bool &IsLoopDeleted) {
679 bool Changed =
false;
702 bool DeleteCurrentLoop =
false;
704 MSSAU ? MSSAU.
getPointer() :
nullptr, DeleteCurrentLoop))
707 if (DeleteCurrentLoop)
717 class LoopSimplifyCFGLegacyPass :
public LoopPass {
728 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
729 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
730 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
731 auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
737 bool DeleteCurrentLoop =
false;
741 if (DeleteCurrentLoop)
756 "Simplify loop CFG",
false,
false)
763 return new LoopSimplifyCFGLegacyPass();
A set of analyses that are preserved following a run of a transformation pass.
This is an optimization pass for GlobalISel generic memory operations.
static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop, Loop *LastLoop=nullptr)
Removes BB from all loops from [FirstLoop, LastLoop) in parent chain.
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
const Function * getParent() const
Return the enclosing method, or null if none.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Legacy pass manager pass to access dependence information.
Represents a single loop in the control flow graph.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Pass * createLoopSimplifyCFGPass()
The main scalar evolution driver.
rpo function Deduce function attributes in RPO
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
static constexpr UpdateKind Insert
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
auto successors(MachineBasicBlock *BB)
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
LLVM Basic Block Representation.
constexpr const T * getPointer() const
bool isComplete() const
Return true if postorder numbers are assigned to all loop blocks.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
This is the shared class of boolean and integer constants.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Legacy analysis pass which computes MemorySSA.
void initializeLoopSimplifyCFGLegacyPassPass(PassRegistry &)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU, bool &IsLoopDeleted)
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Represent the analysis usage information of a pass.
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
iterator_range< block_iterator > blocks() const
RPOIterator endRPO() const
STATISTIC(NumFunctions, "Total number of functions")
auto predecessors(MachineBasicBlock *BB)
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
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...
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Store the result of a depth first search within basic blocks contained by a single loop.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
initializer< Ty > init(const Ty &Val)
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getLoopDepth() const
Return the nesting level of this loop.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
StandardInstrumentations SI(Debug, VerifyEach)
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
void forgetTopmostLoop(const Loop *L)
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
An analysis that produces MemorySSA for a function.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
SmallVector< MachineOperand, 4 > Cond
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
StringRef getName() const
Return a constant reference to the value's name.
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...
bool isLoopHeader(const BlockT *BB) const
void markLoopAsDeleted(Loop &L)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg", "Simplify loop CFG", false, false) INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass
BlockT * getHeader() const
POIterator beginPostorder() const
Iterate over the cached postorder blocks.
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.
Pass interface - Implemented by all 'passes'.
static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU)
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
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.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
A SetVector that performs no allocations if smaller than a certain size.
A container for analyses that lazily runs them and caches their results.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
bool VerifyMemorySSA
Enables verification of MemorySSA.
BlockVerifier::State From
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
Conditional or Unconditional Branch instruction.
POIterator endPostorder() const
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
static cl::opt< bool > EnableTermFolding("enable-loop-simplifycfg-term-folding", cl::init(true))
static constexpr UpdateKind Delete
reference emplace_back(ArgTypes &&... Args)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.