LLVM  8.0.0svn
Public Types | Public Member Functions | Static Public Member Functions | Friends | List of all members
llvm::LoopInfoBase< BlockT, LoopT > Class Template Reference

This class builds and contains all of the top-level loop structures in the specified function. More...

#include "llvm/Analysis/LoopInfo.h"

Inheritance diagram for llvm::LoopInfoBase< BlockT, LoopT >:
Inheritance graph
[legend]

Public Types

typedef std::vector< LoopT * >::const_iterator iterator
 iterator/begin/end - The interface to the top-level loops in the current function. More...
 
typedef std::vector< LoopT * >::const_reverse_iterator reverse_iterator
 

Public Member Functions

 LoopInfoBase ()
 
 ~LoopInfoBase ()
 
 LoopInfoBase (LoopInfoBase &&Arg)
 
LoopInfoBaseoperator= (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 ()
 Return all of the loops in the function in preorder across the loop nests, with siblings in forward program order. More...
 
SmallVector< LoopT *, 4 > getLoopsInReverseSiblingPreorder ()
 Return all of the loops in the function in preorder across the loop nests, with siblings in reverse program order. More...
 
LoopT * getLoopFor (const BlockT *BB) const
 Return the inner most loop that BB lives in. More...
 
const LoopT * operator[] (const BlockT *BB) const
 Same as getLoopFor. More...
 
unsigned getLoopDepth (const BlockT *BB) const
 Return the loop nesting level of the specified block. More...
 
bool isLoopHeader (const BlockT *BB) const
 
LoopT * removeLoop (iterator I)
 This removes the specified top-level loop from this loop info object. More...
 
void changeLoopFor (BlockT *BB, LoopT *L)
 Change the top-level loop that contains BB to the specified loop. More...
 
void changeTopLevelLoop (LoopT *OldLoop, LoopT *NewLoop)
 Replace the specified loop in the top-level loops list with the indicated loop. More...
 
void addTopLevelLoop (LoopT *New)
 This adds the specified loop to the collection of top-level loops. More...
 
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. More...
 
void analyze (const DominatorTreeBase< BlockT, false > &DomTree)
 Create the loop forest using a stable algorithm. More...
 
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. More...
 

Static Public Member Functions

static bool isNotAlreadyContainedIn (const LoopT *SubLoop, const LoopT *ParentLoop)
 

Friends

class LoopBase< BlockT, LoopT >
 
class LoopInfo
 

Detailed Description

template<class BlockT, class LoopT>
class llvm::LoopInfoBase< BlockT, LoopT >

This class builds and contains all of the top-level loop structures in the specified function.

Definition at line 62 of file LoopInfo.h.

Member Typedef Documentation

◆ iterator

template<class BlockT, class LoopT>
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 656 of file LoopInfo.h.

◆ reverse_iterator

template<class BlockT, class LoopT>
typedef std::vector<LoopT *>::const_reverse_iterator llvm::LoopInfoBase< BlockT, LoopT >::reverse_iterator

Definition at line 658 of file LoopInfo.h.

Constructor & Destructor Documentation

◆ LoopInfoBase() [1/2]

template<class BlockT, class LoopT>
llvm::LoopInfoBase< BlockT, LoopT >::LoopInfoBase ( )
inline

Definition at line 617 of file LoopInfo.h.

◆ ~LoopInfoBase()

template<class BlockT, class LoopT>
llvm::LoopInfoBase< BlockT, LoopT >::~LoopInfoBase ( )
inline

Definition at line 618 of file LoopInfo.h.

◆ LoopInfoBase() [2/2]

template<class BlockT, class LoopT>
llvm::LoopInfoBase< BlockT, LoopT >::LoopInfoBase ( LoopInfoBase< BlockT, LoopT > &&  Arg)
inline

Definition at line 620 of file LoopInfo.h.

Member Function Documentation

◆ addTopLevelLoop()

template<class BlockT, class LoopT>
void llvm::LoopInfoBase< BlockT, LoopT >::addTopLevelLoop ( LoopT *  New)
inline

◆ AllocateLoop()

template<class BlockT, class LoopT>
template<typename... ArgsTy>
LoopT* llvm::LoopInfoBase< BlockT, LoopT >::AllocateLoop ( ArgsTy &&...  Args)
inline

◆ analyze()

template<class BlockT, class LoopT>
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 551 of file LoopInfoImpl.h.

Referenced by llvm::VPlanHCFGBuilder::buildHierarchicalCFG(), llvm::OptimizationRemarkEmitter::OptimizationRemarkEmitter(), llvm::LoopAnalysis::run(), and llvm::LoopInfoBase< BasicBlock, Loop >::verify().

◆ begin()

template<class BlockT, class LoopT>
iterator llvm::LoopInfoBase< BlockT, LoopT >::begin ( ) const
inline

◆ changeLoopFor()

template<class BlockT, class LoopT>
void llvm::LoopInfoBase< BlockT, LoopT >::changeLoopFor ( BlockT *  BB,
LoopT *  L 
)
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 716 of file LoopInfo.h.

Referenced by llvm::MachineLoopInfo::changeLoopFor(), cloneLoopNest(), deleteDeadBlocksFromLoop(), llvm::discoverAndMapSubloop(), hoistLoopToNewParent(), rebuildLoopAfterUnswitch(), and separateNestedLoop().

◆ changeTopLevelLoop()

template<class BlockT, class LoopT>
void llvm::LoopInfoBase< BlockT, LoopT >::changeTopLevelLoop ( LoopT *  OldLoop,
LoopT *  NewLoop 
)
inline

Replace the specified loop in the top-level loops list with the indicated loop.

Definition at line 726 of file LoopInfo.h.

Referenced by llvm::MachineLoopInfo::changeTopLevelLoop(), and separateNestedLoop().

◆ destroy()

template<class BlockT, class LoopT>
void llvm::LoopInfoBase< BlockT, LoopT >::destroy ( LoopT *  L)
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 782 of file LoopInfo.h.

Referenced by deleteDeadBlocksFromLoop(), and rebuildLoopAfterUnswitch().

◆ empty()

template<class BlockT, class LoopT>
bool llvm::LoopInfoBase< BlockT, LoopT >::empty ( ) const
inline

Definition at line 663 of file LoopInfo.h.

Referenced by llvm::MachineLoopInfo::empty(), and llvm::LoopSinkPass::run().

◆ end()

template<class BlockT, class LoopT>
iterator llvm::LoopInfoBase< BlockT, LoopT >::end ( ) const
inline

◆ getLoopDepth()

template<class BlockT, class LoopT>
unsigned llvm::LoopInfoBase< BlockT, LoopT >::getLoopDepth ( const BlockT *  BB) const
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 691 of file LoopInfo.h.

Referenced by CompareValueComplexity(), llvm::MachineLoopInfo::getLoopDepth(), and rebuildLoopAfterUnswitch().

◆ getLoopFor()

template<class BlockT, class LoopT>
LoopT* llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor ( const BlockT *  BB) const
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 684 of file LoopInfo.h.

Referenced by llvm::addClonedBlockToLoopInfo(), llvm::DivergenceAnalysis::addUniformOverride(), buildClonedLoops(), castToIncrementInst(), CloneInstructionInExitBlock(), CloneLoop(), CloneLoopBlocks(), cloneLoopNest(), llvm::DivergencePropagator::computeJoinPoints(), computeUnlikelySuccessors(), ConnectProlog(), llvm::createSIFixWWMLivenessPass(), deleteDeadInstruction(), llvm::discoverAndMapSubloop(), llvm::VPBasicBlock::execute(), llvm::VPlan::execute(), llvm::InnerLoopVectorizer::fixFirstOrderRecurrence(), llvm::InnerLoopVectorizer::fixReduction(), llvm::InnerLoopVectorizer::fixVectorizedLoop(), llvm::formLCSSAForInstructions(), getInsertPointForUses(), llvm::MachineLoopInfo::getLoopFor(), getOutermostLoop(), getReductionValue(), hoistLoopToNewParent(), llvm::DivergenceAnalysis::inRegion(), inSubLoop(), IsAcceptableTarget(), isIntegerLoopHeaderPHI(), isInteresting(), isMustExecuteIn(), llvm::isPotentiallyReachable(), llvm::Loop::isRecursivelyLCSSAForm(), isSafeToExecuteUnconditionally(), isSameUnderlyingObjectInLoop(), isSimplifiedLoopNest(), mergeBlocksIntoPredecessors(), needToInsertPhisForLCSSA(), llvm::MachineLoopInfo::operator[](), llvm::promoteLoopAccessesToScalars(), rebuildLoopAfterUnswitch(), recomputeLoopBlockSet(), llvm::simplifyUsersOfIV(), sinkInstruction(), llvm::InnerLoopVectorizer::sinkScalarOperands(), llvm::SplitBlock(), llvm::SplitBlockAndInsertIfThen(), llvm::UnrollLoop(), unswitchBestCondition(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), unswitchTrivialSwitch(), llvm::InnerLoopVectorizer::updateAnalysis(), UpdateAnalysisInformation(), visitIVCast(), and llvm::LoopBlocksTraversal::visitPreorder().

◆ getLoopsInPreorder()

template<class BlockT , class LoopT >
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 580 of file LoopInfoImpl.h.

Referenced by castToIncrementInst(), and llvm::LoopSinkPass::run().

◆ getLoopsInReverseSiblingPreorder()

template<class BlockT , class LoopT >
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.

◆ isLoopHeader()

template<class BlockT, class LoopT>
bool llvm::LoopInfoBase< BlockT, LoopT >::isLoopHeader ( const BlockT *  BB) const
inline

Definition at line 697 of file LoopInfo.h.

Referenced by llvm::GetUnderlyingObjects(), and llvm::MachineLoopInfo::isLoopHeader().

◆ isNotAlreadyContainedIn()

template<class BlockT, class LoopT>
static bool llvm::LoopInfoBase< BlockT, LoopT >::isNotAlreadyContainedIn ( const LoopT *  SubLoop,
const LoopT *  ParentLoop 
)
inlinestatic

Definition at line 755 of file LoopInfo.h.

◆ operator=()

template<class BlockT, class LoopT>
LoopInfoBase& llvm::LoopInfoBase< BlockT, LoopT >::operator= ( LoopInfoBase< BlockT, LoopT > &&  RHS)
inline

Definition at line 627 of file LoopInfo.h.

◆ operator[]()

template<class BlockT, class LoopT>
const LoopT* llvm::LoopInfoBase< BlockT, LoopT >::operator[] ( const BlockT *  BB) const
inline

Same as getLoopFor.

Definition at line 687 of file LoopInfo.h.

◆ print()

template<class BlockT , class LoopT >
void llvm::LoopInfoBase< BlockT, LoopT >::print ( raw_ostream OS) const

Definition at line 630 of file LoopInfoImpl.h.

◆ rbegin()

template<class BlockT, class LoopT>
reverse_iterator llvm::LoopInfoBase< BlockT, LoopT >::rbegin ( ) const
inline

Definition at line 661 of file LoopInfo.h.

◆ releaseMemory()

template<class BlockT, class LoopT>
void llvm::LoopInfoBase< BlockT, LoopT >::releaseMemory ( )
inline

◆ removeBlock()

template<class BlockT, class LoopT>
void llvm::LoopInfoBase< BlockT, LoopT >::removeBlock ( BlockT *  BB)
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 743 of file LoopInfo.h.

Referenced by llvm::foldBlockIntoPredecessor(), llvm::MergeBlockIntoPredecessor(), llvm::MachineLoopInfo::removeBlock(), ReplaceUsesOfWith(), and simplifyOneLoop().

◆ removeLoop()

template<class BlockT, class LoopT>
LoopT* llvm::LoopInfoBase< BlockT, LoopT >::removeLoop ( iterator  I)
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 705 of file LoopInfo.h.

Referenced by rebuildLoopAfterUnswitch(), and llvm::MachineLoopInfo::removeLoop().

◆ rend()

template<class BlockT, class LoopT>
reverse_iterator llvm::LoopInfoBase< BlockT, LoopT >::rend ( ) const
inline

Definition at line 662 of file LoopInfo.h.

◆ verify()

template<class BlockT, class LoopT>
void llvm::LoopInfoBase< BlockT, LoopT >::verify ( const DominatorTreeBase< BlockT, false > &  DomTree) const

Definition at line 701 of file LoopInfoImpl.h.

Referenced by llvm::LoopVerifierPass::run(), and unswitchNontrivialInvariants().

Friends And Related Function Documentation

◆ LoopBase< BlockT, LoopT >

template<class BlockT, class LoopT>
friend class LoopBase< BlockT, LoopT >
friend

Definition at line 610 of file LoopInfo.h.

◆ LoopInfo

template<class BlockT, class LoopT>
friend class LoopInfo
friend

Definition at line 611 of file LoopInfo.h.


The documentation for this class was generated from the following files: