LLVM  9.0.0svn
Classes | Public Member Functions | Friends | List of all members
llvm::Loop Class Reference

Represents a single loop in the control flow graph. More...

#include "llvm/Analysis/LoopInfo.h"

Inheritance diagram for llvm::Loop:
Inheritance graph
[legend]
Collaboration diagram for llvm::Loop:
Collaboration graph
[legend]

Classes

class  LocRange
 A range representing the start and end location of a loop. More...
 
struct  LoopBounds
 Below are some utilities to get loop bounds and induction variable, and check if a given phinode is an auxiliary induction variable, as well as checking if the loop is canonical. More...
 

Public Member Functions

bool isLoopInvariant (const Value *V) const
 Return true if the specified value is loop invariant. More...
 
bool hasLoopInvariantOperands (const Instruction *I) const
 Return true if all the operands of the specified instruction are loop invariant. More...
 
bool makeLoopInvariant (Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr) const
 If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivially loop-invariant. More...
 
bool makeLoopInvariant (Instruction *I, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr) const
 If the given instruction is inside of the loop and it can be hoisted, do so to make it trivially loop-invariant. More...
 
PHINodegetCanonicalInductionVariable () const
 Check to see if the loop has a canonical induction variable: an integer recurrence that starts at 0 and increments by one each time through the loop. More...
 
bool getIncomingAndBackEdge (BasicBlock *&Incoming, BasicBlock *&Backedge) const
 Obtain the unique incoming and back edge. More...
 
Optional< LoopBoundsgetBounds (ScalarEvolution &SE) const
 Return the struct LoopBounds collected if all struct members are found, else None. More...
 
PHINodegetInductionVariable (ScalarEvolution &SE) const
 Return the loop induction variable if found, else return nullptr. More...
 
bool getInductionDescriptor (ScalarEvolution &SE, InductionDescriptor &IndDesc) const
 Get the loop induction descriptor for the loop induction variable. More...
 
bool isAuxiliaryInductionVariable (PHINode &AuxIndVar, ScalarEvolution &SE) const
 Return true if the given PHINode AuxIndVar is. More...
 
bool isCanonical (ScalarEvolution &SE) const
 Return true if the loop induction variable starts at zero and increments by one each time through the loop. More...
 
bool isLCSSAForm (DominatorTree &DT) const
 Return true if the Loop is in LCSSA form. More...
 
bool isRecursivelyLCSSAForm (DominatorTree &DT, const LoopInfo &LI) const
 Return true if this Loop and all inner subloops are in LCSSA form. More...
 
bool isLoopSimplifyForm () const
 Return true if the Loop is in the form that the LoopSimplify form transforms loops to, which is sometimes called normal form. More...
 
bool isSafeToClone () const
 Return true if the loop body is safe to clone in practice. More...
 
bool isAnnotatedParallel () const
 Returns true if the loop is annotated parallel. More...
 
MDNodegetLoopID () const
 Return the llvm.loop loop id metadata node for this loop if it is present. More...
 
void setLoopID (MDNode *LoopID) const
 Set the llvm.loop loop id metadata for this loop. More...
 
void setLoopAlreadyUnrolled ()
 Add llvm.loop.unroll.disable to this loop's loop id metadata. More...
 
void dump () const
 
void dumpVerbose () const
 
DebugLoc getStartLoc () const
 Return the debug location of the start of this loop. More...
 
LocRange getLocRange () const
 Return the source code span of the loop. More...
 
StringRef getName () const
 
- Public Member Functions inherited from llvm::LoopBase< BasicBlock, Loop >
unsigned getLoopDepth () const
 Return the nesting level of this loop. More...
 
BasicBlockgetHeader () const
 
LoopgetParentLoop () const
 
void setParentLoop (Loop *L)
 This is a raw interface for bypassing addChildLoop. More...
 
bool contains (const Loop *L) const
 Return true if the specified loop is contained within in this loop. More...
 
bool contains (const BasicBlock *BB) const
 Return true if the specified basic block is in this loop. More...
 
