1 //===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
13 // Loop pre-header insertion guarantees that there is a single, non-critical
14 // entry edge from outside of the loop to the loop header.  This simplifies a
17 // Loop exit-block insertion guarantees that all exit blocks from the loop
18 // (blocks which are outside of the loop that have predecessors inside of the
19 // loop) only have predecessors from inside of the loop (and are thus dominated
20 // by the loop header).  This simplifies transformations such as store-sinking
25 // Indirectbr instructions introduce several complications. If the loop
27 // to transform the loop and make these guarantees. Client code should check
37 // This pass obviously modifies the CFG, but updates loop information and
74 #define DEBUG_TYPE "loop-simplify"
79 // block' block.  This prevents the preheader from being placed inside the loop
80 // body, e.g. when the loop hasn't been rotated.
83                                      Loop *L) {  in placeSplitBlockCarefully()
96   // block that neighbors a BB actually in the loop.  in placeSplitBlockCarefully()
108   // the loop.  in placeSplitBlockCarefully()
114 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
118 BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT,  in InsertPreheaderForLoop()
123   // Compute the set of predecessors of the loop that are not in the loop.  in InsertPreheaderForLoop()
126     if (!L->contains(P)) {         // Coming in from outside the loop?  in InsertPreheaderForLoop()
127       // If the loop is branched to from an indirect terminator, we won't  in InsertPreheaderForLoop()
128       // be able to fully transform the loop, because it prohibits  in InsertPreheaderForLoop()
138   // Split out the loop pre-header.  in InsertPreheaderForLoop()
171 /// The first part of loop-nestification is to find a PHI node that tells
173 static PHINode *findPHIToPartitionLoops(Loop *L, DominatorTree *DT,  in findPHIToPartitionLoops()
196 /// If this loop has multiple backedges, try to pull one of them out into
197 /// a nested loop.
202 ///  Loop:
204 ///     br cond, Loop, Next
206 ///     br cond2, Loop, Out
209 /// loop.  PHI nodes with unchanging values on one backedge correspond to values
210 /// that change in the "outer" loop, but not in the "inner" loop.
212 /// If we are able to separate out a loop, return the new outer loop that was
215 static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,  in separateNestedLoop()
226   // inner loop. But blocks meant for the inner loop will be  in separateNestedLoop()
251   // Pull out all predecessors that have varying values in the loop.  This  in separateNestedLoop()
264   LLVM_DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");  in separateNestedLoop()
267   // this loop, tell it to forget them, because we're about to  in separateNestedLoop()
279   // Create the new outer loop.  in separateNestedLoop()
280   Loop *NewOuter = LI->AllocateLoop();  in separateNestedLoop()
282   // Change the parent loop to use the outer loop as its child now.  in separateNestedLoop()
283   if (Loop *Parent = L->getParentLoop())  in separateNestedLoop()
288   // L is now a subloop of our outer loop.  in separateNestedLoop()
295   // SplitBlockPredecessors for the outer loop.  in separateNestedLoop()
299   // the Outer loop now.  in separateNestedLoop()
306   // Scan all of the loop children of L, moving them to OuterLoop if they are  in separateNestedLoop()
307   // not part of the inner loop.  in separateNestedLoop()
308   const std::vector<Loop*> &SubLoops = L->getSubLoops();  in separateNestedLoop()
311       ++I;   // Loop remains in L  in separateNestedLoop()
332   // Split edges to exit blocks from the inner loop, if they emerged in the  in separateNestedLoop()
338     // L, can now be used in NewOuter loop. We need to insert phi-nodes for them  in separateNestedLoop()
341     // inside a newly created loop of defs from inner loops as those would  in separateNestedLoop()
352 /// This method is called when the specified loop has more than one
356 /// and have that block branch to the loop header.  This ensures that loops
358 static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader,  in insertUniqueBackedgeBlock()
363   // Get information about the loop  in insertUniqueBackedgeBlock()
374   // Figure out which basic blocks contain back-edges to the loop header.  in insertUniqueBackedgeBlock()
404     // Loop over the PHI node, moving all entries except the one for the  in insertUniqueBackedgeBlock()
449   // If one of the backedges has llvm.loop metadata attached, we remove  in insertUniqueBackedgeBlock()
463   // Update Loop Information - we know that this block is now in the current  in insertUniqueBackedgeBlock()
464   // loop and all parent loops.  in insertUniqueBackedgeBlock()
477 /// Simplify one loop and queue further loops for simplification.
478 static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,  in simplifyOneLoop()
488   // Check to see that no blocks (other than the header) in this loop have  in simplifyOneLoop()
489   // predecessors that are not in the loop.  This is not valid for natural  in simplifyOneLoop()
501     // Delete each unique out-of-loop (and thus dead) predecessor.  in simplifyOneLoop()
519   // the direction which will exit the loop. This will help simplify loop  in simplifyOneLoop()
539   // Does the loop already have a preheader?  If so, don't insert one.  in simplifyOneLoop()
547   // Next, check to make sure that all exit nodes of the loop only have  in simplifyOneLoop()
548   // predecessors that are inside of the loop.  This check guarantees that the  in simplifyOneLoop()
549   // loop preheader/header will dominate the exit blocks.  If the exit block has  in simplifyOneLoop()
550   // predecessors from outside of the loop, split the edge now.  in simplifyOneLoop()
558   // preheader and from multiple backedges), we must adjust the loop.  in simplifyOneLoop()
561     // If this is really a nested loop, rip it out into a child loop.  Don't do  in simplifyOneLoop()
565       if (Loop *OuterL = separateNestedLoop(L, Preheader, DT, LI, SE,  in simplifyOneLoop()
568         // Enqueue the outer loop as it should be processed next in our  in simplifyOneLoop()
572         // This is a big restructuring change, reprocess the whole loop.  in simplifyOneLoop()
582     // loop header.  in simplifyOneLoop()
593   // Scan over the PHI nodes in the loop header.  Since they now have only two  in simplifyOneLoop()
594   // incoming values (the loop is canonicalized), we may have simplified the PHI  in simplifyOneLoop()
608   // If this loop has multiple exits and the exits all go to the same  in simplifyOneLoop()
612   // function), however this code is loop-aware, where SimplifyCFG is  in simplifyOneLoop()
614   // loop-invariant instructions out of the way to open up more  in simplifyOneLoop()
665       // Success. The block is now dead, so remove it from the loop,  in simplifyOneLoop()
700 bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,  in simplifyLoop()
706   // If we're asked to preserve LCSSA, the loop nest needs to start in LCSSA  in simplifyLoop()
717   SmallVector<Loop *, 4> Worklist;  in simplifyLoop()
724     Loop *L2 = Worklist[Idx];  in simplifyLoop()
732   // Changing exit conditions for blocks may affect exit counts of this loop and  in simplifyLoop()
735   // loop is going to be the same for all child loops.  in simplifyLoop()
754       // We need loop information to identify the loops...  in getAnalysisUsage()
779 INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
784 INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
812   // Simplify each loop nest in the function.  in runOnFunction()
819         *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); });  in runOnFunction()
820     assert(InLCSSA && "LCSSA is broken after loop-simplify.");  in runOnFunction()
869 static void verifyLoop(Loop *L) {
871   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
876   // not possible to transform a loop as necessary. We can at least check
888            "LoopSimplify has no excuse for missing loop header info!");
912   // FIXME: This routine is being called mid-way through the loop pass manager  in verifyAnalysis()
913   // as loop passes destroy this analysis. That's actually fine, but we have no  in verifyAnalysis()
915   // hoisted out of the loop pass manager we can add back verification here.  in verifyAnalysis()