|
LLVM 24.0.0git
|
This class builds and contains all of the top-level loop structures in the specified function. More...
#include "llvm/Support/GenericLoopInfo.h"
Public Types | |
| using | iterator = typename std::vector<LoopT *>::const_iterator |
| iterator/begin/end - The interface to the top-level loops in the current function. | |
| using | reverse_iterator |
| using | Edge = std::pair<BlockT *, BlockT *> |
| Edge type. | |
Public Member Functions | |
| LoopInfoBase ()=default | |
| ~LoopInfoBase () | |
| LoopInfoBase (LoopInfoBase &&Arg) | |
| LoopInfoBase & | operator= (LoopInfoBase &&RHS) |
| void | releaseMemory () |
| LoopT * | AllocateLoop () |
| iterator | begin () const |
| iterator | end () const |
| reverse_iterator | rbegin () const |
| reverse_iterator | rend () const |
| bool | empty () const |
| SmallVector< LoopT *, 4 > | getLoopsInPreorder () const |
| Return all of the loops in the function in preorder across the loop nests, with siblings in forward program order. | |
| SmallVector< LoopT *, 4 > | getLoopsInReverseSiblingPreorder () const |
| Return all of the loops in the function in preorder across the loop nests, with siblings in reverse program order. | |
| LoopT * | getLoopFor (const BlockT *BB) const |
| Return the inner most loop that BB lives in. | |
| const LoopT * | operator[] (const BlockT *BB) const |
| Same as getLoopFor. | |
| unsigned | getLoopDepth (const BlockT *BB) const |
| Return the loop nesting level of the specified block. | |
| bool | hasNoExitBlocks (const LoopT &L) const |
Return true if L does not have any exit blocks. | |
| void | getExitEdges (const LoopT &L, SmallVectorImpl< Edge > &ExitEdges) const |
| Return all pairs of (inside_block,outside_block). | |
| BlockT * | getUniqueLatchExitBlock (const LoopT &L) const |
Return the unique exit block for the latch of L, or null if there are multiple different exit blocks or the latch is not exiting. | |
| template<typename PredicateT> | |
| void | removeBlocksIf (LoopT &L, PredicateT Pred) |
Remove every block satisfying Pred from L's block list, preserving the order of the remaining blocks. | |
| template<typename PredicateT> | |
| void | removeBlocksFromLoopAndAncestors (LoopT *Start, LoopT *Stop, PredicateT Pred) |
Remove every block satisfying Pred from Start and each of its ancestors up to but not including Stop, which must be null or an ancestor of Start; a null Stop walks to the top level. | |
| template<typename PredicateT> | |
| SmallVector< LoopT *, 4 > | takeChildrenIf (LoopT *Parent, PredicateT Pred) |
Detach and return the children of Parent (the top-level loops if Parent is null) that satisfy Pred, clearing their parent pointers. | |
| LoopT * | getSmallestCommonLoop (LoopT *A, LoopT *B) const |
| Find the innermost loop containing both given loops. | |
| LoopT * | getSmallestCommonLoop (BlockT *A, BlockT *B) const |
| Find the innermost loop containing both given blocks. | |
| bool | isLoopHeader (const BlockT *BB) const |
| const std::vector< LoopT * > & | getTopLevelLoops () const |
| Return the top-level loops. | |
| LoopT * | removeLoop (iterator I) |
| This removes the specified top-level loop from this loop info object. | |
| void | changeLoopFor (const BlockT *BB, LoopT *L) |
| Change the top-level loop that contains BB to the specified loop. | |
| void | changeTopLevelLoop (LoopT *OldLoop, LoopT *NewLoop) |
| Replace the specified loop in the top-level loops list with the indicated loop. | |
| void | addTopLevelLoop (LoopT *New) |
| This adds the specified loop to the collection of top-level loops. | |
| void | removeBlock (BlockT *BB) |
| This method completely removes BB from all data structures, including all of the Loop objects it is nested in and our mapping from BasicBlocks to loops. | |
| void | analyze (const DominatorTreeBase< BlockT, false > &DomTree) |
| Create the loop forest using a stable algorithm. | |
| void | print (raw_ostream &OS) const |
| void | verify (const DominatorTreeBase< BlockT, false > &DomTree) const |
| void | destroy (LoopT *L) |
| Destroy a loop that has been removed from the LoopInfo nest. | |
Static Public Member Functions | |
| static bool | isNotAlreadyContainedIn (const LoopT *SubLoop, const LoopT *ParentLoop) |
Friends | |
| class | LoopBase< BlockT, LoopT > |
| class | LoopInfo |
This class builds and contains all of the top-level loop structures in the specified function.
Definition at line 524 of file GenericLoopInfo.h.
| using llvm::LoopInfoBase< BlockT, LoopT >::Edge = std::pair<BlockT *, BlockT *> |
Edge type.
Definition at line 716 of file GenericLoopInfo.h.
| using llvm::LoopInfoBase< BlockT, LoopT >::iterator = typename std::vector<LoopT *>::const_iterator |
iterator/begin/end - The interface to the top-level loops in the current function.
Definition at line 602 of file GenericLoopInfo.h.
| using llvm::LoopInfoBase< BlockT, LoopT >::reverse_iterator |
Definition at line 603 of file GenericLoopInfo.h.
|
default |
|
inline |
Definition at line 553 of file GenericLoopInfo.h.
|
inline |
Definition at line 555 of file GenericLoopInfo.h.
|
inline |
This adds the specified loop to the collection of top-level loops.
Definition at line 823 of file GenericLoopInfo.h.
Referenced by llvm::addClonedBlockToLoopInfo(), buildClonedLoops(), llvm::cloneLoop(), cloneLoopNest(), llvm::cloneLoopWithPreheader(), llvm::TileInfo::CreateTiledLoops(), llvm::expandReductionViaLoop(), hoistLoopToNewParent(), rebuildLoopAfterUnswitch(), and updateLoopInfo().
|
inline |
Definition at line 592 of file GenericLoopInfo.h.
Referenced by llvm::addClonedBlockToLoopInfo(), buildClonedLoops(), llvm::cloneLoop(), cloneLoopNest(), llvm::cloneLoopWithPreheader(), llvm::TileInfo::CreateTiledLoops(), llvm::expandReductionViaLoop(), separateNestedLoop(), and updateLoopInfo().
| void llvm::LoopInfoBase< BlockT, LoopT >::analyze | ( | const DominatorTreeBase< BlockT, false > & | DomTree | ) |
Create the loop forest using a stable algorithm.
Analyze LoopInfo discovers loops during a reverse preorder DominatorTree traversal interleaved with backward CFG traversals within each subloop (discoverAndMapSubloop).
The backward traversal skips inner subloops, so this part of the algorithm is linear in the number of CFG edges.
Then build a loop-contiguous reverse postorder for in-loops blocks. Lists are header-first with each subloop's blocks contiguous, ordered by first appearance in RPO; SubLoops keep program order, TopLevelLoops reverse program order.
Definition at line 519 of file GenericLoopInfoImpl.h.
References assert(), llvm::DominatorTreeBase< NodeT, IsPostDom >::dominates(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::DomTreeNodeBase< NodeT >::getDFSNumOut(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getRootNode(), llvm::inverse_children(), llvm::post_order(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::reverse(), llvm::SmallVectorTemplateCommon< T, typename >::size(), and llvm::DominatorTreeBase< NodeT, IsPostDom >::updateDFSNumbers().
Referenced by llvm::OptimizationRemarkEmitter::OptimizationRemarkEmitter(), and llvm::LoopAnalysis::run().
|
inline |
Definition at line 605 of file GenericLoopInfo.h.
Referenced by llvm::LoopFullUnrollPass::run(), and verify().
|
inline |
Change the top-level loop that contains BB to the specified loop.
This should be used by transformations that restructure the loop hierarchy tree.
Definition at line 800 of file GenericLoopInfo.h.
Referenced by cloneLoopNest(), deleteDeadBlocksFromLoop(), hoistLoopToNewParent(), rebuildLoopAfterUnswitch(), separateNestedLoop(), and updateLoopInfo().
|
inline |
Replace the specified loop in the top-level loops list with the indicated loop.
Definition at line 814 of file GenericLoopInfo.h.
Referenced by separateNestedLoop().
|
inline |
Destroy a loop that has been removed from the LoopInfo nest.
This runs the destructor of the loop object making it invalid to reference afterward. The memory is retained so that the pointer to the loop remains valid.
The caller is responsible for removing this loop from the loop nest and otherwise disconnecting it from the broader LoopInfo data structures. Callers that don't naturally handle this themselves should probably call ‘erase’ instead.
Definition at line 871 of file GenericLoopInfo.h.
Referenced by deleteDeadBlocksFromLoop(), llvm::deleteDeadLoop(), and rebuildLoopAfterUnswitch().
|
inline |
Definition at line 609 of file GenericLoopInfo.h.
Referenced by llvm::FunctionToLoopPassAdaptor::run(), llvm::LoopSinkPass::run(), and llvm::LoopUnrollPass::run().
|
inline |
Definition at line 606 of file GenericLoopInfo.h.
Referenced by llvm::deleteDeadLoop(), llvm::LoopInfoBase< BasicBlock, Loop >::removeLoop(), llvm::LoopFullUnrollPass::run(), and verify().
| void llvm::LoopInfoBase< BlockT, LoopT >::getExitEdges | ( | const LoopT & | L, |
| SmallVectorImpl< Edge > & | ExitEdges ) const |
Return all pairs of (inside_block,outside_block).
getExitEdges - Return all pairs of (inside_block,outside_block).
Definition at line 175 of file GenericLoopInfoImpl.h.
References llvm::children(), and llvm::SmallVectorImpl< T >::emplace_back().
Referenced by llvm::peelLoop().
|
inline |
Return the loop nesting level of the specified block.
A depth of 0 means the block is not inside any loop.
Definition at line 710 of file GenericLoopInfo.h.
Referenced by CompareValueComplexity(), and rebuildLoopAfterUnswitch().
|
inline |
Return the inner most loop that BB lives in.
If a basic block is in no loop (for example the entry node), null is returned.
Definition at line 700 of file GenericLoopInfo.h.
Referenced by llvm::addClonedBlockToLoopInfo(), llvm::OpenMPIRBuilder::applySimd(), buildClonedLoops(), canProveExitOnFirstIteration(), llvm::MachineBasicBlock::canSplitCriticalEdge(), checkDependencies(), llvm::cloneLoop(), cloneLoopBlocks(), cloneLoopNest(), llvm::cloneLoopWithPreheader(), collectUnswitchCandidates(), collectUnswitchCandidatesWithInjections(), computeHeuristicUnrollFactor(), ConnectProlog(), llvm::TileInfo::CreateTiledLoops(), llvm::dumpMaxRegPressure(), emitBasicBlockLoopComments(), llvm::expandReductionViaLoop(), llvm::MustBeExecutedContextExplorer::findBackwardJoinPoint(), llvm::MustBeExecutedContextExplorer::findForwardJoinPoint(), foldURemOfLoopIncrement(), formLCSSAForInstructionsImpl(), formLCSSAImpl(), getInnermostLoopFor(), getInsertPointForUses(), getIVIncrement(), llvm::LoopInfoBase< BasicBlock, Loop >::getLoopDepth(), getOutermostLoop(), getReductionInstr(), getSmallestCommonLoop(), getTopMostExitingLoop(), hoistLoopToNewParent(), injectPendingInvariantConditions(), inSubLoop(), IsAcceptableTarget(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), isIntegerLoopHeaderPHI(), isInteresting(), llvm::LoopInfoBase< BasicBlock, Loop >::isLoopHeader(), llvm::isPotentiallyReachable(), isRemOfLoopIncrementWithLoopInvariant(), isSameUnderlyingObjectInLoop(), mergeBlocksIntoPredecessors(), moveLCSSAPhis(), needToInsertPhisForLCSSA(), llvm::LoopInfoBase< BasicBlock, Loop >::operator[](), rebuildLoopAfterUnswitch(), recomputeLoopBlockSet(), llvm::rewriteLoopExitValues(), llvm::simplifyUsersOfIV(), sinkInstruction(), sinkMinMax(), sortBlocks(), splitBlock(), llvm::SplitBlockAndInsertIfThenElse(), SplitBlockImpl(), SplitBlockPredecessorsImpl(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), unswitchNontrivialInvariants(), UpdateAnalysisInformation(), and updateLoopInfo().
| SmallVector< LoopT *, 4 > llvm::LoopInfoBase< BlockT, LoopT >::getLoopsInPreorder | ( | ) | const |
Return all of the loops in the function in preorder across the loop nests, with siblings in forward program order.
Note that because loops form a forest of trees, preorder is equivalent to reverse postorder.
Definition at line 609 of file GenericLoopInfoImpl.h.
Referenced by llvm::LoopSinkPass::run(), runImpl(), llvm::AMDGPUDAGToDAGISelLegacy::runOnMachineFunction(), and warnAboutLeftoverTransformations().
| SmallVector< LoopT *, 4 > llvm::LoopInfoBase< BlockT, LoopT >::getLoopsInReverseSiblingPreorder | ( | ) | const |
Return all of the loops in the function in preorder across the loop nests, with siblings in reverse program order.
Note that because loops form a forest of trees, preorder is equivalent to reverse postorder.
Also note that this is not a reverse preorder. Only the siblings are in reverse program order.
Definition at line 626 of file GenericLoopInfoImpl.h.
References llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
| LoopT * llvm::LoopInfoBase< BlockT, LoopT >::getSmallestCommonLoop | ( | BlockT * | A, |
| BlockT * | B ) const |
Find the innermost loop containing both given blocks.
A and B or nullptr if there is no such loop. Definition at line 675 of file GenericLoopInfoImpl.h.
References A(), B(), getLoopFor(), and getSmallestCommonLoop().
| LoopT * llvm::LoopInfoBase< BlockT, LoopT >::getSmallestCommonLoop | ( | LoopT * | A, |
| LoopT * | B ) const |
Find the innermost loop containing both given loops.
A and B or nullptr if there is no such loop. Definition at line 650 of file GenericLoopInfoImpl.h.
Referenced by getSmallestCommonLoop().
|
inline |
Return the top-level loops.
Definition at line 784 of file GenericLoopInfo.h.
Referenced by llvm::LoopCachePrinterPass::run().
| BlockT * llvm::LoopInfoBase< BlockT, LoopT >::getUniqueLatchExitBlock | ( | const LoopT & | L | ) | const |
Return the unique exit block for the latch of L, or null if there are multiple different exit blocks or the latch is not exiting.
Definition at line 163 of file GenericLoopInfoImpl.h.
References assert(), llvm::children(), and llvm::find_singleton().
Referenced by unswitchTrivialBranch().
| bool llvm::LoopInfoBase< BlockT, LoopT >::hasNoExitBlocks | ( | const LoopT & | L | ) | const |
Return true if L does not have any exit blocks.
Definition at line 94 of file GenericLoopInfoImpl.h.
References llvm::getExitBlockHelper().
Referenced by llvm::deleteDeadLoop(), and deleteLoopIfDead().
|
inline |
Definition at line 778 of file GenericLoopInfo.h.
Referenced by canProveExitOnFirstIteration(), llvm::getUnderlyingObjects(), and SplitBlockPredecessorsImpl().
|
inlinestatic |
Definition at line 844 of file GenericLoopInfo.h.
Referenced by llvm::LoopInfoBase< BasicBlock, Loop >::isNotAlreadyContainedIn().
|
inline |
Definition at line 566 of file GenericLoopInfo.h.
|
inline |
Same as getLoopFor.
Definition at line 706 of file GenericLoopInfo.h.
| void llvm::LoopInfoBase< BlockT, LoopT >::print | ( | raw_ostream & | OS | ) | const |
Definition at line 682 of file GenericLoopInfoImpl.h.
References llvm::print().
|
inline |
Definition at line 607 of file GenericLoopInfo.h.
|
inline |
Definition at line 582 of file GenericLoopInfo.h.
Referenced by llvm::LoopInfoBase< BasicBlock, Loop >::~LoopInfoBase().
|
inline |
This method completely removes BB from all data structures, including all of the Loop objects it is nested in and our mapping from BasicBlocks to loops.
Definition at line 831 of file GenericLoopInfo.h.
Referenced by llvm::deleteDeadLoop(), llvm::MergeBlockIntoPredecessor(), and simplifyOneLoop().
|
inline |
Remove every block satisfying Pred from Start and each of its ancestors up to but not including Stop, which must be null or an ancestor of Start; a null Stop walks to the top level.
Definition at line 743 of file GenericLoopInfo.h.
Referenced by deleteDeadBlocksFromLoop(), and rebuildLoopAfterUnswitch().
|
inline |
Remove every block satisfying Pred from L's block list, preserving the order of the remaining blocks.
Only L itself is updated, not its ancestors or descendants, and not the block-to-loop mapping.
Definition at line 732 of file GenericLoopInfo.h.
Referenced by hoistLoopToNewParent(), rebuildLoopAfterUnswitch(), and llvm::LoopInfoBase< BasicBlock, Loop >::removeBlocksFromLoopAndAncestors().
|
inline |
This removes the specified top-level loop from this loop info object.
The loop is not deleted, as it will presumably be inserted into another loop.
Definition at line 789 of file GenericLoopInfo.h.
Referenced by llvm::deleteDeadLoop(), and rebuildLoopAfterUnswitch().
|
inline |
Definition at line 608 of file GenericLoopInfo.h.
|
inline |
Detach and return the children of Parent (the top-level loops if Parent is null) that satisfy Pred, clearing their parent pointers.
Both the remaining and the returned children keep their relative order.
Definition at line 753 of file GenericLoopInfo.h.
Referenced by deleteDeadBlocksFromLoop(), and rebuildLoopAfterUnswitch().
| void llvm::LoopInfoBase< BlockT, LoopT >::verify | ( | const DominatorTreeBase< BlockT, false > & | DomTree | ) | const |
Definition at line 738 of file GenericLoopInfoImpl.h.
References llvm::SmallVectorImpl< T >::append(), assert(), begin(), E(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), end(), llvm::enumerate(), I, Loops, llvm::Number, llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateCommon< T, typename >::size().
Referenced by FixIrreducibleImpl(), llvm::hoistRegion(), injectPendingInvariantConditions(), llvm::FunctionToLoopPassAdaptor::run(), llvm::LoopBoundSplitPass::run(), llvm::LoopVerifierPass::run(), splitLoopBound(), turnGuardIntoBranch(), unifyLoopExits(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), and unswitchNontrivialInvariants().
|
friend |
Definition at line 543 of file GenericLoopInfo.h.
|
friend |
Definition at line 546 of file GenericLoopInfo.h.