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
40 #define DEBUG_TYPE "loop-simplify"
80 Loop *L;
81 virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
84 // We need loop information to identify the loops...
101 bool ProcessLoop(Loop *L, LPPassManager &LPM);
102 BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
103 BasicBlock *InsertPreheaderForLoop(Loop *L);
104 Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM,
106 BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader);
109 Loop *L);
114 INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
118 INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
128 bool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) {
141 /// ProcessLoop - Walk the loop structure in depth first order, ensuring that
144 bool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) {
148 // Check to see that no blocks (other than the header) in this loop have
149 // predecessors that are not in the loop. This is not valid for natural
152 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
164 // Delete each unique out-of-loop (and thus dead) predecessor.
184 // the direction which will exit the loop. This will help simplify loop
200 // This may make the loop analyzable, force SCEV recomputation.
208 // Does the loop already have a preheader? If so, don't insert one.
218 // Next, check to make sure that all exit nodes of the loop only have
219 // predecessors that are inside of the loop. This check guarantees that the
220 // loop preheader/header will dominate the exit blocks. If the exit block has
221 // predecessors from outside of the loop, split the edge now.
232 // Must be exactly this loop: no subloops, parent loops, or non-loop preds
244 // preheader and from multiple backedges), we must adjust the loop.
247 // If this is really a nested loop, rip it out into a child loop. Don't do
253 // This is a big restructuring change, reprocess the whole loop.
262 // loop header.
270 // Scan over the PHI nodes in the loop header. Since they now have only two
271 // incoming values (the loop is canonicalized), we may have simplified the PHI
283 // If this loop has multiple exits and the exits all go to the same
287 // function), however this code is loop-aware, where SimplifyCFG is
289 // loop-invariant instructions out of the way to open up more
331 // Success. The block is now dead, so remove it from the loop,
336 // If any reachable control flow within this loop has changed, notify
337 // ScalarEvolution. Currently assume the parent loop doesn't change
339 // in the parent loop change, then we need call to forgetLoop() for the
366 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
370 BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) {
373 // Compute the set of predecessors of the loop that are not in the loop.
378 if (!L->contains(P)) { // Coming in from outside the loop?
379 // If the loop is branched to from an indirect branch, we won't
380 // be able to fully transform the loop, because it prohibits
389 // Split out the loop pre-header.
413 /// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit
415 /// outside of the loop.
416 BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
421 loop is exited via an indirect branch.
428 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?");
466 /// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
468 static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT,
493 // being placed inside the loop body, e.g. when the loop hasn't been rotated.
496 Loop *L) {
509 // block that neighbors a BB actually in the loop.
522 // the loop.
529 /// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of
530 /// them out into a nested loop. This is important for code that looks like
533 /// Loop:
535 /// br cond, Loop, Next
537 /// br cond2, Loop, Out
540 /// loop. PHI nodes with unchanging values on one backedge correspond to values
541 /// that change in the "outer" loop, but not in the "inner" loop.
543 /// If we are able to separate out a loop, return the new outer loop that was
546 Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM,
559 // Pull out all predecessors that have varying values in the loop. This
572 DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");
575 // this loop, tell it to forget them, because we're about to
588 // Create the new outer loop.
589 Loop *NewOuter = new Loop();
591 // Change the parent loop to use the outer loop as its child now.
592 if (Loop *Parent = L->getParentLoop())
597 // L is now a subloop of our outer loop.
600 // Add the new loop to the pass manager queue.
603 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
608 // SplitBlockPredecessors for the outer loop.
612 // the Outer loop now.
620 // Scan all of the loop children of L, moving them to OuterLoop if they are
621 // not part of the inner loop.
622 const std::vector<Loop*> &SubLoops = L->getSubLoops();
625 ++I; // Loop remains in L
647 /// InsertUniqueBackedgeBlock - This method is called when the specified loop
649 /// backedges to target a new basic block and have that block branch to the loop
653 LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) {
656 // Get information about the loop
667 // Figure out which basic blocks contain back-edges to the loop header.
699 // Loop over the PHI node, moving all entries except the one for the
754 // Update Loop Information - we know that this block is now in the current
755 // loop and all parent loops.
767 // not possible to transform a loop as necessary. We can at least check
780 "LoopSimplify has no excuse for missing loop header info!");
