1 //===-- UnrollLoopRuntime.cpp - Runtime Loop unrolling utilities ----------===//
9 // This file implements some loop unrolling utilities for loops with run-time
18 // unrolled loop to execute the 'left over' iterations before or after the
19 // unrolled loop.
47 #define DEBUG_TYPE "loop-unroll"
59 // Probability that the loop trip count is so small that after the prolog
60 // we do not enter the unrolled loop at all.
61 // It is unlikely that the loop trip count is smaller than the unroll factor;
64 // Probability that the loop trip count is so small that we skip the unrolled
65 // loop completely and immediately enter the epilogue loop.
66 // It is unlikely that the loop trip count is smaller than the unroll factor;
70 /// Connect the unrolling prolog code to the original loop.
78 /// - Add a PHI operand to a PHI node at the loop exit block
79 ///   for values that exit the prolog and go around the loop.
80 /// - Branch around the original loop if the trip count is less
83 static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,  in ConnectProlog()
90   // Loop structure should be the following:  in ConnectProlog()
102   assert(Latch && "Loop must have a latch");  in ConnectProlog()
105   // Create a PHI node for each outgoing value from the original loop  in ConnectProlog()
109   // the loop header or the loop exit block.  in ConnectProlog()
115       // prolog loop) contains only one predecessor from the loop, i.e. the  in ConnectProlog()
118       // original loop.  in ConnectProlog()
121       // Adding a value to the new PHI node from the original loop preheader.  in ConnectProlog()
124         // Succ is loop header.  in ConnectProlog()
144       // PHI node is in the original loop block, or the exit block.  in ConnectProlog()
153   // Make sure that created prolog loop is in simplified form  in ConnectProlog()
155   Loop *PrologLoop = LI->getLoopFor(PrologLatch);  in ConnectProlog()
165   // Create a branch around the original loop, which is taken if there are no  in ConnectProlog()
174   // loop were executed by the prologue.  Note that if BECount <u (Count - 1)  in ConnectProlog()
178   // Split the exit to maintain loop canonicalization guarantees  in ConnectProlog()
182   // Add the branch to the exit block (around the unrolled loop)  in ConnectProlog()
185     // Assume loop is nearly always entered.  in ConnectProlog()
199 /// Connect the unrolling epilog code to the original loop.
205 /// - Update PHI nodes at the unrolling loop exit and epilog loop exit
206 /// - Create PHI nodes at the unrolling loop exit to combine
207 ///   values that exit the unrolling loop code and jump around it.
208 /// - Update PHI operands in the epilog loop by the new PHI nodes
209 /// - Branch around the epilog loop if extra iters (ModVal) is zero.
211 static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,  in ConnectEpilog()
218   assert(Latch && "Loop must have a latch");  in ConnectEpilog()
221   // Loop structure should be the following:  in ConnectEpilog()
255     // Add incoming PreHeader from branch around the Loop  in ConnectEpilog()
262       // If value comes from an instruction in the loop add VMap value.  in ConnectEpilog()
264     // For the instruction out of the loop, constant or undefined value  in ConnectEpilog()
281   // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).  in ConnectEpilog()
282   // Update corresponding PHI nodes in epilog loop.  in ConnectEpilog()
288       // Add new PHI nodes to the loop exit block and update epilog  in ConnectEpilog()
292       // Adding a value to the new PHI node from the unrolling loop preheader.  in ConnectEpilog()
294       // Adding a value to the new PHI node from the unrolling loop latch.  in ConnectEpilog()
298       // node.  Corresponding instruction in epilog loop should be PHI.  in ConnectEpilog()
307   assert(Exit && "Loop must have a single exit block only");  in ConnectEpilog()
308   // Split the epilogue exit to maintain loop canonicalization guarantees  in ConnectEpilog()
312   // Add the branch to the exit block (around the unrolling loop)  in ConnectEpilog()
326   // Split the main loop exit to maintain canonicalization guarantees.  in ConnectEpilog()
332 /// Create a clone of the blocks in a loop and connect them together. A new
333 /// loop will be created including all cloned blocks, and the iterator of the
334 /// new loop switched to count NewIter down to 0.
336 /// InsertTop should be new preheader, InsertBot new loop exit.
337 /// Returns the new cloned loop that is created.
338 static Loop *
339 CloneLoopBlocks(Loop *L, Value *NewIter, const bool UseEpilogRemainder,  in CloneLoopBlocks()
352   Loop *ParentLoop = L->getParentLoop();  in CloneLoopBlocks()
356   // For each block in the original loop, create a new copy,  in CloneLoopBlocks()
376         // Copy information from original loop to unrolled loop.  in CloneLoopBlocks()
383       // For the last block, create a loop back to cloned head.  in CloneLoopBlocks()
404           // Note: We do not enter this loop for zero-remainders. The check  in CloneLoopBlocks()
405           // is at the end of the loop. We assume equal distribution between  in CloneLoopBlocks()
426   // cloned loop.  in CloneLoopBlocks()
439   Loop *NewLoop = NewLoops[L];  in CloneLoopBlocks()
443   // Only add loop metadata if the loop is not going to be completely  in CloneLoopBlocks()
453     // Do not setLoopAlreadyUnrolled if loop attributes have been defined  in CloneLoopBlocks()
458   // Add unroll disable metadata to disable future unrolling for this loop.  in CloneLoopBlocks()
463 /// Returns true if we can profitably unroll the multi-exit loop L. Currently,
466     Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,  in canProfitablyUnrollMultiExitLoop()
473   // The main pain point with multi-exit loop unrolling is that once unrolled,  in canProfitablyUnrollMultiExitLoop()
475   // There are branches within the unrolled loop that go to the OtherExits.  in canProfitablyUnrollMultiExitLoop()
486   // limits the total number of branches in the unrolled loop to be atmost  in canProfitablyUnrollMultiExitLoop()
522     //  1. There are no iterations to be run in the prolog/epilog loop.  in CreateTripRemainder()
527     // the number of iterations that remain to be run in the original loop is a  in CreateTripRemainder()
544 /// Insert code in the prolog/epilog code when unrolling a loop with a
547 /// This method assumes that the loop unroll factor is total number
548 /// of loop bodies in the loop after unrolling. (Some folks refer
550 /// We assume also that the loop unroll factor is a power-of-two. So, after
551 /// unrolling the loop, the number of loop bodies executed is 2,
558 ///        if (extraiters == 0) jump Loop:
564 /// Loop:
572 /// Loop:  LoopBody; (executes unroll_iter times);
574 ///        if (unroll_iter != 0) jump Loop:
583     Loop *L, unsigned Count, bool AllowExpensiveTripCount,  in UnrollRuntimeLoopRemainder()
586     const TargetTransformInfo *TTI, bool PreserveLCSSA, Loop **ResultLoop) {  in UnrollRuntimeLoopRemainder()
587   LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");  in UnrollRuntimeLoopRemainder()
592   // Make sure the loop is in canonical form.  in UnrollRuntimeLoopRemainder()
605     // The loop-rotate pass can be helpful to avoid this in many cases.  in UnrollRuntimeLoopRemainder()
608         << "Loop latch not terminated by a conditional branch.\n");  in UnrollRuntimeLoopRemainder()
616     // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the  in UnrollRuntimeLoopRemainder()
617     // targets of the Latch be an exit block out of the loop.  in UnrollRuntimeLoopRemainder()
620         << "One of the loop latch successors must be the exit block.\n");  in UnrollRuntimeLoopRemainder()
627   // Support only single exit and exiting block unless multi-exit loop  in UnrollRuntimeLoopRemainder()
639           << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "  in UnrollRuntimeLoopRemainder()
651   // which is proven to be the only exiting block in this loop. This is same as  in UnrollRuntimeLoopRemainder()
652   // calculating getBackedgeTakenCount on the loop (which computes SCEV for all  in UnrollRuntimeLoopRemainder()
662   // Add 1 since the backedge count doesn't include the first loop iteration.  in UnrollRuntimeLoopRemainder()
674   SCEVExpander Expander(*SE, DL, "loop-unroll");  in UnrollRuntimeLoopRemainder()
691   // Loop structure is the following:  in UnrollRuntimeLoopRemainder()
707     // Split PreHeader to insert a branch around loop for unrolling.  in UnrollRuntimeLoopRemainder()
714     // original Loop.  in UnrollRuntimeLoopRemainder()
715     // Fix this by setting Loop's DebugLoc to NewExit.  in UnrollRuntimeLoopRemainder()
718     // Split NewExit to insert epilog remainder loop.  in UnrollRuntimeLoopRemainder()
723     // by assumption there must be another loop exit which branches to the  in UnrollRuntimeLoopRemainder()
724     // outer loop and we must adjust the loop for the newly inserted blocks  in UnrollRuntimeLoopRemainder()
726     // loop. Note that this leaves loopinfo temporarily out of sync with the  in UnrollRuntimeLoopRemainder()
727     // CFG until the actual epilogue loop is inserted.  in UnrollRuntimeLoopRemainder()
738     // Split the original preheader twice to insert prolog remainder loop  in UnrollRuntimeLoopRemainder()
748   // Loop structure should be the following:  in UnrollRuntimeLoopRemainder()
760   // Calculate conditions for branch around loop for unrolling  in UnrollRuntimeLoopRemainder()
761   // in epilog case and around prolog remainder loop in prolog case.  in UnrollRuntimeLoopRemainder()
763   //  extra iterations = run-time trip count % loop unroll factor  in UnrollRuntimeLoopRemainder()
796   // Branch to either remainder (extra iterations) loop or unrolling loop.  in UnrollRuntimeLoopRemainder()
799     // Assume loop is nearly always entered.  in UnrollRuntimeLoopRemainder()
812   // Get an ordered list of blocks in the loop to help with the ordering of the  in UnrollRuntimeLoopRemainder()
818   // For each extra loop iteration, create a copy of the loop's basic blocks  in UnrollRuntimeLoopRemainder()
825   // Clone all the basic blocks in the loop. If Count is 2, we don't clone  in UnrollRuntimeLoopRemainder()
826   // the loop, otherwise we create a cloned loop to execute the extra  in UnrollRuntimeLoopRemainder()
830   Loop *remainderLoop = CloneLoopBlocks(  in UnrollRuntimeLoopRemainder()
837   // Now the loop blocks are cloned and the other exiting blocks from the  in UnrollRuntimeLoopRemainder()
838   // remainder are connected to the original Loop's exit blocks. The remaining  in UnrollRuntimeLoopRemainder()
839   // work is to update the phi nodes in the original loop, and take in the  in UnrollRuntimeLoopRemainder()
843     // loop will be used through these phi nodes at the exit blocks that are  in UnrollRuntimeLoopRemainder()
876   // from both the original loop and the remainder code reaching the exit  in UnrollRuntimeLoopRemainder()
877   // blocks. While the IDom of these exit blocks were from the original loop,  in UnrollRuntimeLoopRemainder()
878   // now the IDom is the preheader (which decides whether the original loop or  in UnrollRuntimeLoopRemainder()
882     // NB! We have to examine the dom children of all loop blocks, not just  in UnrollRuntimeLoopRemainder()
898   // Loop structure should be the following:  in UnrollRuntimeLoopRemainder()
926     // Connect the epilog code to the original loop and update the  in UnrollRuntimeLoopRemainder()
931     // Update counter in loop for unrolling.  in UnrollRuntimeLoopRemainder()
950     // Connect the prolog code to the original loop and update the  in UnrollRuntimeLoopRemainder()
956   // If this loop is nested, then the loop unroller changes the code in the any  in UnrollRuntimeLoopRemainder()
960   // Verify that the Dom Tree and Loop Info are correct.  in UnrollRuntimeLoopRemainder()
968   // For unroll factor 2 remainder loop will have 1 iteration.  in UnrollRuntimeLoopRemainder()
971     // (e.g. breakLoopBackedgeAndSimplify) and reused in loop-deletion.  in UnrollRuntimeLoopRemainder()
979     // Simplify loop values after breaking the backedge  in UnrollRuntimeLoopRemainder()
1007     // Generate dedicated exit blocks for the original loop, to preserve  in UnrollRuntimeLoopRemainder()
1010     // Generate dedicated exit blocks for the remainder loop if one exists, to  in UnrollRuntimeLoopRemainder()
1018     LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");  in UnrollRuntimeLoopRemainder()
1027            "A loop with a convergence heart does not allow runtime unrolling.");  in UnrollRuntimeLoopRemainder()