Lines Matching refs:Loop
1 //===-- UnrollLoopRuntime.cpp - Runtime Loop unrolling utilities ----------===//
10 // This file implements some loop unrolling utilities for loops with run-time
19 // unrolled loop to execute the 'left over' iterations. Other strategies
20 // include generate a loop before or after the unrolled loop.
39 #define DEBUG_TYPE "loop-unroll"
44 /// Connect the unrolling prolog code to the original loop.
52 /// - Add a PHI operand to a PHI node at the loop exit block
53 /// for values that exit the prolog and go around the loop.
54 /// - Branch around the original loop if the trip count is less
57 static void ConnectProlog(Loop *L, Value *TripCount, unsigned Count,
62 assert(Latch && "Loop must have a latch");
64 // Create a PHI node for each outgoing value from the original loop
68 // the loop header or the loop exit block.
78 // Adding a value to the new PHI node from the original loop preheader.
98 // PHI node is in the original loop block, or the exit block.
107 // Create a branch around the orignal loop, which is taken if the
114 assert(Exit && "Loop must have a single exit block only");
115 // Split the exit to maintain loop canonicalization guarantees
124 // Add the branch to the exit block (around the unrolled loop)
129 /// Create a clone of the blocks in a loop and connect them together.
130 /// This function doesn't create a clone of the loop structure.
133 /// for the values in the current loop instance. LVMap contains
134 /// the values from the last loop instance. We need the LVMap values
135 /// to update the initial values for the current loop instance.
137 static void CloneLoopBlocks(Loop *L,
153 // For each block in the original loop, create a new copy,
159 if (Loop *ParentLoop = L->getParentLoop())
169 // previously cloned loop.
195 // LastValueMap is updated with the values for the current loop
203 /// Insert code in the prolog code when unrolling a loop with a
206 /// This method assumes that the loop unroll factor is total number
207 /// of loop bodes in the loop after unrolling. (Some folks refer
209 /// We assume also that the loop unroll factor is a power-of-two. So, after
210 /// unrolling the loop, the number of loop bodies executed is 2,
216 /// if (extraiters == 0) jump Loop:
224 /// Loop:
228 bool llvm::UnrollRuntimeLoopProlog(Loop *L, unsigned Count, LoopInfo *LI,
234 // Make sure the loop is in canonical form, and there is a single
253 // Add 1 since the backedge count doesn't include the first loop iteration
260 // Count is the loop unroll factor, the number of extra copies added + 1.
264 // If this loop is nested, then the loop unroller changes the code in
265 // parent loop, so the Scalar Evolution pass needs to be run again
266 if (Loop *ParentLoop = L->getParentLoop())
273 // prolog code and one for a new loop preheader
279 // extra iterations = run-time trip count % (loop unroll factor + 1)
280 SCEVExpander Expander(*SE, "loop-unroll");
287 // Check if for no extra iterations, then jump to unrolled loop. We have to
294 // Branch to either the extra iterations or the unrolled loop
295 // We will fix up the true branch label when adding loop body copies
307 // Get an ordered list of blocks in the loop to help with the ordering of the
313 // For each extra loop iteration, create a copy of the loop's basic blocks
321 // Clone all the basic blocks in the loop, but we don't clone the loop
327 // Insert the cloned blocks into function just before the original loop
331 // Generate the code for the comparison which determines if the loop
341 if (Loop *ParentLoop = L->getParentLoop()) {
342 // Add the new block to the parent loop, if needed
351 // Branch to either the extra iterations or the unrolled loop
370 // Connect the prolog code to the original loop and update the
