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.
35 template class llvm::LoopBase<BasicBlock, Loop>;
36 template class llvm::LoopInfoBase<BasicBlock, Loop>;
45 VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
46 cl::desc("Verify loop info (time consuming)"));
49 INITIALIZE_PASS_BEGIN(LoopInfo, "loops", "Natural Loop Information", true, true)
51 INITIALIZE_PASS_END(LoopInfo, "loops", "Natural Loop Information", true, true)
53 // Loop identifier metadata name.
54 static const char *const LoopMDName = "llvm.loop";
57 // Loop implementation
60 /// isLoopInvariant - Return true if the specified value is loop invariant
62 bool Loop::isLoopInvariant(Value *V) const {
65 return true; // All non-instructions are loop invariant
69 /// specified instruction are loop invariant.
70 bool Loop::hasLoopInvariantOperands(Instruction *I) const {
79 /// loop and it can be hoisted, do so to make it trivially loop-invariant.
80 /// Return true if the value after any hoisting is loop invariant. This
85 /// If null, the terminator of the loop preheader is used.
87 bool Loop::makeLoopInvariant(Value *V, bool &Changed,
91 return true; // All non-instructions are loop-invariant.
95 /// loop and it can be hoisted, do so to make it trivially loop-invariant.
96 /// Return true if the instruction after any hoisting is loop invariant. This
101 /// If null, the terminator of the loop preheader is used.
103 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
105 // Test if the value is already loop-invariant.
123 // Don't hoist instructions with loop-variant operands.
134 /// getCanonicalInductionVariable - Check to see if the loop has a canonical
136 /// by one each time through the loop. If so, return the phi node that
142 PHINode *Loop::getCanonicalInductionVariable() const {
148 "Loop must have at least one backedge!");
150 if (PI == pred_end(H)) return 0; // dead loop
161 // Loop over all of the PHI nodes, looking for a canonical indvar.
178 /// isLCSSAForm - Return true if the Loop is in LCSSA form
179 bool Loop::isLCSSAForm(DominatorTree &DT) const {
195 // the use is anywhere in the loop. Most values are used in the same
208 /// isLoopSimplifyForm - Return true if the Loop is in the form that
211 bool Loop::isLoopSimplifyForm() const {
213 // exits have all their predecessors inside the loop.
217 /// isSafeToClone - Return true if the loop body is safe to clone in practice.
218 /// Routines that reform the loop CFG and split edges often fail on indirectbr.
219 bool Loop::isSafeToClone() const {
220 // Return false if any loop blocks contain indirectbrs, or there are any calls
222 for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) {
240 MDNode *Loop::getLoopID() const {
245 // Go through each predecessor of the loop header and check the
252 // Check if this terminator branches to the loop header.
274 void Loop::setLoopID(MDNode *LoopID) const {
275 assert(LoopID && "Loop ID should not be null");
276 assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
277 assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");
294 bool Loop::isAnnotatedParallel() const {
300 // The loop branch contains the parallel loop metadata. In order to ensure
301 // that any parallel-loop-unaware optimization pass hasn't added loop-carried
302 // dependencies (thus converted the loop back to a sequential loop), check
303 // that all the memory instructions in the loop contain parallelism metadata
304 // that point to the same unique "loop id metadata" the loop branch does.
315 // The memory instruction can refer to the loop identifier metadata
317 // nested parallel loops). The loop identifier metadata refers to
337 /// hasDedicatedExits - Return true if no exit block for the loop
338 /// has a predecessor that is outside the loop.
339 bool Loop::hasDedicatedExits() const {
343 // Each predecessor of each exit block of a normal loop is contained
344 // within the loop.
356 /// getUniqueExitBlocks - Return all unique successor blocks of this loop.
358 /// This assumes that loop exits are in canonical form.
361 Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const {
363 "getUniqueExitBlocks assumes the loop has canonical form exits!");
378 // If block is inside the loop then it is not a exit block.
414 BasicBlock *Loop::getUniqueExitBlock() const {
423 void Loop::dump() const {
433 /// Find the new parent loop for all blocks within the "unloop" whose last
436 Loop *Unloop;
443 // subloop's new parent will be the nearest loop reachable from either its own
444 // exits *or* any of its nested loop's exits.
445 DenseMap<Loop*, Loop*> SubloopParents;
452 UnloopUpdater(Loop *UL, LoopInfo *LInfo) :
462 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
466 /// updateBlockParents - Update the parent loop for all blocks that are directly
470 // Perform a post order CFG traversal of all blocks within this loop,
471 // propagating the nearest loop from sucessors to predecessors.
476 Loop *L = LI->getLoopFor(*POI);
477 Loop *NL = getNearestLoop(*POI, L);
492 // Each irreducible loop within the unloop induces a round of iteration using
498 // Iterate over the postorder list of blocks, propagating the nearest loop
504 Loop *L = LI->getLoopFor(*POI);
505 Loop *NL = getNearestLoop(*POI, L);
520 // ancestors below the new parent loop.
521 for (Loop::block_iterator BI = Unloop->block_begin(),
523 Loop *OuterParent = LI->getLoopFor(*BI);
531 for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent;
533 assert(OldParent && "new loop is not an ancestor of the original");
539 /// updateSubloopParents - Update the parent loop for all subloops directly
543 Loop *Subloop = *llvm::prior(Unloop->end());
547 if (Loop *Parent = SubloopParents[Subloop])
554 /// getNearestLoop - Return the nearest parent loop among this block's
559 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
563 Loop *NearLoop = BBLoop;
565 Loop *Subloop = 0;
571 assert(Subloop && "subloop is not an ancestor of the original loop");
587 Loop *L = LI->getLoopFor(*I);
609 // Handle critical edges from Unloop into a sibling loop.
613 // Remember the nearest parent loop among successors or subloop exits.
633 /// updateUnloop - The last backedge has been removed from a loop--now the
635 /// update the loop tree. We don't necessarily have valid dominators at this
636 /// point, but LoopInfo is still valid except for the removal of this loop.
638 /// Note that Unloop may now be an empty loop. Calling Loop::getHeader without
640 void LoopInfo::updateUnloop(Loop *Unloop) {
642 // First handle the special case of no parent loop to simplify the algorithm.
644 // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
645 for (Loop::block_iterator I = Unloop->block_begin(),
657 // Remove the loop from the top-level LoopInfo object.
659 assert(I != LI.end() && "Couldn't find loop");
673 // Update the parent loop for all blocks within the loop. Blocks within
681 // Add direct subloops as children in their new parent loop.
684 // Remove unloop from its parent loop.
685 Loop *ParentLoop = Unloop->getParentLoop();
686 for (Loop::iterator I = ParentLoop->begin();; ++I) {
687 assert(I != ParentLoop->end() && "Couldn't find loop");
696 // LoopInfo is a FunctionPass, but verifying every loop in the function
698 // -verify-loop-info option can enable this. In order to perform some
700 // manually during loop pass sequences.
704 DenseSet<const Loop*> Loops;
706 assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
711 for (DenseMap<BasicBlock*, Loop*>::const_iterator I = LI.BBMap.begin(),
713 assert(Loops.count(I->second) && "orphaned loop");
731 /// Traverse the loop blocks and store the DFS result.
