Lines Matching full:loop
1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
10 // and determine the loop depth of various nodes of the CFG. Note that the
12 // header node... not just a single natural loop.
44 template class llvm::LoopBase<BasicBlock, Loop>;
45 template class llvm::LoopInfoBase<BasicBlock, Loop>;
54 VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
55 cl::Hidden, cl::desc("Verify loop info (time consuming)"));
58 // Loop implementation
61 bool Loop::isLoopInvariant(const Value *V) const { in isLoopInvariant()
64 return true; // All non-instructions are loop invariant in isLoopInvariant()
67 bool Loop::hasLoopInvariantOperands(const Instruction *I) const { in hasLoopInvariantOperands()
71 bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt, in makeLoopInvariant()
76 return true; // All non-instructions are loop-invariant. in makeLoopInvariant()
79 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, in makeLoopInvariant()
82 // Test if the value is already loop-invariant. in makeLoopInvariant()
100 // Don't hoist instructions with loop-variant operands. in makeLoopInvariant()
125 bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming, in getIncomingAndBackEdge()
132 assert(PI != pred_end(H) && "Loop must have at least one backedge!"); in getIncomingAndBackEdge()
135 return false; // dead loop in getIncomingAndBackEdge()
151 PHINode *Loop::getCanonicalInductionVariable() const { in getCanonicalInductionVariable()
158 // Loop over all of the PHI nodes, looking for a canonical indvar. in getCanonicalInductionVariable()
175 ICmpInst *Loop::getLatchCmpInst() const { in getLatchCmpInst()
184 /// Return the final value of the loop induction variable if found.
185 static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar, in findFinalIVValue()
202 std::optional<Loop::LoopBounds>
203 Loop::LoopBounds::getBounds(const Loop &L, PHINode &IndVar, in getBounds()
231 using Direction = Loop::LoopBounds::Direction;
233 ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const { in getCanonicalPredicate()
244 // Need to inverse the predicate when first successor is not the loop in getCanonicalPredicate()
275 Direction Loop::LoopBounds::getDirection() const { in getDirection()
288 std::optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const { in getBounds()
295 PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const { in getInductionVariable()
300 assert(Header && "Expected a valid loop header"); in getInductionVariable()
334 bool Loop::getInductionDescriptor(ScalarEvolution &SE, in getInductionDescriptor()
342 bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar, in isAuxiliaryInductionVariable()
344 // Located in the loop header in isAuxiliaryInductionVariable()
349 // No uses outside of the loop in isAuxiliaryInductionVariable()
364 // Incremented by a loop invariant step for each loop iteration in isAuxiliaryInductionVariable()
368 BranchInst *Loop::getLoopGuardBranch() const { in getLoopGuardBranch()
374 "Expecting a loop with valid preheader and latch"); in getLoopGuardBranch()
376 // Loop should be in rotate form. in getLoopGuardBranch()
403 // loop is GuardBI (return GuardBI), otherwise return nullptr. in getLoopGuardBranch()
412 bool Loop::isCanonical(ScalarEvolution &SE) const { in isCanonical()
432 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, in isBlockInLCSSAForm()
435 // Tokens can't be used in PHI nodes and live-out tokens prevent loop in isBlockInLCSSAForm()
452 // the use is anywhere in the loop. Most values are used in the same in isBlockInLCSSAForm()
463 bool Loop::isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens) const { in isLCSSAForm()
464 // For each block we check that it doesn't have any uses outside of this loop. in isLCSSAForm()
470 bool Loop::isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, in isRecursivelyLCSSAForm()
473 // innermost loop. This process will transitively guarantee that the current in isRecursivelyLCSSAForm()
474 // loop and all of the nested loops are in LCSSA form. in isRecursivelyLCSSAForm()
480 bool Loop::isLoopSimplifyForm() const { in isLoopSimplifyForm()
482 // exits have all their predecessors inside the loop. in isLoopSimplifyForm()
486 // Routines that reform the loop CFG and split edges often fail on indirectbr.
487 bool Loop::isSafeToClone() const { in isSafeToClone()
488 // Return false if any loop blocks contain indirectbrs, or there are any calls in isSafeToClone()
502 MDNode *Loop::getLoopID() const { in getLoopID()
526 void Loop::setLoopID(MDNode *LoopID) const { in setLoopID()
528 "Loop ID needs at least one operand"); in setLoopID()
530 "Loop ID should refer to itself"); in setLoopID()
538 void Loop::setLoopAlreadyUnrolled() { in setLoopAlreadyUnrolled()
542 MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable")); in setLoopAlreadyUnrolled()
545 Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD}); in setLoopAlreadyUnrolled()
549 void Loop::setLoopMustProgress() { in setLoopMustProgress()
552 MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress"); in setLoopMustProgress()
558 MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress")); in setLoopMustProgress()
565 bool Loop::isAnnotatedParallel() const { in isAnnotatedParallel()
572 findOptionMDForLoop(this, "llvm.loop.parallel_accesses"); in isAnnotatedParallel()
584 // The loop branch contains the parallel loop metadata. In order to ensure in isAnnotatedParallel()
585 // that any parallel-loop-unaware optimization pass hasn't added loop-carried in isAnnotatedParallel()
586 // dependencies (thus converted the loop back to a sequential loop), check in isAnnotatedParallel()
587 // that all the memory instructions in the loop belong to an access group that in isAnnotatedParallel()
588 // is parallel to this loop. in isAnnotatedParallel()
615 // The memory instruction can refer to the loop identifier metadata in isAnnotatedParallel()
617 // nested parallel loops). The loop identifier metadata refers to in isAnnotatedParallel()
632 DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); } in getStartLoc()
634 Loop::LocRange Loop::getLocRange() const { in getLocRange()
635 // If we have a debug location in the loop ID, then use it. in getLocRange()
638 // We use the first DebugLoc in the header as the start location of the loop in getLocRange()
640 // of the loop. in getLocRange()
667 std::string Loop::getLocStr() const { in getLocStr()
679 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); } in dump()
681 LLVM_DUMP_METHOD void Loop::dumpVerbose() const { in dumpVerbose()
691 /// Find the new parent loop for all blocks within the "unloop" whose last
694 Loop &Unloop;
701 // subloop's new parent will be the nearest loop reachable from either its own
702 // exits *or* any of its nested loop's exits.
703 DenseMap<Loop *, Loop *> SubloopParents;
710 UnloopUpdater(Loop *UL, LoopInfo *LInfo) : Unloop(*UL), LI(LInfo), DFS(UL) {} in UnloopUpdater()
719 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
723 /// Update the parent loop for all blocks that are directly contained within the
727 // Perform a post order CFG traversal of all blocks within this loop, in updateBlockParents()
728 // propagating the nearest loop from successors to predecessors. in updateBlockParents()
732 Loop *L = LI->getLoopFor(POI); in updateBlockParents()
733 Loop *NL = getNearestLoop(POI, L); in updateBlockParents()
747 // Each irreducible loop within the unloop induces a round of iteration using in updateBlockParents()
754 // Iterate over the postorder list of blocks, propagating the nearest loop in updateBlockParents()
761 Loop *L = LI->getLoopFor(*POI); in updateBlockParents()
762 Loop *NL = getNearestLoop(*POI, L); in updateBlockParents()
776 // ancestors below the new parent loop. in removeBlocksFromAncestors()
778 Loop *OuterParent = LI->getLoopFor(BB); in removeBlocksFromAncestors()
786 for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent; in removeBlocksFromAncestors()
788 assert(OldParent && "new loop is not an ancestor of the original"); in removeBlocksFromAncestors()
794 /// Update the parent loop for all subloops directly nested within unloop.
797 Loop *Subloop = *std::prev(Unloop.end()); in updateSubloopParents()
801 if (Loop *Parent = SubloopParents[Subloop]) in updateSubloopParents()
808 /// Return the nearest parent loop among this block's successors. If a successor
813 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { in getNearestLoop()
817 Loop *NearLoop = BBLoop; in getNearestLoop()
819 Loop *Subloop = nullptr; in getNearestLoop()
825 assert(Subloop && "subloop is not an ancestor of the original loop"); in getNearestLoop()
839 Loop *L = LI->getLoopFor(Succ); in getNearestLoop()
861 // Handle critical edges from Unloop into a sibling loop. in getNearestLoop()
865 // Remember the nearest parent loop among successors or subloop exits. in getNearestLoop()
887 void LoopInfo::erase(Loop *Unloop) { in erase()
888 assert(!Unloop->isInvalid() && "Loop has already been erased!"); in erase()
892 // First handle the special case of no parent loop to simplify the algorithm. in erase()
894 // Since BBLoop had no parent, Unloop blocks are no longer in a loop. in erase()
905 // Remove the loop from the top-level LoopInfo object. in erase()
907 assert(I != end() && "Couldn't find loop"); in erase()
921 // Update the parent loop for all blocks within the loop. Blocks within in erase()
929 // Add direct subloops as children in their new parent loop. in erase()
932 // Remove unloop from its parent loop. in erase()
933 Loop *ParentLoop = Unloop->getParentLoop(); in erase()
934 for (Loop::iterator I = ParentLoop->begin();; ++I) { in erase()
935 assert(I != ParentLoop->end() && "Couldn't find loop"); in erase()
953 const Loop *L = getLoopFor(I->getParent()); in wouldBeOutOfLoopUseRequiringLCSSA()
957 // Could be an exit bb of a subloop and contained in defining loop in wouldBeOutOfLoopUseRequiringLCSSA()
960 // We found a (new) out-of-loop use location, for a value defined in-loop. in wouldBeOutOfLoopUseRequiringLCSSA()
963 // common parent loop.) in wouldBeOutOfLoopUseRequiringLCSSA()
984 OS << "Loop info for function '" << F.getName() << "':\n"; in run()
989 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) { in printLoop()
993 OS << Banner << " (loop: "; in printLoop()
1008 OS << "\n; Loop:"; in printLoop()
1030 // No loop metadata node, no loop properties. in findOptionMDForLoopID()
1036 assert(LoopID->getOperand(0) == LoopID && "invalid loop id"); in findOptionMDForLoopID()
1051 // Loop property not found. in findOptionMDForLoopID()
1055 MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) { in findOptionMDForLoop()
1059 /// Find string metadata for loop
1065 llvm::findStringMetadataForLoop(const Loop *TheLoop, StringRef Name) { in findStringMetadataForLoop()
1075 llvm_unreachable("loop metadata has 0 or 1 operand"); in findStringMetadataForLoop()
1079 std::optional<bool> llvm::getOptionalBoolLoopAttribute(const Loop *TheLoop, in getOptionalBoolLoopAttribute()
1097 bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) { in getBooleanLoopAttribute()
1101 std::optional<int> llvm::getOptionalIntLoopAttribute(const Loop *TheLoop, in getOptionalIntLoopAttribute()
1115 int llvm::getIntLoopAttribute(const Loop *TheLoop, StringRef Name, in getIntLoopAttribute()
1120 CallBase *llvm::getLoopConvergenceHeart(const Loop *TheLoop) { in getLoopConvergenceHeart()
1126 // This is the heart if it uses a token defined outside the loop. The in getLoopConvergenceHeart()
1127 // verifier has already checked that only the loop intrinsic can use such in getLoopConvergenceHeart()
1140 bool llvm::isFinite(const Loop *L) { in isFinite()
1144 static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
1146 bool llvm::hasMustProgress(const Loop *L) { in hasMustProgress()
1150 bool llvm::isMustProgress(const Loop *L) { in isMustProgress()
1162 // First remove any existing loop metadata related to this transformation. in makePostTransformationMetadata()
1188 // llvm.loop.unroll.disable and llvm.loop.isvectorized. in makePostTransformationMetadata()
1206 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1209 INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information", in INITIALIZE_PASS_DEPENDENCY()
1219 // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the in verifyAnalysis()
1221 // -verify-loop-info option can enable this. In order to perform some in verifyAnalysis()
1223 // during loop pass sequences. in verifyAnalysis()
1251 /// Traverse the loop blocks and store the DFS result.