LLVM 17.0.0git
|
This class builds and contains all of the top-level loop structures in the specified function. More...
#include "llvm/Analysis/LoopInfo.h"
Public Types | |
typedef std::vector< LoopT * >::const_iterator | iterator |
iterator/begin/end - The interface to the top-level loops in the current function. | |
typedef std::vector< LoopT * >::const_reverse_iterator | reverse_iterator |
Public Member Functions | |
LoopInfoBase ()=default | |
~LoopInfoBase () | |
LoopInfoBase (LoopInfoBase &&Arg) | |
LoopInfoBase & | operator= (LoopInfoBase &&RHS) |
void | releaseMemory () |
template<typename... ArgsTy> | |
LoopT * | AllocateLoop (ArgsTy &&... Args) |
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 | isLoopHeader (const BlockT *BB) const |
const std::vector< LoopT * > & | getTopLevelLoops () const |
Return the top-level loops. | |
std::vector< LoopT * > & | getTopLevelLoopsVector () |
Return the top-level loops. | |
LoopT * | removeLoop (iterator I) |
This removes the specified top-level loop from this loop info object. | |
void | changeLoopFor (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 912 of file LoopInfo.h.
typedef std::vector<LoopT*>::const_iterator llvm::LoopInfoBase< BlockT, LoopT >::iterator |
iterator/begin/end - The interface to the top-level loops in the current function.
Definition at line 964 of file LoopInfo.h.
typedef std::vector<LoopT*>::const_reverse_iterator llvm::LoopInfoBase< BlockT, LoopT >::reverse_iterator |
Definition at line 966 of file LoopInfo.h.
|
default |
|
inline |
Definition at line 926 of file LoopInfo.h.
|
inline |
Definition at line 928 of file LoopInfo.h.
References Arg.
|
inline |
This adds the specified loop to the collection of top-level loops.
Definition at line 1049 of file LoopInfo.h.
References assert().
Referenced by llvm::addClonedBlockToLoopInfo(), llvm::MachineLoopInfo::addTopLevelLoop(), buildClonedLoops(), llvm::cloneLoop(), cloneLoopNest(), llvm::cloneLoopWithPreheader(), createNaturalLoopInternal(), llvm::TileInfo::CreateTiledLoops(), llvm::VPRegionBlock::execute(), hoistLoopToNewParent(), llvm::PopulateLoopsDFS< BlockT, LoopT >::insertIntoLoop(), and rebuildLoopAfterUnswitch().
|
inline |
Definition at line 956 of file LoopInfo.h.
References llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold, GrowthDelay >::Allocate().
Referenced by llvm::addClonedBlockToLoopInfo(), buildClonedLoops(), llvm::cloneLoop(), cloneLoopNest(), llvm::cloneLoopWithPreheader(), createNaturalLoopInternal(), llvm::TileInfo::CreateTiledLoops(), llvm::VPRegionBlock::execute(), and separateNestedLoop().
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 postorder 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. Subloop and Block vectors are then populated during a single forward CFG traversal (PopulateLoopDFS).
During the two CFG traversals each block is seen three times: 1) Discovered and mapped by a reverse CFG traversal. 2) Visited during a forward DFS CFG traversal. 3) Reverse-inserted in the loop in postorder following forward DFS.
The Block vectors are inclusive, so step 3 requires loop-depth number of insertions per block.
Definition at line 557 of file LoopInfoImpl.h.
References llvm::children(), llvm::discoverAndMapSubloop(), llvm::DominatorTreeBase< NodeT, IsPostDom >::dominates(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getRootNode(), llvm::DominatorTreeBase< NodeT, IsPostDom >::isReachableFromEntry(), llvm::post_order(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::PopulateLoopsDFS< BlockT, LoopT >::traverse().
Referenced by llvm::OptimizationRemarkEmitter::OptimizationRemarkEmitter(), llvm::LoopAnalysis::run(), and llvm::LoopInfoBase< BlockT, LoopT >::verify().
|
inline |
Definition at line 967 of file LoopInfo.h.
Referenced by llvm::MachineLoopInfo::begin(), CalculateUnswitchCostMultiplier(), llvm::LoopFullUnrollPass::run(), and llvm::ScalarEvolution::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 1030 of file LoopInfo.h.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase().
Referenced by llvm::MachineLoopInfo::changeLoopFor(), cloneLoopNest(), createNaturalLoopInternal(), llvm::discoverAndMapSubloop(), hoistLoopToNewParent(), rebuildLoopAfterUnswitch(), and separateNestedLoop().
|
inline |
Replace the specified loop in the top-level loops list with the indicated loop.
Definition at line 1040 of file LoopInfo.h.
References assert(), llvm::find(), and I.
Referenced by llvm::MachineLoopInfo::changeTopLevelLoop(), and 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 1096 of file LoopInfo.h.
References llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold, GrowthDelay >::Deallocate().
Referenced by deleteDeadBlocksFromLoop(), llvm::deleteDeadLoop(), and rebuildLoopAfterUnswitch().
|
inline |
Definition at line 971 of file LoopInfo.h.
Referenced by llvm::MachineLoopInfo::empty(), llvm::FunctionToLoopPassAdaptor::run(), llvm::LoopUnrollPass::run(), llvm::LoopVectorizePass::run(), and llvm::LoopSinkPass::run().
|
inline |
Definition at line 968 of file LoopInfo.h.
Referenced by CalculateUnswitchCostMultiplier(), llvm::deleteDeadLoop(), llvm::MachineLoopInfo::end(), llvm::LoopFullUnrollPass::run(), and llvm::ScalarEvolution::verify().
|
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 999 of file LoopInfo.h.
Referenced by CompareValueComplexity(), llvm::MachineLoopInfo::getLoopDepth(), getUserBonus(), rebuildLoopAfterUnswitch(), and runImpl().
|
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 992 of file LoopInfo.h.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup().
Referenced by llvm::addClonedBlockToLoopInfo(), llvm::IVUsers::AddUsersIfInteresting(), llvm::OpenMPIRBuilder::applySimd(), buildClonedLoops(), canVectorizeLoads(), checkDependencies(), llvm::cloneLoop(), cloneLoopBlocks(), cloneLoopNest(), llvm::cloneLoopWithPreheader(), collectUnswitchCandidates(), collectUnswitchCandidatesWithInjections(), computeHeuristicUnrollFactor(), ConnectProlog(), createNaturalLoopInternal(), llvm::TileInfo::CreateTiledLoops(), llvm::DependenceInfo::depends(), llvm::discoverAndMapSubloop(), llvm::VPRegionBlock::execute(), llvm::LoopVectorizationPlanner::executePlan(), llvm::MustBeExecutedContextExplorer::findBackwardJoinPoint(), llvm::MustBeExecutedContextExplorer::findForwardJoinPoint(), llvm::InnerLoopVectorizer::fixVectorizedLoop(), llvm::formLCSSA(), llvm::formLCSSAForInstructions(), getInnermostLoopFor(), getInsertPointForUses(), getIVIncrement(), llvm::MachineLoopInfo::getLoopFor(), getOutermostLoop(), getReductionValue(), llvm::DependenceInfo::getSplitIteration(), getTopMostExitingLoop(), hoistLoopToNewParent(), injectPendingInvariantConditions(), llvm::PopulateLoopsDFS< BlockT, LoopT >::insertIntoLoop(), inSubLoop(), IsAcceptableTarget(), llvm::ScalarEvolution::isBasicBlockEntryGuardedByCond(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), isIntegerLoopHeaderPHI(), isInteresting(), llvm::isPotentiallyReachable(), llvm::Loop::isRecursivelyLCSSAForm(), isSameUnderlyingObjectInLoop(), mergeBlocksIntoPredecessors(), moveLCSSAPhis(), needToInsertPhisForLCSSA(), oneUseOutsideLoop(), llvm::MachineLoopInfo::operator[](), llvm::ScalarEvolution::print(), rebuildLoopAfterUnswitch(), recomputeLoopBlockSet(), llvm::rewriteLoopExitValues(), llvm::simplifyUsersOfIV(), sinkInstruction(), llvm::InnerLoopVectorizer::sinkScalarOperands(), SplitBlockAndInsertIfThenImpl(), llvm::splitBlockBefore(), SplitBlockImpl(), SplitBlockPredecessorsImpl(), unifyLoopExits(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), unswitchNontrivialInvariants(), unswitchTrivialSwitch(), UpdateAnalysisInformation(), llvm::InstCombinerImpl::visitGEPOfGEP(), and llvm::LoopBlocksTraversal::visitPreorder().
SmallVector< LoopT *, 4 > llvm::LoopInfoBase< BlockT, LoopT >::getLoopsInPreorder |
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 587 of file LoopInfoImpl.h.
References llvm::SmallVectorImpl< T >::append(), and llvm::reverse().
Referenced by llvm::LoopSinkPass::run(), runImpl(), AMDGPUDAGToDAGISel::runOnMachineFunction(), and warnAboutLeftoverTransformations().
SmallVector< LoopT *, 4 > llvm::LoopInfoBase< BlockT, LoopT >::getLoopsInReverseSiblingPreorder |
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 605 of file LoopInfoImpl.h.
References llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
|
inline |
Return the top-level loops.
Definition at line 1011 of file LoopInfo.h.
|
inline |
Return the top-level loops.
Definition at line 1014 of file LoopInfo.h.
|
inline |
Definition at line 1005 of file LoopInfo.h.
Referenced by canProveExitOnFirstIteration(), llvm::getUnderlyingObjects(), llvm::MachineLoopInfo::isLoopHeader(), makeReducible(), and SplitBlockPredecessorsImpl().
|
inlinestatic |
Definition at line 1069 of file LoopInfo.h.
|
inline |
Definition at line 935 of file LoopInfo.h.
References RHS.
|
inline |
Same as getLoopFor.
Definition at line 995 of file LoopInfo.h.
void llvm::LoopInfoBase< BlockT, LoopT >::print | ( | raw_ostream & | OS | ) | const |
Definition at line 630 of file LoopInfoImpl.h.
References E, I, OS, and llvm::print().
Referenced by llvm::LoopInfoWrapperPass::print().
|
inline |
Definition at line 969 of file LoopInfo.h.
|
inline |
Definition at line 947 of file LoopInfo.h.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), and llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold, GrowthDelay >::Reset().
Referenced by llvm::LoopInfoWrapperPass::releaseMemory(), and llvm::MachineLoopInfo::releaseMemory().
|
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 1057 of file LoopInfo.h.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and I.
Referenced by llvm::deleteDeadLoop(), llvm::MergeBlockIntoPredecessor(), llvm::MachineLoopInfo::removeBlock(), and simplifyOneLoop().
|
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 1019 of file LoopInfo.h.
Referenced by llvm::deleteDeadLoop(), rebuildLoopAfterUnswitch(), and llvm::MachineLoopInfo::removeLoop().
|
inline |
Definition at line 970 of file LoopInfo.h.
void llvm::LoopInfoBase< BlockT, LoopT >::verify | ( | const DominatorTreeBase< BlockT, false > & | DomTree | ) | const |
Definition at line 699 of file LoopInfoImpl.h.
References llvm::addInnerLoopsToHeadersMap(), llvm::LoopInfoBase< BlockT, LoopT >::analyze(), assert(), llvm::compareLoops(), llvm::dbgs(), E, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), I, llvm_unreachable, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), and Loops.
Referenced by createNaturalLoopInternal(), llvm::hoistRegion(), injectPendingInvariantConditions(), llvm::LoopVerifierPass::run(), llvm::FunctionToLoopPassAdaptor::run(), llvm::LoopBoundSplitPass::run(), unifyLoopExits(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), unswitchNontrivialInvariants(), and llvm::LoopInfoWrapperPass::verifyAnalysis().
|
friend |
Definition at line 916 of file LoopInfo.h.
|
friend |
Definition at line 919 of file LoopInfo.h.