bool contains (const InstT *Inst) const
 Return true if the specified instruction is in this loop. More...
 
const std::vector< Loop *> & getSubLoops () const
 Return the loops contained entirely within this loop. More...
 
std::vector< Loop *> & getSubLoopsVector ()
 
iterator begin () const
 
iterator end () const
 
reverse_iterator rbegin () const
 
reverse_iterator rend () const
 
bool empty () const
 
ArrayRef< BasicBlock *> getBlocks () const
 Get a list of the basic blocks which make up this loop. More...
 
block_iterator block_begin () const
 
block_iterator block_end () const
 
iterator_range< block_iteratorblocks () const
 
unsigned getNumBlocks () const
 Get the number of blocks in this loop in constant time. More...
 
std::vector< BasicBlock *> & getBlocksVector ()
 Return a direct, mutable handle to the blocks vector so that we can mutate it efficiently with techniques like std::remove. More...
 
SmallPtrSetImpl< const BasicBlock *> & getBlocksSet ()
 Return a direct, mutable handle to the blocks set so that we can mutate it efficiently. More...
 
const SmallPtrSetImpl< const BasicBlock *> & getBlocksSet () const
 Return a direct, immutable handle to the blocks set. More...
 
bool isInvalid () const
 Return true if this loop is no longer valid. More...
 
bool isLoopExiting (const BasicBlock *BB) const
 True if terminator in the block can branch to another block that is outside of the current loop. More...
 
bool isLoopLatch (const BasicBlock *BB) const
 
unsigned getNumBackEdges () const
 Calculate the number of back edges to the loop header. More...
 
void getExitingBlocks (SmallVectorImpl< BasicBlock * > &ExitingBlocks) const
 Return all blocks inside the loop that have successors outside of the loop. More...
 
BasicBlockgetExitingBlock () const
 If getExitingBlocks would return exactly one block, return that block. More...
 
void getExitBlocks (SmallVectorImpl< BasicBlock * > &ExitBlocks) const
 Return all of the successor blocks of this loop. More...
 
BasicBlockgetExitBlock () const
 If getExitBlocks would return exactly one block, return that block. More...
 
bool hasDedicatedExits () const
 Return true if no exit block for the loop has a predecessor that is outside the loop. More...
 
void getUniqueExitBlocks (SmallVectorImpl< BasicBlock * > &ExitBlocks) const
 Return all unique successor blocks of this loop. More...
 
void getUniqueNonLatchExitBlocks (SmallVectorImpl< BasicBlock * > &ExitBlocks) const
 Return all unique successor blocks of this loop except successors from Latch block are not considered. More...
 
BasicBlockgetUniqueExitBlock () const
 If getUniqueExitBlocks would return exactly one block, return that block. More...
 
void getExitEdges (SmallVectorImpl< Edge > &ExitEdges) const
 Return all pairs of (inside_block,outside_block). More...
 
BasicBlockgetLoopPreheader () const
 If there is a preheader for this loop, return it. More...
 
BasicBlockgetLoopPredecessor () const
 If the given loop's header has exactly one unique predecessor outside the loop, return it. More...
 
BasicBlockgetLoopLatch () const
 If there is a single latch block for this loop, return it. More...
 
void getLoopLatches (SmallVectorImpl< BasicBlock * > &LoopLatches) const
 Return all loop latch blocks of this loop. More...
 
SmallVector< const Loop *, 4 > getLoopsInPreorder () const
 Return all loops in the loop nest rooted by the loop in preorder, with siblings in forward program order. More...
 
SmallVector< Loop *, 4 > getLoopsInPreorder ()
 
void addBasicBlockToLoop (BasicBlock *NewBB, LoopInfoBase< BasicBlock, Loop > &LI)
 This method is used by other analyses to update loop information. More...
 
void replaceChildLoopWith (Loop *OldChild, Loop *NewChild)
 This is used when splitting loops up. More...
 
