Lines Matching refs:Loop
1 //===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
14 // Loop pre-header insertion guarantees that there is a single, non-critical
15 // entry edge from outside of the loop to the loop header. This simplifies a
18 // Loop exit-block insertion guarantees that all exit blocks from the loop
19 // (blocks which are outside of the loop that have predecessors inside of the
20 // loop) only have predecessors from inside of the loop (and are thus dominated
21 // by the loop header). This simplifies transformations such as store-sinking
26 // Indirectbr instructions introduce several complications. If the loop
28 // to transform the loop and make these guarantees. Client code should check
35 // This pass obviously modifies the CFG, but updates loop information and
72 #define DEBUG_TYPE "loop-simplify"
78 // block' block. This prevents the preheader from being placed inside the loop
79 // body, e.g. when the loop hasn't been rotated.
82 Loop *L) {
95 // block that neighbors a BB actually in the loop.
107 // the loop.
113 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
117 BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT,
121 // Compute the set of predecessors of the loop that are not in the loop.
126 if (!L->contains(P)) { // Coming in from outside the loop?
127 // If the loop is branched to from an indirect branch, we won't
128 // be able to fully transform the loop, because it prohibits
137 // Split out the loop pre-header.
154 /// \brief Ensure that the loop preheader dominates all exit blocks.
157 /// the loop.
158 static BasicBlock *rewriteLoopExitBlock(Loop *L, BasicBlock *Exit,
165 // Don't do this if the loop is exited via an indirect branch.
172 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?");
204 /// \brief The first part of loop-nestification is to find a PHI node that tells
206 static PHINode *findPHIToPartitionLoops(Loop *L, DominatorTree *DT,
229 /// \brief If this loop has multiple backedges, try to pull one of them out into
230 /// a nested loop.
235 /// Loop:
237 /// br cond, Loop, Next
239 /// br cond2, Loop, Out
242 /// loop. PHI nodes with unchanging values on one backedge correspond to values
243 /// that change in the "outer" loop, but not in the "inner" loop.
245 /// If we are able to separate out a loop, return the new outer loop that was
248 static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
263 // Pull out all predecessors that have varying values in the loop. This
276 DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");
279 // this loop, tell it to forget them, because we're about to
291 // Create the new outer loop.
292 Loop *NewOuter = new Loop();
294 // Change the parent loop to use the outer loop as its child now.
295 if (Loop *Parent = L->getParentLoop())
300 // L is now a subloop of our outer loop.
303 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
308 // SplitBlockPredecessors for the outer loop.
312 // the Outer loop now.
320 // Scan all of the loop children of L, moving them to OuterLoop if they are
321 // not part of the inner loop.
322 const std::vector<Loop*> &SubLoops = L->getSubLoops();
325 ++I; // Loop remains in L
345 /// \brief This method is called when the specified loop has more than one
349 /// and have that block branch to the loop header. This ensures that loops
351 static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader,
355 // Get information about the loop
366 // Figure out which basic blocks contain back-edges to the loop header.
398 // Loop over the PHI node, moving all entries except the one for the
452 // Update Loop Information - we know that this block is now in the current
453 // loop and all parent loops.
462 /// \brief Simplify one loop and queue further loops for simplification.
463 static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
470 // Check to see that no blocks (other than the header) in this loop have
471 // predecessors that are not in the loop. This is not valid for natural
474 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
486 // Delete each unique out-of-loop (and thus dead) predecessor.
505 // the direction which will exit the loop. This will help simplify loop
521 // This may make the loop analyzable, force SCEV recomputation.
529 // Does the loop already have a preheader? If so, don't insert one.
539 // Next, check to make sure that all exit nodes of the loop only have
540 // predecessors that are inside of the loop. This check guarantees that the
541 // loop preheader/header will dominate the exit blocks. If the exit block has
542 // predecessors from outside of the loop, split the edge now.
553 // Must be exactly this loop: no subloops, parent loops, or non-loop preds
565 // preheader and from multiple backedges), we must adjust the loop.
568 // If this is really a nested loop, rip it out into a child loop. Don't do
572 if (Loop *OuterL =
575 // Enqueue the outer loop as it should be processed next in our
579 // This is a big restructuring change, reprocess the whole loop.
589 // loop header.
599 // Scan over the PHI nodes in the loop header. Since they now have only two
600 // incoming values (the loop is canonicalized), we may have simplified the PHI
611 // If this loop has multiple exits and the exits all go to the same
615 // function), however this code is loop-aware, where SimplifyCFG is
617 // loop-invariant instructions out of the way to open up more
656 // The loop disposition of all SCEV expressions that depend on any
669 // Success. The block is now dead, so remove it from the loop,
675 // parent loop doesn't change (spliting edges doesn't count). If blocks,
676 // CFG edges, or other values in the parent loop change, then we need call
703 bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
709 SmallVector<Loop *, 4> Worklist;
716 Loop *L2 = Worklist[Idx];
744 // We need loop information to identify the loops...
766 INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
774 INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
793 // Simplify each loop nest in the function.
803 static void verifyLoop(Loop *L) {
805 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
810 // not possible to transform a loop as necessary. We can at least check
823 "LoopSimplify has no excuse for missing loop header info!");
847 // FIXME: This routine is being called mid-way through the loop
848 // as loop passes destroy this analysis. That's actually fine, but we have no
850 // hoisted out of the loop pass manager we can add back verification here.
