Lines Matching full:loop
1 //===--------- LoopSimplifyCFG.cpp - Loop CFG Simplification Pass ---------===//
9 // This file implements the Loop SimplifyCFG Pass. This pass is responsible for
10 // basic loop CFG cleanup, primarily to assist other loop passes. If you
11 // encounter a noncanonical CFG construct that causes another loop pass to
35 #define DEBUG_TYPE "loop-simplifycfg"
37 static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
43 "Number of loop blocks deleted");
45 "Number of loop exiting edges deleted");
77 static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop, in removeBlockFromLoops()
78 Loop *LastLoop = nullptr) { in removeBlockFromLoops()
80 "First loop is supposed to be inside of last loop!"); in removeBlockFromLoops()
81 assert(FirstLoop->contains(BB) && "Must be a loop block!"); in removeBlockFromLoops()
82 for (Loop *Current = FirstLoop; Current != LastLoop; in removeBlockFromLoops()
87 /// Find innermost loop that contains at least one block from \p BBs and
88 /// contains the header of loop \p L.
89 static Loop *getInnermostLoopFor(SmallPtrSetImpl<BasicBlock *> &BBs, in getInnermostLoopFor()
90 Loop &L, LoopInfo &LI) { in getInnermostLoopFor()
91 Loop *Innermost = nullptr; in getInnermostLoopFor()
93 Loop *BBL = LI.getLoopFor(BB); in getInnermostLoopFor()
111 Loop &L;
120 // Whether or not the current loop has irreducible CFG.
122 // Whether or not the current loop will still exist after terminator constant
124 // 1. Loop's latch(es) become unreachable from loop header;
125 // 2. Loop's header becomes unreachable from method entry.
127 // current loop and its preheader and do not affect preheader's reachibility
128 // from any other block. So this variable set to true means that loop's latch
129 // has become unreachable from loop header.
132 // The blocks of the original loop that will still be reachable from entry
135 // The blocks of the original loop that will become unreachable from entry
138 // The exits of the original loop that will still be reachable from entry
141 // The exits of the original loop that will become unreachable from entry
144 // The blocks that will still be a part of the current loop after folding.
152 dbgs() << "Constant terminator folding for loop " << L << "\n"; in dump()
153 dbgs() << "After terminator constant-folding, the loop will"; in dump()
171 PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks); in dump()
172 PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks); in dump()
176 PrintOutSet("The following blocks will still be part of the loop:", in dump()
180 /// Whether or not the current loop has irreducible CFG.
194 // with lesses number, and it is not a loop backedge, then it can only in hasIrreducibleCFG()
195 // be a part of irreducible non-loop cycle. in hasIrreducibleCFG()
201 /// Fill all information about status of blocks and exits of the current loop
208 // When the loop has only reducible CFG inside, then the invariant "all in analyze()
210 // an irreducible loop can break this invariant (e.g. latch does not have to in analyze()
219 // Collect live and dead loop blocks and exits. in analyze()
224 // If a loop block wasn't marked as live so far, then it's dead. in analyze()
233 // folding. Only handle blocks from current loop: branches in child loops in analyze()
250 // Amount of dead and live loop blocks should match the total number of in analyze()
251 // blocks in loop. in analyze()
256 // predecessors are in the loop. This may not be the case, as the input loop in analyze()
257 // may not by in loop-simplify/canonical form. in analyze()
277 // The loop will not be destroyed if its latch is live. in analyze()
280 // If we are going to delete the current loop completely, no extra analysis in analyze()
286 // current loop after the transform. in analyze()
288 // If the loop is live, then we should compute what blocks are still in in analyze()
289 // loop after all branch folding has been done. A block is in loop if in analyze()
290 // it has a live edge to another block that is in the loop; by definition, in analyze()
291 // latch is in the loop. in analyze()
304 "Header not in loop?"); in analyze()
306 "All blocks that stay in loop should be live!"); in analyze()
309 /// We need to preserve static reachibility of all loop exit blocks (this is)
310 /// required by loop pass manager. In order to do it, we make the following
322 /// We cannot simply remove edge from the loop to dead exit because in this
343 /// remove edges from the loop to these blocks.
384 if (Loop *OuterLoop = LI.getLoopFor(Preheader)) { in handleDeadExits()
385 // When we break dead edges, the outer loop may become unreachable from in handleDeadExits()
386 // the current loop. We need to fix loop info accordingly. For this, we in handleDeadExits()
387 // find the most nested loop that still contains L and remove L from all in handleDeadExits()
389 Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI); in handleDeadExits()
391 // Okay, our loop is no longer in the outer loop (and maybe not in some of in handleDeadExits()
405 // in the current loop. Now it is not their child anymore, so such uses in handleDeadExits()
407 Loop *FixLCSSALoop = OuterLoop; in handleDeadExits()
410 assert(FixLCSSALoop && "Should be a loop!"); in handleDeadExits()
431 /// Delete loop blocks that have become unreachable after folding. Make all
441 // it tries to remove a loop which is not the top-level loop. In particular, in deleteDeadLoopBlocks()
442 // it requires loop's preheader to be strictly in loop's parent. We cannot in deleteDeadLoopBlocks()
444 // break this invariant for the dead loop. So we detatch and erase all dead in deleteDeadLoopBlocks()
448 assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!"); in deleteDeadLoopBlocks()
449 Loop *DL = LI.getLoopFor(BB); in deleteDeadLoopBlocks()
462 "Header of the current loop cannot be dead!"); in deleteDeadLoopBlocks()
463 LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName() in deleteDeadLoopBlocks()
481 assert(LI.getLoopFor(BB) == &L && "Should be a loop block!"); in foldTerminators()
495 // If our successor lies in a different loop, we don't want to remove in foldTerminators()
528 ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT, in ConstantTerminatorFoldingImpl()
553 dbgs() << "No constant terminator folding candidates found in loop " in run()
558 // TODO: Support deletion of the current loop. in run()
562 << "Give up constant terminator folding in loop " << Header->getName() in run()
563 << ": we don't currently support deletion of the current loop.\n"); in run()
567 // TODO: Support blocks that are not dead, but also not in loop after the in run()
572 dbgs() << "Give up constant terminator folding in loop " in run()
575 "being a part of the loop after constant-folding.\n"); in run()
585 LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop " in run()
596 << " terminators in loop " << Header->getName() << "\n"); in run()
607 << " dead blocks in loop " << Header->getName() << "\n"); in run()
642 static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI, in constantFoldTerminators()
660 static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT, in mergeBlocksIntoPredecessors()
695 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI, in simplifyLoopCFG()
715 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM, in run()
727 LPMU.markLoopAsDeleted(L, "loop-simplifycfg"); in run()