void addChildLoop (Loop *NewChild)
 Add the specified loop to be a child of this loop. More...
 
LoopremoveChildLoop (iterator I)
 This removes the specified child from being a subloop of this loop. More...
 
LoopremoveChildLoop (Loop *Child)
 This removes the specified child from being a subloop of this loop. More...
 
void addBlockEntry (BasicBlock *BB)
 This adds a basic block directly to the basic block list. More...
 
void reverseBlock (unsigned from)
 interface to reverse Blocks[from, end of loop] in this loop More...
 
void reserveBlocks (unsigned size)
 interface to do reserve() for Blocks More...
 
void moveToHeader (BasicBlock *BB)
 This method is used to move BB (which must be part of this loop) to be the loop header of the loop (the block that dominates all others). More...
 
void removeBlockFromLoop (BasicBlock *BB)
 This removes the specified basic block from the current loop, updating the Blocks as appropriate. More...
 
void verifyLoop () const
 Verify loop structure. More...
 
void verifyLoopNest (DenseSet< const Loop * > *Loops) const
 Verify loop structure of this loop and all nested loops. More...
 
bool isAnnotatedParallel () const
 Returns true if the loop is annotated parallel. More...
 
void print (raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
 Print loop with all the BBs inside it. More...
 

Friends

class LoopInfoBase< BasicBlock, Loop >
 
class LoopBase< BasicBlock, Loop >
 

Additional Inherited Members

- Public Types inherited from llvm::LoopBase< BasicBlock, Loop >
typedef std::vector< Loop *>::const_iterator iterator
 
typedef std::vector< Loop *>::const_reverse_iterator reverse_iterator
 
typedef ArrayRef< BasicBlock *>::const_iterator block_iterator
 
typedef std::pair< BasicBlock *, BasicBlock *> Edge
 Edge type. More...
 
- Static Public Member Functions inherited from llvm::LoopBase< BasicBlock, Loop >
static void getInnerLoopsInPreorder (const Loop &L, SmallVectorImpl< Type > &PreOrderLoops)
 Return all inner loops in the loop nest rooted by the loop in preorder, with siblings in forward program order. More...
 
- Protected Member Functions inherited from llvm::LoopBase< BasicBlock, Loop >
 LoopBase ()
 This creates an empty loop. More...
 
 LoopBase (BasicBlock *BB)
 
 ~LoopBase ()
 

Detailed Description

Represents a single loop in the control flow graph.

Note that not all SCCs in the CFG are necessarily loops.

Definition at line 510 of file LoopInfo.h.

Member Function Documentation

◆ dump()

LLVM_DUMP_METHOD void Loop::dump ( ) const

◆ dumpVerbose()

LLVM_DUMP_METHOD void Loop::dumpVerbose ( ) const

◆ getBounds()

Optional< Loop::LoopBounds > Loop::getBounds ( ScalarEvolution SE) const

Return the struct LoopBounds collected if all struct members are found, else None.

Definition at line 283 of file LoopInfo.cpp.

References llvm::Loop::LoopBounds::getBounds(), getInductionVariable(), and llvm::None.

◆ getCanonicalInductionVariable()

PHINode * Loop::getCanonicalInductionVariable ( ) const

Check to see if the loop has a canonical induction variable: an integer recurrence that starts at 0 and increments by one each time through the loop.

If so, return the phi node that corresponds to it.

The IndVarSimplify pass transforms loops to have a canonical induction variable.

Definition at line 146 of file LoopInfo.cpp.

References llvm::MCID::Add, llvm::BasicBlock::begin(), llvm::LoopBase< BasicBlock, Loop >::getHeader(), getIncomingAndBackEdge(), llvm::PHINode::getIncomingValueForBlock(), H, and I.

Referenced by getInductionVariable(), and llvm::isUniformLoop().

◆ getIncomingAndBackEdge()

bool Loop::getIncomingAndBackEdge ( BasicBlock *&  Incoming,
BasicBlock *&  Backedge 
) const

Obtain the unique incoming and back edge.

Return false if they are non-unique or the loop is dead; otherwise, return true.

Definition at line 120 of file LoopInfo.cpp.

References assert(), llvm::LoopBase< BasicBlock, Loop >::contains(), llvm::LoopBase< BasicBlock, Loop >::getHeader(), H, llvm::pred_begin(), llvm::pred_end(), and std::swap().

Referenced by getCanonicalInductionVariable().

◆ getInductionDescriptor()

bool Loop::getInductionDescriptor ( ScalarEvolution SE,
InductionDescriptor IndDesc 
) const

Get the loop induction descriptor for the loop induction variable.

Return true if the loop induction variable is found.

Definition at line 328 of file LoopInfo.cpp.

References getInductionVariable(), and llvm::InductionDescriptor::isInductionPHI().

Referenced by isCanonical().

◆ getInductionVariable()

PHINode * Loop::getInductionVariable ( ScalarEvolution SE) const

Return the loop induction variable if found, else return nullptr.

An instruction is considered as the loop induction variable if

  • it is an induction variable of the loop; and
  • it is used to determine the condition of the branch in the loop latch

Note: the induction variable doesn't need to be canonical, i.e. starts at zero and increments by one each time through the loop (but it can be).

Definition at line 290 of file LoopInfo.cpp.

References assert(), llvm::dyn_cast(), llvm::LoopBase< BasicBlock, Loop >::getHeader(), llvm::InductionDescriptor::getInductionBinOp(), getLatchCmpInst(), llvm::User::getOperand(), llvm::InductionDescriptor::isInductionPHI(), isLoopSimplifyForm(), and llvm::BasicBlock::phis().

Referenced by getBounds(), and getInductionDescriptor().

◆ getLocRange()

Loop::LocRange Loop::getLocRange ( ) const

Return the source code span of the loop.

Definition at line 571 of file LoopInfo.cpp.

References getLoopID().

Referenced by getStartLoc().

◆ getLoopID()

MDNode * Loop::getLoopID ( ) const

Return the llvm.loop loop id metadata node for this loop if it is present.

If this loop contains the same llvm.loop metadata on each branch to the header then the node is returned. If any latch instruction does not contain llvm.loop or if multiple latches contain different nodes then 0 is returned.

Definition at line 447 of file LoopInfo.cpp.

References llvm::LoopBase< BasicBlock, Loop >::getLoopLatches(), llvm::Instruction::getMetadata(), llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), and llvm::LLVMContext::MD_loop.

