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.
44 #define DEBUG_TYPE "loop-unroll"
49 /// Connect the unrolling prolog code to the original loop.
57 /// - Add a PHI operand to a PHI node at the loop exit block
58 /// for values that exit the prolog and go around the loop.
59 /// - Branch around the original loop if the trip count is less
62 static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
68 assert(Latch && "Loop must have a latch");
70 // Create a PHI node for each outgoing value from the original loop
74 // the loop header or the loop exit block.
84 // Adding a value to the new PHI node from the original loop preheader.
104 // PHI node is in the original loop block, or the exit block.
113 // Create a branch around the orignal loop, which is taken if there are no
122 // and all of the iterations of this loop were executed by the prologue. Note
127 assert(Exit && "Loop must have a single exit block only");
128 // Split the exit to maintain loop canonicalization guarantees
132 // Add the branch to the exit block (around the unrolled loop)
137 /// Create a clone of the blocks in a loop and connect them together.
138 /// If UnrollProlog is true, loop structure will not be cloned, otherwise a new
139 /// loop will be created including all cloned blocks, and the iterator of it
142 static void CloneLoopBlocks(Loop *L, Value *NewIter, const bool UnrollProlog,
153 Loop *NewLoop = nullptr;
154 Loop *ParentLoop = L->getParentLoop();
156 NewLoop = new Loop();
163 // For each block in the original loop, create a new copy,
183 // InsertBot. If not, create a loop back to cloned head.
207 // cloned loop.
225 // Add unroll disable metadata to disable future unrolling for this loop.
231 // First remove any existing loop unrolling metadata.
237 IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
246 DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
251 // Set operand 0 to refer to the loop id itself.
257 /// Insert code in the prolog code when unrolling a loop with a
260 /// This method assumes that the loop unroll factor is total number
261 /// of loop bodes in the loop after unrolling. (Some folks refer
263 /// We assume also that the loop unroll factor is a power-of-two. So, after
264 /// unrolling the loop, the number of loop bodies executed is 2,
270 /// if (extraiters == 0) jump Loop:
276 /// Loop:
280 bool llvm::UnrollRuntimeLoopProlog(Loop *L, unsigned Count,
288 // Make sure the loop is in canonical form, and there is a single
307 // Add 1 since the backedge count doesn't include the first loop iteration
315 SCEVExpander Expander(*SE, DL, "loop-unroll");
320 // Count is the loop unroll factor, the number of extra copies added + 1.
329 // If this loop is nested, then the loop unroller changes the code in
330 // parent loop, so the Scalar Evolution pass needs to be run again
331 if (Loop *ParentLoop = L->getParentLoop())
337 // prolog code and one for a new loop preheader
343 // extra iterations = run-time trip count % (loop unroll factor + 1)
353 // 1. there are no iteration to be run in the prologue loop
358 // number of iterations that remain to be run in the original loop is a
364 // Branch to either the extra iterations or the cloned/unrolled loop
365 // We will fix up the true branch label when adding loop body copies
372 // Get an ordered list of blocks in the loop to help with the ordering of the
378 // For each extra loop iteration, create a copy of the loop's basic blocks
387 // Clone all the basic blocks in the loop. If Count is 2, we don't clone
388 // the loop, otherwise we create a cloned loop to execute the extra
393 // Insert the cloned blocks into function just before the original loop
408 // Connect the prolog code to the original loop and update the
