Lines Matching refs:Loop
1 //===-- UnrollLoop.cpp - Loop unrolling utilities -------------------------===//
10 // This file implements some loop unrolling utilities. It does not define any
11 // actual pass or policy, but provides a single function to perform loop
41 #define DEBUG_TYPE "loop-unroll"
70 /// successful references to the containing loop must be removed from
77 SmallPtrSetImpl<Loop *> &ForgottenLoops) {
111 // ScalarEvolution holds references to loop exit blocks.
113 if (Loop *L = LI->getLoopFor(BB)) {
129 /// Unroll the given loop by Count. The loop must be in LCSSA form. Returns true
130 /// if unrolling was successful, or false if the loop was unmodified. Unrolling
131 /// can only fail when the loop's latch block is not terminated by a conditional
133 /// loop unrolling will mostly produce more code that is no faster.
135 /// TripCount is generally defined as the number of times the loop header
138 /// exits were taken. Note that UnrollLoop assumes that the loop counter test
140 /// test. In other words, control may exit the loop prior to TripCount
141 /// iterations via an early branch, but control may not exit the loop from the
145 /// execute without exiting the loop.
150 /// iterations before branching into the unrolled loop. UnrollLoop will not
151 /// runtime-unroll the loop if computing RuntimeTripCount will be expensive and
158 bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
165 DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n");
171 DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n");
177 DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n");
185 // The loop-rotate pass can be helpful to avoid this in many cases.
187 " Can't unroll; loop not terminated by a conditional branch.\n");
192 // The loop-rotate pass can be helpful to avoid this in many cases.
194 " Won't unroll loop: address of header block is taken.\n");
217 // Are we eliminating the loop control altogether?
221 Loop *ParentL = L->getParentLoop();
227 // figure out the loop trip count and the unroll-runtime
236 // Notify ScalarEvolution that the loop will be substantially changed,
258 DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()
261 Twine("completely unrolled loop with ") +
266 "unrolled loop by a factor of " + Twine(Count) +
270 DEBUG(dbgs() << "UNROLLING loop %" << Header->getName()
288 // For the first iteration of the loop, we should use the precloned values for
307 // Stash the DFS iterators before adding blocks to the loop.
313 SmallDenseMap<const Loop *, Loop *, 4> NewLoops;
323 assert(LI->getLoopFor(*BB) == L && "Header should not be in a sub-loop");
326 // Figure out which loop New is in.
327 const Loop *OldLoop = LI->getLoopFor(*BB);
328 assert(OldLoop && "Should (at least) be in the loop being unrolled!");
330 Loop *&NewLoop = NewLoops[OldLoop];
332 // Found a new sub-loop.
336 Loop *NewLoopParent = NewLoops.lookup(OldLoop->getParentLoop());
338 "Expected parent loop before sub-loop in RPO");
339 NewLoop = new Loop;
342 // Forget the old loop, since its inputs may have changed.
350 // Loop over all of the PHI nodes in the block, changing them to use
399 // Loop over the PHI nodes in the original block, setting incoming values.
408 // If this value was defined in the loop, take the value defined by the
409 // last iteration of the loop.
453 // Remove phi operands at this loop exit
473 SmallPtrSet<Loop *, 4> ForgottenLoops;
489 // Incrementally updating domtree after loop unrolling would be easy.
493 // Simplify any new induction variables in the partially unrolled loop.
528 Loop *OuterL = L->getParentLoop();
529 // Update LoopInfo if the loop is completely removed.
535 // at least one layer outside of the loop that was unrolled so that any
536 // changes to the parent loop exposed by the unrolling are considered.
543 // LCSSA must be performed on the outermost affected loop. The unrolled
544 // loop's last loop latch is guaranteed to be in the outermost loop after
546 Loop *LatchLoop = LI->getLoopFor(Latches.back());
555 "Loops should be in LCSSA form after loop-unroll.");
562 /// Given an llvm.loop loop id metadata node, returns the loop hint metadata
563 /// node with the given name (for example, "llvm.loop.unroll.count"). If no
566 // First operand should refer to the loop id itself.
568 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