Referenced by AddRuntimeUnrollDisableMetaData(), llvm::addStringMetadataToLoop(), CloneLoopBlocks(), llvm::InnerLoopVectorizer::createVectorizedLoopSkeleton(), llvm::findOptionMDForLoop(), getLocRange(), GetUnrollMetadataForLoop(), HasAnyUnrollPragma(), isAnnotatedParallel(), llvm::LoopVectorizePass::processLoop(), llvm::LoopVectorizeHints::setAlreadyVectorized(), setLoopAlreadyUnrolled(), tryToUnrollAndJamLoop(), and tryToUnrollLoop().

◆ getName()

StringRef llvm::Loop::getName ( ) const
inline

◆ getStartLoc()

DebugLoc Loop::getStartLoc ( ) const

Return the debug location of the start of this loop.

This looks for a BB terminating instruction with a known debug location by looking at the preheader and header blocks. If it cannot find a terminating instruction with location information, it returns an unknown location.

Definition at line 569 of file LoopInfo.cpp.

References getLocRange(), and llvm::Loop::LocRange::getStart().

Referenced by llvm::LoopVectorizeHints::allowVectorization(), areLoopExitPHIsSupported(), llvm::LoopAccessInfo::blockNeedsPredication(), llvm::computeUnrollCount(), containsSafePHI(), llvm::createLVMissedAnalysis(), llvm::LoopVectorizationRequirements::doesNotMeet(), getDebugLocString(), getInductionVariable(), isProfitableForVectorization(), llvm::LoopVectorizePass::processLoop(), llvm::SplitBlockPredecessors(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), and warnAboutLeftoverTransformations().

