llvm::Loop::LoopBounds Struct Reference

Below are some utilities to get the loop guard, loop bounds and induction variable, and to check if a given phinode is an auxiliary induction variable, if the loop is guarded, and if the loop is canonical. More...

#include "llvm/Analysis/LoopInfo.h"

Public Types
enum	Direction { Direction::Increasing, Direction::Decreasing, Direction::Unknown }
	An enum for the direction of the loop. More...

Public Member Functions
Value &	getInitialIVValue () const
	Get the initial value of the loop induction variable. More...
Instruction &	getStepInst () const
	Get the instruction that updates the loop induction variable. More...
Value *	getStepValue () const
	Get the step that the loop induction variable gets updated by in each loop iteration. More...
Value &	getFinalIVValue () const
	Get the final value of the loop induction variable. More...
ICmpInst::Predicate	getCanonicalPredicate () const
	Return the canonical predicate for the latch compare instruction, if able to be calcuated. More...
Direction	getDirection () const
	Get the direction of the loop. More...

Static Public Member Functions
static Optional< Loop::LoopBounds >	getBounds (const Loop &L, PHINode &IndVar, ScalarEvolution &SE)
	Return the LoopBounds object if. More...

Detailed Description

Below are some utilities to get the loop guard, loop bounds and induction variable, and to check if a given phinode is an auxiliary induction variable, if the loop is guarded, and if the loop is canonical.

Here is an example:

for (int i = lb; i < ub; i+=step)
  <loop body>
--- pseudo LLVMIR ---
beforeloop:
  guardcmp = (lb < ub)
  if (guardcmp) goto preheader; else goto afterloop
preheader:
loop:
  i_1 = phi[{lb, preheader}, {i_2, latch}]
  <loop body>
  i_2 = i_1 + step
latch:
  cmp = (i_2 < ub)
  if (cmp) goto loop
exit:
afterloop:

• getBounds
  • getInitialIVValue --> lb
  • getStepInst --> i_2 = i_1 + step
  • getStepValue --> step
  • getFinalIVValue --> ub
  • getCanonicalPredicate --> '<'
  • getDirection --> Increasing
• getInductionVariable --> i_1
• isAuxiliaryInductionVariable(x) --> true if x == i_1
• getLoopGuardBranch() --> if (guardcmp) goto preheader; else goto afterloop
• isGuarded() --> true
• isCanonical --> false

Definition at line 660 of file LoopInfo.h.

Member Enumeration Documentation

Direction

enum llvm::Loop::LoopBounds::Direction

strong

An enum for the direction of the loop.

• for (int i = 0; i < ub; ++i) --> Increasing
• for (int i = ub; i > 0; –i) --> Descresing
• for (int i = x; i != y; i+=z) --> Unknown

Enumerator
Increasing
Decreasing
Unknown

Definition at line 723 of file LoopInfo.h.

Member Function Documentation

getBounds()

Optional< Loop::LoopBounds > Loop::LoopBounds::getBounds ( const Loop &  L, PHINode &  IndVar, ScalarEvolution &  SE  )

static

Return the LoopBounds object if.

• the given IndVar is an induction variable
• the initial value of the induction variable can be found
• the step instruction of the induction variable can be found
• the final value of the induction variable can be found

Else None.

Definition at line 201 of file LoopInfo.cpp.

References findFinalIVValue(), llvm::InductionDescriptor::getInductionBinOp(), llvm::User::getOperand(), llvm::ScalarEvolution::getSCEV(), llvm::InductionDescriptor::getStartValue(), llvm::InductionDescriptor::getStep(), and llvm::InductionDescriptor::isInductionPHI().

Referenced by llvm::Loop::getBounds().

getCanonicalPredicate()

ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate

(

)

const

Return the canonical predicate for the latch compare instruction, if able to be calcuated.

Else BAD_ICMP_PREDICATE.

A predicate is considered as canonical if requirements below are all satisfied:

1. The first successor of the latch branch is the loop header If not, inverse the predicate.
2. One of the operands of the latch comparison is StepInst If not, and
   • if the current calcuated predicate is not ne or eq, flip the predicate.
   • else if the loop is increasing, return slt (notice that it is safe to change from ne or eq to sign compare)
   • else if the loop is decreasing, return sgt (notice that it is safe to change from ne or eq to sign compare)

Here is an example when both (1) and (2) are not satisfied:

loop.header:
 %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header]
 %inc = add %iv, %step
 %cmp = slt %iv, %finaliv
 br %cmp, %loop.exit, %loop.header
loop.exit:

• The second successor of the latch branch is the loop header instead of the first successor (slt -> sge)
• The first operand of the latch comparison (cmp) is the IndVar (iv) instead of the StepInst (inc) (sge -> sgt)

The predicate would be sgt if both (1) and (2) are satisfied. getCanonicalPredicate() returns sgt for this example. Note: The IR is not changed.

Definition at line 232 of file LoopInfo.cpp.

References assert(), llvm::CmpInst::BAD_ICMP_PREDICATE, D, llvm::BranchInst::getCondition(), llvm::CmpInst::getFlippedStrictnessPredicate(), llvm::CmpInst::getInversePredicate(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::BranchInst::getSuccessor(), llvm::CmpInst::getSwappedPredicate(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, and llvm::BranchInst::isConditional().

getDirection()

Direction Loop::LoopBounds::getDirection

(

)

const

Get the direction of the loop.

Definition at line 274 of file LoopInfo.cpp.

References llvm::pdb::Unknown.

getFinalIVValue()

Value& llvm::Loop::LoopBounds::getFinalIVValue ( ) const

inline

Get the final value of the loop induction variable.

Definition at line 682 of file LoopInfo.h.

getInitialIVValue()

Value& llvm::Loop::LoopBounds::getInitialIVValue ( ) const

inline

Get the initial value of the loop induction variable.

Definition at line 672 of file LoopInfo.h.

getStepInst()

Instruction& llvm::Loop::LoopBounds::getStepInst ( ) const

inline

Get the instruction that updates the loop induction variable.

Definition at line 675 of file LoopInfo.h.

Referenced by checkSafeInstruction().

getStepValue()

Value* llvm::Loop::LoopBounds::getStepValue ( ) const

inline

Get the step that the loop induction variable gets updated by in each loop iteration.

Return nullptr if not found.

Definition at line 679 of file LoopInfo.h.

---

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

• include/llvm/Analysis/LoopInfo.h
• lib/Analysis/LoopInfo.cpp