Lines Matching refs:Loop
1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
11 // and determine the loop depth of various nodes of the CFG. Note that the
13 // header node... not just a single natural loop.
34 template class llvm::LoopBase<BasicBlock, Loop>;
35 template class llvm::LoopInfoBase<BasicBlock, Loop>;
44 VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
45 cl::desc("Verify loop info (time consuming)"));
48 INITIALIZE_PASS_BEGIN(LoopInfo, "loops", "Natural Loop Information", true, true)
50 INITIALIZE_PASS_END(LoopInfo, "loops", "Natural Loop Information", true, true)
52 // Loop identifier metadata name.
53 static const char *const LoopMDName = "llvm.loop";
56 // Loop implementation
59 /// isLoopInvariant - Return true if the specified value is loop invariant
61 bool Loop::isLoopInvariant(Value *V) const {
64 return true; // All non-instructions are loop invariant
68 /// specified instruction are loop invariant.
69 bool Loop::hasLoopInvariantOperands(Instruction *I) const {
78 /// loop and it can be hoisted, do so to make it trivially loop-invariant.
79 /// Return true if the value after any hoisting is loop invariant. This
84 /// If null, the terminator of the loop preheader is used.
86 bool Loop::makeLoopInvariant(Value *V, bool &Changed,
90 return true; // All non-instructions are loop-invariant.
94 /// loop and it can be hoisted, do so to make it trivially loop-invariant.
95 /// Return true if the instruction after any hoisting is loop invariant. This
100 /// If null, the terminator of the loop preheader is used.
102 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
104 // Test if the value is already loop-invariant.
122 // Don't hoist instructions with loop-variant operands.
133 /// getCanonicalInductionVariable - Check to see if the loop has a canonical
135 /// by one each time through the loop. If so, return the phi node that
141 PHINode *Loop::getCanonicalInductionVariable() const {
147 "Loop must have at least one backedge!");
149 if (PI == pred_end(H)) return nullptr; // dead loop
160 // Loop over all of the PHI nodes, looking for a canonical indvar.
177 /// isLCSSAForm - Return true if the Loop is in LCSSA form
178 bool Loop::isLCSSAForm(DominatorTree &DT) const {
189 // the use is anywhere in the loop. Most values are used in the same
202 /// isLoopSimplifyForm - Return true if the Loop is in the form that
205 bool Loop::isLoopSimplifyForm() const {
207 // exits have all their predecessors inside the loop.
211 /// isSafeToClone - Return true if the loop body is safe to clone in practice.
212 /// Routines that reform the loop CFG and split edges often fail on indirectbr.
213 bool Loop::isSafeToClone() const {
214 // Return false if any loop blocks contain indirectbrs, or there are any calls
216 for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) {
234 MDNode *Loop::getLoopID() const {
239 // Go through each predecessor of the loop header and check the
246 // Check if this terminator branches to the loop header.
268 void Loop::setLoopID(MDNode *LoopID) const {
269 assert(LoopID && "Loop ID should not be null");
270 assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
271 assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");
288 bool Loop::isAnnotatedParallel() const {
294 // The loop branch contains the parallel loop metadata. In order to ensure
295 // that any parallel-loop-unaware optimization pass hasn't added loop-carried
296 // dependencies (thus converted the loop back to a sequential loop), check
297 // that all the memory instructions in the loop contain parallelism metadata
298 // that point to the same unique "loop id metadata" the loop branch does.
306 // The memory instruction can refer to the loop identifier metadata
308 // nested parallel loops). The loop identifier metadata refers to
331 /// hasDedicatedExits - Return true if no exit block for the loop
332 /// has a predecessor that is outside the loop.
333 bool Loop::hasDedicatedExits() const {
334 // Each predecessor of each exit block of a normal loop is contained
335 // within the loop.
347 /// getUniqueExitBlocks - Return all unique successor blocks of this loop.
349 /// This assumes that loop exits are in canonical form.
352 Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const {
354 "getUniqueExitBlocks assumes the loop has canonical form exits!");
364 // If block is inside the loop then it is not a exit block.
400 BasicBlock *Loop::getUniqueExitBlock() const {
409 void Loop::dump() const {
419 /// Find the new parent loop for all blocks within the "unloop" whose last
422 Loop *Unloop;
429 // subloop's new parent will be the nearest loop reachable from either its own
430 // exits *or* any of its nested loop's exits.
431 DenseMap<Loop*, Loop*> SubloopParents;
438 UnloopUpdater(Loop *UL, LoopInfo *LInfo) :
448 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
452 /// updateBlockParents - Update the parent loop for all blocks that are directly
456 // Perform a post order CFG traversal of all blocks within this loop,
457 // propagating the nearest loop from sucessors to predecessors.
462 Loop *L = LI->getLoopFor(*POI);
463 Loop *NL = getNearestLoop(*POI, L);
478 // Each irreducible loop within the unloop induces a round of iteration using
484 // Iterate over the postorder list of blocks, propagating the nearest loop
490 Loop *L = LI->getLoopFor(*POI);
491 Loop *NL = getNearestLoop(*POI, L);
506 // ancestors below the new parent loop.
507 for (Loop::block_iterator BI = Unloop->block_begin(),
509 Loop *OuterParent = LI->getLoopFor(*BI);
517 for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent;
519 assert(OldParent && "new loop is not an ancestor of the original");
525 /// updateSubloopParents - Update the parent loop for all subloops directly
529 Loop *Subloop = *std::prev(Unloop->end());
533 if (Loop *Parent = SubloopParents[Subloop])
540 /// getNearestLoop - Return the nearest parent loop among this block's
545 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
549 Loop *NearLoop = BBLoop;
551 Loop *Subloop = nullptr;
557 assert(Subloop && "subloop is not an ancestor of the original loop");
573 Loop *L = LI->getLoopFor(*I);
595 // Handle critical edges from Unloop into a sibling loop.
599 // Remember the nearest parent loop among successors or subloop exits.
619 /// updateUnloop - The last backedge has been removed from a loop--now the
621 /// update the loop tree. We don't necessarily have valid dominators at this
622 /// point, but LoopInfo is still valid except for the removal of this loop.
624 /// Note that Unloop may now be an empty loop. Calling Loop::getHeader without
626 void LoopInfo::updateUnloop(Loop *Unloop) {
628 // First handle the special case of no parent loop to simplify the algorithm.
630 // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
631 for (Loop::block_iterator I = Unloop->block_begin(),
643 // Remove the loop from the top-level LoopInfo object.
645 assert(I != LI.end() && "Couldn't find loop");
659 // Update the parent loop for all blocks within the loop. Blocks within
667 // Add direct subloops as children in their new parent loop.
670 // Remove unloop from its parent loop.
671 Loop *ParentLoop = Unloop->getParentLoop();
672 for (Loop::iterator I = ParentLoop->begin();; ++I) {
673 assert(I != ParentLoop->end() && "Couldn't find loop");
682 // LoopInfo is a FunctionPass, but verifying every loop in the function
684 // -verify-loop-info option can enable this. In order to perform some
686 // manually during loop pass sequences.
690 DenseSet<const Loop*> Loops;
692 assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
697 for (DenseMap<BasicBlock*, Loop*>::const_iterator I = LI.BBMap.begin(),
699 assert(Loops.count(I->second) && "orphaned loop");
717 /// Traverse the loop blocks and store the DFS result.