◆ hasLoopInvariantOperands()

bool Loop::hasLoopInvariantOperands ( const Instruction I) const

Return true if all the operands of the specified instruction are loop invariant.

Definition at line 67 of file LoopInfo.cpp.

References llvm::all_of(), isLoopInvariant(), and llvm::User::operands().

Referenced by generateLoopLatchCheck(), llvm::hoistRegion(), shouldRotateLoopExitingLatch(), sinkLoopInvariantInstructions(), llvm::sinkRegion(), and llvm::InnerLoopVectorizer::widenInstruction().

◆ isAnnotatedParallel()

bool Loop::isAnnotatedParallel ( ) const

Returns true if the loop is annotated parallel.

A parallel loop can be assumed to not contain any dependencies between iterations by the compiler. That is, any loop-carried dependency checking can be skipped completely when parallelizing the loop on the target machine. Thus, if the parallel loop information originates from the programmer, e.g. via the OpenMP parallel for pragma, it is the programmer's responsibility to ensure there are no loop-carried dependencies. The final execution order of the instructions across iterations is not guaranteed, thus, the end result might or might not implement actual concurrent execution of instructions across multiple iterations.

Definition at line 494 of file LoopInfo.cpp.

References assert(), llvm::LoopBase< BasicBlock, Loop >::blocks(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::drop_begin(), llvm::findOptionMDForLoop(), getLoopID(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isValidAsAccessGroup(), llvm::LLVMContext::MD_access_group, llvm::LLVMContext::MD_mem_parallel_loop_access, and llvm::MDNode::operands().

Referenced by llvm::MemoryDepChecker::Dependence::print().

◆ isAuxiliaryInductionVariable()

bool Loop::isAuxiliaryInductionVariable ( PHINode AuxIndVar,
ScalarEvolution SE 
) const

Return true if the given PHINode AuxIndVar is.

  • in the loop header
  • not used outside of the loop
  • incremented by a loop invariant step for each loop iteration
  • step instruction opcode should be add or sub Note: auxiliary induction variable is not required to be used in the conditional branch in the loop latch. (but it can be)

Definition at line 336 of file LoopInfo.cpp.

References llvm::MCID::Add, llvm::LoopBase< BasicBlock, Loop >::contains(), llvm::LoopBase< BasicBlock, Loop >::getHeader(), llvm::InductionDescriptor::getInductionOpcode(), llvm::Instruction::getParent(), llvm::InductionDescriptor::getStep(), I, llvm::InductionDescriptor::isInductionPHI(), llvm::ScalarEvolution::isLoopInvariant(), and llvm::Value::users().

◆ isCanonical()

bool Loop::isCanonical ( ScalarEvolution SE) const

Return true if the loop induction variable starts at zero and increments by one each time through the loop.

Definition at line 362 of file LoopInfo.cpp.

References llvm::MCID::Add, llvm::InductionDescriptor::getConstIntStepValue(), getInductionDescriptor(), llvm::InductionDescriptor::getInductionOpcode(), llvm::InductionDescriptor::getStartValue(), llvm::ConstantInt::isOne(), and llvm::ConstantInt::isZero().

◆ isLCSSAForm()

bool Loop::isLCSSAForm ( DominatorTree DT) const

◆ isLoopInvariant()

bool Loop::isLoopInvariant ( const Value V) const

◆ isLoopSimplifyForm()

bool Loop::isLoopSimplifyForm ( ) const

◆ isRecursivelyLCSSAForm()

bool Loop::isRecursivelyLCSSAForm ( DominatorTree DT,
const LoopInfo LI 
) const

◆ isSafeToClone()

bool Loop::isSafeToClone ( ) const

Return true if the loop body is safe to clone in practice.

Definition at line 432 of file LoopInfo.cpp.

References llvm::LoopBase< BasicBlock, Loop >::blocks(), and I.

Referenced by EqualityPropUnSafe(), and llvm::UnrollLoop().

◆ makeLoopInvariant() [1/2]

bool Loop::makeLoopInvariant ( Value V,
bool Changed,
Instruction InsertPt = nullptr,
MemorySSAUpdater MSSAU = nullptr 
) const

If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivially loop-invariant.

Return true if the value after any hoisting is loop invariant. This function can be used as a slightly more aggressive replacement for isLoopInvariant.

If InsertPt is specified, it is the point to hoist instructions to. If null, the terminator of the loop preheader is used.

Definition at line 71 of file LoopInfo.cpp.

References I.

Referenced by isLoopDead(), makeLoopInvariant(), and willNotOverflow().

◆ makeLoopInvariant() [2/2]

bool Loop::makeLoopInvariant ( Instruction I,
bool Changed,
Instruction InsertPt = nullptr,
MemorySSAUpdater MSSAU = nullptr 
) const

If the given instruction is inside of the loop and it can be hoisted, do so to make it trivially loop-invariant.

Return true if the instruction after any hoisting is loop invariant. This function can be used as a slightly more aggressive replacement for isLoopInvariant.

If InsertPt is specified, it is the point to hoist instructions to. If null, the terminator of the loop preheader is used.

Definition at line 78 of file LoopInfo.cpp.

References llvm::Instruction::dropUnknownNonDebugMetadata(), llvm::MemorySSA::End, llvm::LoopBase< BasicBlock, Loop >::getLoopPreheader(), llvm::MemorySSA::getMemoryAccess(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::Instruction::isEHPad(), isLoopInvariant(), llvm::isSafeToSpeculativelyExecute(), makeLoopInvariant(), llvm::Instruction::mayReadFromMemory(), llvm::Instruction::moveBefore(), llvm::MemorySSAUpdater::moveToPlace(), and llvm::User::operands().

◆ setLoopAlreadyUnrolled()

void Loop::setLoopAlreadyUnrolled ( )

Add llvm.loop.unroll.disable to this loop's loop id metadata.

Remove existing unroll metadata and add unroll disable metadata to indicate the loop has already been unrolled. This prevents a loop from being unrolled more than is directed by a pragma if the loop unrolling pass is run more than once (which it generally is).

Definition at line 483 of file LoopInfo.cpp.

References Context, llvm::MDString::get(), llvm::MDNode::get(), llvm::BasicBlock::getContext(), llvm::LoopBase< BasicBlock, Loop >::getHeader(), getLoopID(), llvm::makePostTransformationMetadata(), and setLoopID().

Referenced by CloneLoopBlocks(), tryToUnrollAndJamLoop(), and tryToUnrollLoop().

◆ setLoopID()

void Loop::setLoopID ( MDNode LoopID) const

Set the llvm.loop loop id metadata for this loop.

The LoopID metadata node will be added to each terminator instruction in the loop that branches to the loop header.

The LoopID metadata node should have one or more operands and the first operand should be the node itself.

Definition at line 471 of file LoopInfo.cpp.

References assert(), llvm::LoopBase< BasicBlock, Loop >::getLoopLatches(), llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), and llvm::LLVMContext::MD_loop.

Referenced by AddRuntimeUnrollDisableMetaData(), CloneLoopBlocks(), llvm::InnerLoopVectorizer::createVectorizedLoopSkeleton(), DisableAllLoopOptsOnLoop(), llvm::LoopVectorizePass::processLoop(), llvm::LoopVectorizeHints::setAlreadyVectorized(), setLoopAlreadyUnrolled(), tryToUnrollAndJamLoop(), and tryToUnrollLoop().

Friends And Related Function Documentation

◆ LoopBase< BasicBlock, Loop >

friend class LoopBase< BasicBlock, Loop >
friend

Definition at line 811 of file LoopInfo.h.

◆ LoopInfoBase< BasicBlock, Loop >

friend class LoopInfoBase< BasicBlock, Loop >
friend

Definition at line 810 of file LoopInfo.h.


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