LLVM  14.0.0git
Classes | Namespaces | Macros | Functions
SimplifyIndVar.cpp File Reference
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
Include dependency graph for SimplifyIndVar.cpp:

Go to the source code of this file.

Classes

class  WidenIV
 
struct  WidenIV::NarrowIVDefUse
 Record a link in the Narrow IV def-use chain along with the WideIV that computes the same value as the Narrow IV def. More...
 

Namespaces

 llvm
 ---------------------— PointerInfo ------------------------------------—
 

Macros

#define DEBUG_TYPE   "indvars"
 

Functions

 STATISTIC (NumElimIdentity, "Number of IV identities eliminated")
 
 STATISTIC (NumElimOperand, "Number of IV operands folded into a use")
 
 STATISTIC (NumFoldedUser, "Number of IV users folded into a constant")
 
 STATISTIC (NumElimRem, "Number of IV remainder operations eliminated")
 
 STATISTIC (NumSimplifiedSDiv, "Number of IV signed division operations converted to unsigned division")
 
 STATISTIC (NumSimplifiedSRem, "Number of IV signed remainder operations converted to unsigned remainder")
 
 STATISTIC (NumElimCmp, "Number of IV comparisons eliminated")
 
static InstructionfindCommonDominator (ArrayRef< Instruction * > Instructions, DominatorTree &DT)
 Find a point in code which dominates all given instructions. More...
 
static InstructionGetLoopInvariantInsertPosition (Loop *L, Instruction *Hint)
 
static void pushIVUsers (Instruction *Def, Loop *L, SmallPtrSet< Instruction *, 16 > &Simplified, SmallVectorImpl< std::pair< Instruction *, Instruction * > > &SimpleIVUsers)
 Add all uses of Def to the current IV's worklist. More...
 
static bool isSimpleIVUser (Instruction *I, const Loop *L, ScalarEvolution *SE)
 Return true if this instruction generates a simple SCEV expression in terms of that IV. More...
 
bool llvm::simplifyUsersOfIV (PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, const TargetTransformInfo *TTI, SmallVectorImpl< WeakTrackingVH > &Dead, SCEVExpander &Rewriter, IVVisitor *V=nullptr)
 simplifyUsersOfIV - Simplify instructions that use this induction variable by using ScalarEvolution to analyze the IV's recurrence. More...
 
bool llvm::simplifyLoopIVs (Loop *L, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, const TargetTransformInfo *TTI, SmallVectorImpl< WeakTrackingVH > &Dead)
 SimplifyLoopIVs - Simplify users of induction variables within this loop. More...
 
static InstructiongetInsertPointForUses (Instruction *User, Value *Def, DominatorTree *DT, LoopInfo *LI)
 Determine the insertion point for this user. More...
 
static void truncateIVUse (WidenIV::NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI)
 This IV user cannot be widened. More...
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "indvars"

Definition at line 33 of file SimplifyIndVar.cpp.

Function Documentation

◆ findCommonDominator()

static Instruction* findCommonDominator ( ArrayRef< Instruction * >  Instructions,
DominatorTree DT 
)
static

Find a point in code which dominates all given instructions.

We can safely assume that, whatever fact we can prove at the found point, this fact is also true for each of the given instructions.

Definition at line 105 of file SimplifyIndVar.cpp.

References assert(), llvm::DominatorTree::dominates(), llvm::DominatorTreeBase< NodeT, IsPostDom >::findNearestCommonDominator(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), and Instructions.

Referenced by WidenIV::widenWithVariantUse().

◆ getInsertPointForUses()

static Instruction* getInsertPointForUses ( Instruction User,
Value Def,
DominatorTree DT,
LoopInfo LI 
)
static

Determine the insertion point for this user.

By default, insert immediately before the user. SCEVExpander or LICM will hoist loop invariants out of the loop. For PHI nodes, there may be multiple uses, so compute the nearest common dominator for the incoming blocks. A nullptr can be returned if no viable location is found: it may happen if User is a PHI and Def only comes to this PHI from unreachable blocks.

Definition at line 1083 of file SimplifyIndVar.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::tgtok::Def, llvm::DominatorTree::dominates(), llvm::numbers::e, llvm::DominatorTreeBase< NodeT, IsPostDom >::findNearestCommonDominator(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), i, llvm::DominatorTree::isReachableFromEntry(), and llvm_unreachable.

Referenced by truncateIVUse(), and WidenIV::widenLoopCompare().

◆ GetLoopInvariantInsertPosition()

static Instruction* GetLoopInvariantInsertPosition ( Loop L,
Instruction Hint 
)
static

Definition at line 636 of file SimplifyIndVar.cpp.

References BB, and llvm::LoopBase< BlockT, LoopT >::getLoopPreheader().

◆ isSimpleIVUser()

static bool isSimpleIVUser ( Instruction I,
const Loop L,
ScalarEvolution SE 
)
static

Return true if this instruction generates a simple SCEV expression in terms of that IV.

This is similar to IVUsers' isInteresting() but processes each instruction non-recursively when the operand is already known to be a simpleIVUser.

Definition at line 808 of file SimplifyIndVar.cpp.

References llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getSCEV(), I, llvm::ScalarEvolution::isSCEVable(), and S.

◆ pushIVUsers()

static void pushIVUsers ( Instruction Def,
Loop L,
SmallPtrSet< Instruction *, 16 > &  Simplified,
SmallVectorImpl< std::pair< Instruction *, Instruction * > > &  SimpleIVUsers 
)
static

Add all uses of Def to the current IV's worklist.

Definition at line 774 of file SimplifyIndVar.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::tgtok::Def, and llvm::JumpTable::Simplified.

◆ STATISTIC() [1/7]

STATISTIC ( NumElimCmp  ,
"Number of IV comparisons eliminated"   
)

◆ STATISTIC() [2/7]

STATISTIC ( NumElimIdentity  ,
"Number of IV identities eliminated"   
)

◆ STATISTIC() [3/7]

STATISTIC ( NumElimOperand  ,
"Number of IV operands folded into a use  
)

◆ STATISTIC() [4/7]

STATISTIC ( NumElimRem  ,
"Number of IV remainder operations eliminated"   
)

◆ STATISTIC() [5/7]

STATISTIC ( NumFoldedUser  ,
"Number of IV users folded into a constant  
)

◆ STATISTIC() [6/7]

STATISTIC ( NumSimplifiedSDiv  ,
"Number of IV signed division operations converted to unsigned division"   
)

◆ STATISTIC() [7/7]

STATISTIC ( NumSimplifiedSRem  ,
"Number of IV signed remainder operations converted to unsigned remainder  
)

◆ truncateIVUse()

static void truncateIVUse ( WidenIV::NarrowIVDefUse  DU,
DominatorTree DT,
LoopInfo LI 
)
static

This IV user cannot be widened.

Replace this use of the original narrow IV with a truncation of the new wide IV to isolate and eliminate the narrow IV.

Definition at line 1398 of file SimplifyIndVar.cpp.

References Builder, llvm::dbgs(), getInsertPointForUses(), llvm::Value::getType(), LLVM_DEBUG, WidenIV::NarrowIVDefUse::NarrowDef, WidenIV::NarrowIVDefUse::NarrowUse, llvm::User::replaceUsesOfWith(), and WidenIV::NarrowIVDefUse::WideDef.

Referenced by WidenIV::widenIVUse().